Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
30
Elementyteoriiinformacji
Wpowyższymprzykładziewidzimy,żeprawdopodobieństwawygenerowania
poszczególnychwiadomscisąjednakowe.Źródłobezpamięciowemiałobywtedymak-
symalnąentropięrównąH(X)=1.Obliczeniaentropiirozpatrywanegoźródłaciągów
Markowadokonanewprzykładzie1.7wskazują,żejegoentropiajestmniejsza.Wcelu
porównaniawartscientropiizentropiąźródłabezpamięciowegootychsamychpraw-
dopodobieństwachwygenerowaniaposzczególnychwiadomsciwprowadzasiędefinicję
źródłastowarzyszonegozeźródłemciągówMarkowa.
Definicja1.7.NiechX={a1,...,aK}będziealfabetemźródłaciągówMarkowa
m-tegorzędu.NiechP(a1),...,P(aK)będąprawdopodobieństwamiwystąpieniapo-
szczególnychwiadomościnawyjściutegoźródła.ŹródłemstowarzyszonymXzeźró-
dłemciągówMarkowaXnazywamyźródłobezpamięcioweposiadającetensamalfabet
Xiidentycznyrozkładprawdopodobieństwwystąpieniaposzczególnychwiadomościele-
mentarnych.
Poniżejpokażemy,żeentropiaźródłaciągówMarkowajestmniejszalubrówna
entropiiźródłaznimstowarzyszonego.Wtymceluwykażemynajpierwpomocniczą
nierównsć,którąwykorzystamynastępniekilkakrotniewnaszymkursieteoriiinfor-
macji.
Niechpiorazqi(ż=1,...,N)mająsensprawdopodobieństw,dlaktórych
zachodzi
N
N
Σ
pi=
Σ
qi=1orazpi≥0,qi≥0dlaż=1,...,N
i=1
i=1
Pokażemy,że
Σ
i=1
N
pilog
pi
qi
≤0
(1.17)
Ponownieskorzystamyzoszacowanialnx≤x−1.Mamybowiem
n=1
Σ
pnlog
qn
pn
=
ln2
1
Σ
n=1
N
pnln
pn
qn
≤
ln2
1
n=1
Σ
N
pn(
qn
pn
−1)=
N
=
ln2(
1
n=1
Σ
N
qn−
Σ
n=1
N
pn)=0
Skorzystajmyobecnieztakwyprowadzonejnierównsci,abyznaleźćzależnsćmiędzy
entropiąźródłaciągówMarkowapierwszegorzęduaentropiąźródłaznimstowarzy-
szonego.Wtymceluzastosujemynastępującepodstawienia
pn=P(xi,xi11)=Pr{xi=ak,xi11=aj}
qn=P(xi)P(xi11)=Pr{xi=ak}Pr{xi11=aj}
k,j=1,...,K
Takwięc,biorącpoduwagęnierównsć(1.17)orazpowyższepodstawienia,otrzymu-
jemy(wzapisieuproszczonym)
Σ
xz
xz
Σ
11
P(xi,xi11)log
P(xi)P(xi11)
P(xi,xi11)
≤0
(1.18)
