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

3. INFORMÁCIÓ ÉS BIZONYTALANSÁG

3. INFORMÁCIÓ ÉS BIZONYTALANSÁG

A Barkochba játéknál a kérdező, mielőtt az első kérdést feltette volna, bizonytalanságban van arra vonatkozóan, hogy a másik játékos mire gondolt. A bizonytalansága minden egyes kérdésre kapott válasz után csökken, míg végül, amikor kitalálta a másik gondolatát, teljesen megszűnik. A bizonytalanság tehát tulajdonképpen nem más, mint információhiány, azaz negatív információ, míg az információ nem más, mint a bizonytalanság csökkenése (negatív bizonytalanság). Bizonytalanság és információ tehát tulajdonképpen ugyanazt jelenti, más-más oldalról nézve, csak előjelben különböznek egymástól. Így tehát célszerű a bizonytalanság nagyságát azzal mérni, hogy mennyi információ szükséges annak teljes megszüntetéséhez. Mondhatjuk tehát, hogy ha a Barkochba játéknál megállapodunk, hogy 512 keresztnév valamelyikére lehet csak gondolni, akkor a kérdezés megkezdése előtt a kérdező bizonytalansága a gondolt keresztnevet illetőleg 9 bit; ez a bizonytalanság a lehető legjobb (vagyis a fennmaradó lehetőségek halmazát mindig két egyenlő részre felező) kérdezés mellett minden egyes válasz után 1 bittel csökken, és így 9 válasz után szűnik meg teljesen. A játék folyamán bármely időpontban az addig kapott információ és a még fennálló bizonytalanság összege (vagyis a már megszerzett és a még hiányzó információ összege) 9-cel egyenlő. A bizonytalanság mennyiségét az információelméletben entrópiának is nevezik.[36]

Vizsgáljuk most meg azt a kérdést, hogy ha a Barkochba játéknál a játékosok abban állapodnak meg, hogy N

N dolog valamelyikére lehet gondolni, és N N nem egyenlő 2-nek egy hatványával, akkor mekkora a kérdező bizonytalansága a játék kezdetén a gondolt dologra vonatkozólag?

Tegyük fel, hogy 2^KlNl2^(K+1)

2 K l N l 2 K + 1 . Ez esetben nyilván K+1 K + 1 kérdéssel lehet csak kitalálni a gondolt dolgot. Viszont nyilván azért a bizonytalanság kisebb, mint ha tényleg 2^(K+1) 2 K + 1 (tehát több) lehetőség állna fenn, de nagyobb, mint ha csak 2^K 2 K (tehát kevesebb) lehetőség állna fenn. Mivel K=[log_2N] K = [ log 2 N ] (itt és a következőkben [x] [ x ] az x x valós szám egészrészét jelöli), tehát, ha a kérdező bizonytalanságát (a helyzet entrópiáját) H(N) H ( N ) -nel jelöljük:

[log_2N]lH(N)l[log_2N]+1.
[ log 2 N ] l H ( N ) l [ log 2 N ] + 1 .

Meg fogjuk mutatni az eddigi meggondolásainkkal összhangban, hogy ilyen estekben ésszerű az

(1)

H(N)=log_2N
H ( N ) = log 2 N

ún. Hartley-képlettel értelmezni a fennálló bizonytalanságot. Az egyszerűség kedvéért ezt azon a példán keresztül mutatjuk be, amikor N=3

N = 3 ; tetszőleges N N -re lényegében ugyanígy végezhető el a meggondolás.

Tegyük fel tehát, hogy a játékosok abban állapodtak meg, hogy csak 3 dolog valamelyikére lehet gondolni, pl. az a

a , b b , c c betűk egyikére. Mivel 2^1=2l3l4=2^2 2 1 = 2 l 3 l 4 = 2 2 , tehát a játék kezdetén fennálló bizonytalanság nyilván 1 bitnél nagyobb, de 2 bitnél kisebb. Azt, hogy a bizonytalanság ez esetben log_23=1,584 96…, log 2 3 = 1,584 96 , a következőképpen láthatjuk be. A kérdező pl. előszörre kérdezheti, hogy a gondolt betű az a a betű-e; ha a válasz igen, már ki is találta a gondolt betűt; ha azonban a válasz nemleges, fel kell tenni a kérdést, hogy a gondolt betű a b b betű-e. Akármi is erre a kérdésre a válasz, ebből már a kérdező megtudja, hogy mi volt a gondolt betű. Ha sokszor megismétlik ezt a játékot és a felelő mind a 3 betűre ugyanolyan sokszor gondol, akkor az esetek kb. (1/3) 1 3 -ában 1 kérdés, (2/3) 2 3 -ában 2 kérdés, átlagban tehát 1⋅((1/3))+2⋅((2/3))=(5/3)=1,6666… 1 ( 1 3 ) + 2 ( 2 3 ) = 5 3 = 1,6666 kérdésre van szükség. Így tehát mondhatjuk, hogy a bizonytalanság ennél a játéknál legfeljebb (5/3) 5 3 ; valójában azonban a bizonytalanság még kisebb, ugyanis az említett „stratégia” (a játék sokszori ismétlése estében) nem a lehető legjobb. Ha a két játékos a játékot nem egyszer, hanem sokszor játssza, megadható egy jobb stratégia. A kérdező nem külön-külön kérdez a betűkre, hanem megkéri a felelőt, hogy egyszerre gondoljon az a a , b b , c c betűkből álló 5 tagú betűsorozatra, és megpróbálja e betűsorozatot egyszerre kitalálni. Mivel az a a , b b , c c betűkből 3^5=243 3 5 = 243 öttagú betűsorozat képezhető és 243l256=2^8 243 l 256 = 2 8 , tehát a szóban forgó 5 betűből álló betűsorozatot a kérdező 8 kérdéssel biztosan ki tudja találni, és így egy betű kitalálására átlagban (8/5)=1,6 8 5 = 1,6 kérdés jut, ami valamivel kevesebb, mint (5/3) 5 3 .

Még jobb eredményt kapunk, ha a kérdező egyszerre kérdez az a

a , b b , c c betűkből álló 17 tagú betűsorozatra. Az ilyen sorozatok („szövegek”) száma

3^(17)=129 140 163l2^(27)=134 217 728,
3 17 = 129 140 163 l 2 27 = 134 217 728 ,

tehát a 17 betűt 27 kérdéssel ki lehet találni és így egy betűre átlagban (27/17)=1,588 23…

27 17 = 1,588 23 kérdés esik. Általában, ha egy n n tagú, az a a , b b , c c betűkből álló betűsorozatra egyszerre kérdezünk, és k(n) k ( n ) jelöli 2-nek a legkisebb olyan hatványát, amely nagyobb, mint 3^n 3 n , tehát

(2)

2^(k(n)–1)l3^nl2^(k(n)),
2 k ( n ) 1 l 3 n l 2 k ( n ) ,

akkor k(n)

k ( n ) kérdéssel az egész n n betűből álló betűsorozatot kitalálhatjuk és így egy betűre (k(n)/n) k ( n ) n kérdés jut. A (2) egyenlőtlenségből (2 alapú logaritmust véve) azonban következik, hogy

k(n)–1lnlog_23lk(n)
k ( n ) 1 l n log 2 3 l k ( n )

és így

(k(n)/n)–(1/n)llog_23l(k(n)/n),
k ( n ) n 1 n l log 2 3 l k ( n ) n ,

vagyis

(3)

log_23l(k(n)/n)llog_23+(1/n).
log 2 3 l k ( n ) n l log 2 3 + 1 n .

Így tehát (k(n)/n)

k ( n ) n sohasem lesz kisebb, mint log_23 log 2 3 , azonban azt tetszőleges pontossággal meg fogja közelíteni felülről; ha ugyanis pl. azt akarjuk, hogy az egy betűre jutó kérdések száma log_23+(1/10 000) log 2 3 + 1 10 000 -nél kisebb legyen, ehhez csak n n -et kell 10 000 10 000 -nél nagyobbra választani. Így tehát indokolt azt mondani, hogy ha az a a , b b , c c betűk közül valamelyikre lehet gondolni, úgy a kérdező bizonytalansága a gondolt számra vonatkozólag log_23=1,584 96… log 2 3 = 1,584 96 Ez azonban nem úgy értendő, hogy (átlagban) log_23 log 2 3 kérdéssel ki lehet találni a gondolt számot, hanem úgy, hogy ennél kevesebb kérdés átlagban nem lehet elég és tetszőleges, ennél nagyobb számnál átlagban kevesebb kérdéssel ki lehet találni a számot alkalmas játékrendszer mellett. (Érdekes megjegyezni, hogy a fent kapott (27/17) 27 17 felső becslés a kérdések minimális számára kevesebb, mint (4/1000) 4 1000 -del haladja csak meg log_23 log 2 3 -at, tehát sokkal jobban közelít, mint amire a (3) egyenlőtlenség alapján biztosan számítani lehetett.) Így tehát bebizonyítottuk, hogy (a bizonytalanság fogalma értelmezésének kézenfekvő kiterjesztése mellett) ha a másik játékos az a a , b b , c c betűk egyikére gondolt, úgy a gondolt betűre vonatkozó bizonytalanságunk log_23=1,584 96… log 2 3 = 1,584 96 bit. Pontosan ugyanúgy látható be, hogy ha N N dologra lehet gondolni a Barkochba játéknál, úgy a kérdező bizonytalansága a kérdezés megkezdése előtt log_2N log 2 N bit. Ha N N éppen 2-nek egy hatványa, N=2^k N = 2 k , akkor persze log_2N=k log 2 N = k , és így a kapott eredmény speciális esetként tartalmazza azt a legelőször tárgyalt esetet, amikor 2^k 2 k dologra szabad gondolni.



[36] Az információelméleti entrópia-fogalomnak a statisztikus fizika entrópia-fogalmával való kapcsolatával itt nem foglalkozhatunk részletesen, csak azt jegyezzük meg, hogy a két fogalom szorosan összefügg. A statisztikus fizikában egy fizikai rendszer entrópiáján az illető rendszer rendezetlenségének mértékszámát értjük; ez a szám felfogható úgy is, mint annak mértékszáma, hogy mennyire bizonytalan az adott rendszer részecskéinek állapota.