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
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
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
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
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
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
[D]
[D]
[D]
[D]
Míg tehát, ha
3 lehetőség valószínűsége egyenlő, mint láttuk,
átlagban
[D]
[D]
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
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
[D]
Jelölje
[D]
vagyis
(5) |
![]() [D]
|
E közül a
[D]
[D]
[D]
Viszont (5)-ből
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
[D]
[D]
[D]
Figyeljük meg, hogy ebben az esetben már nem állíthatjuk,
hogy
[D]