Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

4. A SHANNON-FÉLE FORMULA

4. A SHANNON-FÉLE FORMULA

Térjünk vissza ahhoz a példához, amikor a Barkochbát játszó játékosok abban állapodnak meg, hogy csak 512 keresztnév egyikére lehet gondolni. Ebben az esetben, mint láttuk, a kérdező bizonytalansága a kérdezés megkezdése előtt 9 bit. Közelebbről megvizsgálva a kérdést, könnyű észrevenni, hogy amikor ezt beláttuk, tulajdonképpen hallgatólagosan feltettük, hogy az 512 keresztnév mindegyikére ugyanolyan valószínűséggel gondolt a felelő (pl. az 512 keresztnevet egy-egy cédulára felírja, e cédulákat egy kalapba teszi, megkeveri és találomra kihúz egy cédulát, és az azon álló keresztnévre gondol). Ha ez nem így van, akkor állításunk nem érvényes és módosításra szorul. Ha pl. a felelő annak a személynek a keresztnevére gondol, akivel legutoljára beszélt telefonon, nem jogosult az a feltevés, hogy mind az 512 keresztnév egyformán valószínű, hiszen az egyes keresztnevek gyakoriságai erősen eltérnek. Sokkal valószínűbb, hogy azt, akivel beszélt, Évának, Jánosnak, Andrásnak vagy Máriának hívják, mint hogy Anasztáziának, Szerafinnak, Kleofásnak vagy Upornak. Vizsgáljuk tehát meg a következő, az eddig tárgyaltnál általánosabb kérdést: Jelöljék x_1

x 1 , x_2 x 2 , …, x_N x N azokat a különböző „dolgokat”, amelyekre a Barkochba játéknál gondolni lehet. (x_1 x 1 , x_2 x 2 , …, x_N x N lehetnek nevek vagy általában szavak, számok, tárgyak stb.) Tegyük fel, hogy a kérdező tudja, hogy ezekre a dolgokra a másik játékos milyen valószínűséggel szokott gondolni; jelölje P_k P k annak a valószínűségét, hogy a másik játékos x_k x k -ra gondolt. (Ez esetben természetesen a P_k P k számok pozitívak, és P_1+P_2+…+P_N=1 P 1 + P 2 + + P N = 1 ; ez azt fejezi ki, hogy másra, mint x_1 x 1 , x_2 x 2 , …, x_N x N valamelyikére, nem gondolhat a „felelő” a játékosok megállapodása szerint.)

Kérdés, mekkora ebben az esetben a kérdező bizonytalansága a kérdezés megkezdése előtt? E szám nyilván csak a P_1

P 1 , P_2 P 2 , …, P_N P N valószínűségektől fog függeni, és x_1 x 1 , x_2 x 2 , …, x_N x N -től nem (hiszen pl. teljesen mellékes, hogy magára a gondolt keresztnévre gondolok-e, vagy a keresztnév sorszámára a keresztnevek egy listájában). Így tehát x_k x k -t mindig helyettesíthetjük k k -val, azaz x_k x k sorszámával, más szóval feltehetjük, hogy az x_1 x 1 , x_2 x 2 , …, x_N x N sorozat az 1, 2, …, N N számok sorozata. Jelölje a szóban forgó bizonytalanságot H(P_1, P_2, …, P_N) H ( P 1 , P 2 , , P N ) . A H(P_1, P_2, …, P_N) H ( P 1 , P 2 , , P N ) számot a P_1, P_2, …, P_N P 1 , P 2 , , P N valószínűségeloszlás entrópiájának nevezzük. C. Shannon (és tőle függetlenül N. Wiener) megmutatta, hogy

 

H(P_1, P_2, …, P_N)=
H ( P 1 , P 2 , , P N ) =

(4)

=P_1log_2(1/P_1)+P_2log_2(1/P_2)+…+P_Nlog_2(1/P_N).
= P 1 log 2 1 P 1 + P 2 log 2 1 P 2 + + P N log 2 1 P N .

A (4) képletet Shannon-féle formulának nevezik.[37] A Shannon-formula helyességét először egy példán keresztül mutatjuk be. Vizsgáljuk a következő példát! Tegyük fel, hogy az első játékos a játék előtt két pénzdarabot feldob úgy, hogy ő látja, de a kérdező nem látja a dobás eredményét. A kérdezőnek azt kell kitalálni, hogy a dobások eredménye 1. mindkét érmével fej, 2. mindkét érmével írás, vagy 3. az egyik érmével fej, a másikkal írás volt-e. A harmadik lehetőségen belül nem teszünk különbséget aközött, hogy melyik érmével dobott a játékos fejet és melyikkel írást (a két érmét ugyanis egyformának tételezzük fel, amikor is e két eset valójában nem is különböztethető meg).

Így tehát az 1, 2 és 3 lehetőségek valószínűségei P_1=(1/4)

P 1 = 1 4 , P_2=(1/4) P 2 = 1 4 , P_3=(1/2) P 3 = 1 2 . Nyilván a kérdező a következőképpen járhat el. Először megkérdezi, hogy a harmadik eset következett-e be; ha a válasz igenlő, már ki is találta, hogy mi történt, csak nemleges válasz esetében kell feltennie a második kérdést, ti. hogy a második lehetőség következett-e be. Így tehát az eseteknek kb. a felében 1 kérdéssel, a másik felében 2 kérdéssel ér célhoz, vagyis átlagban (1+2/2)=1,5 1 + 2 2 = 1,5 kérdéssel ki tudja találni, hogy mi történt.

Míg tehát, ha 3 lehetőség valószínűsége egyenlő, mint láttuk, átlagban log_23=1,584 96…

log 2 3 = 1,584 96 kérdésre van szüksége, ha e lehetőségek valószínűségei (1/4),(1/4),(1/2) 1 4 , 1 4 , 1 2 , akkor átlagban 1,5 kérdés is elegendő. A Shannon-formula erre az esetre nézve ugyanazt az eredményt adja, mivel

(1/4)log_24+(1/4)log_24+(1/2)log_22=(1/4)⋅2+(1/4)⋅2+(1/2)⋅1=(3/2)=1,5.
1 4 log 2 4 + 1 4 log 2 4 + 1 2 log 2 2 = 1 4 2 + 1 4 2 + 1 2 1 = 3 2 = 1,5 .

A tárgyalt példa alapján már kitalálhatjuk, hogy ha a számításba jövő lehetőségek nem egyformán valószínűek, akkor nem arra kell törekednünk, hogy kérdéseinkkel a lehetőségek számát csökkentsük a felére, hanem arra, hogy a még fennmaradó lehetőségeket úgy csoportosítsuk két osztályba, hogy a két osztályba sorolt lehetőségek valószínűségeinek összege legyen egyenlő (vagy ha ez nem lehetséges, közel egyenlő). Az előbbi példában ez pontosan keresztülvihető volt; az általános esetben ez nem mindig érhető el; tetszőlegesen megközelíthető azonban az ilyen kérdezési módszer akkor, ha megint arra kérjük a másik játékost, hogy ne egy dologra gondoljon, hanem egyszerre sokra, és ezeket együtt igyekszünk kitalálni. Ennek szabatos bizonyítása hosszadalmas, ezért a bizonyításnak csak a gondolatmenetét vázoljuk, a részletek kidolgozása nélkül.

Ha az első játékos n

n -szer egymás után gondol az x_1 x 1 , x_2 x 2 , …, x_N x N dolgok egyikére, és minden alkalommal az x_k x k -t (k=1, 2, …, N) ( k = 1 , 2 , , N ) P_k P k valószínűséggel választja (az előző választásoktól függetlenül), akkor a nagy számok törvénye szerint körülbelül nP_1 n P 1 -szer fogja x_1 x 1 -et, nP_2 n P 2 -ször x_2 x 2 -t, …, nP_N n P N -szer x_N x N -et választani, és a gondolt dolgok minden egyes valószínű sorozatának valószínűsége ennek megfelelően körülbelül P_1^(n^(P_1))⋅P_2^(nP_2)⋅…⋅P_N^(nP_N) P 1 n P 1 P 2 n P 2 P N n P N lesz.

Jelölje S

S a valószínű sorozatok számát, akkor tehát (mivel a valószínűtlen sorozatok együttes valószínűsége igen kicsiny és így a valószínű sorozatok együttes valószínűsége közel 1 lesz),

S⋅P_1^(nP_1)⋅P_2^(nP_2)⋅…⋅P_N^(nP_N)∼1,
S P 1 n P 1 P 2 n P 2 P N n P N 1 ,

vagyis

(5)

S∼[((1/P_1))^(P_1)((1/P_2))^(P_2)⋯((1/P_N))^(P_N)]^n.
S [ ( 1 P 1 ) P 1 ( 1 P 2 ) P 2 ( 1 P N ) P N ] n .

E közül a S

S , közel egyenlő valószínűségű sorozat közül egyet nyilván körülbelül log_2S log 2 S kérdéssel tudunk kitalálni, és így átlagban egy gondolt dologra (1/n)log_2S 1 n log 2 S kérdés jut.

Viszont (5)-ből

(1/n)log_2S∼P_1log_2(1/P_1)+P_2log_2(1/P_2)+…+P_Nlog_2(1/P_N).
1 n log 2 S P 1 log 2 1 P 1 + P 2 log 2 1 P 2 + + P N log 2 1 P N .

Tehát a Shannon-formula valóban megadja, hogy átlagban körülbelül hány kérdéssel lehet majdnem biztosan kitalálni, hogy a másik játékos x_1

x 1 , x_2 x 2 , …, x_N x N közül melyikre gondol.

Figyeljük meg, hogy ebben az esetben már nem állíthatjuk, hogy H(P_1,P_2,…,P_N)

H ( P 1 , P 2 , , P N ) (ill. annál tetszőleges kevéssel több) kérdés biztosan elegendő átlagban a gondolt dolog kitalálásához, csak azt, hogy ennyi kérdéssel 1-hez tetszőlegesen közeli valószínűséggel („majdnem biztosan”) ki tudjuk azt találni. Ez azonban inkább csak elvileg jelent különbséget.



[37] A Shannon-formula speciális esetként tartalmazza a Hartley-formulát; ugyanis (4)-ből H((1/N),(1/N),…,(1/N))=log_2N

H ( 1 N , 1 N , , 1 N ) = log 2 N .