Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Markov láncok

Orosz Gyula

Markov láncok II. rész

Az I. és II. rész közös tartalomjegyzéke

  1. Bevezető
  2. Fogalmak (a Markov-láncok bevezetése)
  3. Sorsolások visszatevéssel
    • A Markov-láncok módszere (összefoglalás)
  4. Érmedobálások
    • Könnyen eldönthető játékok
    • Néhány szó a szimmetriáról
    • További feladatok
    • Érmedobálások számítógépes támogatással
  5. Statisztikus golyójátékok
    • A golyójátékok osztályozása
    • Három klasszikus példa
    • Konform- és kontrastratégiák
    • Visszatevés nélküli sorsolások
    • Vegyes feladatok
  6. Ferdefoci
  7. A ferdefoci játék általános vizsgálata
  8. Bolyongások
    • Egyszerű síkbeli bolyongások
    • Bolyongások adott geometriai alakzaton
    • Ki nevet a végén?
  9. Vegyes feladatok
    • A Conway algoritmus
  10. Számítógéppel támogatott problémamegoldás
    • Golyómodell-szimulációk
    • Sorsolási modellek
    • Dinamikus golyómodellek
    • Konform- és kontrastratégiák
    • A játékok számítógépes megvalósítása a tanítási órán
  11. Érdekességek, paradoxonok
    • Kibe szerelmes a királylány?
    • Az osztozkodás-paradoxon
    • Érmedobálási paradoxonok
  12. Feladatgyűjtemény PDF-ben, DOC-ban, ZIPped doc-ban.

7. Bolyongások

Az 5-6. fejezet ferdefoci-játékaiban lineáris pálya mentén történő bolyongásokat vizsgáltunk; ebben a fejezetben a bolyongási pályák egyéb geometriai alakzatok lesznek. Általában az egyes feladatokban, még a számolás megkezdése előtt érdemes megkérdeznünk a tanulóktól, hogy szerintük – melyik esetben (honnan indulva) hagyja el leghamarabb a bolyongó pont a pályát; – s az egyes mezőkről indulva mi az átlagos lépésszámok nagyságrendi viszonya? A tippeket próbáljuk egyenletek felírása nélkül, pusztán a „józan ész” segítségével megindokoltatni!

Egyszerű síkbeli és térbeli bolyongások:

7.1. feladat:A síkbeli négyzetrács egyik mezőjében elhelyezkedő bolyongó pont mindegyik lépésében véletlenszerűen, egyenlő valószínűséggel lép a négy, élben szomszédos mező egyikére. A bolyongó pont kezdetben a 3x3-as táblázat egyik mezőjében van.

a) Átlagosan hány lépés múlva hagyja el a pont a táblázatot?

b) Mennyivel változik meg az átlagos lépésszám, ha a csúcsban érintkező négy mezőre is léphet a pont? (Tehát a szomszédsági definíciót változtattuk meg: egy mezőnek most nyolc szomszédja lehet.)

c) Mennyivel változik meg az átlagos lépésszám, ha irányfüggő valószínűséggel dolgozunk? Például balra kétszer akkora valószínűséggel lép a pont, mint a többi irányba; vagyis egyik irányba támogatott, „szélfútta” bolyongásról van szó.

Megoldás: a) Ebben a játékban is 1 valószínűséggel elhagyja a pont a pályát. Az ábra szerint azonos számmal jelölt mezők ekvivalens szerepűek.
1 2 1
2 3 2
1 2 1

Jelöljük L1, L2, L3-mal a táblázat elhagyásához szükséges lépések átlagos számát, ha a bolyongó pont rendre az 1., 2., illetve 3. típusú mezőkön van. A felírható egyenletrendszer:

markov

Az egyenletrendszer megoldása  markov a táblázat elhagyásához átlagosan ennyi lépésre van szükség.

b) A mezők ekvivalenciája nem változik meg, csak az átmeneti valószínűségek lesznek mások. Ismét jelöljük L1, L2, L3-mal a táblázat elhagyásához szükséges lépések átlagos számát, ha a bolyongó pont rendre az 1., 2., illetve 3. típusú mezőkön van. Ekkor a felírható egyenletrendszer:

markov

markov

Az egyenletrendszer megoldása  markov a táblázat elhagyásához átlagosan ennyi lépésre van szükség.

Megjegyzés: Érdekességképpen: L1, L2 és L3 is kevesebb, mint a)-ban; a több lehetséges mozgási irány miatt könnyebb lejutni a pályáról.

c) Az a) feladatbeli 4 irányú szomszédság-definícióval oldjuk meg a feladatot. Az ekvivalens állapotok és az egyenletek az markov, valószínűségekkel a következők (L1, L2, …, L6 jelentése hasonló a)-hoz és b)-hez):

1 3 5
2 4 6
1 3 5

markov

Az egyenletrendszer megoldása: L1 ≈ 2,22, L2 ≈ 2,73, L3 ≈ 3,36, L4 ≈ 4,22, L5 ≈ 3,13, L6 ≈ 3,94. Láthatjuk, hogy a tábla bal széléhez közelebbi mezők esetén csökkent, a jobb oldaliaknál pedig megnőtt az átlagos lépésszám.

7.2. feladat:Egy bolyongó pont kezdetben a 2x2x2-es kocka egyik egységkockájában van. Minden lépésében a hat lehetséges oldallap közül véletlenszerűen választ egyet, s a lapon keresztül átmegy a szomszéd egységkockába vagy kijut a kocka felszínére. Átlagosan hány lépés múlva kerül ki a pont a 2x2x2-es kocka felszínére?
Megoldás: A térbeli szimmetriaviszonyok miatt a 2x2x2-es kocka egységkockái ekvivalensek egymással. A szimmetriaokok miatt az egyenletet közvetlen „logikai rekurzióval” is felírhatjuk: markov, s a megoldás L = 2.
Megjegyzés:A feladat megoldása - formailag és számszerűen is - ugyanaz, mint a 2x2-es táblázatbeli bolyongás esetén. Érdekes kérdés, hogy vajon a 2- és 3-dimenziós feladattal analóg n-dimenziós esetben is (n > 3) ugyanezt az eredményt kapjuk?
7.3. feladat: Hogy legyen egyéb összehasonlító adatunk is, oldjuk meg a 7.1. feladattal analóg térbeli problémát, vagyis:

Egy bolyongó pont kezdetben a 3x3x3-as kocka egyik egységkockájában van. Minden lépésében a hat lehetséges oldallap közül véletlenszerűen választ egyet, s a lapon keresztül átmegy a szomszéd egységkockába vagy a nagy kocka felszínére. Átlagosan hány lépés múlva jut ki a pont a 3x3x3-as kocka felszínére?

Megoldás:4 irányú szomszédságot vizsgálunk. Négy különböző helyzetben lehet a bolyongó pont: csúcs, élközép, lapközép és testközép. Az állapotokat ebben a sorrendben rendre 1, 2, 3, 4 számokkal jelölve

markov

Az egyenletrendszer megoldása markov. Más eredményt kaptunk, mint a 7.1. feladat 3x3-as síkbeli bolyongásakor.

Bolyongások adott geometriai alakzatokon:

7.4. feladat (kitűzés):Egy szabályos nyolcszög alakú pálya két szemköztes csúcsában egy egér és egy sajtdarab van. Adott időközönként az egér átmegy egy szomszédos csúcsba a sokszög valamelyik oldala mentén. (A sajtot nem látja, útválasztása véletlenszerű.) Átlagosan hány lépés múlva találja meg a sajtot?
Útmutatás:Nevezzük i. állapotnak azt a helyzetet, amikor az egér-sajt távolság i egység (egységnyi hosszúnak tekintjük a szabályos nyolcszög egy élét); a kérdés ekkor L4.

markov

Vegyük észre, hogy a probléma ugyanaz, mint a ferdefoci alapfeladat, azzal a módosítással, hogy a sajt helyzetét jellemző S állapotot egyszerre tekintjük a 0. és a 8. állapotnak is.

(Az analógiára érdemes a feladat megoldása rákérdezni.)

Megjegyzés:Az analógia átvitele szabályos 2k-szögre nem okoz gondot, de szabályos (2k + 1)-szög esetén kissé megváltozik a helyzet. Ekkor a második peremfeltétel markov, s az eredmény: Ln = n(2k + 1 – n).
7.5. feladat: Egy szabályos nyolcszög alakú labirintus egyik csúcsában egy egér, másik csúcsában egy sajtdarab van. Az egér nem látja a sajtot; minden lépésben a nyolcszög oldalai vagy átlói közül véletlenszerűen választ egyet, és az utat csúcstól csúcsig végigjárja (tehát például a második lépésben visszatérhet a kiindulási helyére).

a) Mekkora annak a valószínűsége, hogy az egér nem találja meg a sajtot?

b) Átlagosan hány lépés múlva találja meg az egér a sajtot?

c) Átlagosan mennyi időre van szüksége az egérnek, míg az összes csúcsot sikerül átkutatnia?

d) Mennyivel csökken a keresési idő, ha az egér intelligensebb, és visszafelé nem keres? (Tehát minden, a kezdetitől különböző lépésben hat irány közül választ.)

Előzetes megjegyzés: Ismét hangsúlyozzuk, hogy módszertani szempontból még a számolás megkezdése előtt érdemes megkérdeznünk a tanulóktól, hogy például

– mennyiben változik a helyzet (az előző feladathoz képest);

– mekkora átlagos lépésszámokra tippelnek (s milyen indokokkal);

– ismernek-e alkalmazható analógiákat stb.

Megoldás: A csúcsok szerepe szimmetrikus. Az egér bármely csúcsból markov valószínűséggel találja meg a sajtot, illetve markov valószínűséggel egy másik csúcsba jut.

a) Annak a valószínűsége, hogy az egér az N. lépésig nem találja meg a sajtot, markov. Ez az érték a lépésszám növekedtével nullához tart, tehát az egér előbb-utóbb 1 valószínűséggel rátalál a sajtra.

b) Jelöljük L-lel a sajt megtalálásához szükséges átlagos lépésszámot. Az egér az alaphelyzetből vagy markov valószínűséggel egy lépésben célt ér, vagy markov valószínűséggel lép egyet és egy másik csúcsba kerül. Ez az állapot a kiindulási helyzettel ekvivalens, innen továbbra is L a sajt megtalálásához szükséges átlagos lépésszám. Ennek alapján a felírható rekurzív összefüggés: L = markov, s ennek megoldása L =  7.

A sajt megtalálásához szükséges átlagos "idő" tehát 7 lépés.

c) Színezzük be a csúcsokat: legyen például piros színű az a csúcs, ahol már járt az egér, és legyen kék, ahol még nem. Kezdetben egy csúcs piros, ahol az egér áll, a többi hét kék színű. Az első lépésével az egér mindenféleképpen "pirosra színez" egy csúcsot. A második lépés már kétféle lehet: markov valószínűséggel piros csúcsba vezető élt választ az egér, markov valószínűséggel kék csúcsba vezetőt. (Ekkor 3 piros és 5 kék csúcs lesz.) Általában ha a kék csúcsok száma i, markov valószínűséggel kék, markov valószínűséggel piros csúcsot választ az egér. (Itt kihasználtuk, hogy az egér mindig piros csúcson áll.) Jelöljük  Li-vel azt az átlagos lépésszámot, ami az összes csúcs pirosra színezéséhez szükséges, ha még i darab kék van közöttük. A feladat L7 meghatározása.

Ha a kék csúcsok száma i, markov valószínűséggel kék csúcsot választ az egér. Ekkor történt egy lépés, és (i – 1) kék csúcs maradt; az ezek „színezéséhez” szükséges lépésszám  Li–1. Ha markov valószínűséggel piros csúcsot választ az egér, akkor lép egyet, és továbbra is átlagosan Li lépésre van szüksége. Ez alapján az Li = markov véges rekurziót írhatjuk fel (i = 1, 2, ..., 7 és L0 = 0).

A képlet átalakítása után az Li = Li–1 + markov formulát kapjuk, ahonnan L7 = markov =  32,15; ennyi a csúcsok bejárásához szükséges átlagos lépésszám.

d) Ha az egér intelligensebben keres, akkor az alaphelyzetből markov valószínűséggel találja meg a sajtot, a későbbi állapotokból viszont markov valószínűséggel (visszafelé nem keres). A felírható egyenletrendszer:

markov

Az egyenletrendszer megoldása L = 6 és markov; majdnem egy lépéssel kevesebb, mint az unintelligens keresés lépésszáma.

Megjegyzés: Az egyes feladatokkal korábban már találkozhattunk a tárgyalt típuspéldák között. A b) feladatban a sajt megtalálásához szükséges átlagos lépésszám analógiája például a 2.6. feladatban tárgyalt visszatevéses sorsolási modell; míg a c) feladatban az összes csúcs bejárásához szükséges lépésszám a 4.1. konform stratégiájú golyójáték közvetlen alkalmazása.
7.6. feladat: Válaszoljuk meg az előző feladat b) - d) kérdéseit nyolcszög helyett szabályos n-szög alakú labirintusra!
Megoldás: A csúcsok szerepe szimmetrikus. Az egér bármely csúcsból markov valószínűséggel találja meg a sajtot, illetve markov valószínűséggel egy másik csúcsba jut.

b) Az átlagos lépésszámra L = markov, ahonnan L = n – 1.

c) Ha az egér intelligensebben keres, akkor az alaphelyzetből markov valószínűséggel találja meg a sajtot, a későbbi állapotokból viszont markov valószínűséggel (visszafelé nem keres). A felírható egyenletrendszer:

markov

Az egyenletrendszer megoldása L = n – 2 és markov.

7.7. feladat:Egy 2x2-es négyzetrács alakú pálya egyik csúcsában egy egér, a középső rácsponton pedig egy macska van. Az egér és a macska nem látja egymást; egyenlő időközönként az élben szomszédos pontok közül véletlenszerűen kiválasztanak egyet, és az él mentén megteszik az utat (tehát például a második lépésben visszatérhetnek a kiindulási helyükre). Átlagosan hány lépés múlva találkoznak?

markov

Megoldás: Ha az egyes rácspontokat megkülönböztetnénk, a macska is és az egér is 9 helyen lehetne, ez 81 különböző állapotot jelent. Ha kihagyjuk a találkozásokat, még mindig 72 helyzet marad. Tovább csökkenthetjük az állapotok számát, ha észrevesszük, hogy a macska-egér megkülönböztetés a feladat szempontjából nem lényeges; így marad  markov  állapot. Még két észrevételt tehetünk. Az egyik, hogy a táblázat geometriai szimmetriaviszonyai miatt (tükrözés, forgásszimmetria) is jelentősen lecsökken a lehetséges állapotok száma; a másik észrevétel pedig, hogy vannak olyan helyzetek, amelyek nem jöhetnek létre.

Jelöljük meg a rácspontokat koordinátákkal, legyen például a bal alsó pont az origó, ekkor a jobb felső pont koordinátái (2, 2). Észrevehetjük, hogy a koordináták összegének paritása lépésenként változik. Kezdetben az egér és a macska helykoordinátáinak összege is páros; az első lépés után mindkettőnek páratlan lesz, a második lépés után ismét páros stb. Vagyis nem állhat elő olyan állapot, amikor az egér és a macska helykoordinátái összegének paritása különböző. Ennek alapján összesen öt különböző állapot lehetséges:

markov

Az 1., 2., 3. állapotokból bizonyos valószínűségekkel csak a 4., 5. állapotokba kerülhetünk (esetleg a macska elkapta az egeret); és fordítva, a 4., 5. állapotokból csak az 1., 2., 3. állapotokba juthatunk. A feladat L1-et kérdezi. Az ezek alapján felírható egyenletrendszer:

markov 

Az egyenletrendszer megoldása: markov

7.8. (kitűzött) feladat: Készítsünk a 7.4 - 7.7. feladatokkal analóg térbeli problémákat!

Ki nevet a végén? - problémakör

A fenti alcímben jelzett feladattípus az egyirányú bolyongások egy speciális fajtájára utal. Ezekben a játékokban az egyirányban haladó, diszkrét bolyongást végző pont adott nagyságú lépéseket adott valószínűséggel tesz meg, s arra a kérdésre keressük a választ, hogy a pont mekkora eséllyel lép valamely mezőre.

[12]-ből származik a következő feladat:

Mindenki ismeri a „Ki nevet a végén” játékot, ahol pontosan a célmezőre kell lépni a győzelemhez. Ha a cél pontosan a 100. mező és egy dobókockával játszunk, akkor eltekintve a kiütéstől vagy egyéb trükköktől, mekkora eséllyel fogunk pontosan a 100-as mezőre lépni a végén: markov, markov vagy markov?

Ezt a feladatot később kitűzzük (9. fejezet: Számítástechnikai támogatás, 9.24. feladat), s egyszerű számítógépes szimulációt, illetve algoritmust adunk megoldásként. Most egyszerűbb feladatokat vizsgálunk meg.

7.9. feladat: Az egyszerű „Ki nevet a végén”-típusú játékban a bábuval a 0. mezőről indulunk, s minden lépésben véletlenszerűen 1-et vagy 2-t lépünk előre. (Mindig feldobunk egy érmét; ha a dobás írás, akkor 1-et, ha pedig fej, akkor 2-t lépünk.) Mekkora valószínűséggel lépünk rá a 100-as mezőre?
Megoldás: Jelentse pi annak a valószínűségét, hogy a játékban az i-edik mezőre lépünk. Ez a valószínűség a fiktív 0. mezőre p0 = 1, az 1. mezőre p1 = markov, a 2. mezőre p2 = markov (hiszen a második mezőre vagy az első, vagy a nulladik mezőről léphetünk, mindkettőről markov valószínűséggel); a 3. mezőre p3 = markov (a harmadik mezőre vagy a második, vagy az első mezőről léphetünk, mindkettőről markov valószínűséggel). Általában is felírhatjuk a markov rekurziót, ha n ³ 2.

A karakterisztikus egyenlet 2x2x – 1 = 0, ennek két gyöke x1 = 1 és x2 = markov. A (p) sorozat explicit alakja markov, ahol az A és B konstansokat a kezdeti feltételekből határozhatjuk meg.

Az n = 0 helyettesítéssel markov, az n = 1 helyettesítéssel markov. Az egyenletrendszer megoldása markov, vagyis markov.

Ellenőrzésképpen: markov, markov.

A századik mezőre markov valószínűséggel lépünk, ami igen jó közelítéssel markov.

7.10. feladat: Az előző „Ki nevet a végén”-játékot annyiban módosítjuk, hogy most minden lépésben véletlenszerűen 1-et, 2-t vagy 3-at lépünk, mindegyiket markov valószínűséggel. Mekkora valószínűséggel lépünk rá a 100-as mezőre?
Megoldás: Jelentse pi annak a valószínűségét, hogy a játékban az i-edik mezőre lépünk. Néhány kezdeti érték: p0 = 1, p1 = markov, p2 = markov, p3 = markov. Általában is felírhatjuk a markov rekurziót, ha n ≥ 3. (Minden mezőre az előtte lévő három mező valamelyikéről léphetünk, egyforma markov valószínűséggel).

A rekurzív sorozat karakterisztikus egyenlete 3x3x2x – 1 = 0, ennek három gyöke x1 = 1, x2 = markov és x3 = markov. (Az utóbbi kettő komplex gyök.) Innen a (p) sorozat explicit alakja markov, ahol az A, B és C konstansokat a kezdeti feltételekből határozhatjuk meg.

Az n = 0 helyettesítéssel markov, az n = 1 helyettesítéssel markov. A második egyenletben a képzetes rész eltűnik, így B = C következik; ekkor tehát a két egyenlet markov és markov alakú. Ennek megoldása markov, vagyis markov.

Ellenőrzésképpen: markov = markov = markov.

A századik mezőre markov valószínűséggel lépünk, ami igen jó közelítéssel markov. (A markov és markov komplex számok abszolútértéke 0-hoz tart.)

7.11. (kitűzött) feladat (KöMaL F.3042.): Egy a Ki nevet a végén?-hez hasonló játékban egy bábuval legalább 100 lépést kell megtenni. Egyszerre véletlenszerűen 1, 2, 3 vagy 4 mezővel léphetünk tovább. Jelölje pn annak a valószínűségét, hogy rálépünk az n-edik mezőre. (A bábu a nulladik mezőről indul.) Bizonyítsuk be, hogy 0,399 999 < p100 < 0,400 001.

Vegyes feladatok

7.12. (kitűzött) feladat:A bolyongó pont kezdetben a 2x3-as táblázat egyik mezőjében van.

a) Átlagosan hány lépés múlva hagyja el a pont a táblázatot?

b) Mennyivel változik meg a lépésszám, ha a táblázatot csak balról hagyhatja el a pont? (A másik három irányban a tábla szélén gát van; ezekhez érve a pont „visszapattan”.)

c) Mennyivel változik meg az átlagos lépésszám, ha a csúcsban érintkező négy mezőre is léphet a pont? (Tehát a szomszédsági definíciót változtattuk meg: egy mezőnek most nyolc szomszédja lehet.)

d) Mennyivel változik meg az átlagos lépésszám, ha balra kétszer akkora valószínűséggel lép a pont, mint a többi irányba? (Vagyis irányfüggő valószínűséggel dolgozunk: „szélfútta” bolyongásról van szó.)

e) Vizsgáljuk meg a fenti egyszerű kétdimenziós problémákat 2x4-es, 2x5-ös stb. alakú táblákra is!

7.13. (kitűzött) feladat:Egy kocka élein bolyongó pók az egyik csúcsból indul, és a kocka szemközti csúcsában lévő légyhez igyekszik. Minden lépésben egy élt csúcstól-csúcsig jár végig, s minden csúcsban a lehetséges 3 irányból véletlenszerűen választja ki a továbbhaladási irányt (akár visszafelé is mehet az előző lépéséhez képest).

a) Átlagosan hány lépés múlva éri el a legyet?

b) Mihez kell több idő (lépés): ahhoz, hogy a légyhez érjen, vagy ahhoz, hogy visszatérjen a kiindulási helyére?

c) Átlagosan hány lépés kell a póknak, hogy a kocka összes csúcsát bejárja?

d) Mennyivel csökken a keresési (bejárási) idő, ha a pók intelligensebb, és visszafelé nem keres? (Tehát minden, a kezdetitől különböző lépésben már csak két irány közül választ.)

7.14. (kitűzött) feladat: Az előző feladat a) részét (pók keresi a legyet) annyiban módosítjuk, hogy most a légy is véletlenszerű mozgást végez, hasonlóan a pókhoz. Átlagosan hány lépés múlva találkoznak?
7.15. (kitűzött) feladat:Egy kocka hét csúcsában egy-egy bogár, a nyolcadik csúcsban pedig egy pókháló van. Adott jelre a bogarak azonos sebességű, véletlenszerű bolyongást végeznek a kocka élein. Minden lépésben egy élt csúcstól-csúcsig végigjárnak, s minden csúcsban a lehetséges 3 irányból véletlenszerűen választják ki a továbbhaladási irányt (akár visszafelé is mehetnek az előző lépésükhöz képest). Ha egy bogár a pókhálóba kerül, akkor onnan már nem tud elszabadulni. Átlagosan mennyi idő múlva kerül az összes bogár a pókhálóba?
7.16. (kitűzött) feladat: Egy bolyongó pont kezdetben a 2x2xn-es kocka egyik egységkockájában van. Minden lépésében a hat lehetséges oldallap közül véletlenszerűen választ egyet, s a lapon keresztül átmegy a szomszéd egységkockába, vagy kijut a kocka felszínére. Átlagosan hány lépés múlva kerül ki a pont a 2x2xn-es kocka felszínére, ha

a) n = 3;

b) n = 4;

c) n = 5?

8. Vegyes feladatok

Ebben a fejezetben néhány általános jellegű észrevételt teszünk; megválaszolunk korábban felvetődött problémákat, s megismerkedünk Conway nevezetes algoritmusával. A tárgyalt feladatok egy része nehezebb fogalmakat vagy módszereket használ, így ezt a fejezetet kiegészítő anyagnak szánjuk.
8.1. feladat: Milyen kapcsolat áll fenn az eddig ismertetett, különböző típusú játékok között?
Útmutatás: A cikkben tárgyalt játékok nagy része szorosan kapcsolódik egymáshoz, ezeket a kapcsolódási pontokat alkalmanként jeleztük is. A kimerítő válasz helyett gondoljuk meg a következő - korábban már jelzett - kapcsolatokat, leszűkítve például a ferdefoci játékra:

a) ferdefoci és egydimenziós bolyongás;

b) ferdefoci gáttal és bolyongás sokszögön;

c) p = q = markov paraméterű ferdefoci és érmedobálás;

Érdemes átgondolni:

d) ferdefoci és sorsolások (például a visszatevéses sorsolás az állandó valószínűségű ferdefoci-játéknak felel meg);

e) ferdefoci és statisztikus golyójátékok (például a színpárbaj felfogható egy változó valószínűségű ferdefoci-játéknak);

f) ehhez kapcsolódóan a sorsolási modellek és statisztikus golyójátékok.

8.2. feladat: Milyen megoldási módszereket alkalmazhatunk akkor, ha sok (igen sok) állapotot kell vizsgálnunk?
Útmutatás:

1. Legkevesebb előismeretet igényel az egyenletrendszerek használata. Ha nagyszámú egyenletünk van, segítségül hívhatjuk a számítógépet. (Például gépi számítás eredménye a 6.3. feladat táblázata.)

2. Szerencsés esetben alkalmazhatjuk a „logikai rekurzió” módszerét. (Például 2.1. harmadik megoldása, vagy 5.1. b) második megoldása.) Erre egy további példa a következő 8.3. feladat megoldása is.

3. Előzetes felkészülést igényel a rekurziók alkalmazása. Sajnos, teljes körben nem alkalmazhatók, megoldásuk néha reménytelenül nehéz. Ha nem ismerjük például egyes színpárbaj-típusú rekurziók általános megoldását, akkor kisszámú golyóval vagyunk kénytelenek kitűzni a játékot.

4. Egy eddig nem ismertetett lehetőség a mátrix-reprezentáció alkalmazása. Ekkor az átmeneti valószínűségeket folyamatábra helyett egy mátrixszal adjuk meg, s a mátrixműveletek segítségével kezeljük a problémát. Az [A] mátrix ai,j eleme pi,j, vagyis annak a valószínűsége, amellyel az i. állapotból a j. állapotba jutunk. Elképzelhető, hogy ezzel a témakörrel kibővítjük a későbbiekben ezt a cikket, az érdeklődőknek a [4] szakirodalom ajánlható. Konkrét példaként a h = 3 hosszú pálya markov és markov paraméterű ferdefoci játékának a mátrixa:

  0 1 2 3 4
0 1 0 0 0 0
1 1/3 0 2/3 0 0
2 0 1/3 0 2/3 0
3 0 0 1/3 0 2/3
4 0 0 0 0 1
8.3. feladat:A bolyongások egy alkalmazása lehet a következő általános probléma: átlagosan hány lépésben jutunk el adott gráf egyik csúcsából a másikba? (A bolyongás csúcstól-csúcsig történik, az éleket minden csúcsban véletlenszerűen választva.)

Ebben a feladatban most egyszerű láncokat vizsgálunk (egyetlen útból álló, n pontú, n – 1 élű fagráfokat); s a „logikai rekurzió” módszerét alkalmazzuk.

Megoldás: a) Ha n = 3, akkor kérdés, hogy az 1. csúcsból a 3. csúcsba átlagosan hány lépésben jutunk el. (Vagyis hány lépés kell a gráf éleinek a bejárásához.) Jelöljük ezt a keresett lépésszámot L-lel.

Az 1. lépésben 2-be kerülünk; innen vagy markov valószínűséggel 3-ba jutunk, vagy markov valószínűséggel 1-be (ahonnan továbbra is L lépésre van szükség). Innen L = 1 + markov + markov; ahonnan L = 4.

b) Ha n = 5, akkor a 3. csúcsba átlagosan 4 lépés szükséges a) miatt. Innen további 4 lépésben vagy markov valószínűséggel 3-ba jutunk, vagy markov valószínűséggel 1-be, ahonnan további L lépés szükséges. Vagyis L = 4 + markov; L = 16.

c) Ha n = 4, új változót vezetünk be. H jelentse a táv teljesítéséhez szükséges átlagos lépésszámot, ha a 3. csúcsban vagyunk (L jelentése hagyományosan ugyanez, ha az első csúcsból indulunk). Ekkor egyrészt L = 4 + H  a) miatt, másrészt H = markov, innen H = 5, L = 9.

És hasonlóan haladhatunk tovább. (Persze a kapott értékekre ráismerhetünk a ferdefoci és a lineáris bolyongás lépésszámaiból.)

Megjegyzés:Az általános gráfelméleti feladat egyes speciális esetei nem nehezek. Már korábban is láttunk példát gráfokon történő bolyongásokra (például szabályos n-szög vagy teljes gráf), további egyszerű eseteket önállóan is konstruálhatunk. (Könnyen tárgyalható például az n-ágú csillag.)
8.4. feladat: A Markov-láncokat akkor alkalmazhatjuk, ha bármely állapot bekövetkezésének valószínűsége csak az őt közvetlenül megelőző állapottól függ. Mit tehetünk akkor, ha egy állapot bekövetkezése például két korábbi állapottól függ?
Útmutatás: Módosítani kell az állapotteret. Az alábbiakban ezt egy konkrét példán végezzük el.

Tegyük fel, hogy egy országban a választásoknak két lehetséges kimenetele van: vagy az A, vagy a B párt győz. Az utolsó 30 választás eredményei a következők:

A A B A A B B A B B A B B B A B A B B A B A A B A B B A B B.

Szeretnénk megjósolni a további választások kimenetelét. Mit tegyünk?

Első közelítésben tegyük fel, hogy csak a legutolsó választás eredménye befolyásolja a következő választás kimenetét. Ekkor a két állapotból (A és B) álló Markov-lánc állapotvalószínűség-mátrixa:

  A B
A 3/29 10/29
B 9/29 7/29

(Itt például a markov érték úgy értendő, hogy a 29 vizsgált átmenetben 3-szor fordult elő, hogy az A párt ismételni tudott, így az AA átmenet valószínűsége markov.)

Pontosabb közelítést kapunk, ha feltesszük, hogy az utolsó két év választási eredménye befolyásolja a kimenetelt. (Erre a helyzetre vonatkozott a feladat eredeti kérdése.) Ekkor négy állapotot veszünk fel: AA, AB, BA, BB, s értelemszerűen ezek táblázatát (vagy folyamatábráját) készítjük el:

  AA AB BA BB
AA 0 3/28 0 0
AB 0 0 4/28 6/28
BA 2/28 7/28 0 0
BB 0 0 5/28 1/28

Az eljárás tovább folytatható. A modell közelítése egyre pontosabb lesz, de a számítások egyre bonyolultabbak.

8.5. feladat: Többször említettük, hogy a cikkben szereplő játékok 1 valószínűséggel véget érnek. Mi ennek a magyarázata?
Útmutatás: Ún. elnyelő Markov-láncokkal foglalkoztunk. A definíció azt jelenti, hogy a láncban vannak elnyelő állapotok, amelyekből nem lehet másik állapotba eljutni (vagyis vége a játéknak); és bármely más állapotból el lehet jutni valamely elnyelő állapotba. Egy tétel szerint elnyelő Markov-láncban a folyamat mindig 1 valószínűséggel lezárul.

A gondolatmenet lényegét egy konkrét példán mutatjuk meg; tekintsük például a h = 5 hosszú pálya p = markov és q = markov paraméterű ferdefoci játékát.

B           J
0 1 2 3 4 5 6
    p   q    

Minden i állapotból (játékmezőről) el lehet jutni a 0 vagy 6 elnyelő állapotokba. Az ehhez szükséges minimális lépésszámot jelöljük Li-vel (most L1 = L5 = 1, L2 = L4 = 2, L3 = 3). Legyen továbbá pi annak a valószínűsége, hogy az i. állapotból kiindulva a folyamat Li lépés után nem zárult le; nyilván pi < 1. (Konkrétan például p2 < markov, hiszen már két balra lépés is markov valószínűséggel következik be.) Legyen L az Li-k és P a pi-k legnagyobbika. Annak valószínűsége, hogy a folyamat nem zárul le, L lépés után kisebb P-nél, 2L lépés után kisebb P2-nél stb. Mivel P < 1, a valószínűségek valóban 0-hoz tartanak.

Becsülhetünk sokkal durvábban is. A játék például mindig véget ér, ha bármikor (legfeljebb) 5 egymás utáni balra lépés következik. Ennek valószínűsége markov. Hogy semelyik 5N számú lépésben sem történik ez meg, annak valószínűsége kisebb, mint markov, ami 0-hoz tart.

A Conway-algoritmus

Az alább vázolt algoritmus elegáns eljárást mutat arra, hogy hogyan tudjuk az érmedobálásos játékok (lásd 3. fejezet) átlagos lépésszámát és győzelmi valószínűségeit egyszerűen meghatározni. (Ezzel a módszerrel számoltuk ki például a 8.13. és 8.14. feladatok táblázatainak értékeit, vagy a 8.15. feladatbeli eredményeket is.) A szellemes algoritmus Conway amerikai matematikustól származik. Most csak a lényeget emeljük ki a [9] szakirodalomból; akit mélyebben érdekelnek a bizonyításhoz kapcsolódó problémák, annak feltétlenül érdemes elolvasnia a cikket.

Conway bűvös algoritmusát egy játékon keresztül ismerhetjük meg, előtte azonban bevezetünk néhány fogalmat.

Átfedés:

Tekintsünk két célsorozatot, például A = IFF, B = FFI.

(Emlékeztetőül: az A és B játékosok a játék elején kiválasztanak (tippelnek) egy-egy dobássorozatot, majd egy szabályos érmét dobálnak fel. A dobások eredményét sorban lejegyzik, s a játéknak akkor van vége, ha előáll valamelyik, a játékosok által választott dobássorozat. A játék nyertese az a játékos, akinek a tippje sikeres volt. A fej dobásokat F, az írás dobásokat I betűvel jelöljük; tehát most ebben a játékban az A játékos választott sorozata írás, fej, fej; a B játékosé fej, fej, írás.)

Észrevehetjük, hogy amikor az A sorozat nyer, akkor a B is épp a győzelem felé halad. Ennek az az oka, hogy a sorozatok között ún. átfedés van. (Átfedés: az egyik sorozat utolsó néhány eleme rendre megegyezik a másik sorozat első néhány elemével.)

A konkrét példát tekintve A-t B átfedi 1 hosszúságban, mert az A sorozat harmadik eleme megegyezik B első elemével (jelölés: A(3) = B(1) = F). Ugyanakkor A-t B átfedi 2 hosszúságban is, mert A második és harmadik eleme megegyezik B első és második elemével (jelölés: A(2, 3) = B(1, 2) = FF).

Az átfedés nagyságát definíció szerint 2-hatványok összegével mérjük: összeadjuk 2k-t minden olyan k-ra, amelyre van k hosszúságú átfedés. Az A és B sorozatokra így kiszámolt összeget átfedési számnak nevezzük, és A o B-vel jelöljük. Az előző konkrét esetben A o B = 2 + 22 = 6.

További példák:

B o A = 2 (mert csak az utolsó és első I átfedés: B(3) = A(1)). Ebből a példából láthatjuk, hogy általában A o BB o A.

A o A = 23 = 8 (csak egy átfedés van, maga a teljes sorozat).

B o B = 23 = 8 szintén.

Például a 3.1. feladat sorozatait tekintve: FFF o FIF = 2; FIF o FFF = 2; FFF o FFF = 2 + 22 + 23 = 14; FIF o FIF = 2 + 23 = 10.

Megjegyzés: Az átfedés fogalmát - igény szerint - esetleg érdemes gyakorolni, tovább mélyíteni. Néhány lehetőség (X és Y célsorozatok):

– meghatározhatjuk X o Y-t bonyolultabb (hosszabb) sorozatok esetén;

– kitűzhetünk egyéb típusfeladatokat (például van-e olyan adott hosszúságú X és Y, amelyekre X o Y = valamely adott érték);

– megvizsgálhatjuk a művelet egyes tulajdonságait (például igaz-e, hogy a művelet kommutatív?);

– valamint elgondolkozhatunk azon is, hogy hogyan alakulhatott ki a fogalom: miért éppen ezt a tulajdonság a „fontos”; hogyan vehette ezt észre Conway stb.

A játék:

Egykaszinóban érmedobásokra alapozott dupla vagy semmit lehet játszani. Ez azt jelenti, hogy minden érmedobás előtt a játékosok bizonyos téttel fogadhatnak a dobás eredményére. Ha ezt eltalálják, a tét dupláját fizeti nekik a bank; ha viszont nem jól tippelnek, a tétet elveszítik. (Máris előrebocsátjuk, hogy ez a játék “igazságos”: minden dobás után, minden játékos várható nyereménye 0.)

Egy társaság tagjai elhatározzák, hogy fejenként 1 forintot szánnak a játékra. Mindannyian a FIFI tippsorozatot játsszák, s egymás után kapcsolódnak be a játékba úgy, hogy minden dobásnál egy új játékos lép be.

Tehát az első játékos (J1) felteszi az 1 forintját, s fejet tippel. Ha az első dobás írás, már ki is esett; ha az első dobás fej, kap 2 forintot. Ezután J1 (ha még játékban van) a második játékban írást tippel (FIFI(2) = I). Bekapcsolódik a játékba a második játékos (J2), aki fejet tippel, mert most kezdi FIFI-t. (FIFI(1) = F.) Ha a második dobás I, J1 4 forintot kap, J2 kiesik. Ha a második dobás F, J1 kiesik, J2 kap 2 forintot.

Ezután jön a harmadik dobás. Ha J1 még játékban van, felteszi a 4 forintját, s F-et mond; J2 - ha még játékban van - felteszi 2 forintját, s I-t mond; végül bekapcsolódik 1 forinttal a harmadik játékos (J3), aki F-et tippel és így tovább.

Így folytatódik a játék egészen addig, amíg valamelyik játékosnak ki nem jön a teljes FIFI sorozat.

Pénzügyi mérleg:

Tegyük fel, hogy az előző játékban a 12., 13., 14., 15. dobásra jött ki (először) a FIFI sorozat. Mennyi lesz ekkor a 15 játékos nyeresége?

Mindannyian befizettek 1 forintot, ez összesen 15 forint. J12 nyeresége 16 forint, de J14 is nyert 4 forintot, mert kétszer talált: FIFI(3, 4) = FIFI(1, 2). A játékosok nettó nyereménye tehát 20 – 15 = 5 forint.

Észrevehetjük, hogy J12 és J14 esetében éppen a fentebb definiált átfedésről van szó. Vagyis azért nyertek 4 + 16 = 20 forintot, mert FIFI o FIFI = 22 + 24 = 20.

Mi történik akkor, ha egy hasonló játék az N. dobás után fejeződik be?

Ekkor is igaz, hogy az (N – 3). játékos 24 és az (N – 1). játékos 22 forintot nyer, tehát az össznyeremény ismét FIFI o FIFI; a nettó nyeremény pedig FIFI o FIFI – N forint.

Sőt, a fenti gondolat általánosítható: tetszőleges A sorozat esetén az utolsó i. játékos akkor kap 2i forintot, ha A-nak önmagával i hosszú átfedése van (i = 1, 2, …). A játékosok nettó össznyereménye tehát A o AN forint, a játék lefolyásától függetlenül. (Csak az elért végállapot számít, az oda vezető út nem.)

Mivel az érmedobálásos dupla vagy semmi játék ezzel a lebonyolítással méltányos (igazságos), a nettó nyeremény várható értéke 0. Emiatt ha L az A sorozat eléréséhez szükséges átlagos dobásszámot jelenti, akkor A o AL = 0, s innen L = A o A.

Vagyis ahhoz, hogy az érmedobálásos játékban először megkapjuk az A sorozatot, átlagosan A o A dobásra van szükség.

Megjegyzés: Módszertani szempontból persze helyesebb, ha a fenti kérdéseket, illetve kijelentéseket feladatként tűzzük ki, s engedjük, hogy a válaszokra a tanítványaink jöjjenek rá.

Amikor két sorozat versenyez:

A fogadás továbbra is az A tippsorozattal történik, de a dobássorozatban az A-val versenyez egy B sorozat is, s a játék akkor ér véget, ha A vagy B jön ki. (Konkrét példa: A = FIFI, B = IFFI.)

Ha például a B megjelenése vet véget a játéknak, akkor az A-ra tippelők között lehetnek, akik épp nyerésben vannak, s nekik a bank - könnyen látható - éppen B o A forintot fizet. (A konkrét példában B o A = 22, mert B(3, 4) = A(1, 2).)

Mennyi a játékosok nettó össznyereménye? Ha a játék N dobásig tart, akkor a nettó össznyeremény vagy B o AN (ha a B sorozat jött ki), vagy A o AN (ha az A sorozat nyert).

Mennyi az átlagos nettó nyeremény ebben a játékban? Ha az A sorozat nyerési esélye pA, a B sorozat nyerési esélye pB, L pedig az átlagos dobásszámot jelenti, akkor pA×A o A + pB×B o AL az átlagos nyeremény. (Az összeadási és szorzási szabályt alkalmaztuk. Eszerint vagy pA valószínűséggel nyer A, s ekkor a nyereség A o A; vagy pB valószínűséggel nyer B, ekkor a nyereség B o A; s a kettő súlyozott összegéből le kell vonni az átlagosan befizetett L forintot.) A játék igazságossága miatt most is pA×A o A + pB×B o AL = 0.

Hasonló egyenletet írhatunk fel akkor is, ha a játékosok B-re fogadnak: pA×A o B +
pB×B o BL = 0. Végül a játékban nincs döntetlen, így pA + pB = 1 a harmadik egyenletünk.

A három ismeretlent tartalmazó egyenletrendszer:

(1) pA×A o A + pB×B o A = L;

(2) pA×A o B + pB×B o B = L;

(3) pA + pB = 1.

Ennek megoldása: markov, markov. A pB valószínűséget megkaphatjuk 1 – pA-ból, vagy felírhatjuk a pA-ra szimmetrikus képletet: markov.

Összefoglalva:

Ezzel a módszerrel egyszerűen és gyorsan kiszámíthatjuk az egyes győzelmi valószínűségeket és az átlagos lépésszámokat. Sőt, az átfedési szám meghatározása könnyen algoritmizálható, így segítségül hívhatjuk a számítógépet. Nyolcadik osztályos diákjaim kiíratták például az összes 4 hosszú fej-írás sorozat egymással szembeni nyerési esélyeit, és a hozzájuk tartozó átlagos lépésszámokat; a lejjebb közölt táblázat-részletek is tőlük származnak.

Általánosítási lehetőségként megemlítjük, hogy a Conway-algoritmust alkalmazhatjuk akkor is, ha

kettőnél több versengő sorozat játszik; valamint ha

nem azonos hosszúak a versengő sorozatok. (Itt csak arra kell vigyázni, hogy egyik sorozat sem fordulhat elő teljes egészében semelyik másikban.)

Konkrét példák:

1. Oldjuk meg Conway módszerével a 3.1. és 3.2. bevezető érmedobálásos feladatokat! Ebben A = FFF, B = FIF; keressük az A és B győzelmi valószínűségeit és a játék befejezéséhez szükséges átlagos lépésszámot.
Megoldás:A o A = 2 + 4 + 8 = 14; A o B = 2; B o A = 2; B o B = 2 + 8 = 10. Innen markov, markov. Természetesen ezek az értékek megegyeznek a 3.1. és 3.2. eredményeivel.
2. Legyenek most négy hosszúak a versengő sorozatok; oldjuk meg például a fenti fogadás két sorozatához kapcsolódó feladatot! Tehát: A = FIFI, B = IFFI, s három kérdésre keressük a választ:

a) Mennyi a valószínűsége annak, hogy FIFI adódik előbb?

b) Határozzuk meg, átlagosan hány dobásig tart a játék!

c) Határozzuk meg, átlagosan hány dobásból áll elő külön-külön az FIFI, illetve az IFFI sorozat!

Megoldás: A o A = 4 + 16 = 20; A o B = 2; B o A = 4; B o B = 2 + 16 = 18. Innen markov, markov.

a) markov; b) 11; c) L(FIFI) = 20; L(IFFI) = 18.

8.6. feladat: Ebben a játékban három sorozat verseng egymással: A = FIFI, B = IIFF,
C = IFII.

a) Mennyi az egyes sorozatok győzelmi valószínűsége?

b) Határozzuk meg, átlagosan hány dobásig tart a játék!

c) Határozzuk meg, átlagosan hány dobásból áll elő külön-külön az FIFI, IIFF, illetve IFII sorozat!

Megoldás: A három sorozat négy ismeretlen változójára négy egyenletet írhatunk fel, a korábbi egyszerűbb esetek analógiájára:

(1) pA×A o A + pB×B o A + pC×C o A = L;

(2) pA×A o B + pB×B o B + pC×C o B = L;

(3) pA×A o C + pB×B o C + pC×C o C = L;

(3) pA + pB + pC = 1.

A o A = 4 + 16 = 20, B o B = 16, C o C = 2 + 16 = 18; ezek egyúttal az egyes sorozatok átlagos bekövetkezéséhez szükséges lépésszámok.

A o B = 2, A o C = 2 + 8 = 10, B o A = 2, B o C = 0, C o A = 0, C o B = 2 + 4 = 6. Az egyenletrendszer számokkal:

(1) 20pA + 2pB + 0pC = L;

(2) 2pA + 16pB + 6pC = L;

(3) 10pA + 0pB + 18pC = L;

(3) pA + pB + pC = 1.

Az a) - b) eredmények: (pA, pB, pC, L) = markov. A c) kérdésre a válasz: L(FIFI) = 20, L(IIFF) = 16, L(IFII) = 18 a lépésszámok.

Feladatok

8.7. (kitűzött) feladat: Két játékos egy szabályos érmét folyamatosan dobál. András akkor győz, ha a fejek száma 6-tal több, mint az írások száma; Béla pedig akkor, ha az írások száma lesz több 6-tal a fejek számánál. A játszma egy adott pillanatában a dobott fejek száma éppen 2-vel több, mint az írásoké.

a) Mekkora ebben a pillanatban András nyerési esélye?

b) Átlagosan hány dobásig tart még a játék?

c) Mekkora András nyerési esélye akkor, ha a dobott fejek száma 1-gyel, 3-mal, 4-gyel, 5-tel több az írások számánál?

8.8. (kitűzött) feladat:

a) Átlagosan hány lépésben jutunk el az n pontú teljes gráf egyik csúcsából egy kijelölt másik csúcsba? (A bolyongás csúcstól-csúcsig történik, az éleket minden csúcsban véletlenszerűen választva.)

b) Átlagosan hány lépésben járjuk be az n pontú teljes gráf minden csúcsát?

8.9. (kitűzött) feladat: Bizonyos értelemben a “legnehezebben” bejárható gráfok a “sárkány” alakúak (lásd [3]). Konkrétan tekintsünk egy teljes 4 pontú gráfot, és egy hozzá csatlakozó 8 pontú láncot. Határozzuk meg, hogy véletlenszerű bolyongást végezve a lánc végpontjából átlagosan hány lépésben érjük el

a) valamelyik előre megadott csúcsot;

b) az összes csúcsot!

8.10. (kitűzött) feladat: Elemezzük Conway algoritmusát alkalmazva a következő érmedobálásos játékokat (győzelmi valószínűség, lépésszámok külön-külön és együtt):

a) A = IFI, B = IFF;

b) A = IFI, B = IIF;

c) A = IFF, B = IIF;

d) A = IFI, B = IFF, C = IIF.

8.11. (kitűzött) feladat: Elemezzük Conway algoritmusát alkalmazva a következő érmedobálásos játékokat (győzelmi valószínűség, lépésszámok külön-külön és együtt):

a) A = FIFI, B = FIFF;

b) A = FIFI, B = FIIF;

c) A = FIFF, B = FIIF;

d) A = FIFI, B = FIFF, C = FIIF.

8.12. (kitűzött) feladat: Elemezzük Conway algoritmusát alkalmazva a következő érmedobálásos játékokat (győzelmi valószínűség, lépésszámok külön-külön és együtt):

a) A = IFI, B = FIFF;

b) A = IFI, B = FIFFI;

c) A = IFI, B = FIFFF;

d) A = IFI, B = FIFF, C = FFIF.

8.13. (kitűzött) feladat: Conway algoritmusa (és egy kis számítógépes segítség) alkalmazásával állítsuk elő a kétszemélyes, 3 hosszú célsorozatú érmedobálásos játékok valószínűségekre vonatkozó eredménytáblázatát!
Eredmény: Az egyes játékok esélyeit tartalmazó táblázat:
  FFF FFI FIF FII IFF IFI IIF III
FFF 1:1 2:3 2:3 1:7 5:7 3:7 1:1
FFI 1:1 2:1 2:1 1:3 5:3 1:1 7:3
FIF 3:2 1:2 1:1 1:1 1:1 3:5 7:5
FII 3:2 1:2 1:1 1:1 1:1 3:1 7:1
IFF 7:1 3:1 1:1 1:1 1:1 1:2 3:2
IFI 7:5 3:5 1:1 1:1 1:1 1:2 3:2
IIF 7:3 1:1 5:3 1:3 2:1 2:1 1:1
III 1:1 3:7 5:7 1:7 2:3 2:3 1:1

(Például az FFF : FIF = 2 : 3 arány úgy értendő, hogy FFF győzelmének a valószínűsége markov.

8.14. (kitűzött) feladat: Conway algoritmusa (és egy kis számítógépes segítség) alkalmazásával állítsuk elő a kétszemélyes, 3 hosszú célsorozatú érmedobálásos játékok átlagos lépésszámainak az eredménytáblázatát!
Eredmény: Az egyes játékok lépésszámait tartalmazó táblázat:
  FFF FFI FIF FII IFF IFI IIF III
FFF 14 7 6,8 5,6 7 5,83 5,6 7
FFI 7 8 6 5,3 6,5 5 5 5,6
FIF 6,8 6 10 5 6 7 5 5,83
FII 5,6 5,3 5 8 5 6 6,5 7
IFF 7 6,5 6 5 8 5 5,3 5,6
IFI 5,83 5 7 6 5 10 6 6,8
IIF 5,6 5 5 6,5 5,3 6 8 7
III 7 5,6 5,83 7 5,6 6,8 7 14
8.15. (kitűzött) feladat: Vizsgáljuk meg az IIII sorozat viselkedését a többi 4 hosszú célsorozat ellenében! (Például: FIII : IIII = 15 : 1.) Milyen érdekességet vehetünk észre és mi ennek az oka?
8.16. (kitűzött) feladat (KöMaL P.380.): Jelölje pn annak a valószínűségét, hogy egy találomra kiválasztott (nem feltétlenül értelmes) n betűs szövegben előfordul a „vagyok” szó. Bizonyítsuk be, hogy markov.

9. Számítógéppel támogatott problémamegoldás

Ebben a fejezetben - ígéretünkhöz híven - néhány egyszerű példát mutatunk arra, hogyan lehet a számítógépet segédeszközként felhasználni a problémamegoldás folyamatában.

Mint a cikk bevezetőjében is említettük, a következő munkafolyamatokról lesz szó:

1. Gépi szimuláció.

Itt sok-sok játék szimulálása, futtatása történik.

2. Sejtések, becslések, tippek megfogalmazása.

Érdekes és tanulságos a tippek összehasonlítása; ha szükséges, erre a részre arányaiban több időt is szánhatunk. (Becslések összegyűjtése, rögzítése; versenyeztetés, utólagos kiértékelés, tanulságok.) Akkor is érdemes becsültetni, ha esetleg a probléma olyan bonyolult, hogy matematikailag már nem tudjuk megoldani. Ekkor marad a számítógépes szimulációk sokasága; a futási eredmények átlaga jó közelítéssel a megoldást adja.

3. A játék matematikai modellezése.

4. A játék matematikai elemzése; feladatmegoldás.

9.1. feladat: Szimuláljunk néhány egyszerű diszkrét egydimenziós bolyongást!

A modell a következő: megadjuk a  h hosszú lineáris pályán bolyongó pont kezdeti helyzetét (ez 1-től  h-ig lehet valamelyik pozíció); majd ezután minden lépésben véletlenszerűen, 0,5 - 0,5 valószínűséggel elmozdítjuk valamelyik irányba a bolyongó pontot. A bolyongás egyfajta játéknak is tekinthető, melyben azt vizsgáljuk, hogy a pont melyik irányban hagyta el a pályát. A játéknak tehát akkor van vége, ha a pont aktuális pozíciója 0 vagy  h + 1 lesz.

a) <3; 2> játék: Szimuláljuk a bolyongó pont mozgását a  h = 3 hosszú, k = 2 kezdőhelyzetű játékban! (A továbbiakban ezt a kiindulási helyzetet a <3; 2> szimbólummal jelöljük.) Átlagosan mennyi a játék befejezéséhez szükséges L lépésszám, és hányszor hagyta el a pont balról, illetve jobbról a játékteret?
Eredmény: 100 000 futtatás alapján  L = 4,00;  Bal = 50 040,  Jobb = 49 960. (Természetesen ez és a következő futtatások csak egyetlen konkrét értékek; más szimulációk során más-más eredményeket kapunk.)
b) Szimuláljuk az <5; 3> játékot!
Eredmény: 100 000 futtatás alapján  L = 8,97;  Bal = 49 987,  Jobb = 50 013.
c)A <7; 4> játék 100 000 szimulációja alapján próbáljunk megfogalmazni egy sejtést, s ezt erősítsük meg a <9; 5>, <11; 6> és <13; 7> játékok vizsgálatával!
Eredmény: A <7; 4> játékban: L = 15,63;  Bal = 50 006,  Jobb = 49 994. A Bal és Jobb relatív gyakorisága ≈ 0,5 a játékokban, ezt szemléletünk el is fogadja. A lépésszámok esetében észrevehetjük, hogy ha a középső mezőn álló pontnak mindkét irányban  k lépést kell tennie, hogy elhagyja a pályát, akkor ehhez jó közelítéssel ≈ k2 lépésre van szükség.

A szimuláció eredménye a <9; 5>, <11; 6> és <13; 7> játékokban:

<9; 5>:                   L = 24,64;  Bal = 50 021,  Jobb = 49 979,

<11; 6>:                 L = 35,07;  Bal = 49 977,  Jobb = 50 023,

<13; 7>:                 L = 48,55;  Bal = 50 002,  Jobb = 49 998.

d) Vizsgáljunk meg néhány játékot akkor is, ha a kiindulási helyzetben nem középen áll a bolyongó pont!
Szimulációs eredmények (100 000 futtatás alapján) 2, 3, 4, 5, 6, 10 hosszú pályákon:

2 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 2,00 66 756 0,67 33 244 0,33
2 2,00 33 282 0,33 66 718 0,67

3 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 2,99 75 037 0,75 24 963 0,25
2 4,00 49 981 0,50 50 019 0,50
3 2,99 24 966 0,25 75 034 0,75

4 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 3,99 79 989 0,80 20 011 0,20
2 5,95 60 037 0,60 39 963 0,40
3 5,96 39 949 0,40 60 051 0,60
4 3,99 20 013 0,20 79 987 0,80

5 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 4,99 83 335 0,83 16 665 0,17
2 7,74 66 699 0,67 33 301 0,33
3 8,97 50 007 0,50 49 993 0,50
4 7,74 33 347 0,33 66 653 0,67
5 4,99 16 650 0,17 83 350 0,83

6 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 5,95 85 687 0,86 14 313 0,14
2 10,02 71 468 0,71 28 532 0,29
3 11,96 57 131 0,57 42 869 0,43
4 11,96 42 855 0,43 57 145 0,57
5 10.01 28 573 0,29 71 427 0,71
6 5,95 14 250 0,14 85 750 0,86

10 hosszú pályán:

Pozíció Lépésszám Bal Rel. gyak. Jobb Rel. gyak.
1 9,97 90 893 0,91 9 107 0,09
2 17,70 81 827 0,82 18 173 0,18
3 24,03 72 715 0,73 27 285 0,27
4 27,64 63 636 0,64 36 364 0,36
5 30,10 54 543 0,55 45 457 0,45
6 30,09 45 457 0,45 54 543 0,55
7 27,65 36 364 0,36 63 636 0,64
8 24,02 27 270 0,27 72 730 0,73
9 17,71 18 201 0,18 81 799 0,82
10 9,96 9 089 0,09 90 911 0,91
e) A fenti eredmények alapján fogalmazzunk meg sejtéseket!
Sejtések: Úgy tűnik, hogy a  h hosszúságú pályán a  k. kezdőhelyről induló pont

1. ha balról  p valószínűséggel hagyja el a játékteret, akkor (1 – p) valószínűséggel hagyja el jobbról;

2. markov valószínűséggel hagyja el balról a játékteret;

3. átlagosan ugyanannyi lépést végez, mint a (h + 1 – k). helyről induló pont;

4. átlagos lépésszáma  k(h + 1 – k).

(Ez utóbbi sejtést érdemes további példákkal megerősíteni. Egyébként mint véletlen egészen fantasztikus a 10 hosszú pálya 4 - 7., illetve 5 - 6. kezdőmezőkhöz tartozó lépésszámainak egyezése.)

9.2. (kitűzött) feladat: Bizonyítsuk be az előző feladatban kapott 1 - 4. (igaz) sejtéseket!
Útmutatás: Az 5. és 6. fejezetben találhatók a hasonló ferdefoci-problémák bizonyításai.

Golyómodell-szimulációk

Képzeljük el, hogy egy 10 tagú társaság tagjai közül sorsolással választja ki a vezetőjét. A sorsolást úgy végzik el, hogy a tagok egymás után feldobnak egy dobókockát, és az lesz a vezető, aki először dob 6-ost.

Ezt a sorsolást egyfajta golyómodellként is felfoghatjuk. Például egy urnába beteszünk 5 kék és 1 piros (egyforma méretű) golyót, s közülük a jelöltek sorban kihúznak egyet-egyet úgy, hogy ha a golyó színe kék, akkor visszateszik. (Piros golyó húzása esetén vége a sorsolásnak.)

Ezekben a modellekben a golyók szerepe minimális, a két szín megoszlása csak azt befolyásolja, hogy a soron következő húzással mekkora valószínűséggel ér véget a sorsolás. (Ilyen problémák egyszerűbb eseteit vizsgáltunk a 2. fejezetben.)

Ebben a fejezetben további golyómodelleket vizsgálunk meg; ezek a játékok általában bonyolultabbak lesznek. A modell bármelyik paraméterén változtathatunk: a színek, a golyók vagy a kihúzott golyók számán; a húzási technikán (a kihúzott golyót nem szükségképpen tesszük vissza), illetve ennek stratégiáján (például ha egy kék és egy zöld golyót húzunk ki, visszateszünk egy pirosat); különböző végállapotok esetén érhet véget egy-egy játék és így tovább. Bár alkalmanként nem hagyjuk el a modellek matematikai vizsgálatát sem, a hangsúlyt elsősorban a játékok szimulációjára, illetve ezek eredményeinek vizsgálatából a megfogalmazható sejtésekre helyezzük.

Megjegyzés: Módszertani szempontból – most és a későbbiekben is –

érdemes először azt megvizsgálni, hogy a konkrét feladat hogyan modellezhető;

ezután rátérni arra, hogy mit is várunk, hogyan „viselkedik” a modell;

majd végül ez alapján hogyan célszerű „helyezkedni” a sorsolásban résztvevőknek.

Nagyon érdekes például, hogy az első 6-os dobást általában a 3-4. helyre várják a diákok; de amikor a kérdést átfogalmazzuk, és azt kérdezzük, hogy hogyan érdemes helyezkedni, akkor a véleményük megváltozik, és inkább kezdeni szeretnének. Az (eltérő) tippek ütköztetésére is szánjunk időt; izgalmas összehasonlítani a különböző érveléseket.

Sorsolási modellek

9.3. feladat: A fenti bevezető sorsolás (10 játékos, visszatevéses húzás markov nyerési eséllyel) a legegyszerűbb feladatok közé tartozik, de néhány érdekes kérdést felvet.

a) Ha valaki elnök akar lenni, akkor hogyan érdemes „helyezkednie”? Igyekezzen hamar húzni, vagy inkább később? (A kérdés matematikai megfogalmazása: n játékos esetén melyik helyen legvalószínűbb az első piros húzás?)

b) Átlagosan hány húzásig tart a játék?

c) Hogyan változnak a fenti eredmények, ha megváltoztatjuk a golyók színmegoszlását?

d) És ha többféle golyóval végezzük a húzásokat? (Például 7 kék, 1 piros és 2 sárga golyóval játszunk; aki először húz sárga golyót, a társaság jegyzője lesz.)

Megoldás: A szimulációs program 100 000 futási eredménye alapján az átlagos dobásszám 6,01, az egyes nyerések száma pedig:
személy 1 2 3 4 5 6 7 8 9 10
nyerés 19 876 16 556 13 693 11 562 9636 7945 6616 5653 4682 3781
rel. gyak. 0,20 0,17 0,14 0,12 0,10 0,08 0,07 0,06 0,05 0,04

Úgy tűnik, érdemes minél hamarabb húzni (≈ 20% eséllyel az elsőnek húzóé lesz a piros golyó), az átlagos húzásszám pedig ≈ 6.

A bizonyítást általános esetben végezzük el. Legyen a társaság n tagú, és p annak a valószínűsége, hogy a soron következő játékos piros golyót húz. Ekkor annak valószínűsége, hogy az i. húzásra húzunk először piros golyót, (1 – p)i–1×p.

Az 1. játékos ez alapján  P1 = p + (1 – p)10×p + (1 – p)20×p + … valószínűséggel nyer;

a második  P2 = (1 – pp + (1 – p)11×p + (1 – p)21×p + … = (1 – pP1-gyel;

a harmadik  P3 = (1 – p)2×p + (1 – p)12×p + (1 – p)22×p + … = (1 – p)2×P1-gyel;

… az  i. pedig  Pi = (1 – p)i–1×p + (1 – p)i+9×p + (1 – p)i+19×p + … = (1 – p)i–1×P1-gyel,

s ezek az értékek  i növekedtével valóban csökkennek.

A végtelen sorok összege: P1 = markovP2 = markov, … ,
P10 = markov. Konkrétan  p = markov értékekkel P1 = 0,198 768 964;  P2 = 0,165 640 803;
P3 = 0,138 034 003;  P4 = 0,115 028 336 stb., elég jó egyezést kapunk a szimulációs eredményekkel.

A húzások átlagos számát többféleképpen is meghatározhatjuk. (Lásd például 2.6. feladat.)

Alkalmazhatjuk a várható érték definícióját: H = p×1 + (1 – pp×2 + (1 – p)2×p×3 + … + (1 – p)n–1×p×n + …, s ezt a végtelen összeget mértani sorok összegeként állíthatjuk elő.

Egy másik lehetőség a „logikai rekurziós” gondolat: H = p×1 + (1 – p)(1 + H). Ezt az egyenletet a következőképpen értelmezhetjük: Vagy  p valószínűséggel összesen 1-et húzunk (egy pirosat), vagy (1 – p) valószínűséggel húzunk 1-et (egy kéket), plusz még annyit, amennyi a további játék során szükséges. Mivel a további játék ekvivalens a kezdetivel (a kék golyót visszatettük), ebből az állapotból is H a hátralévő húzások átlagos száma.

Az egyenletből  H = 6.

Ezzel sikerült az a) - c) feladatokat megválaszolnunk, s a d) feladat is hasonlóan vizsgálható. (Például gondoljunk arra, hogy a piros golyó szempontjából a sárga és kék golyók egyenértékűek.)

9.4. (kitűzött) feladat:Láttuk, hogy a húzások átlagos száma 6. Magyarázzuk meg, ez miért nem jelenti azt, hogy leggyakrabban a 6. jelölt húzza a piros golyót!
9.5. feladat:Egy dobozban  n (egyforma méretű) golyó van, közülük 1 piros, a többi kék. Véletlenszerűen, ezúttal visszatevés nélkül húzzuk ki a golyókat. Mi annak a valószínűsége, hogy az i. húzás piros? (Az előző feladatbeli modellt tehát annyiban változtattuk meg, hogy a kihúzott golyót most nem tesszük vissza. Így sorsolták ki Mikszáth: A fekete város c. regényének egyik filmfeldolgozásában Lőcse város főbíráját.)
Megoldás: Hasonló feladatokat vizsgáltunk a 4. fejezetben, ez volt a visszatevés nélküli sorsolási modell.

Egy tipikus diákokoskodás szerint a kihúzott golyók n hosszú sorozatának elején - a kék golyók kezdeti túlsúlyának megfelelően - inkább kék golyók szerepelnek, így talán érdemesebb későbbi időpontban húzni, ha célunk a piros golyó megszerzése. (Az említett filmben az utoljára húzó tanácstagnak maradt a piros.) Nézzük, mit mutat a gyakorlat!

100 000 szimulációs futtatás eredménye a következő:

Ha a golyók száma n = 6 (1 piros, 5 kék), a piros golyó átlagos húzásszáma 3,50:

személy 1 2 3 4 5 6
nyerés 16 734 16 738 16 427 16 680 16 649 16 772
rel. gyak. 0,17 0,17 0,16 0,17 0,17 0,17

Ha a golyók száma n = 10 (1 piros, 9 kék), a piros golyó átlagos húzásszáma 5,50:

személy 1 2 3 4 5 6 7 8 9 10
nyerés 10037 10058 9907 10036 9928 10029 9944 10009 10100 9952
rel. gyak. 0,10 0,10 0,10 0,10 0,10 0,10 0,10 0,10 0,10 0,10

Az eredmény elég egyértelmű: sejthető, hogy mindegyik helyen ugyanakkora a piros golyó húzási valószínűsége. Az első helyen ez a valószínűség markov, a második helyen markov, … , az  i. helyen (1 < in) markov = markov valóban; az említett diákokoskodás tehát hibás.

9.6. feladat: Vizsgáljuk meg az előző feladatot, ha a golyók kezdeti eloszlása 3 piros és 7 kék! Készítsünk a kihúzott golyókból egy 10 hosszúságú sorozatot, és állapítsuk meg, hogy

a) melyik helyen legvalószínűbb az első piros húzás;

b) melyik helyen legvalószínűbb a piros húzás;

c) melyik sorozat húzása a legvalószínűbb?

Megoldás:Az előző feladat megoldása alapján ismét azt sejthetjük, hogy mindegyik helyen egyforma az első piros golyó húzási valószínűsége. A szimuláció eredménye:

Ha a golyók száma n = 10 (3 piros, 7 kék), az első piros golyó átlagos húzásszáma 2,76:

személy 1 2 3 4 5 6 7 8 9 10
nyerés 29 882 23 057 17 612 12 746 8321 4975 2559 848 0 0
rel. gyak. 0,30 0,23 0,18 0,13 0,08 0,05 0,03 0,01 0 0

Váratlan eredményt kaptunk; mi lehet ennek az oka?

a) Annak valószínűsége, hogy az első húzás piros,  p1 = markov; hogy másodszorra húzunk először pirosat,  p2 = markov = markov; hogy harmadikra,  p3 = markov = markov; hogy i.-re (1 < i≤ 8):  pi = markov = markov, s e szorzat i növekedtével valóban monoton csökken.

b) Tehát az első piros golyót nagyobb valószínűséggel húzzuk a sorozat elején, mint később. Következik-e ebből, hogy a sorozat elején nagyobb valószínűséggel húzunk piros golyót?

Hát nem következik. Annak valószínűsége, hogy a 2. húzás piros,  P2 = markov = markov. Hogy a 3. piros: P3 = markov = markov (itt rendre a  kkp, kpp, pkp, ppp eseteket számoltuk). P4 = markov = markov (az esetek: kkkp, (kkp)p 3-szor, (kpp)p 3-szor); innen már sejthető, hogy bármelyik helyen markov valószínűséggel húzunk piros golyót. Ennek bizonyítására gondoljuk meg, hogy ha a sorozatban egy kiválasztott  i. helyen piros golyó szerepel, akkor a maradék 9 helyen markov-féleképpen fordulhat elő a két piros golyó, s szimmetriaokok miatt ez minden kiválasztott i helyre igaz. Annak valószínűsége tehát, hogy az  i. helyen piros golyó van, markov = markov.

A gondolatmenet 3 és 7 helyett tetszőleges golyószámok esetén is alkalmazható.

c) A sorozatok egyformán valószínűek.

Vegyes feladatok

9.7. (kitűzött) feladat: Oldjuk meg az előző feladatot, ha a golyók kezdeti megoszlása

a) 1 piros, 3 sárga, 6 kék;

b) 3 piros, 2 kék és 5 sárga!

9.8. (kitűzött) feladat: A 9.6. feladatban szimulációs eredményül azt kaptuk, hogy ha kezdetben a piros és kék golyók száma 3, illetve 6, akkor az első piros golyót átlagosan 2,76. húzásra kapjuk meg. Mennyire valós ez az eredmény? Mi a pontos matematikai érték?
9.9. (kitűzött) feladat: Az 9.6. feladat szimulációjaként diákjainktól kétféle algoritmust kaptunk. Mindkét algoritmus kezdetben a g[1..10] vektorban tárolja a golyók színét.

Az egyik: Az 1 - 10 közötti i véletlenszámú g[i] golyót a g[1]-gyel megcseréli; ezután a 2 - 10 közötti i véletlenszámú g[i] golyót a g[2]-vel megcseréli és így tovább. Az algoritmus eredményeképp g[]-ben a keresett sorozatot kapjuk.

A másik: Az 1 - 10 közötti  i véletlenszámú g[i] golyót eltárolja h[1]-ben,  i-t megjegyzi; ezután addig generál 1 - 10 közötti véletlenszámot, míg olyan golyót nem talál, amelyiket még nem jegyzett meg, s ezt tárolja el h[2]-ben és így tovább. Eredményül h[]-ban kapjuk a keresett sorozatot.

Azonos eredményt ad mindkét eljárás? Átlagosan hányszor generálunk véletlenszámot az egyik, illetve a másik eljárásban? (A második eljárás módszerét alkalmaztuk 4.4.-ben.)

Dinamikus golyómodellek

A következő játékokban a kihúzott golyók színétől függő szabály szerint változtatjuk a golyók színét vagy számát. A játékok osztályozását több szempontból is elvégezhetjük, mint ezt a 4. fejezet elején láttuk. Ismétlésként: szempont lehet

– a kezdeti színek száma: 2, 3 vagy több (ezeket az eseteket a 2, 3, … kódokkal szimbolizáljuk);

– a kihúzott golyók száma: 1, 2 vagy több (kódok: 1, 2, …);

– a golyószám változási módja: csökkenő, állandó, növekvő (kódok: –1, 0, 1) stb.

A [színek száma, húzott golyók száma, golyószám változása] számhármassal a játékok egy-egy osztályát jellemezhetjük. Például a 9.3. feladat [2, 1, 0], a 9.5. feladat [2, 1, –1], a 9.7. pedig [3, 1, –1] típusú volt.

A játékokkal kapcsolatban több érdekes kérdés is felvethető. Például:

a)Lehetséges-e, hogy csak egyfajta golyó marad a játék végén?

b)Ha igen, ez milyen kezdőhelyzetekre érhető el?

c)Lehetséges-e, hogy csak egyetlen golyó marad a játék végén? (A kérdésnek nyilván csak csökkenő golyószám esetén van értelme.)

d)Mennyi az invariáns helyzet eléréséhez szükséges átlagos lépésszám?

A fejezetben vizsgált golyómodellek sokféleképp általánosíthatók. Csak egyetlen példa: a húzásokkal kapcsolatban geometriai korlátozást, egyfajta feltételt adhatunk, ha a golyókat lineáris pálya vagy kör mentén, esetleg egy táblázatban rendezzük el, s a szabály a geometriai szomszédságtól függ. (Ilyen golyómodellek azok a sejtautomaták is, amelyekben az egyes cellákat véletlenszerűen választjuk ki.)

Három klasszikus feladat

Ezeket a feladatokat már korábban példaként említettük a 4. fejezet elején.

9.10. feladat:Egy dobozban p darab piros színű és k darab kék golyó van. A dobozból kiveszünk két golyót. Ha ezek különböző színűek, akkor a piros golyót visszatesszük, ha egyforma színűek, akkor egy kék golyót teszünk vissza. Ezt az eljárást addig ismételjük, míg egyetlen golyó marad a dobozban. Mi a valószínűsége annak, hogy ez a golyó piros?
Megoldás: A játék kódja [2, 2, –1]. Különböző  p és  k értékekre futtatva a szimulációkat, észrevehetjük, hogy a végeredmény - rögzített  p és  k értékekre - mindig egyértelmű; nem függ az eredmény attól, hogy milyen golyókat, melyik sorrendben húzzuk, csak attól, hogy milyen  p és  k megoszlása. Az alábbi táblázatban  p és  k lehetséges változásait tüntettük fel:
húzás p, p p, k k, k
p –2 0 0
k + 1 –1 –1

Innen kiolvasható, hogy a piros golyók számának paritása állandó. A golyók száma húzásonként 1-gyel csökken, így az utolsó golyó piros, ha  p páratlan, és kék, ha  p páros.

Megjegyzés: Ez a feladat tehát nem is valószínűségszámítási, hanem kombinatorikai jellegű.
9.11. feladat: Egy táblára felírtunk 1996 darab 1-est, 1997 darab 2-est és 1998 darab 3-ast. Bármely két számjegyet letörölhetjük, ha helyette a harmadik számjegyet egyszer felírjuk a táblára. Igaz-e, hogy ezt az eljárást ismételve elérhetjük, hogy a) csak egyfajta; b) csak egyetlen szám marad? Ha igen, melyik lehet ez a szám?
Megoldás: A számjegyek számának lehetséges változásai:
törlés 1, 2 1, 3 2, 3
1 –1 –1 + 1
2 –1 + 1 –1
3 + 1 –1 –1

a) Egy 2-es és 3-as törlése után az (1997, 1996, 1997) hármasból elérhető a csupa 2-es helyzet. Egy-egy lépésben mindegyik számjegy paritása megváltozik, a számjegyek közötti paritások különbözősége a játék folyamán végig megmarad. Másfajta végállapot tehát nem lehetséges, mert a 2-esek számának kezdeti paritása eltér a másik két szám paritásától, és a végállapotban az 1-esek és 3-asok számának paritása meg kell, hogy egyezzen.

b) Ciklikusan szimmetrikus csökkentés után elérhető a (0, 1, 2) helyzet, innen (1, 0, 1)-et, majd (0, 1, 0)-t kapjuk.

(Más megoldási lehetőségek: 1, 2 törlésével elérhető (0, 1, 3994), innen ⇒ (1, 0, 3993) ⇒ (0, 1, 3992) ⇒ … ⇒ (1, 0, 1) ⇒ (0, 1, 0).)

Megjegyzések: A játék felfogható egy olyan golyómodellnek, amelyben az 1-es, 2-es és 3-as számjegyek a piros, kék, sárga golyóknak feleltethetők meg. Ha nem irányított, hanem véletlenszerű folyamatot akarunk, akkor annyiban módosítjuk a visszatevési szabályt, hogy ha két egyforma golyót húzunk (számjegyet választunk), akkor mindkettőt visszatesszük. Így a játék kódja [3, 2, –1], a golyószám (nem szigorúan monoton módon) csökkenő.
9.12. (kitűzött) feladat: Annak szükséges feltétele, hogy a végállapotban a három számjegy közül bármelyik megmaradhasson, az, hogy a három számjegy darabszámának azonos legyen a paritása. Ez a feltétel vajon elégséges is?
9.13. feladat:Egy szigeten 13 szürke, 15 barna és 17 zöld kaméleon él. Ha két különböző színű kaméleon találkozik, megijednek egymástól, mindketten a harmadik színre változtatják a bőrüket. Két azonos színű találkozásakor nem változtatják meg a színüket. Lehetséges-e, hogy egy idő múlva minden kaméleon ugyanolyan színűvé válik?
Megoldás: A játéknak megfelelő golyómodell kódja [3, 2, 0]. Az  s, b, z színű kaméleonok számának lehetséges változásai:
törlés s, b s, z b, z
s –1 –1 + 2
b –1 + 2 –1
z + 2 –1 –1

Észrevehetjük, hogy a játék folyamán (sb), (sz) és (bz) 3-as maradéka állandó. A végállapotban kétfajta kaméleonnak 3-mal osztva azonos maradékúnak (t.i. 0-nak) kellene lennie. Mivel kezdetben a számuk 1, 0, 2 (mod 3), így nem lehetséges, hogy csak egyfajta kaméleon maradjon.

Másik megoldási lehetőség: Kódoljuk rendre az egyes fajtájú kaméleonokat 1, 2, 3 számokkal! Kezdetben a számok összege 94, s mivel az összeg lépésenként 0, + 3, –3-mal változhat, a 3-mal osztható végállapot nem állhat elő.
9.14. (kitűzött) feladat: Annak szükséges feltétele, hogy a végállapotban a három közül bármelyik színű kaméleon megmaradhasson, az, hogy a három szín darabszáma (mod 3) azonos maradékot adjon. Ez a feltétel vajon elégséges is?

Konform- és kontrastratégiák

9.15. feladat: Egy urnában tíz golyó van, kezdetben mind kék. Minden lépésben véletlenszerűen kiválasztunk egy golyót. A húzási szabály a következő: Ha a kiválasztott golyó kék, pirosra cseréljük ki, ha piros, akkor változtatás nélkül visszatesszük. A játéknak akkor van vége, amikor minden golyó piros. Átlagosan hány lépésig tart egy játék?
Megoldás: Ebben a [2, 1, 0] típusú játékban a piros golyók száma csak nőhet, a szabály a piros színt támogatja (piros konform stratégia). Többféle megoldási gondolatmenet lehetséges, amelyeket más golyómodellek vizsgálatakor is gyakran sikerrel alkalmazhatunk. Ezeket részletesen elemeztük a 4.1. feladat kapcsán, most csak az eredményt közöljük: 1000 szimuláció eredményeként 29,2-es átlagot kaptunk.
Megjegyzés:Észrevehetjük, hogy a 9.9. feladat második algoritmusa éppen ennek a konform stratégiájú golyómodellnek feleltethető meg.
9.16. feladat: Határozzuk meg a 9.13. feladat kaméleon-problémájának  s = 1,  b = 3,
z = 4 kiindulási adatokhoz tartozó várható lépésszámát! (Emlékeztetőül: ha két egyforma színű kaméleon találkozik, nem történik semmi; különböző színűek a harmadik színre változtatják a színüket; a játéknak akkor van vége, ha minden kaméleon azonos színű; a várható lépésszám pedig a végállapot eléréséig a találkozások átlagos számát jelenti.)
Megoldás: Korábban megállapítottuk, hogy a végállapotban minden kaméleon barna színű lesz. A lépésszámok szempontjából tehát például az {s, b, z} = {1, 3, 4} és {s, b, z} =
{4, 3, 1} állapotok ekvivalensek, ezeket nem érdemes megkülönböztetnünk egymástól. A játék folyamán - a színektől függetlenül - a következő állapotok lehetségesek:

A = {1, 3, 4}; B = {0, 2, 6}, C = {0, 3, 5}; D = {2, 3, 3}, E = {1, 2, 5}; F = {2, 2, 4},
G = {0, 1, 7}; H = {4, 4, 0}, I = {1, 1, 6}. A modellt tekintve 8 golyó közül 2-t markov = 28-féleképpen választhatunk ki; az egyes állapotok közötti átmeneti valószínűségek tehát markov alakúak lesznek. Jelöljük  a, b, … , i-vel a folyamat befejezéséig várható lépésszámot, ha a játék az  A, B, …, I állapotokban van; ekkor például az  A állapothoz tartozó átlagos lépésszámot az  a = markov egyenlet adja meg. (Az  A állapotból 1×3 = 3-féleképpen jutunk a  B állapotba; 1×4 = 4-féleképpen  C-be; 3×4 = 12 esetben  D-be; végül 3 + 6 = 9 esetben  A-ba. Az egyenlet értelmezése: az  A állapotból lépünk 1-et, plusz markov valószínűséggel átjutunk a  B állapotba, és innen átlagosan további  b lépés szükséges stb.; a korábbi játékokhoz hasonló eljárással.)

Az állapotok közötti kapcsolatokat tehát az alábbi egyenletrendszerrel adhatjuk meg:

markov, vagyis 19a – 3b – 4c – 12d = 28;

markov, 12b – 12e = 28;

markov 15c – 15f = 28;

markov 21d – 12e – 9f = 28;

markov –10a + 17e – 2g – 5h = 28;

markov –16a + 20f – 4i = 28;

markov –7b + 7g = 28;

markov –16d + 16h = 28;

markov –12c + 13i = 28.

(Ez utóbbi egyenletben az markov tag a végállapothoz tartozó 0 lépésszámot jelzi.)

Az egyenletrendszer elég bonyolult, a megoldást számítógéppel érdemes meghatároznunk.

Eredmény:

(a; b; c; d; e; f; g; h; i) = (647,9; 653,1; 640,2; 646,8; 650,8; 638,3; 657,1; 648,5; 593,1).

9.17. feladat Egy dobozban 3 piros, 2 sárga és 4 kék golyó van. A statisztikus golyómodell szabályait megadhatjuk az alábbi mátrixszal:
  p s k
p p p k
s p s k
k k k p

Itt a p sor és s oszlop p eleme azt a szabályt jelenti, hogy ha elsőnek egy piros, majd másodiknak egy sárga golyót húzunk, akkor egy piros golyót teszünk vissza a dobozba.

Elemezzük a játékot! Mekkora valószínűséggel marad egyetlen piros, sárga, illetve kék golyó a dobozban?

Megoldás: A táblázat szimmetrikus a főátlóra, vagyis a két kihúzott golyó sorrendjétől nem függ a visszatevési szabály. A játék csökkenő golyószámú, [3, 2, –1] típusú; a végállapotban egyetlen golyó marad, 8 lépés után. Az s sor elemei rendre  p, s, k; vagyis ha egy húzásban szerepel sárga golyó, akkor a sárga golyók darabszáma csökken.

Sárga golyó csak az (s, s) állapot után maradhatna; ez pedig csak akkor fordulhatna elő, ha az első 6 húzás egyikében sem lenne sárga golyó. Ez nem lehetséges, hiszen legkésőbb a 6. húzásban biztosan húzunk sárga golyót.

Előbb-utóbb tehát minden sárga golyó elfogy. A piros és kék golyók szempontjából pedig a játék az 5.7. játékkal analóg; ha a sárga golyókat tartalmazó húzásokat figyelmen kívül hagyjuk, akkor a kék golyók számának paritása állandó, tehát a végállapotban csak piros golyó maradhat.

Vegyes feladatok

9.18. (kitűzött) feladat: Egy dobozban 3 piros és 3 kék golyó van. Minden lépésben véletlenszerűen (visszatevéssel) kihúzunk egy golyót, s a színét feljegyezzük. A játéknak akkor van vége, ha a húzott piros és kék golyók számának különbsége eléri az 5-öt. Átlagosan hány húzásig tart a játék?
Megjegyzés: A piros és kék golyókat csak a fejezetcím kedvéért használtuk; a célnak ugyanígy megfelelt volna például egy szabályos érme is.
9.19. (kitűzött) feladat: Egy urnában 8 golyó van, kezdetben 4 piros és 4 kék. Minden lépésben véletlenszerűen kiválasztunk egy golyót, és ellenkező színűre cseréljük ki. A játéknak akkor van vége, ha minden golyó színe egyforma. Átlagosan hány lépésig tart ez a [2, 1, 0] típusú játék? (A játék mindkét színben kontrastratégiájú.)
(Eredmény: 149,3.)
9.20. (kitűzött) feladat: Az előző feladatot annyiban módosítjuk, hogy a játéknak akkor van vége, ha minden golyó piros. Átlagosan hány lépésig tart ez a [2, 1, 0] típusú játék?
(Eredmény: 305,4.)
9.21. (kitűzött) feladat: Egy dobozban négy különböző színű golyó van. Véletlenszerűen kiválasztunk kettőt, majd az első golyót olyan színűre festjük, mint amilyen a második. (A játék típusa [4, 2, 0].) Várhatóan hány húzás kell ahhoz, hogy minden golyó egyszínű legyen?
(Eredmény: 9.)
9.22. (kitűzött) feladat:Egy kémcsőbe egy amőbát helyezünk el. Az amőba szaporodási stratégiája a következő: minden perc végén

- vagy meghal;

- vagy kettéosztódik;

- vagy háromfelé osztódik;

- vagy ül tovább, mintha mi sem történt volna.

Mi annak a valószínűsége, hogy előbb-utóbb elpusztul az összes amőba, ha mind a négy állapotváltozás markov valószínűséggel következik be?

(Eredmény: markov – 1 ≈ 0,414.)
9.23. (kitűzött) feladat: Egy dobozban kezdetben 3 piros, 2 sárga és 4 kék golyó van. Elemezzük az alábbi a) - d) játékokat!
a) b) c) d)
  p s k     p s k     p s k     p s k
p s k s   p s k s   p s k s   p pp k s
s k s p   s k ss p   s k p   s k s p
k s p s   k s p s   k s p s   k s p pp

(Itt ss és pp azt jelenti, hogy a dobozba két sárga, illetve két piros golyót teszünk vissza.)

9.24. (kitűzött) feladat (egyirányú bolyongás): [12]-ből származik a következő feladat:

Mindenki ismeri a „Ki nevet a végén” játékot, ahol pontosan a célmezőre kell lépni a győzelemhez. Ha a cél pontosan a 100. mező és egy dobókockával játszunk, akkor eltekintve a kiütéstől vagy egyéb trükköktől, mekkora eséllyel fogunk pontosan a 100-as mezőre lépni a végén: markov, markov vagy markov?

Jelentse pi annak a valószínűségét, hogy a játékban az i-edik mezőre lépünk.

Írjunk egy programot, amellyel elvégezhetjük a játék nagyszámú szimulációját, s állapítsuk meg, hogy a három számérték közül melyik a helyes!

Igazoljuk, hogy markov, ha i = 1, 2, … , 6.

Igazoljuk, hogy markov.

 Írjunk egy programot, amellyel kiszámoljuk p100 értékét a fenti rekurzív formula segítségével.

A játékok számítógépes megvalósítása a tanítási órán

Véleményem szerint a játékra három szinten van lehetőség.

Az alapszint az lehet, amikor a témakört előkészítjük; vagyis mindenfajta elméleti tárgyalás nélkül, a diákok józan értékítéletére hagyatkozva például becsléseket végeztetünk velük. Egyik ilyen lehetőség a játékok szimulációja. A 9.3. játékot véletlen k, p paraméterekkel futtatva, a diákok tippelhetnek a győztes személyére és a húzások várható számára. Lehet egyéni vagy csapatversenyt is rendezni (például 13 + 1-es totó).

A 9.5. játék szabályait is megváltoztathatjuk: lehetséges, hogy az A játékosnak x darab, a B játékosnak y darab piros (vagy kék) golyót kell a győzelméhez kihúznia; játszhatunk különböző színű golyókkal (ekkor egyes színek esetleg semlegesek); lehet több játékos stb.

Gyakoroltassuk a fordított irányú játékot is: amikor például a játékszabály (játékosok száma, a győzelem definíciója) ismertetése után megadjuk a piros golyók számát, s kérdés az, hogy az igazságos játékhoz hány kék golyót tegyünk az urnába; vagy adott az összes golyó száma, s a kérdés a piros és kék golyók aránya.

S persze számtalan lehetőség képzelhető el; érdemes meghallgatnunk a tanulók ötleteit is.

A játékok második szintje a matematikai alapozás után képzelhető el. Ekkor az egyszerűbb, kis paraméterű feladatok valószínűségei konkrétan kiszámíthatók; a számítógépes játék mintegy "ellenőrzi" a kapott eredményt. (Itt kiderülhet, mi is az a véletlen; valamint felvetődhetnek a gépi véletlenszámokkal kapcsolatos problémák is.)

A harmadik szint az lehet, amikor tetszőlegesen paraméterezett feladatot is meg tudunk oldani a számítógéppel; vagyis amikor a diákok a programozásba is bekapcsolódnak.

10.1. feladat (a véletlen számok „kiegyenlítődési hajlama”): A [6] könyvben olvashatunk egy újságcikkről: „Ha feldobunk egytrillió tízfillérest, rendkívül furcsa eredményt kapunk: néhány pénzdarab eltéréssel féltrillió fej lesz és féltrillió írás.” Átlagosan mennyi ez az újság által említett „néhány pénzdarabnyi eltérés”?
Megoldás: Hajlamosak vagyunk azt hinni, hogy nagyszámú (például 102k) dobás esetén a fejek és írások száma megközelítőleg egyenlő lesz. Ez nem így van.

Ez a probléma lényegében egy „fej vagy írás”-típusú érmedobálási vagy bolyongási feladat, ilyen volt például 3.6. és 6.3. Ezeknél a feladatoknál is jeleztük, hogy az egyensúlyi helyzettől való eltérés ez esetben a dobásszám gyökével arányos. Jó közelítéssel mondhatjuk, hogy egytrilliónyi (1018) dobás esetén a „néhány pénzdarabnyi eltérés” kb. 109 nagyságrendű, vagyis egymilliárdnyi érmét jelent. (Annak ellenére, hogy a legvalószínűbb dobássorozat az, amelyikben a fejek és írások száma megegyezik!) Ez pedig azt jelenti, hogy csak a relatív eltérés tart nullához (102k dobás esetén ez közelítőleg 10k), az abszolút eltérés tetszőlegesen nagy lehet.

Megjegyzés: Emlékeztetőül: ha például 2N dobás esetén F fejet dobunk, akkor a fejek számának az egyensúlyi helyzettől való abszolút eltérése |F – N|, a relatív eltérés pedig az abszolút eltérés és az összes dobás hányadosa: markov.

Tekintsük a következő, gyakran elhangzó kijelentést: „Szabályos érme esetén a fejek számának relatív gyakorisága 0,5-hez tart.” A fenti példánk mutatja, hogy milyen nehézségekkel találkozunk a valószínűség fogalmának a definiálásakor; hiszen itt a „tart” szó egyáltalán nem a hagyományos, az analízisben már megszokott konvergencia-fogalmat jelenti.

Kibe szerelmes a királylány?

10.2. feladat: Három herceg, A, B és C egyaránt szerelmes Bergengócia királylányába. Elhatározzák, hogy egyetlen pisztolypárbajban eldöntik, melyikük legyen a kérő. Egyszerre körbeállnak és bármelyikük lőhet bármelyikükre. Tudják egymásról, hogy ha lő, A 1, B 0,8 és C 0,5 valószínűséggel talál, ezért abban állapodnak meg, hogy először lő C, utána (ha életben van) B, végül A. Ha nincs vége a párbajnak, akkor még egy kört lőnek azonos sorrendben.

Mikor a királylány meghallotta a feltételeket, a párbaj előtti este titokban kicserélte C első golyóját vaktöltényre.

a) Kibe szerelmes a királylány?

b) Hogyan változnak meg a párbaj valószínűségei, ha most a felek nemcsak kettő, hanem tetszőleges számú lövést adhatnak le?

(A királylány most is csak az első golyót cseréli ki vaktöltényre.)

Megoldás:

Jelöljük A, B, C győzelmi esélyét a, b, c-vel, a döntetlen valószínűségét D-vel.

1. eset: Nézzük azt az esetet, amikor megtörtént a csere, tehát C első golyója vaktöltény. Az első lövésből C nem talál, B következik. Ő nyilván A-ra lő (mert ha C-re lőne, és őt véletlenül eltalálná, akkor A következik; A lelövi B-t és nyert). Ha B eltalálja A-t, akkor a játék "kétszemélyes" lesz B és C között; míg ha B nem találja el A-t, akkor A következik lövésre. Ő a két lehetséges ellenfele közül nyilván a veszélyesebb B-re lő, akit el is talál, így ismét "kétszemélyes játékot" kaptunk A és C között. A teljes játék folyamatábrája:

markov

Mekkora valószínűséggel győznek az egyes párbajozók?

P(A nyer)markov (a folyamatot jelölhetjük például markov módon is);

P(B nyer) = markov (a folyamat: markov).

B élve marad további  markov  eséllyel, ez a  B-C döntetlen párbaj eredménye: markov.

P(C nyer) = markov (a folyamat jelölése: markov vagy markov).

C élve marad további  markov  eséllyel, a döntetlen miatt.

2. eset: Vizsgáljuk most meg azt a helyzetet, amikor C első lövése nem vaktöltény!

Első lövésével C nyilván A-ra lő; ha nem találja el, előáll az első eset, míg ha talál, akkor B és C között egy kétszemélyes párbajt kapunk (amely meglehetősen előnyös B-nek, hiszen ő lő először, nagyobb valószínűséggel talál, és két lövési lehetősége van, míg C-nek csak egy). A folyamatábra:

markov

P(A nyer)markovmarkov, markov,  valamint B és C egyaránt élve marad a döntetlen lehetősége miatt  markov  eséllyel.

Nos, kibe szerelmes a királylány?

Az eredmények alapján bármily meglepő, de úgy tűnik, hogy C-be, hiszen győzelmi esélye 20 %-kal megnőtt. De az is elképzelhető, hogy A-ba, hiszen neki a beavatkozás után kétszeresre nőtt a nyerési esélye.

Vizsgáljuk meg azt az esetet is, amikor B első golyóját cserélné ki a királylány! (Erre azért van szükség, mert elképzelhető, hogy ekkor A vagy C nyerési esélye jobban megnőne, mint az előző esetben. )

Ekkor a folyamatábra a következő:

markov

Az egyes párbajozók nyerési esélyei:

P(A nyer)markov (a folyamat markov);

P(B nyer) = markov (a folyamat: markov).

P(döntetlen B, C között) = markov (a folyamat: markov).

P(C nyer) = markov (a folyamat jelölése: markov vagy markov).

Foglaljuk táblázatba az eredményeket:

Az egyes játékosok
(a = 1, b = 0,8, c = 0,5)
Győzelmi valószínűségek C vaktöltényével Győzelmi valószínűségek B vaktöltényével Győzelmi valószínűségek éles töltényekkel
       
A 10 % 25 % 5 %
B 32 % 20 % 60 %
C 50 % 50 % 30 %
döntetlen B és C között 8 % 5 % 5 %

A királynő tehát biztos, hogy C-be szerelmes. (Ha A-ba lenne szerelmes, akkor B töltényét cserélné ki.)

Megjegyzések:

1. Az általános eset folyamatábrája a, b, c valószínűségekkel, ha C első golyója vaktöltény:

markov

Ennek alapján, ha C első golyója vaktöltény, a nyerési esélyek az alábbiak:

A nyer: a1 = (1 – b)(1 – c);

B nyer: b1 = b2(1 – c);

C nyer: c1 = c;

D (döntetlen): d1 = b(1 – b)(1 – c).

Hogyan néz ki a folyamatábra akkor, ha az első golyó nem vaktöltény?

markov

Ha C első lövésével A-t veszi célba, és golyója nem vaktöltény, akkor az alábbi győzelmi valószínűségeket kapjuk:

A nyer:  (1 – c)a1;

B nyer:  (1 – c)b1 + bc + bc(1 – b)(1 – c);

C nyer:  (1 – c)c1 + c2(1 – b);

D:  (1 – c)d1 + c(1 – c)(1 – b)2.

Példaképpen nézzük meg, hogyan változnak a valószínűségek b és c csökkentésével:

Az egyes játékosok
(a = 1; b = 0,5; c = 0,3)
A győzelmi valószínűségek vaktölténnyel A győzelmi valószínűségek éles tölténnyel
     
A 35 % 24,5 %
B 17,5 % 32,5 %
C 30 % 25,5 %
döntetlen B és C között 17,5 % 17,5 %
Az egyes játékosok
(a = 1; b = 0,8; c = 0,3)
A győzelmi valószínűségek vaktölténnyel A győzelmi valószínűségek éles tölténnyel
     
A 14 % 9,8 %
B 44,8 % 58,7 %
C 30 % 22,8 %
döntetlen B és C között 11,2 % 8,7 %

2. A megoldás folyamán feltételeztük, hogy a királylány használni tudja a matematikai folyamatábrákat. Ha C is elég jó matematikus, akkor az egész csere-tranzakció felesleges, mert C első lövésével úgyis szándékosan a levegőbe lő.

3. Nem vizsgáltuk meg azt az esetet, ha a királylány A első golyóját cseréli ki. Ekkor ugyanis A első lövésekor kiderülne a turpisság.

Az osztozkodás-paradoxon

10.3. feladat (osztozkodás-paradoxon): Két játékos egy szabályos érmével játszik. András akkor győz, ha - nem szükségképpen egymás után - öt fej jön ki, Béla pedig akkor, ha öt írás. A játszma négy fej, két írás állásnál véglegesen félbeszakad. Hogyan osztozzanak a játékosok az 1600 Ft-os téten?

Az alábbiakban felsorolunk néhány gondolatmenetet, amelyek különböző megfontolásokon alapulnak.

Első gondolatmenet: Az összeget 4 : 2 arányban kell felosztaniuk, hiszen ennyi a dobott fejek és írások aránya.

Második gondolatmenet: Az összeget 3 : 1 arányban kell felosztaniuk, hiszen ennyi fej, illetve írás dobás hiányzik a játékosok győzelméhez.

Harmadik gondolatmenet: Még nincs vége a játéknak, vagy András nyer, vagy Béla. Az arány legyen 1 : 1, így igazságos.

Negyedik gondolatmenet (Niccolo Tartaglia (1499 - 1557) olasz matematikus): András 2 játékkal nyert többet, mint Béla, ezért meg kell kapnia az összes tét markov részét, a maradékot pedig fele-fele arányban kell elosztani. Az arány 7 : 3.

Ötödik gondolatmenet:A 4 fej, 2 írás valószínűsége markov = markov. Ennyivel volt szerencsésebb András, ezért a javasolt osztozkodási arány 49 : 15.

Hatodik gondolatmenet: Csak az egyenlőnek számító "2 fej - 2 írás" álláshoz képest történt változást vizsgáljuk. András előnyösebb helyzetben van 2 fej dobással. A 2 többletdobás kimenetele 4-féle lehet, a 2 fej dobás markov valószínűségű. Ennek megfelelően a helyes osztozkodási arány 3 : 1.

Megjegyzések:

1. A fenti megoldások többségét diákjaim is javasolták, de egyik sem jó.

2. A helyes gondolatmenet kiválasztását érdemes feladatként kitűzni.

Megoldás: A feladat megoldásakor az a helyes kiindulási alap, ha azt vizsgáljuk meg, hogy a játékot tovább folytatva, a játék befejezéséig mekkora valószínűséggel nyerne András, illetve Béla. Ugyanis Béla csak akkor nyerhetne, ha a következő három dobás mindegyike írás lenne, ennek valószínűsége pedig markov. Minden más esetben András nyer, az igazságos osztozkodási arány tehát 7 : 1.

A hasonló típusú bonyolultabb feladatok (más kezdőhelyzet, más végállapot) a Markov-láncok segítségével tárgyalhatók; most erre nem volt szükségünk.

3. Egy kis matematikatörténet:

Már 1380-as és 1494-es kéziratokban is találkozunk a paradoxonnal (persze a korabeli megoldók még nem vették észre, hogy a feladat valószínűségszámítási jellegű, hiszen akkor ez a fogalom még nem is létezett). 1654-ben Pascal és Fermat egymástól függetlenül megoldotta a problémát, s ez akkoriban olyan komoly felfedezésnek számított, hogy sokan ma is ettől az időponttól számítják a valószínűségszámítás megszületését. Végül 1657-ben Huygens három játékos esetére is általánosította a problémát.

10.4. (kitűzött) feladat: A 10.3. alapfeladatban András 5 fej, Béla 5 írás esetén nyert (nem szükségképpen egymás utáni dobásokkal); s a játék András 4:2-es vezetésekor szakadt félbe. Vizsgáljunk meg egyéb félbeszakadt játékokat is: például ha András vezet

a) 4:1;

b) 3:2;

c) 3:1 arányban.

Mekkora valószínűséggel nyer ekkor András?

10.5. (kitűzött) feladat: Egyéb általánosítási lehetőségek is elképzelhetők. Például: Andrásnak 6 fejet, Bélának 4 írást kell elérnie, s András 2:1-re vezet. Most mekkora valószínűséggel nyer András?
10.6. (kitűzött) feladat: Két játékos egy szabályos érmét folyamatosan dobál. András akkor győz, ha a fejek száma 5-tel több, mint az írások száma; Béla pedig akkor, ha az írások száma lesz több 5-tel a fejek számánál. Amikor a játszma véglegesen félbeszakad, a dobott fejek száma éppen 2-vel több, mint az írásoké. Hogyan osztozzanak a játékosok az 1600 Ft-os téten?
10.7. (kitűzött) feladat: Az osztozkodási alapfeladatot három játékosra általánosítjuk.

András akkor győz, ha - nem szükségképpen egymás után - öt fej jön ki; Béla akkor, ha öt írás; Csaba pedig akkor, ha három fej és három írás.

a) Melyik játékosnak mekkora kezdetben a nyerési esélye?

b) Átlagosan hány dobásig tart egy játék?

c) A játszma két fej, egy írás állásnál véglegesen félbeszakad. Hogyan osztozzanak a játékosok a mindannyiuk által befizetett 1600 Ft-os téten?

Érmedobálási paradoxonok

Csak néhány példát sorolunk fel; további példák bőségesen találhatók [9]-ben.

10.8. (kitűzött) feladat: Három játékos, A, B, C játékában három hosszú érmedobás-sorozatot vizsgálunk. Egy szabályos érmét folyamatosan dobálnak a játékosok úgy, hogy a játék szempontjából mindig csak az utolsó három dobás eredményét veszik figyelembe. (Egy lehetséges játék lenne például a következő: A nyer, ha az utolsó 3 dobás az FFF célsorozat, B nyer, ha III, C nyer, ha IFI.) A szabály ebben a játékban a következő:

Először az A játékos választ egy három hosszúságú sorozatot, ez lesz az ő célsorozata; ezután B választ egy célsorozatot úgy, hogy A-val szemben ez a lehető legjobb legyen számára; majd C választja azt, amelyik számára B-vel szemben a lehető legelőnyösebb. A játékosok által befizetett tét játékonként és fejenként 12 egység. Ez a játék A számára nagyon előnytelennek tűnik, ezért ha B vagy C nyer a játékban, akkor fájdalomdíjként a 36 egység nyereményből 3 egységet átad A-nak.

Kinek legelőnyösebb így ez a játék? Hogyan kezdjen A?

(Tapasztalunk valami érdekeset?)

Útmutatás: A 8.13. feladatban megadtuk a kétszemélyes, háromdobásos érmedobálási játékok esélyeit tartalmazó táblázatot, ezt most is közöljük:
  FFF FFI FIF FII IFF IFI IIF III
FFF 1:1 2:3 2:3 1:7 5:7 3:7 1:1
FFI 1:1 2:1 2:1 1:3 5:3 1:1 7:3
FIF 3:2 1:2 1:1 1:1 1:1 3:5 7:5
FII 3:2 1:2 1:1 1:1 1:1 3:1 7:1
IFF 7:1 3:1 1:1 1:1 1:1 1:2 3:2
IFI 7:5 3:5 1:1 1:1 1:1 1:2 3:2
IIF 7:3 1:1 5:3 1:3 2:1 2:1 1:1
III 1:1 3:7 5:7 1:7 2:3 2:3 1:1

(Itt például az IFF sor FFF oszlopában lévő 7:1 arány azt jelenti, hogy az érmét folyamatosan dobálva annak valószínűsége, hogy előbb jön ki FFF, mint IFF, markov, míg annak a valószínűsége, hogy hamarabb kapunk IFF-et, markov.)

10.9. feladat: Ha a kétszemélyes „fej vagy írás” játékokban az A és B célsorozatok egymással szemben ugyanakkora valószínűséggel nyernek, a játékot „igazságosnak” nevezzük. Mutassuk meg, hogy az „igazságosság” nem tranzitív reláció!
Megoldás: Megfelelő például a 3.5. feladat három sorozata: A = FF, B = II, C = IF. Ugyanis a győzelmi arányok A : B = 1 : 1, B : C = 1 : 1, de C : A = 3 : 1.
10.10. (kitűzött) feladat: Ha a kétszemélyes „fej vagy írás” játékokban az A és B célsorozatok egymás ellen játszanak, és A nagyobb valószínűséggel nyer, mint B, akkor az A sorozatot „jobb”-nak nevezzük. Mutassuk meg, hogy a „jobb” nem tranzitív reláció!
Útmutatás: Válasszuk ki a FFI, IFF, IIF, FII sorozatokat; s hasonlítsuk össze őket abból a szempontból, hogy melyiknek van nagyobb esélye arra, hogy korábban előforduljon. Legyen a sorrend FFI – IFF, IFF – IIF, IIF – FII, FII – FFI (lásd előző táblázat). Milyen érdekességet tapasztalunk?
10.11. (kitűzött) feladat: Próbáljuk az előző feladat eredményei alapján megbecsülni, hogy „fej vagy írás” játék esetén az FFI, IFF, IIF, FII sorozatokat (külön-külön) átlagosan hány dobás után kapjuk meg! Számoljuk is ki ezeket az értékeket.
10.12. feladat: Szabályos érmét sokszor ismételten feldobunk, míg vagy szomszédos FIFI, vagy szomszédos IFII sorozatokat kapunk. András akkor nyer, ha az FIFI sorozat jön ki hamarabb, míg Csaba akkor, ha az IFII sorozat.

a) Melyik játékosnak előnyös ez a játék?

b) Átlagosan hány dobást kell végeznünk, míg megkapjuk az egyik, illetve a másik sorozatot?

c) Nincs itt valamilyen ellentmondás?

Megoldás:

a) Az első sorozat markov valószínűséggel hamarabb fordul elő, a játék Andrásnak előnyös.

b) Az első sorozathoz átlagosan 20, a másodikhoz átlagosan 18 dobás szükséges.

c) Azt kaptuk, hogy az első esemény (FIFI) bekövetkezésének nagyobb a valószínűsége, mégis átlagban később következik be, mint IFII. Ennek az az oka, hogy ha IFII nyer, akkor általában ez gyorsan (és kis valószínűséggel) történik; míg ha FIFI nyer, az gyakrabban előfordul, de alkalmanként sok lépést igényelhet.

10.13. (kitűzött) feladat: Adottak IFF, IIF, FII, FFI. Két játékos játszik; először A választ egy sorozatot, majd egy ettől különbözőt B. „Mennyire” előnyös a korábban választó A számára ez a játék? Ha játékonként 100 Ft a tét, mennyi az átlagos nyereménye?
Útmutatás: 10.10. alapján a sorozatok “körbeverik” egymást, tehát hiába választhat elsőnek A, az ő sorozatánál mindig fog jobbat találni B. Tehát A átlagos nyereménye negatív lesz.
10.14. (kitűzött) feladat: A kétszemélyes „fej vagy írás” játékban a célsorozatok: A = IFF, B = FFI. Az előállásukhoz szükséges átlagos lépésszám egyforma: L(A) = 8, L(B) = 8; mégis a győzelmi arány A : B = 3 : 1. Hogyan lehetséges ez?
Útmutatás: Lásd a 10.12. c) feladat megoldását.
10.15. feladat: A 8.6. feladatban (ami a 10.12. „kibővítése”) három játékos játszott egymás ellen. András akkor nyert, ha az FIFI sorozat jött ki hamarabb, Béla akkor, ha az IIFF sorozat, míg Csaba akkor, ha az IFII sorozat. Elemezzük a kapott eredményeket! Milyen érdekességeket vehetünk észre?

a) Ha az A = FIFI, B = IIFF, C = IFII sorozatok „önállóan” vesznek részt a játékban, akkor a bekövetkezésükhöz szükséges átlagos lépésszámokra az L(FIFI) = 20, L(IIFF) = 16, L(IFII) = 18 értékeket kaptuk. Átlagban legkésőbb tehát az A, legkorábban pedig a B sorozat jön ki. De ebből nem következik, hogy a legelőnyösebb az A sorozat választása, hiszen a nyerési valószínűségekre kapott értékek (pA, pB, pC) = markov. (Hasonló a helyzet, mint a 10.12. és 10.14. feladatokban.)

Vagyis átlagban C veszít, A és B között pedig igazságosnak tekinthető a játék.

b) Ha a leggyengébb Csaba kiesik a versenyből (például elfogy a pénze), akkor A és B között folytatódik az elvileg igazságos játék. De itt váratlan dolog történik, ez a kétszemélyes játék már B-nek előnyös: A : B = 7 : 9. C kiesésével tehát megváltoztak az A és B közötti nyerési esélyek.

Az igazolás Conway algoritmusával a legegyszerűbb. A o A = 4 + 16 = 20; A o B = 2;
B o A = 2; B o B = 16; innen markov.

c) Mekkorák a B és C közötti játékban a győzelmi valószínűségek?

Conway módszerét alkalmazzuk. B o B = 16; B o C = 0; C o B = 2 + 4 = 6; C o C = 2 + 16 = 18. Innen markov = markov, a kétszemélyes játék már C-nek előnyös: B : C = 3 : 4. Tehát váratlan eredményt kaptunk: A kiválásával megváltoztak a B és C közötti nyerési esélyek, a korábban leggyengébb C most erősebb lett B-nél.

d) Mekkorák az A és C közötti játékban a győzelmi valószínűségek?

Eredmény: A : C = 9 : 5 (10.12. feladat).

e) Ez az „igazság pillanata”: a kétszemélyes játékokban A legyőzi C-t, C legyőzi B-t, és B legyőzi A-t. Úgy is fogalmazhatunk, hogy az A, B, C sorozatok „körbeverik” egymást.

Korábban is láttuk már (a 10.10. feladatban), hogy a „jobb” vagy a „legyőzi” nem tranzitív reláció; az ott adott FFI, IFF, IIF, FII három hosszúságú célsorozatok körbeverték egymást. De most - a négy hosszúságú célsorozatok körében - a körbeverés példájához már elég volt három sorozatot megadnunk.

Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.