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

A cikk létrehozását a Fazekas Mihály Oktatási Kulturális és Sport Alapítványon keresztül támogatta az Infosyscon Kft

Az internetes változatot Kiss Marcell (2009d) diák készítette

 

Tartalomjegyzék

  1. Bevezető
    • A Markov-láncok módszere (összefoglalás)
  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.

Bevezető

A valószínűségszámítás témaköre

A valószínűségszámítás témaköre korábban úgy szerepelt a középiskolás matematika-oktatásban, mint “nem hangsúlyozott anyagrész”. Nem volt törzsanyag, ezért az országos középiskolai versenyeken és a főiskolai-egyetemi felvételi feladatok között is csak elvétve találtunk példákat ebből a témakörből. Ugyanakkor szakkörön vagy fakultáción a téma általában sikeresnek bizonyult: a tanulókat érdekelték az általános- és középiskolai alapfeladatokon túlmutató problémák. Pozitív változást a kétszintű érettségi vizsga bevezetését megelőző időszak hozott. A formailag és tartalmilag megváltozott érettségi kapcsán módosultak a tantárgyi követelmények. Az új típusú vizsga előkészítő szakaszában, például a statisztika-tanítási koncepció keretében ismét kötelezően tanítottuk a témát, elsősorban mint a statisztika segédeszközét. A jelenlegi érettségi vizsgakövetelmények pedig - amelyek, remélhetőleg, jó néhány évig változatlanok maradnak - emelt szinten tartalmazzák a nagy számok törvényének szemléletes tartalmát; a geometriai valószínűség fogalmát; egyes eloszlások alkalmazását, várható értékét és szórását; a relatív gyakoriság becslését a sokaság paramétereinek ismeretében.

A Markov-láncok

Ebben a cikkben a valószínűségszámítás egy speciális területéről, a Markov-láncok témaköréből válogattunk feladatokat. A Markov-láncok alkalmazását középiskolában általában nem tanítjuk. Ennek - a lecsökkent óraszámok miatti időhiány mellett - elsősorban az az oka, hogy a témakör mélyebb tárgyalásához szükség van például a feltételes valószínűség fogalmára vagy a lineáris algebra egyes tételeire. Azonban a téma elemi úton is tanítható; ekkor csupán a kombinatorika összeadási és szorzási szabályának ismeretére van szükség, amelyet alkalmazhatunk a klasszikus valószínűségekre is.
Összeadási és szorzási szabály:Ha egy bizonyos A objektumot m, egy másik független B objektumot n-féleképpen lehet kiválasztani, akkor az összeadási szabály azt jelenti, hogy a "vagy A, vagy B" kiválasztás m + n féleképpen történhet; a szorzási szabály pedig azt, hogy az (A, B) pár kiválasztása ("A és B") mn-féleképpen lehetséges.
A diákok már a Markov-láncok minimális ismeretében is látványos eredményeket érhetnek el. Sokféle, korábban megoldhatatlannak tűnő, vagy megfelelő matematikai eszköz hiányában kezelhetetlen feladatra egyszerű, elegáns megoldást találhatnak. Itt fontos egy módszertani megjegyezést tennünk. Általában nem érdemes egyszerre “nagyot markolni”; például nem szabad új elméleti anyagot úgy tárgyalnunk, hogy közben párhuzamosan tanítjuk a tárgyaláshoz szükséges technikai apparátust is. Ekkor a feladat - és a diákjaink is - könnyen “elúsznak”. Javasoltabb időben széthúzni, kisebb részekre bontani, többször előásni a problémát, vagyis a “kis (de jól megtervezett) lépések taktikáját” alkalmazni. Egy konkrét példa későbbről: a bolyongások tárgyalásához szükség lehet a másodrendű lineáris rekurziók megoldásának ismeretére. Teljesen reménytelen ugyanazon a tanítási órán a bolyongást modellezni, felállítani egy másodrendű rekurzív összefüggést, valamint ezt a rekurziót - melyet életében először lát a diák - általánosan megoldani. A tanár számára komoly módszertani feladat az előzményeket és az aktuális témát eredményesen összekapcsolni, ez pedig nyilván csak megfelelő felkészüléssel érhető el. Mi ennek az írásnak a célja? Több célt tűztünk magunk elé. Szeretnénk egyrészt a Markov-láncokkal kapcsolatos megoldási technikákat és módszereket minél szélesebb körben ismertté tenni. Gyakran élünk (tanárokhoz szóló) módszertani megjegyzésekkel, de úgy gondoljuk, hogy ez nem kizáró ok: a cikket bárki - tanuló, érdeklődő, egyéb olvasó - számára ajánljuk. A következő fejezetek mindegyike egy-egy tipikus alkalmazásra mutat példát. A problémák egy részét a gyakorlati életből vettük; tárgyalásukban, feldolgozásuk módjában igyekszünk - amennyire csak lehetséges - elemi módszereket alkalmazni. A Markov-láncok tipikus témaköreinek (sorsolások, érmedobálások, statisztikus golyójátékok, bolyongások) vizsgálatakor az volt a célunk, hogy a bevezető típusfeladatok részletes szakmai és módszertani feldolgozása után biztos alapot kapjon az Olvasó. Erre a vázra építve, az egyes fejezetek anyagának további bővítése már önállóan is elvégezhető. (Nem törekedhettünk teljességre, még az egyes speciális témakörökön belül sem. Ennek a szakmai okokon túl olyan egyszerű technikai akadályai is vannak, mint például az időhiány, vagy a terjedelmi korlátok. Kit ne rettentene el egy bevezető jellegű írás, ha az több száz oldal hosszú?) Végül a speciális fejezetek (számítógépes támogatás, paradoxonok, versenyfeladatok) reményeink szerint hangsúlyozzák, hogy érdemes volt az Olvasónak átrágnia magát a korábbi fejezetek anyagán; hiszen egy érdekes, széles körben és igen eredményesen alkalmazható módszerhez jutott. A feladatok feldolgozásának számítógépes támogatása A következő fejezetekben a valószínűségszámítási problémák játékok elemzéseként jelennek meg. A matematikai játékok rendszeres, órai alkalmazását rendkívül fontosnak tartjuk. Általában is igaz, hogy adott témakörön belül egyes feladatokat - ha lehetséges - érdemes egy- vagy többszemélyes játék “köntösébe csomagolva” tálalni. A diákok számára a játék mindig új kihívást jelent. A hagyományos feladat friss, játékos, újszerű megfogalmazása “környezetváltozással” jár; a diákjaink lényegesen lelkesebben, motiváltabban s gyakran eredményesebben teszik próbára képességeiket. A cikkben szereplő játékok számítógépes játékokként is bevezethetők és elemezhetők. Feltétlenül érdemes a játékok némelyikét (talán többségét is) a hagyományos matematikai tanulmányozás mellett számítógépes szimulációként futtatni. A véletlenszerű folyamatok szimulálására kiváló segédeszköz a számítógép. A diák egyik leghatékonyabb tanulási módja a játék; manapság pedig ebben a témakörben (valószínűségszámítási, statisztika kísérletek, szimulációk) a számítógép gyakorlatilag nem nélkülözhető. A diákok szeretnek a számítógéppel játszani, nem kell őket különösebben motiválni, hogy leüljenek a gép elé; ugyanakkor a játszva-tanulás sokkal érdekesebb, élményszerűbb, plasztikusabb (alkalmanként maradandóbb is) a hagyományos oktatásnál. A játékok programjai viszonylag kis programozói rutinnal, házilag is elkészíthetők. (Általában a diákokra bízhatjuk a megírásukat; majdnem mindig találunk erre alkalmas tanulót az osztályban.) Egy-két fejezet végén megemlítünk néhány alkalmazási-feldolgozási lehetőséget. Ezek természetesen csak minták, hiszen az esetleges programok számtalan további variációja képzelhető el. A 9. fejezetben a számítógéppel támogatott problémamegoldásra mutatunk néhány példát. Itt a feladatok javasolt feldolgozási módja a következő:
  • gépi szimuláció (sok-sok játék futtatása);
  • sejtések, becslések, a diákok tippjei (erre a részre mindenképpen szánjunk időt; rendkívül tanulságos tapasztalatok gyűjthetők);
  • a játék matematikai modellezése;
  • ahol szakmailag indokolt és lehetséges, a játék matematikai elemzése.

Köszönetnyilvánítás:

Ennek a cikknek az alapjait elsősorban a diákokkal végzett közös szakköri feldolgozó munka jelenti. Merítettem a Módszertani Lapok - Matematika c. folyóiratban megjelent írásaim, valamint a 90-es évek elején a pécsi Vándorgyűlésen, továbbá a váci és balatonberényi előadásokon elhangzottakból is. Külön szeretnék köszönetet mondani

  • Kőváry Károly matematika-tanáromnak, mindannyiunk által szeretett Kavicsnak, aki a témát középiskolás koromban megismertette velem;
  • valamint Surányi László kollégámnak, akitől nagyon sokat tanultam.

Felhasznált és javasolt irodalom:

[1] Bognárné - Nemetz - Tusnády: Ismerkedés a véletlennel (Tankönyvkiadó, 1980)

[2] Erben P. - Orosz Gy.: Matematika és informatika I-III, KOMA, Fazekas M. OKS Alapítvány, 2004-2005.

[3] Hraskó A. szerk.: Új matematikai mozaik, Typotex, 2002

[4] Kemeny - Snell - Thompson: A modern matematika alapjai (Műszaki, 1971)

[5] Közös nevezőnk a matematika, Kőszeg, 2001, Jakab Tamás cikke

[6] Nemetz Tibor: Valószínűségszámítás (Tankönyvkiadó, 1986)

[7] Nemetz -Wintsche: Valószínűségszámítás és statisztika mindenkinek (Polygon, 1999)

[8] Szevasztyanov - Csisztyakov - Zubkov: Valószínűségelméleti feladatok (Tankönyvkiadó, 1987)

[9] Székely J. Gábor: Paradoxonok a véletlen matematikájában (Műszaki, 1982)

[10] Élet és Tudomány LIII. évfolyam 12-17. számok, Móri Tamás cikkei

[11] A Fazekas Mihály Gimnázium honlapján található szakanyagok (www.fazekas.hu)

[12] Középiskolai Matematikai Lapok évfolyamai

[13] Módszertani Lapok - Matematika évfolyamai

[14] Orosz Gyula: Válogatás külföldi nemzeti matematikaversenyek feladataiból (www.fazekas.hu)

1. Véges sztochasztikus (valószínűségi) folyamatok

A görög ’sztochosz’ szó egyik jelentése ’sejtés’; így a fenti elrettentő cím valójában egyszerűen csak olyan kísérletsorozatokat (eseménysorozatokat) jelöl, amelyekben a kísérletek lehetséges kimenetelei véletlen tényezőktől függnek. A folyamat végessége úgy értendő, hogy a továbbiakban csak olyan eseményrendszereket vizsgálunk, amelyekben a kísérletek száma és az egyes kísérletek kimenetelei (az elemi események) egyaránt véges számúak. A folyamatok egészével kapcsolatos kijelentéseket teszünk, a célunk pedig az lesz, hogy ezen kijelentések valószínűségeit határozzuk meg. Például: egy pénzdarabot többször feldobva megkérdezhetjük, mi annak a valószínűsége, hogy a fejek és írások száma megegyezik; vagy hogy a dobások adott százalékában fej lett az eredmény és így tovább.

A folyamat egészéhez kell tehát egy valószínűségi mértéket hozzárendelnünk; nézzünk erre egy konkrét példát.

A fenti ábrán két kísérletből álló sorozat folyamatábrája látható.

Az összes kísérlet lehetséges kimenetelei {A, B, C, D, E}; nem számítottuk ide az S kezdőhelyzetet. Az ábra alapján az első kísérlet eredménye vagy A, vagy B lehet. Pa-val jelöltük annak a valószínűségét, hogy az első kísérlet eredménye A, Pb-vel pedig azt, hogy az első kísérlet eredménye B.

Nézzük most a második kísérletet! Ha az első kísérlet eredménye A, akkor a második kísérlet lehetőségeinek halmaza már csak {C, A}-ra szűkült le. Az ábrán Pac-vel jelöltük annak a valószínűségét, hogy a második kísérlet eredménye C, feltéve, hogy az elsőé A. Ennek megfelelően értelmezzük a Paa, Pbd, … , Pbe valószínűségeket is.

Ha hangsúlyozni kívánjuk a kísérletsorozat folyamat-jellegét, akkor az S, A, B, … , E kimeneteleket nevezhetjük állapotoknak, a Pa, Pb, … , Pbe értékeket átmeneti valószínűségeknek, a folyamatábrát pedig átmenetdiagramnak.

A két kísérlet lehetséges kimenetelei az ábrán látható irányított fagráf S-ből induló egyes ágai, ezeken az ágakon definiáljuk a valószínűségi mértéket.

Mekkora valószínűséggel lesz a második kísérlet eredménye C? Ez akkor következik be, ha az első kísérlet eredménye A (ennek Pa a valószínűsége), és a második kísérlet eredménye C (ennek Pac a valószínűsége). Alkalmazhatjuk a valószínűségekre a szorzási szabályt, így a C kísérlet P(C) = PaPac valószínűséggel következik be. Hasonlóan P(D) = PbPbd, P(E) = PbPbe . Végül a második kísérletre az A eredményt kétféleképpen kaphatjuk: vagy rendre A, A következik be (ennek valószínűsége PaPaa ), vagy B, A (ennek valószínűsége Pb Pba ). Az összeadási szabály miatt P(A) = Pa Paa + PbPba .

Ezzel a módszerrel (amikor tehát az egyes ágakhoz tartozó valószínűségek szorzatával súlyozzuk az utakat) megállapíthatjuk a fa összes irányított útjához tartozó valószínűségeket.

Az egyes ágakhoz rendelt számok elemi eseményekhez rendelt valószínűségek, így a Pa, Pb, … , Pbe rendelkeznek néhány tulajdonsággal:

(1) Pa, Pb, … , Pbe pozitívak;

(2) Pa + Pb = 1;

(3) Pac + Paa = 1;

(4) Pbd + Pba + Pbe = 1.

(Megjegyezzük, hogy (1)-ben nem érdemes megengednünk a 0 értéket.

A 0 valószínűségű esemény nincs hatással a folyamat egészére, nem módosítja az egyes ágakon definiált valószínűségi mértéket; megállapodhatunk tehát abban, hogy ha valamelyik esemény 0 valószínűségű, akkor nem soroljuk fel a gráfban.)

A fenti alaptulajdonságokon kívül a sztochasztikus folyamatok témakörében általában nem teszünk fel egyéb megszorításokat. Például az egyes valószínűségek függhetnek az előző (vagy azokat megelőző) kísérletek eredményeitől, vagy akár az is lehetséges, hogy értékük nem független az időtől és így tovább. Hogy az egyes valószínűségeknek konkrétan milyen jellemzőik vannak, azt mindig az általunk alkalmazott modell, illetve annak pontossági igénye dönti el.

Például a legtöbb matematikai modellben ha feldobunk egy érmét, akkor közelítőleg 0,5 - 0,5 valószínűséggel kapunk fejet vagy írást. Ez az érték nyilván csak (jó) közelítés, hiszen szabályos érme nem létezik. „Fizikus szemmel nézve” a leeső érme az ütközés miatt deformálódik, így a fejek és írások előfordulásának a valószínűsége minden dobás után megváltozik. Sőt, ha fejet vagy írást dobunk, akkor más-más a deformáció mértéke, így az újabb dobás esetén nemcsak az előző dobás ténye befolyásolja az eredményt, hanem az is, hogy mi volt az előző dobás eredménye. A sort folytathatnánk; de azért azt is megemlíthetjük, hogy „matematikus szemmel nézve” az elméleti 0,5 értéktől vett eltérés általában olyan csekély, hogy gyakorlatilag állandó értéknek vehető, s hasonlóan azt is feltehetjük, hogy minden egyes kísérlet független az előzőek eredményétől.

A továbbiakban olyan kísérletsorozatokat vizsgálunk, amelyekben az egyes kimenetelek valószínűségei csak a közvetlenül előttük álló kísérletek eredményétől függnek. Ebben a modellben ha tudjuk, hogy az eseménysorozat milyen kezdőállapotból indul, és ismerjük az egyes állapotok lehetséges kimeneteleit, valamint az ezekhez tartozó átmeneti valószínűségeket, akkor kiszámíthatjuk az eseménysorozat fa-mértékét. Az ilyen eseménysorozatokat nevezzük Markov-láncoknak (A. A. Markov orosz matematikus, 1856 - 1922).

A fenti példa is egy {A, B, C, D, E} kimenetelű Markov-lánc. Az új fogalmat természetesen konkrét példákon, alkalmazásokon keresztül lehet igazán megérteni, úgyhogy a következő fejezet anyagának feldolgozása közben visszautalunk ezen fejezet elméleti tartalmára.

2. Sorsolások visszatevéssel

Néhány konkrét feladat segítségével vezetjük be a Markov-láncok fogalmát és a hozzájuk kapcsolódó megoldási módszereket, tipikus eljárásokat. Ahol lehet, több megoldást is adunk; így lehetőségünk nyílik ezek szakmai-módszertani összehasonlítására.

A következő 2.1. - 2.4. játékokban ketten játszanak egymás ellen. A kezdő játékost jelöljük A-val, a másodikat B-vel.

2.1. feladat:Egy urnában k darab kék és p darab piros golyó van (k + p = n). Ketten felváltva húznak véletlenszerűen egy-egy golyót úgy, hogy miután megnézték a golyó színét, visszateszik az urnába. Az a játékos győz, aki először húz piros golyót. Mekkora eséllyel nyer A, illetve B?
Első megoldás (mértani sor): Jelentse P(i) az i esemény valószínűségét. Ekkor P( A nyer) és P( B nyer) a kérdés.P(A nyer) = P(A nyer vagy az első, vagy a harmadik, vagy az ötödik stb. lépésben (és közben B nem nyer)). Alkalmazhatjuk az összeadási és szorzási szabályt, ennek segítségével formailag a  egyenletet kapjuk. A végtelen mértani sor összege , tehát az A játékos    valószínűséggel nyer. Második megoldás(Markov-láncok): Az előző fejezet alapján megadhatjuk a probléma folyamatábráját:
Hogyan kaptuk ezt az ábrát? S jelenti a startállapotot, amikor A húz. Az A játékos vagy piros golyót húz  valószínűséggel, amikor is eljutunk az ábrán A-val jelölt állapotba (ekkor A győzött), vagy kék golyót húz  valószínűséggel, ekkor jutunk a C állapotba. Innen folytatva megint két eset lehetséges: vagy piros golyót húz B (ekkor a B állapotba jutunk, amikor is B győz), vagy kék golyót (D állapotba jutunk - a játék folytatódik).Ezzel a gondolatmenettel a gráf végtelen hosszú lenne. Észrevehetjük azonban, hogy a játék szempontjából az S és a D állapot nem különbözik lényegesen egymástól: mindkettőben a kezdő A játékos következik húzásra D-ben úgy, “mintha eddig nem történt volna semmi a játékban”. Alkalmazhatjuk tehát a D º S egyszerűsítést (összevonást), amellyel a lánc végessé tehető.Az ábrán feltüntettük az egyes ágakhoz rendelt átmeneti valószínűségeket. Ezek segítségével az előző fejezetben leírt módon meghatározhatjuk a fagráf egyes útjaihoz tartozó valószínűségeket. Legyen s annak a valószínűsége, hogy A nyer az S állapotból, hasonlóan legyen P(A nyer C-ből) = c. Ekkor az ábra alapján felírható egyenletrendszer:Az egyenletek az összeadási és szorzási szabály egyszerű alkalmazásai. (1) azt jelenti, hogy A az S állapotból vagy  valószínűséggel piros golyót húz, tehát rögtön (1 valószínűséggel) nyer, vagy  valószínűséggel kék golyót húz, és a továbbiakban c valószínűséggel nyer, a C állapotból folytatva a játékot. Hasonlóan (2) matematikai tartalma: a B játékos a C állapotból vagy  valószínűséggel piros golyót húz, tehát rögtön veszít A; vagy  valószínűséggel kék golyót húz, amikor is eljutunk a D állapotba, és a továbbiakban s valószínűséggel nyer A a Dº S állapotból.Az egyenletrendszer megoldása (Mellékeredmény: )
Megjegyzések:1. A kapott kifejezés nem szimmetrikus, k < n miatt s mindig nagyobb, mint 0,5; vagyis a kezdő játékosnak mindig előnyös ez a sorsolás. 2. A játékban a döntetlen valószínűsége , ami nullához tart, ha N tart végtelenhez (ez egyébként a cikkben tárgyalt legtöbb játékra igaz lesz). Így a kezdőállapotban B győzelmének a valószínűsége 1 – P(A nyer) = (1 – s) = . Ez az érték természetesen megegyezik az egyenletrendszer megoldásakor kapott P(C) = c értékkel, hiszen az S állapotban A, valamint a C állapotban B szerepe szimmetrikus. Ez utóbbi észrevétel segítségével egy harmadik típusmegoldást is adhatunk.
Harmadik megoldás („logikai rekurzió”): Mivel a döntetlen valószínűsége 0, ha az A játékos s valószínűséggel nyer a kiindulási állapotból, akkor innen a B játékos nyerési esélye (1 – s). Ekkor vagy  valószínűséggel A nyer, vagy  valószínűséggel olyan állapotba kerül a játék, amelyet úgy tekinthetünk, mintha B lenne a kezdő egy most induló játékban. Tehát innen már B nyer s valószínűséggel, A nyerési esélye pedig ekkor (1 – s). Az ez alapján felírható egyenlet ennek megoldása

Ezt a módszert – amelyet házi használatra „logikai rekurziónak” neveztünk el – a későbbiekben is alkalmazni fogjuk. Lényege, hogy valamely változóra önmagával hivatkozunk. A fenti egyenletben a hivatkozás közvetlenül történt; később esetleg előfordulhat, hogy a hivatkozás több lépés mélységű lesz.

Például a k = p = 1 (n = 2) választással az érmedobálási modellt kapjuk. Vagyis ha két játékos felváltva egy szabályos pénzérmét dobál, s az győz, akinek először sikerül fejet dobnia, akkor az első játékos , a második játékos pedig  valószínűséggel nyer.
2.2. feladat: Két játékos felváltva dob fel egy dobókockát. Az a játékos győz, aki először tud hatost dobni. Mekkora valószínűséggel nyernek az egyes játékosok?
Megoldás: A p = 1, k = 5 (n = 6) választással a 2.1. feladat speciális esetét kapjuk, tehát s =  valószínűséggel győz A,  valószínűséggel pedig B.
2.3. feladat: A 2.1. játékot annyiban módosítjuk, hogy az A játékos győzelméhez a piros golyót kétszer kell kihúznia, míg B-nek továbbra is elég egy piros húzás a győzelemhez. Mekkora eséllyel nyer most A, illetve B?
Megoldás: Készítsük el a játék folyamatábráját!
Most is sikerül egyszerűsítéseket végeznünk, fel tudjuk használni a 2.1. feladat eredményét.A startállapotból  valószínűséggel a C állapotba jutunk (ekkor A már húzott egy piros golyót). Innen vagy győz B  valószínűséggel, vagy  valószínűséggel az S1 állapotba jut a játék, ami megegyezik a 2.1. játék kezdőállapotával; ugyanis ekkor A vagy B közül az a játékos győz, aki előbb húz piros golyót.Ha a startállapotból  valószínűséggel kék golyót húz A, akkor a D állapotba jutunk. Innen vagy győz B, vagy - kék golyó húzása esetén - minden kezdődik elölről, az S kezdőállapotba kerül a játék. Jelöljük s-sel az A játékos győzelmének a valószínűségét. A 2.1. feladat jelöléseit és eredményét felhasználva a felírható egyenletrendszer: Az egyenletrendszer megoldása  ekkora valószínűséggel győz a kezdő játékos. A következő feladatban a folyamatok egy másik jellemzőjét, az átlagos hosszukat határozzuk meg.
2.4. feladat: Átlagosan hány húzásig tart a 2.1. játék?
Első megoldási lehetőség: A húzások számának várható értéke a kérdés. A játék  valószínűséggel 1 lépésben véget ér a piros golyó húzásával. 2 lépés hosszú akkor lehet a játék, ha előbb egy kék, majd egy piros golyót húzunk; ennek a valószínűsége 3 lépés hosszú a játék, ha 2 kék és 1 piros golyó húzása történik, ennek a valószínűsége Általában a játék N lépésben ér véget, ha (N – 1) kék és 1 piros golyó húzása történik, s ennek a valószínűsége  A várható érték kiszámolása ezek után úgy történhet, hogy az egyes valószínűségeket szorozzuk a hozzájuk tartozó húzásszámokkal, s az így kapott tagokat összegezzük. A definíciót alkalmazva az átlagos L húzásszám kiszámításához tehát az sor összegét kellene meghatározni.Második megoldás:A Markov-láncok segítségével elkerüljük a várható érték fogalmát. A játék folyamatábrája alapján egyenletrendszert írhatunk fel a játék befejezésig szükséges húzások átlagos számára.
Jelentse Li a befejezésig szükséges húzások átlagos számát, ha a játék az i állapotban van. Ekkor felírható az alábbi egyenletrendszer:

Az (1) egyenlet úgy értelmezhető, hogy a kezdőállapotból kiindulva a befejezésig szükséges húzások átlagos számát a következő módon kaphatjuk meg: vagy  valószínűséggel húzunk összesen egy golyót, vagy  valószínűséggel a C állapotba kerülünk; vagyis egyet húzunk, plusz még annyi húzás történik, amennyit a C állapotból átlagosan végzünk a továbbiakban a játék folyamán (ezt jelöltük Lc-vel).A (2) egyenlet értelmezése: a C állapotból kiindulva a befejezésig szükséges húzások átlagos száma vagy  valószínűséggel összesen egy golyó; vagy  valószínűséggel egyet húzunk, plusz még annyi húzás történik, amennyit a továbbiakban az S állapotból átlagosan végzünk (ezt jelöltük LS-sel).Az (1) egyenlet átalakítás után formailag az LS =  alakba is írható, jelentése ekkor hasonlóan értelmezhető: a kezdőállapotból mindig húzunk 1-et, valamint  valószínűséggel még annyi további húzás történik, amennyi átlagosan a C állapotból szükséges a játék végéig. (Hasonlóan alakítható át (2) is.)Az egyenletrendszer megoldása LS = , átlagosan ennyi húzást végzünk egy játék alatt.
Megjegyzések: 1. Érdemes tudatosítani, hogy megkaptuk az első megoldás végtelen sorának összegét. 2. Az érmedobálási modellben (k = p = 1, n = 2) az átlagos dobásszám 2; a dobókocka-modellben (k = 5, p = 1, n = 6) az átlagos dobásszám 6. 3. Határozzuk meg LC-t: az  egyenletből  vagyis LC = LS. Hát persze: a C állapot az átlagos lépésszám tekintetében egyenértékű S-sel, hiszen a játék „nem tudja”, hogy az A vagy a B játékos következik soron.
Harmadik megoldás („logikai rekurzió”): Ha a megoldás első lépéseként felismerjük az LC = LS kapcsolatot, közvetlen összefüggést írhatunk fel az L átlagos lépésszámra: Láthatjuk, hogy nemcsak a valószínűségekre ( 2.1. 3. megjegyzés), hanem a lépésszámokra is felírhatunk olyan egyenletet, amelyben a változóra önmagával hivatkozunk.

Ha a diákok nem találkoztak még a várható érték fogalmával, problémát jelenthet számukra, hogy az összeadási és szorzási szabályt valószínűségekre mondtuk ki, ezekben az egyenletekben pedig a lépésszámok (tehát más “dimenziójú” mennyiségek) szerepelnek. Itt tulajdonképpen a véletlen számok azon tulajdonságát használjuk fel, hogy összegük várható értéke megegyezik a várható értékeik összegével. Tapasztalataink szerint ez a nehéz gondolat szemléletesen világos a diákok számára; a mély tétel bizonyítása megtalálható például a [6] tankönyvben.

A további feladatok megoldása során igyekszünk elkerülni a várható érték fogalmát, illetve a várható érték definíció szerinti kiszámolását; s erre hatékonyan alkalmazhatjuk a fenti „trükköt”, az egyenletrendszer módszerét. Mivel tehát ezt a módszert a későbbiekben is gyakran használjuk, fontos, hogy a diákok valóban megértsék, s ne csak automatikusan alkalmazzák.

2.5. feladat: Átlagosan hány húzásig tart a 2.3. játék?
Megoldás: Az előző feladat megoldásához hasonlóan a folyamatábra alapján felírjuk a lépésszámokra (a húzások számára) vonatkozó egyenletrendszert.
Jelentse Li a befejezésig szükséges húzások átlagos számát, ha a játék az i állapotban van (továbbá L1 jelenti az S1 állapotból szükséges húzások számát). Ekkor:Az egyenletek rendezett alakja:Felhasználhatjuk az előző feladat megoldása alapján, hogy (2)-ből  adódik. Így van: ha már történt egy piros húzás (C állapot), akkor a továbbiakban az a játékos nyer, aki először húz piros golyót; s ehhez átlagosan L1 húzásra van szükség.(1)-ből és (3)-ból Innen látható, hogy a lépésszám nagyobb, mint L1.A konkrét p = 1, k = 1 (n = 2) értékekkel (érmedobálás)  a dobókockának megfelelő p = 1, k = 5 (n = 6) értékekkel

A Markov-láncok módszere (összefoglalás)

Tekintsünk egy sztochasztikus folyamatot, melyben a kísérletek lehetséges kimeneteleit, az egyes állapotokat a0, a1, a2, … módon jelöljük. Ha a folyamat diszkrét időben változik, az ai állapotok száma véges, és az egyes állapotok bekövetkezésének a valószínűségei csak a közvetlenül előttük álló állapotoktól függnek, akkor a folyamatot Markov-láncnak nevezzük.

Tegyük fel, hogy az a0 állapotból p01 valószínűséggel az a1 állapotba, innen p12 valószínűséggel az a2 vagy p10 valószínűséggel vissza az a0 állapotba jutunk, az a2 állapotból p23 valószínűséggel az a3 állapotba stb. A folyamatot átmenetdiagrammal ábrázolhatjuk:

Ha most ismerjük az a0 kezdőállapotot és a pij átmeneti valószínűségeket, akkor az összes további ai esemény valószínűsége meghatározható, sőt a folyamat átlagos hosszáról is információkat kaphatunk. (Elképzelhető, hogy a folyamat, a vizsgált kísérletsorozat végtelen hosszú. Mivel azonban csak véges sok állapotot engedünk meg, maga a lánc mindig végessé tehető.)

A megoldási technikák:

A Markov-láncok segítségével bizonyos típusú feladatok megoldása egyszerűen tárgyalható. Összefoglaljuk a megoldás lépéseit:

  1. megrajzoljuk az eseménysorozathoz tartozó folyamatábrát;
  2. az eseményrendszer ekvivalens állapotait összevonjuk;
  3. elkészítjük az egyszerűsített folyamatábrát;
  4. az átmeneti valószínűségek segítségével egyenletrendszert állítunk fel (ezekben az ai események bekövetkezésének a valószínűsége, illetve a folyamat befejezéséhez szükséges átlagos lépésszámok szerepelnek);
  5. az egyenletrendszer megoldása adja meg az egyes állapotok valószínűségét vagy a folyamat átlagos hosszát.

(Az egyenletrendszerek alkalmazása mellett dolgozhatunk rekurzív sorozatokkal vagy mátrixokkal is, mint később látni fogjuk.)

Az átmeneti valószínűségek megadása többféleképpen történhet.

Az eddig használt (irányított) fagráf mellett alkalmazhatjuk az alábbi folyamatábra-típust is:

 

Ekkor úgy ábrázolhatjuk a folyamatot, hogy a1-ből a p10 valószínűséghez tartozó élt egyszerűen visszanyilazzuk a0-ba. Ekkor nem fagráfot kapunk, de a korábbihoz hasonló módon határozhatjuk meg az egyes utakhoz tartozó valószínűségeket.

Az átmeneti valószínűségeket megadhatjuk egy mátrix segítségével is. Például három állapot esetén a mátrix  alakú. Itt az i. sor j. eleme, pij jelenti annak a valószínűségét, hogy az i. állapotból a j. állapotba kerül a folyamat. A 2.1. feladat diagramjának például az alábbi mátrix felel meg:

  S A C B
S 0 p/n k/n 0
A 0 0 0 0
C k/n 0 0 p/n
B 0 0 0 0

A mátrix-reprezentáció alkalmazásával, erősebb matematikai segédeszközöket igénybe véve, természetesen komolyabb eredményeket is elérhetünk (lásd például a [4] szakirodalomban).

2.6. feladat: Végezzük el a 2.1. játék általános vizsgálatát (kétszemélyes visszatevéses sorsolás állandó P valószínűséggel).
Az alábbi táblázat konkrét értékekre mutatja a 2.1, 2.4. feladatok eredményeit.Az első két sorban a piros és kék golyók számát, a harmadikban ezek összegét tüntettük fel. A negyedik sorban P-vel jelöltük annak a valószínűségét, hogy piros golyót húzunk ; az ötödik sorban A nyerési esélye, a hatodikban pedig az átlagos lépésszám található.
p 1 1 1 1 1 1 1
k 1 2 3 4 5 9 99
n 2 3 4 5 6 10 100
P 0,5 0,333333 0,25 0,2 0,166667 0,1 0,01
P(A nyer) 0,666667 0,6 0,571429 0,555556 0,545455 0,526316 0,502513
L 2 3 4 5 6 10 100
A játékban valójában a piros és kék golyók szerepe csak annyi, hogy segítségükkel adjuk meg a játékra jellemző  valószínűséget. Ezzel a jellemzővel kifejezve a kezdő játékos s nyerési esélyére az s = P + (1 – P)(1 – s) rekurziót írhatjuk fel, melynek megoldása  (s amely természetesen összhangban van a korábban kapott  értékkel). Alkalmazzunk hasonló rekurziót az LS átlagos lépésszámra is: LS = 1 + (1 – P)LS, innen  (A kapott lépésszám megegyezik a korábban kapott  eredménnyel.)
Megjegyzés:Általában is megmutatható, hogy ha egy esemény lépésenként 0 < P valószínűséggel következik be, akkor

a) 1 valószínűséggel véges sok lépésben következik be;

b) és első bekövetkezéséhez átlagosan  számú kísérletre van szükség. (Ez éppen a P paraméterű geometriai eloszlás várható értéke.)

Ugyanis a komplementer valószínűségre a Q = 1 – P jelölést használva

a) annak a valószínűsége, hogy n számú kísérlet alatt nem következik be az esemény, Qn, s ez tetszőlegesen kicsi lesz n növekedtével;

b) a kísérletek várható száma pedig (a végtelen mértani sor összegképletét felhasználva)
P + 2QP + 3Q2P + … = P(1 + Q + Q2 + …) + (Q + Q2 + Q3 + …) + (Q2 + Q3 + Q4 + …) + …  

2.7. feladat: Végezzük el a 2.3. és 2.5. játék általános vizsgálatát (kétszemélyes visszatevéses sorsolás állandó P valószínűséggel; a kezdőnek kétszer kell piros golyót húznia).

A jellemző  valószínűség segítségével átalakítjuk az  eredményt. így P( A nyer) = s = Az átlagos húzásszámra Az alábbi táblázatban néhány konkrét esetet tüntettünk fel.

p 1 1 1 1 1 1 2 3 2 3 9
k 1 2 3 4 5 9 3 4 1 1 1
n 2 3 4 5 6 10 5 7 3 4 10
 
P 0,500 0,333 0,250 0,200 0,167 0,100 0,400 0,429 0,667 0,750 0,900
 
A nyer 0,222 0,240 0,245 0,247 0,248 0,249 0,234 0,231 0,188 0,160 0,083
 
L 3,333 4,800 6,286 7,778 9,273 15,263 4,063 3,818 2,625 2,400 2,121
Megjegyzés:Az A nyerési esélyét megadó s = s(P) függvény deriváltja A függvény szigorúan monoton csökkenő a ]0; 1[ intervallumon, határértéke s(0) = 0,25, s(1) = 0. Tehát A nyerési esélye a P = 0 értékhez közeledve a legnagyobb; számára az a szerencsés, ha a piros golyók számához képest minél több a kék golyó.

Az átlagos lépésszámokat megadó  függvény deriváltja  ha P ]0; 1[. A függvény szigorúan monoton csökkenő, határértéke P = 0-ban + ¥, a P = 1 helyen pedig L = 2. Tehát a játék annál tovább tart, minél nagyobb a kék golyók aránya a piros golyókhoz képest.

2.8. (kitűzött) feladat:Megvizsgálhatjuk a probléma következő módosításait, illetve általánosításait (ezekre a későbbiekben még visszatérünk):

a) Módosíthatjuk a nyerési valószínűségeket. Például A nyer p, B nyer q = 1 – p valószínűséggel húzásonként.

b) Adott golyóeloszlás esetén az A játékosnak x-szer, a B játékosnak (x + k)-szor kell kihúznia a piros golyót, hogy nyerjen.

c)Ha adott x és k, akkor közelítőleg milyen golyóeloszlás esetén lesz igazságos a játék?

d) További általánosítási lehetőség, ha R valószínűséggel „nem történik semmi”: ekkor p + q + R = 1.

e) Az eredeti játékokat és a fenti általánosításukat kettőnél több személy is játszhatja.

A számítógépes támogatást akkor érdemes igénybe venni, ha a feladat modellezése vagy matematikai tárgyalása túlságosan nehéznek bizonyulna. A fenti általánosítások megoldásai például nem tartalmaznak elvi újdonságot, csak a paraméterek növekedése miatt bonyolultabbak lesznek az állapotdiagramok, és a belőlük következő egyenletrendszerek.

3. Érmedobálások

Az alábbiakban egyszerű kétszemélyes érmedobálásos játékokat vizsgálunk meg. A 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, például fej, fej, írá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 továbbiakban a fej dobásokat F, az írás dobásokat I betűvel jelöljük.

Könnyen eldönthető játékok

A témakör elején feltétlenül érdemes néhány könnyen eldönthető játékot megvizsgálni; ezekben nincs szükség a Markov-láncokkal kapcsolatban eddig alkalmazott megoldási technikákra. Az alábbiakban csak példákat mutatunk ezekre az egyszerű esetekre.

1 hosszú sorozatok esetén:

Ha az A játékos például az F, a B pedig az I sorozatot választja, akkor a játék nem túl izgalmas: biztosan véget ér 1 lépésben, valamelyik játékos győzelmével. A játék igazságos: mindkét játékos  valószínűséggel nyer.

2 hosszú sorozatok esetén:

Ha az A játékos tippje az FF, a B tippje pedig az FI sorozat, akkor egy játék lefolyása lehet például az IIFF, illetve IFI sorozat. (Az első játékot A nyerte a 4. lépésben; a másodikat B a 3. lépésben.)

Könnyen látható, hogy ez a játék is igazságos. Ha ugyanis kezdetben néhány I-t dobnak, akkor tulajdonképpen „nem történt semmi”, olyan, mintha csak ezután kezdődne a játék. Ha pedig a kezdeti I dobások után bármikor F dobás történik, akkor a következő dobás után a játék véget ér, FF vagy FI befejezéssel; s a győzelemre mindkét játékosnak egyenlő esélye van.

(A 3.4. feladatban áttekintjük azokat a játékokat, amelyekben A és B kettő hosszúságú (különböző) célsorozatot választ.)

3 hosszú sorozatok esetén is könnyen adhatunk példát igazságos játékokra. Nyilván ilyen lehet az A: FFF, B: FFI; vagy az A: FFF, B: III játék.

Érdemes olyan 2 vagy 3 hosszú játékot is elemezni, amely nem igazságos, s amely könnyen (egyszerű megfontolásokkal) igazolható. A továbbiakban is találhatók ilyen feladatok (3.3., 3.4.), bár a céljaink szerint nehezebb (eszközigényesebb) játékokat vizsgálunk meg

3.1. feladat (KöMaL P.209.):Két játékos egy szabályos érmét többször feldob egymás után úgy, hogy mindig csak a legutolsó három dobás eredményét veszik figyelembe. Az A játékos akkor győz, ha az utolsó három dobás FFF volt, B pedig akkor, ha az utolsó három dobás FIF volt. Melyik félnek kedvező a játék?

(Például az FIIFFF játékot A nyerte a 6. lépésben; az IIIFFIF játékot pedig B a 7. lépésben.)

Megoldás: A játék kiértékelésekor a lehetséges nyolc állapot közül egyesek összevonhatók, mint az alábbi átmenetdiagram mutatja:

Hogyan keletkezett ez a folyamatábra?
Tekintsük például az IF állapotot, vagyis amikor már egy I és egy F dobás történt. Ha a következő dobás F, a játék szempontjából a kapott IFF sorozatnak csak az utolsó két tagja vehető figyelembe; ekkor kapjuk az FF állapotot (az ábrán E-vel jelöltük). Ugyanígy az IFI sorozat megfelel az FI állapotnak (az ábrán D); vagyis az IF állapot ekvivalens az F állapottal (az ábrán C).
Induljunk ki tehát a kezdő S állapotból. Ha az első dobás írás, akkor a játék szempontjából semmi sem történt: a dobásból sem A-nak, sem B-nek nincs haszna, kezdődik minden elölről (S állapot). Ha az első dobás fej, a második dobás kétféle lehet, így eljutunk a D, illetve E állapotokba.
Ezután észrevehetjük, hogy az FII állapot megegyezik az S kezdőállapottal, valamint az FI és FFI állapotok is ekvivalensek (D). Ezzel a gondolatmenettel sikerült a nyolc lehetséges állapot számát négyre redukálnunk. A kezdőállapottal együtt négy ismeretlenünk van, szükségünk van tehát négy egyenletre.
Az érme szabályos, így az állapotok közötti átmeneti valószínűségek értéke . Ahogy a korábbi játékokban, most is jelöljük rendre s, c, d, e-vel annak a valószínűségét, amellyel az A játékos nyer az S, C, D, E állapotokból indulva. A folyamatábra alapján felírható egyenletrendszer:

Az egyenletrendszer megoldása  tehát az A játékos  valószínűséggel nyer. A további értékek:

Megjegyzések:
  1. Most is igaz, és a későbbi érmedobálásos feladatokban is teljesül, hogy a játék 1 valószínűséggel véget ér. A döntetlen 0 valószínűségű, így ebben a játékban a B játékos  valószínűséggel nyer.
  2. A folyamatábra nem szimmetrikus, számolás nélkül is észrevehetjük, hogy a játék B-nek előnyös. Az (1) egyenletből rögtön adódik s = c. A folyamatábrán ez úgy látszik, hogy a baloldali S ág önmagára vezet vissza, a játék szempontjából semleges szerepű, tehát a "tényleges játék" a C állapotban kezdődik. B nagyobb nyerési esélye pedig abból következik, hogy a C állapot négy kimenetele közül egyben-egyben A és B nyer, a harmadik ág a semleges S-re vezet, a negyedik viszont (és itt jön B előnye) egy olyan D állapotra, ahonnan vagy rögtön nyerni tud B, vagy az S állapotba jut a játék.
  3. Talán a szimmetria megbontása jobban látható, ha a folyamatábrát fagráf helyett körrel adjuk meg.
  4. Látható, hogy akkor kapnánk szimmetrikus ábrát (akkor lenne igazságos a játék), ha a D ® S átmenet helyett a D ® E átmenet szerepelne.

  5. Mi a későbbiek folyamán általában a fa-diagramot alkalmazzuk. Elképzelhető - mint ebben az esetben is -, hogy a kör-diagram alkalmazása célravezetőbb; tehát a megoldás tervezésénél ezzel a lehetőséggel (módszerrel) is érdemes számolni.
  6. A  értékek mutatják, hogy az FI dobások után igen nehezen tud győzni az A játékos, viszont az FF dobások után már neki előnyös a játék.
3.2. feladat: Átlagosan hány dobásig tart a 3.1. játék?
Megoldás:

Jelöljük Ls-sel azt az átlagos dobásszámot, ameddig tart még a játék az S állapotból kiindulva. (Hasonló a jelentése az Lc, Ld, Le változóknak is.) Az előző fejezet játékaihoz hasonlóan itt is felírhatjuk a lépésszámokra (dobásszámokra) vonatkozó egyenletrendszert:

(Itt például az első egyenlet azt jelenti, hogy az S állapotból indulva egyet dobnak a játékosok, aminek eredményeképpen  valószínűséggel vagy a C, vagy az S állapotba jutunk. Ezekből az állapotokból halad tovább a dobás után a játék, s az ehhez szükséges átlagos dobásszámot éppen Ls-sel, illetve Lc-vel jelöltük.)

Az egyenletrendszer megoldása  tehát egy játék átlagosan 6,8 dobásig tart.

Megjegyzés:A fenti két feladatban alkalmazott megoldási technikával az összes hasonló játék tárgyalható (például tetszőleges hosszú és tetszőleges tartalmú sorozatokat választhatunk).
3.3. feladat:Két játékos egy szabályos érmét többször feldob egymás után úgy, hogy mindig csak a legutolsó három dobás eredményét veszik figyelembe. Az A játékos akkor győz, ha az utolsó három dobás FFF volt. A B játékos szabadon választhat egy saját, három dobás hosszú célsorozatot; B akkor győz, ha az utolsó három dobás az általa választott célsorozattal egyezik meg. Hogyan érdemes B-nek választania?
Megoldás:

Vegyük észre, hogy ha B az IFF sorozatot választja, akkor csak úgy győzhet A, ha az első három dobás FFF. Ugyanis ha a játék folyamán bármikor egy I-t dobnak a játékosok, akkor további FF után B győz, egyébként egy újabb I dobás után az előző I dobással ekvivalens állapotot kapunk. A három kezdeti FFF dobás valószínűsége , vagyis B nyerési esélye , ha az IFF sorozatot választja.

A három hosszú érmedobás-sorozatok folyamatábrájának harmadik szintje legfeljebb nyolc állapotot különböztet meg, melyekből egy biztosan A győzelmét jelenti. B legfeljebb hét állapot elérésekor győzhet, ezért B nyerési esélye legfeljebb , vagyis a megadott IFF sorozat optimális.

Néhány szó a szimmetriáról

A fenti játékokat tekintve világos, hogy az FFF, illetve III sorozatok szimmetrikus szerepűek: ha ezeket választja A és B, akkor mindketten  valószínűséggel nyernek, a játék igazságos. Hasonlót állíthatunk az FFF, illetve FFI sorozatokról is: itt két egymás utáni fej dobásra mindkét játékosnak szüksége van, azután pedig mindketten  valószínűséggel nyernek. Az előző 3.3. feladatban láttuk, hogy FFF és IFF - ebben az értelemben - nem szimmetrikusak. Kérdés, hogy vajon vannak-e más karakterű szimmetrikus sorozatok is?

3.4. feladat:Elemezzük a szimmetria szempontjából azokat a játékokat, amelyekben A és B kettő hosszúságú (különböző) célsorozatot választ! Kinek melyik játék az előnyös?
Megoldás:

A 12 lehetőség közül az A és B játékos szimmetrikus szerepe miatt csak 6-ot kell megvizsgálnunk (legyenek ezek az alábbi táblázat jobb felső háromszögének elemei). Igazságos az FF – II, FF – FI, IF – II játék.

  FF FI IF II
FF 1:1   1:1
FI 1:1    
IF     1:1
II 1:1   1:1

A további három játék vizsgálata:

  1. Az A: FF – B: IF játékban könnyen látható, hogy FF csak az első két dobás folyamán jöhet ki (ha bármikor I-t dobunk, már B nyer). Vagyis az alábbi ábra C, D, E, G állapotai közül három esetben nyer B; a győzelmi valószínűségek aránya A : B = 1 : 3. (Akár a táblázatban, itt is A és B egymáshoz viszonyított győzelmi esélyét jelöltük. Ez alapján tehát P( A nyer) = , P( B nyer) = .)
  2. Az A: FI – B: IF játékot szimmetrikusnak érezzük, s valóban: fej dobás után már csak A, írás kezdés után pedig már csak B nyerhet. ( D-ben A, E-ben B nyer; de C és A, valamint B és G ekvivalens állapotok. Az FI és IF sorozatok egyike sem lehet kitüntetett a másikkal szemben, a lehetséges átbetűzés miatt.)
  3. Végül az A: FI – B: II játék tulajdonképpen megegyezik az elsőnek tárgyalt A: FF – B: IF játékkal, a játékosok fordított szereposztásával és a fej-írás cserével. Tehát A : B = 3 : 1.

Ez alapján a 2 hosszú fej-írás sorozatok nyerési esélytáblázata az alábbi:

  FF FI IF II
FF 1:1 1:3 1:1
FI 1:1 1:1 3:1
IF 3:1 1:1 1:1
II 1:1 1:3 1:1
Megjegyzés: Érdekes, hogy ebben a feladatban a „szimmetria” szót három értelemben is használtuk. Szimmetrikus lehetett az A és B játékosok játékbeli szerepe; szimmetria állt fenn az érme írás és fej oldala között; végül a célsorozatok szimmetriáját vizsgáltuk, ami az igazságossággal, az esélyek egyenlőségével volt kapcsolatban.
3.5. feladat (problémafelvetés): Bebizonyítjuk, hogy a 2 hosszú célsorozatok közül bármely két sorozat „szimmetrikus”; abban az értelemben, hogy bármelyiket is választja A és B, a játék igazságos lesz.
Bizonyítás (hibás):

A szimmetriaviszonyok miatt elég az FF és IF sorozatokat összehasonlítani. Az FF – II játék nyilván igazságos; az II – IF játék is a fentiek miatt; ebből pedig FF – IF igazságossága már adódik.

A táblázatból látjuk, hogy ez nem így van. Hol lehet a hiba a bizonyításban?

Megoldás: Csak azzal lehet a baj, hogy az igazságosság mint reláció nem tranzitív; s ezt a táblázat értékei megerősítik. (Tehát FF – II igazságos játék; II – IF szintén; de ebből nem következik, hogy FF – IF is az.)
Megjegyzés: Ugyanezzel az eljárással a 2-nél hosszabb célsorozatok szimmetriája is „bizonyítható”; hasonló problémákkal bőségesen találkozunk a 10. fejezetben.

További feladatok

3.6. feladat:

Két játékos egy szabályos érmét többször feldob egymás után. Az A játékos akkor győz, ha a fejek száma hárommal több lesz, mint az írások száma; míg B akkor győz, ha az írások száma lesz hárommal több, mint a fejek száma.

Elemezzük a játékot! Mekkora valószínűséggel győz A és B a játék különböző állapotaiban? Mennyi ezekben az állapotokban a játék befejezéséig szükséges dobások átlagos száma?

Megoldás:

Jelölje az i. állapot azt a helyzetet, amikor a fejek és írások különbsége i; pi annak a valószínűségét, amellyel A nyer az i. állapotból, Li pedig azt a dobásszámot, ameddig átlagosan tart a játék az i. állapotból indulva. (Ekkor a 0. állapot a kezdőállapot.) A játék folyamatábrája:

A folyamatábra szimmetriája is mutatja, hogy pS = p0 =  (szabályos érme). Ezt felhasználva, a többi valószínűség meghatározásához felírjuk a valószínűségi egyenleteket:

Ennek megoldása p1 =  és p2 = . A p1 =  például azt jelenti, hogy ha a dobott fejek száma eggyel nagyobb, mint az írások száma, akkor ebből az állapotból az A játékos  valószínűséggel nyer. Meg lehet mutatni, hogy a játék előbb-utóbb véget ér (pontosabban 1 valószínűséggel; lásd 8.4. feladat), tehát a játékban nem lehet döntetlen. Így szimmetriaokok miatt és

A játék szimmetriája miatt a lépésszámokra teljesül, hogy Li = L–i, ezért a „hagyományos módon” kapjuk az alábbi egyenletrendszert:

Az egyenletrendszer megoldása L2 = 5, L1 = 8, L0 = 9, s ezért L –2 = 5, L –1 = 8.

Megjegyzés:

Vizsgáljuk meg a játék általános esetét!

A játéknak legyen akkor vége, ha a fejek és írások számának különbsége h. Ekkor általában is megmutatható (lásd 6.3. feladat), hogy L0 = h2, vagyis átlagosan h2-szer kell egy szabályos érmét feldobnunk ahhoz, hogy a fejek és írások eltérése (először) h legyen. Ugyanakkor a feladat egyfajta duálisa is bizonyítható (ezt most nem tesszük meg): eszerint ha egy szabályos érmét h2-szer feldobunk, a fejek és írások számának átlagos eltérése arányos lesz h-val.

Érdemes elgondolkodni azon, hogy ez az eredmény mit is jelent azzal kapcsolatban, amit úgy szoktunk nevezni, hogy „a véletlen számok kiegyenlítődési hajlama” (lásd 10.1. feladat).

3.7. feladat:

Két játékos felváltva dobál fel egy szabályos pénzérmét. Az a játékos győz, aki először dob fejet. Vizsgáljuk meg a játékot!

Észrevehető, hogy a 2.1. problémával analóg feladatot kaptunk a p = k = 1, n = 2 paraméterekkel. Az ott adott megoldás alapján a kezdő játékos nyerési esélye  a dobások várható száma pedig  A második játékos természetesen  valószínűséggel győz.

3.8. feladat:

A 3.1. feladatban az A játékos FFF sorozatával szemben nagyobb eséllyel nyert a B játékos FIF sorozata, a nyerési arány A : B = 2 : 3 volt. Módosítsunk B sorozatán úgy, hogy nehezebb dolga legyen; például B akkor nyerjen, ha a FIFI sorozat jön ki eredményül.

a) Mennyivel lett igazságosabb a játék?

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

c) Határozzuk meg, átlagosan hány dobásból kapjuk meg külön-külön az FFF, illetve FIFI sorozatokat!

Megoldás:

A játék folyamatábrája:

Ugyanezt a folyamatábrát megadjuk gráfelméleti körrel is:

a) Az egyes állapotok a következő dobássorozatokkal ekvivalensek: C = F, D = FF, E = FI, G = FIF. Jelentse s, c, d, e, g rendre A győzelmének a valószínűségét az S, C, D, E, G állapotokból; ekkor az ábra alapján felírható egyenletrendszer a következő:

Az egyenletrendszer megoldása  Tehát a módosítás után sem kaptunk igazságos játékot, ez a játék már A-nak előnyös. A nyerési valószínűségek aránya A : B = 5 : 3.

b) A lépésszámokra felírható egyenletrendszer:

Az egyenletrendszer megoldása Tehát a dobások átlagos száma

c) Az FFF célsorozat esetén a folyamatábra és az egyenletrendszer:

Az egyenletrendszer megoldása ( Ls, Lc, Ld) = (14, 12, 8).

Az FIFI célsorozat esetén a folyamatábra és az egyenletrendszer:

Az egyenletrendszer megoldása ( Ls, Lc, Ld, Le) = (20, 18, 16, 10).

Tehát külön-külön az A sorozatnak átlagosan 14, a B-nek 20 dobásra van szüksége; ha pedig a két sorozat együtt vesz részt a játékban, az átlagos dobásszám 8,75.

3.9. (kitűzött) feladat (KöMaL B.3849.) Egy szabályos érmét addig dobálunk, amíg legalább egyszer kapunk fejet is és írást is. Mennyi a dobások számának várható értéke?
3.10. (kitűzött) feladat: Egy érmét hajigálunk. Várhatóan hányszor kell feldobni, hogy a) FF, illetve b) FI jöjjön ki egymás után? (Ez két különböző feladat.)
3.11. (kitűzött) feladat:

Egy érmét addig dobálunk, amíg három egymás utáni dobásban FIF vagy IIF nem adódik.

a) Mennyi a valószínűsége annak, hogy FIF 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 kapjuk meg külön-külön az FIF, illetve az IIF sorozatokat!

3.12. (kitűzött) feladat:

Módosítsuk az előző sorozatokat úgy, hogy egy F dobással mindkettőt megtoldjuk. Tehát: egy érmét addig dobálunk, amíg három egymás utáni dobásban FIFF vagy IIFF nem adódik. Mennyiben változtak meg az egyes nyerési valószínűségek? 

a) Mennyi a valószínűsége annak, hogy FIFF 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 FIFF, illetve az IIFF sorozat!

3.13. (kitűzött) feladat: Három játékos egy szabályos érmét többször feldob egymás után úgy, hogy mindig csak a legutolsó három dobás eredményét veszik figyelembe. Az A játékos akkor győz, ha az utolsó három dobás FIF volt; B akkor, ha az utolsó három dobás FII; végül C akkor, ha az utolsó három dobás FFI volt. Mekkora eséllyel nyernek az egyes játékosok? Átlagosan hány dobásig tart a játék?

Érmedobálások számítógépes támogatással

Több, a feladathoz hasonló számítógépes játék is elképzelhető.

Nézzünk néhány példát, amikor a játékos ellenfele a számítógép (de a játékokat tanulók is játszhatják egymással):

  1. Először a játékos választ egy három hosszúságú érmedobás-sorozatot, majd a gép választ véletlenszerűen egy három hosszúságú sorozatot.
  2. Először a gép választ véletlenszerűen egy három hosszúságú érmedobás-sorozatot, majd a gép sorozata ismeretében a játékos választ egy három hosszúságú sorozatot.
  3. Az előző feladatokat játszhatjuk eltérő hosszúságú sorozatokkal is.
    A fenti feladatokban a kérdés mindig az, hogy hogyan érdemes sorozatot választani.

  4. Először a játékos választ egy három hosszúságú érmedobás-sorozatot, majd a gép választ optimális stratégiával egy három hosszúságú sorozatot.
  5. Ha a játék bizonyos tétre megy, akkor a kérdés az is lehet, hogy milyen stratégiával minimalizálható a veszteség; vagy esetleg nem egyenlő „beugróval” történik a játék.
    A fenti játékokat játszhatja kettőnél több játékos is.

  6. És természetesen az 1 - 5. játékokban mindig tippelhet arra minden néző (mint kívülálló, egymással versengő játékos), hogy ki győz, és hogy hány lépésig tart a játék.

Az ilyen típusú játékok viszonylag könnyen programozhatók (talán az osztályban is van olyan gyerek, aki szívesen ír egy egyszerű játszó programot). Érdemes a könnyebb változatokat megmutatni a diákoknak, s hagyni őket játszani, gyakorolni, tapasztalatot szerezni. A nehezebb játékok (például 4.) önmagukban is érdekes kérdéseket vetnek fel; ezekre a cikk későbbi részeiben megpróbálunk majd válaszolni.

4. Statisztikus golyójátékok

Egy urnában kezdetben különböző színű golyók vannak. Ezek közül véletlenszerűen kiválasztunk egyet, és a követett stratégiától függően kiveszünk vagy beteszünk újabb golyókat az urnába. Ezt a lépést addig folytatjuk, míg a golyók darabszáma, színösszetétele vagy egyéb jellemzője el nem ér egy előre rögzített értéket. A „statisztikus golyójátékok” elnevezést olyan golyómodellek esetén használjuk, amikor az urnában lévő golyók összetétele előírt szabály szerint változik, a húzás tartalmától függően; de a golyók húzása véletlenszerűen történik. A játékokban a golyók eloszlásával kapcsolatos valószínűségi kérdéseket vizsgálunk, például az egyes célállapotok elérésének a valószínűségét, az ide vezető folyamat átlagos hosszát stb.

A 2. fejezetben (visszatevéses sorsolási modell) a golyók színmegoszlása a játék alatt változatlan volt, s így állandó valószínűséggel húztunk azonos színű golyókat. A most következő golyójátékokban - a különböző színű golyók számának változása miatt - ez a valószínűség nem állandó, a golyók aktuális számával lesz arányos. Ez alapján a statisztikus golyójátékokat az állandó valószínűségű golyójátékok általánosításának is tekinthetjük.

A golyójátékok osztályozása

A fejezet játékaiban a kihúzott golyók színétől függő szabály szerint változtatjuk az urnában lévő golyók színét vagy számát. A játékokat több szempontból osztályozhatjuk.

Osztályozási szempont lehet:

a) A kezdeti színek száma. Ez lehet 2, 3 vagy több (állapodjunk meg abban, hogy ezeket az eseteket a 2, 3, 4, 5, … kódokkal szimbolizáljuk).

b) A kihúzott golyók száma. Ez lehet 1, 2 vagy több (kódok: 1, 2, 3, …).

c) A játék folyamán a golyók számának változása. Ez lehet állandó (cserélünk vagy ugyanannyi golyót teszünk vissza, mint amennyit kivettünk), lehet csökkenő (kihúzunk vagy kevesebbet teszünk vissza) és lehet növekvő. A változási módokhoz rendelt kódok: a csökkenő, állandó, növekvő esetben rendre –1, 0, +1.

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 2.1. feladat [2, 1, 0] típusú, a 2.2. feladat [2, 1, 0] vagy [6, 1, 0] típusú volt. (A sorsolási modellben a dobókocka hat oldallapjának hat golyót feleltethetünk meg. Ez lehet akár 6 különböző színű golyó is, de mivel kitüntetett szerepe csak a 6-os lapnak van, a többi lapot jellemző golyót tekinthetjük egyforma színűnek.)

d) Más típusú osztályozást kapunk, ha az egyes színek változását jellemző stratégiákat vizsgáljuk.

A stratégia lehet a kiválasztott golyó színét támogató, ún. konform stratégia. Például ha a kiválasztott golyó piros, akkor egy további piros golyót helyezünk az urnába. Lehet a stratégia semleges (ha a kiválasztott golyó piros, akkor nem csinálunk semmit), és végül lehet kontrastratégia, mely a kiválasztott szín ellen hat (például ha a kiválasztott golyó piros, akkor kicseréljük egy kék golyóra).
Általában azt mondhatjuk, hogy módszertanilag igen hasznos a hasonló típusú golyójátékok tárgyalása. Sok feladat átfogalmazható a golyójátékok modelljére, mint erre mindjárt látunk példákat, s az átfogalmazás-modellezés technikáját a későbbiekben is gyakran alkalmazzuk.

Ugyanakkor a golyójátékok igen alkalmasak számítógépes játékok alapjául is. Könnyen programozhatók, tetszőlegesen paraméterezhetők, a szimulációk és játékok igen sok variációja képzelhető el. (Erről kissé bővebben a 9. fejezetben írunk.)

Három klasszikus példa

Az alábbiakban - megoldásuk nélkül - három klasszikus feladatot említünk, melyekkel a fent bevezetett fogalmakra példákat mutatunk.

  1. 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?
  2. Egy táblára felírtunk 1996 darab 1-est, 1997 darab 2-est és 1998 darab 3-ast. Bármely két különböző 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?
  3. A feladatnak valószínűségszámítási értelmezést is adhatunk. Ekkor az eljárás folyamán két különböző, véletlenszerűen kiválasztott számjegyet letörlünk, s helyettük a harmadik számjegyet egyszer felírjuk a táblára. Mi a valószínűsége annak, hogy a) csak egyfajta; b) csak egyetlen szám marad?

  4. 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? (Mi ennek a valószínűsége, ha a kaméleonok találkozása véletlenszerű?)
  5. Az első játék kódja [2, 2, –1]. A második 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 pedig nem szigorúan monoton módon csökkenő. A harmadik játék kódja [3, 2, 0]; itt az egyes kaméleonokat azonosíthatjuk hasonló színű golyókkal.
    A végállapotok valószínűségét a 9. fejezetben megadjuk; ezek meghatározásához nincs szükségünk a Markov-láncok módszerére. Ha azonban a 2. b) vagy a 3. példa esetleges végállapotának (csupa egyforma számjegy, illetve egyforma kaméleon) eléréséhez szükséges átlagos lépésszámára vagyunk kíváncsiak, már eredményesen alkalmazhatjuk a tanult eljárást.
    A továbbiakban néhány egyszerű stratégiájú, kevés golyóból álló modell viselkedését vizsgáljuk meg.

Konform- és kontrastratégiák

4.1. feladat (konform piros stratégia): Egy urnában 10 golyó van, kezdetben 7 kék és 3 piros. Minden lépésben véletlenszerűen kiválasztunk egy golyót. A játékszabá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. (Ebben a játékban tehát csak nőhet a piros golyók száma.) 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 játékban a piros szín 1 valószínűséggel „győz”.

Jelentse Li a hátralévő húzások átlagos számát, ha a 10 golyóból i darab kék van az urnában. A feladat L7 meghatározása. A játék folyamatábrájának felírása helyett rögtön vizsgáljuk meg az általános egyenletet.

Mivel i darab kék golyó esetén  eséllyel húzunk kék és  eséllyel piros golyót, az  egyenletet kapjuk. (Az egyenlet első tagja úgy értelmezhető, hogy  valószínűséggel kék golyót húzunk; mivel ezt kicseréljük pirosra, történik egy húzás, plusz még annyi, amennyi átlagosan az (i – 1) kék golyó esetén várható, vagyis Li–1 számú. Hasonlóan a második tag a piros golyó húzásának folyamatát írja le.) Innen átalakításokkal Li = Li–1 +  következik. Ezt az egyenletet felírva az i = 7, 6, ... , 2, 1 esetekben, az alábbi egyenletrendszer adódik:

Csak az egyenletrendszer szimmetriája miatt használtuk L0-t, nyilván L0 = 0.

Most az egyenletrendszerben alulról felfelé haladva, a kisebb indexű tagokat sorban behelyettesítve, az  összefüggést kapjuk, innen  L7 ≈ 26.

Megjegyzések:
  1. A követett megoldási módszerrel hasonlóan látható be, hogy n golyó esetén, kezdeti k kék golyóval, a húzások átlagos száma  ; speciálisan, ha minden golyó kék kezdetben, akkor a húzások átlagos száma
  2. Mellékmegoldásként megkaptuk az L1 = 10 már ismert eredményt, mely azt mutatja meg, hogy ha tíz golyóból egy kék, átlagosan tízszer kell visszatevéssel húznunk, míg sikerül a kék golyót kihúzni. (Ugyanez az érték érmedobálásnál 2, kockadobásnál 6, visszatevéses sorsolásnál  volt (2.4. feladat).)
4.2. feladat (kétirányú színpárbaj):Egy urnában 6 golyó van, kezdetben 3 piros és 3 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ékot akkor nyeri Piros (P), ha minden golyó piros lesz; míg Kék (K) akkor, ha minden golyó kék lesz. Átlagosan hány lépésig tart egy játék?
Megoldás:

A játék mindkét szín szempontjából kontrastratégiájú. Legvalószínűbb, hogy a golyók színeloszlása az egyensúlyi állapot körül ingadozik, ezért a játék végét várhatóan magas lépésszámmal lehet elérni.

Legyen az i. állapotban i darab piros golyó az urnában; jelentse Li az i. állapotból indulva a húzások várható számát, pi pedig P győzelmének a valószínűségét, szintén az i. állapotban. Ekkor tudjuk, hogy szimmetriaokok miatt (igazságos a játék) és pi = 1 – p6–i (nincs döntetlen; a játék előbb-utóbb véget ér). A többi pi meghatározásához - a szokott módon - felírhatjuk, hogy:

és most

Az egyenletrendszer megoldása  és  vagyis a játék erősen kiegyensúlyozott akkor is, ha nem a szimmetrikus kezdőhelyzetből indulunk.

A lépésszámokra teljesül az Li= L6–i szimmetria, így a felírható egyenletrendszer:

Az egyenletrendszer megoldása L1 = 31, L2 = 36, L3 = 37.

4.3. feladat (egyirányú színpárbaj): Egy urnában 6 golyó van, kezdetben 3 piros és 3 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ó piros lesz. Átlagosan hány lépésig tart egy játék? (Először próbáljuk számolás nélkül megbecsülni, hogy mennyivel nőnek a 4.2. feladat lépésszámai!)
Megoldás: Ha i darab piros és 6 – i darab kék golyónk van, a lépésszámokra  teljesül. Az egyenlet átalakítva , ezt írjuk fel rendre az i = 5, 4, 3, 2, 1 esetekben:

Két peremfeltételünk van a szélsőhelyzetekből: L6 = 0, illetve L0 = 1 + L1. Például a második feltételt felhasználva az egyenletekből - lentről felfelé haladva - minden változót kifejezhetünk L1-gyel:

Mivel L6 = 0, a kapott értékek: L1 =  és korábban láttuk, hogy

Érdemes összehasonlítanunk az előző 4.2. feladat L1 = 31, L2 = 36, L3 = 37 lépésszámait a most kapott L1 = 82,2, L2 = 80,8, L3 = 78,6 értékekkel.

Megjegyzések:

Az egy- és kétirányú színpárbaj játéknak több általánosítása képzelhető el.

  1. Megtehetjük, hogy az alapjáték paramétereit (kezdeti golyószám, célállapot) változtatjuk meg. Például legyen a kezdőállapot k darab kék és p darab piros golyó, Kék győzelméhez a kék golyók számának el kell érnie a k + 4-et, Piros győzelméhez pedig a piros golyók számának kell elérne a p + 3-at.
  2. Felvehetünk több színt, s az új színekre speciális szabályokat érvényesíthetünk. Például a piros és kék golyók mellett sárga golyókat is az urnába helyezünk, s ha sárga golyót húzunk, kicseréljük pirosra.
  3. És hát természetesen több „játékos” is játszhat. Két lehetséges szabály piros, kék, sárga golyók esetén:

  4. Ha sárga golyót húzunk, visszatesszük. (Ez a játék vegyesen konform és kontrastratégiájú. Láthatóan csak sárga nyerhet; kérdés az ehhez szükséges lépésszám.)
  5. Piros golyót kékre, kéket sárgára, sárgát pirosra cserélünk.

A következő feladat a statisztikus golyójátékok egy gyakorlati alkalmazására mutat példát.

4.4. feladat: Egy 486 DLC 40 MHz-es AT számítógép az [1, 32] intervallumban egymillió véletlenszámot 11,59 másodperc alatt generált ki. Ugyanez a gép átlagosan mennyi idő alatt osztott ki négy játékos között egy 32 lapos kártyapaklit? (Az osztási algoritmus a következő: a gép először egy véletlenszámot választ az [1, 32] intervallumból; ha a számnak megfelelő kártyalap még nem foglalt, kiosztja a soron következő játékosnak; ha a lapot már megkapta valamelyik játékos, akkor a gép új véletlenszámot generál és így tovább.)
Megoldás:

Ez a feladat a golyójátékok egy alkalmazása; megpróbáljuk valamelyik játékkal modellezni az osztást.

A gép szempontjából a 32 kártyalap kétféle lehet: "jó" vagy "rossz". "Jó" a kártyalap akkor, ha a véletlen választáskor még nem osztottuk ki a soron következő játékosnak, ellenkező esetben "rossz". Ugyanakkor ha a gép egy "jó" kártyalapot kiválaszt és kioszt a soron következő játékosnak, utána már a kártyalapot "rossznak" kell jelölni, hiszen többé nem osztható ki.

A kártyalapok száma állandó, tehát a 32 lap közüli véletlen választás egy 32 golyót tartalmazó urnából való húzásnak felel meg. Kezdetben minden lap "jó", legyenek a kezdeti golyók például kékek. Ha egy "jó" lapot húzunk, azt kiosztjuk, és "rossznak" jelöljük; ennek megfelel az, hogy ha egy kék golyót kihúzunk az urnából, helyette egy pirosat teszünk vissza (a golyószám állandó). Ha egy "rossz" lapot húzunk, azt továbbra is "rossznak" tekintjük; ennek megfelelően, ha egy piros golyót húzunk az urnából, változtatás nélkül visszatesszük.

Vegyük észre, hogy a kártyapakli osztásának a 4.1. játék konform piros stratégia modellje felel meg. Ekkor a kérdés az, hogy ha kezdetben 32 kék golyó van az urnában, akkor átlagosan hány húzás után lesz minden golyó piros?

A 4.1. feladatban követett megoldással   így az osztás átlagosan kb. 1,5 ×10–3 másodpercig tartott.

Megjegyzések:
  1. A kapott idő igen rövid; nincs szükség arra, hogy az esetleges programozó kiírja a hagyományos információs szöveget: "Várj egy kicsit, most éppen osztok." (A feladat is ebből a gyakorlati problémából származik.)
  2. Az osztás nyilván gyorsabbá tehető, ha számláljuk a kiosztott lapokat. Az utolsó nyolc lap már egy kézbe kerül, tehát csak 24 lapot kell ekkor kiosztani.
  3. A feladat szép példa a matematika gyakorlati alkalmazására. Érdemes ezt tudatosítani a diákjaink körében; valamint azt is hangsúlyozhatjuk, hogy általában egyáltalán nem könnyű egy gyakorlati feladat matematikai modelljét felállítani.

Visszatevés nélküli sorsolások

Egy urnában kezdetben különböző színű golyókat helyezünk el. A játékosok felváltva húznak úgy, hogy a kihúzott golyót nem teszik vissza (tehát az urnában lévő golyók száma monoton csökken). Mindegyik játékosnak van nyerő színe (színkombinációja); s akkor győz valamelyikük, hogy ha ennek megfelelő színű golyót húz. A játékban döntetlen eredményt is kaphatunk, ha elfogytak a golyók és senki sem nyert.

Ezekben a játékokban tehát a 2. fejezet sorsolási eljárását módosítjuk, s így egy csökkenő golyószámú modellt kapunk.

4.5. feladat:

Vizsgáljuk meg az egyszerűbb alapjátékokat! Ebben két játékos, a kezdő A és a másodhúzó B játszik egymással. A nyer, ha piros golyót húz, B nyer, ha kéket; s a golyók kezdeti színmegoszlása

a) (p, k) = (1, 1);

b) (p, k) = (1, 2);

c) (p, k) = (1, 3);

d) (p, k) = (2, 3);

e) (p, k) = (2, 4);

f) (p, k) = (3, 5);

g) (p, k) = (2, 1);

h) (p, k) = (2, 2);

i) (p, k) = (3, 2);

j) (p, k) = (3, 3).

(Természetesen a tanórán a mennyiség helyett a minőségre törekedjünk: kevesebb feladatot tűzzünk ki, de lehetőleg az érdekesebbeket.)

Megoldás:

a) P(A nyer) =  (ha elsőre piros golyót húz), P(B nyer) = 0, P(döntetlen) = P(D) = .

b) P(A nyer) = . (Elsőre pirosat kell húznia. Ha ugyanis kéket húz, akkor a következő húzással vagy B nyer, vagy döntetlen lesz a játék.) P(B nyer) =  (egymás után két kék húzás következik); P(D) =  (kék - piros - kék (kpk) a húzások sorrendje).

Ez a játék igazságos.

c) P(A nyer) =  (elsőre pirosat kell húznia). P(B nyer) =  (ha az első két húzás kék - piros (kp) vagy kék - kék (kk), akkor is nyer); P(D) = 0.

d) P(A nyer) =  (a húzások sorrendje p vagy kpp). P(B nyer) =  (a húzások sorrendje kk vagy kpkk). P(D) =  (kpkpk).

e) P( A nyer) =  ( p vagy kpp). P(D) = 0, így P(B nyer) = . (Persze ki is számolhatjuk a kk, illetve kpk sorozatok valószínűségét: .)

Általában is igaz, hogy ha a kék golyók száma legalább 2-vel több, mint a pirosaké, akkor a játékban nem lehet döntetlen.

f) P(A nyer) =  (pkpp vagy kpkpp); P(B nyer) = .

g) P(A nyer) = 1.

A következő feladatokban a piros golyók száma nem kevesebb a kék golyók számánál; a játékok nyilván nem lehetnek A számára előnytelenek.

h) P(A nyer) =  ( p vagy kpp). P(D) =  (kpk), így P(B nyer) = .

i) P(A nyer) =  (p, kpp vagy kpk; tulajdonképpen p vagy kp).

j) P(A nyer) =  (p, kpp vagy kpkpp). P(D) =  (kpkpk), így P(B nyer) = .

4.6. (kitűzött) feladat: Határozzuk meg az előző játékokban a húzások átlagos számát!
Útmutatás: Legegyszerűbb a definíciót alkalmaznunk. Például a d) (2, 3) játékban annak a valószínűsége, hogy a játék 1, 2, 3, 4, 5 lépésben ér véget (tehát a húzások p, kk, kpp, kpkk, kpkpk), rendre  , , , , . Innen az átlagos húzásszám
4.7. feladat: Egy urnában kezdetben 1 piros, 2 kék és 3 sárga golyó van. Három játékos, A, B és C felváltva húz visszatevés nélkül. A nyer, ha piros golyót húz; B nyer, ha kéket; C, ha sárgát. Határozzuk meg A, B, C nyerési esélyét!
Megoldás:

A játék állapotdiagramja 6 mélységű (7 szintű) fagráf, melynek felrajzolásakor igyekeztünk egyszerűsítéseket végezni. Az egyes állapotokat a golyók aktuális számával jelöltük (kezdetben ez (123)); a döntetlen végállapot jele D.

Nem rajzoltuk ki például az egyértelmű utolsó szintet; vagy az (102) állapotból rögtön következtettünk vagy A, vagy C győzelmére.

Az ábra alapján P(A nyer) =
P(B nyer) =
P(C nyer) =  +
és a döntetlen valószínűsége D =

(A folyamatábra lényegében nem könnyítette meg a munkánkat, de a megoldás szerves része, így nem hagytuk el. Bizonyos értelemben feleslegesen dolgoztunk, de ez a feladatmegoldás folyamán gyakran előfordul.)

4.8. (kitűzött) feladat: Határozzuk meg az előző játékban a húzások átlagos számát!
Megjegyzések:

A visszatevés nélküli sorsolási modelleket általánosíthatjuk. Változtathatjuk a golyók kezdeti megoszlását, többféle (többszínű) golyóval játszhatunk, és növelhetjük a játékosok számát is.

A csökkenő golyószám miatt nehezebb ekvivalens állapotokat találni, így a játék folyamatábrája könnyen megnövekedhet, a játék elemzése elnehezedhet. (A 4.7. feladatban kevés kezdeti golyóval játszottunk, ennek ellenére az állapotdiagram gráfja igen bonyolult lett.) Természetesen minél összetettebb a feladat, annál inkább előtérbe kerül a számítógép alkalmazása.

Vegyes feladatok

4.9. (kitűzött) feladat (KöMaL A.381.): Egy n oldalú „dobókockát” addig dobálunk, amíg mind az n lehetséges eredményt legalább egyszer megkapjuk. Mennyi a dobások számának várható értéke?
4.10. (kitűzött) feladat: Egy fizikusok által a gázok diffúziójára használt modell a következő:

Egy urna üres, egy másikban 6 darab számozott golyó van. Egy kísérlet abból áll, hogy véletlenszerűen kiválasztunk egy számot 1-től 6-ig, és a neki megfelelő golyót áttesszük a másik urnába. A játéknak akkor van vége, ha a golyók eloszlása 3 - 3.

a) Átlagosan hány lépésig tart a kísérlet?

b) Oldjuk meg a fordított feladatot is: 3 -3 golyó esetén várhatóan hány lépés után fog kiürülni valamelyik urna?

4.11. (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 a második. Várhatóan hány húzás kell ahhoz, hogy minden golyó egyszínű legyen?

5. Ferdefoci

Két játékos a következő, ferdefoci nevű játékot játssza (az elnevezés az [1] könyvből származik; az elnevezés magyarázatát az 5.5. feladatban láthatjuk). Adott h hosszúságú pálya egyik mezőjére egy korongot helyeznek el, majd szabályos érmével dobásokat végeznek. Ha a dobás fej, a korongot egy mezővel balra, írás esetén egy mezővel jobbra mozdítják el. A jobb oldali játékos (továbbiakban J) akkor győz, ha a korong a játékmezőt bal oldalról hagyja el; a bal oldali játékos (B) pedig akkor, ha jobbról. Ha a mezőket balról jobbra megszámozzuk, akkor úgy is tekinthetjük a játékot, mintha J győzelméhez a korongnak a 0. mezőre (B kapuja), B győzelméhez pedig a (h + 1). mezőre (J kapuja) kell kerülnie.

B             J
0 1 2 3 ...   H h+1
5.1. feladat:Vizsgáljuk meg a ferdefoci alapjátékot h = 2 hosszúságú pályán!

a) Mi annak a valószínűsége, hogy a játék döntetlennel ér véget?

b) Mekkora valószínűséggel győz J, ha a korong kezdetben az első, illetve a második mezőn van?

c) Átlagosan meddig (hány dobásig) tart a játék? (A játéknak akkor van vége, ha a korong valamelyik oldalon elhagyja a pályát.)

Megoldás:

Nevezzük a további játékokban is i. állapotnak azt a helyzetet, amikor a korong az i. mezőn van. Jelölje pi annak a valószínűségét, mellyel J nyer az i. állapotból indulva; Li pedig az átlagos lépésszámot. Az érmedobás véletlenszerűsége miatt a balra, illetve a jobbra lépés valószínűsége egyaránt .

Legyen a korong kezdetben az első mezőn. A játék csak akkor lehet döntetlen, ha a dobások egymás után írás, fej, írás, fej stb. sorrendben következnek. Annak valószínűsége, hogy a játék N dobás után nem ér véget, ; ennek határértéke nulla, ha N tart a végtelenhez. Ha a korong a második mezőről indul, a helyzet - szimmetriaokok miatt - ugyanez. Vagyis a döntetlen valószínűsége nulla, ez a játék is 1 valószínűséggel véget ér.

Első megoldás (mértani sor): Tudjuk, hogy p1 = P(J nyer) = P(J vagy az első, vagy a harmadik, vagy az ötödik, vagy a ... lépésben nyer (és közben B nem nyer)). Ez formailag a
 p1 = P(J nyer) = ... egyenletet jelenti. Ez egy hányadosú végtelen mértani sor, melynek összege . Tehát p1 = P(J nyer) = .

Második megoldás („logikai rekurzió”): Mivel a játékban nincs döntetlen, bármely állapotban P(J nyer) + P(B nyer) = 1. Ezért ha egy írás dobás után a korong a 2. mezőre kerül, a játék szerepcserével folytatódik, ahonnan már B nyer p1 és J nyer (1 – p1) valószínűséggel. Ez alapján a kezdőállapotra felírható egyenlet p1 = ,  melynek p1 =  a megoldása.

Harmadik megoldás (Markov-láncok):A probléma folyamatábrája (a mezők sorszámával jelöltük a megfelelő állapotokat):

A játék szempontjából az 1. kezdőállapot, valamint egy fej és egy írás dobás után kapott állapot ekvivalens. A felírható egyenletrendszer:

Az egyenletrendszer megoldása valóban p1 = .

Első megoldás (a várható érték definíciója alapján):

Második megoldás (Markov-láncok):A folyamatábra alapján a lépésszámokra felírható egyenletrendszer:

Az egyenletrendszer megoldása L1 = L2 = 2.

Harmadik megoldás („logikai rekurzió”):A várható lépésszám szempontjából az 1. és 2. állapotok szimmetrikus szerepük miatt ekvivalensek. Az L1 =L2 szimmetria miatt közvetlenül felírható egyenlet:

, ennek megoldása L1 = 2.

Megjegyzések:

1. A ferdefoci játék tulajdonképpen egy egyenes mentén történő diszkrét (egységeket lépő) bolyongási modell; ennek 5.1. a lehető legegyszerűbb feladata.

2. Az érmedobás szerepe gyakorlatilag az, hogy megadja a balra, illetve a jobbra lépés valószínűségét.

3. Természetesen p1 > p2 a várakozásunknak megfelelően.

4. A 2.7. feladat megjegyzése alapján L1 = 2 megjósolható volt. (Megmutattuk, hogy ha egy esemény bekövetkezésének valószínűsége p, akkor az ehhez szükséges átlagos lépésszám . Itt pedig erről van szó: mindig  valószínűséggel ér véget a folyamat.)

5.2. feladat:

Vizsgáljuk meg a ferdefoci alapjáték valószínűségeit a h = 3 hosszúságú pályán!

a) Mekkora valószínűséggel győz J, ha a korong kezdetben az első (második, harmadik) mezőn van?

b) Mekkora az átlagos lépésszám az egyes esetekben?

B       J
  1 2 3  
Megoldás: Ismét igaz, hogy nincs döntetlen (részletesebb indoklás: 8.5. feladat), a játék előbb-utóbb véget ér. Az előző feladat jelöléseivel p2 = , p1 =  = , s így p3 = . A lépésszámokra ,  és . Innen L1 = L3 = 3, L2 = 4.
5.3. feladat: Vizsgáljuk meg a ferdefoci alapjáték valószínűségeit a h = 4 hosszúságú pályán!

a) Mekkora valószínűséggel győz J, ha a korong kezdetben az első (második, ..., negyedik) mezőn van?

b) Mekkora az átlagos lépésszám az egyes esetekben?

B         J
  1 2 3 4  
Megoldás:

a) A játék (B és J szerepcseréjéből adódó) szimmetriája miatt p1 = 1 – p4, p2 = 1 – p3. Így az egyenletrendszer egyszerűsödik, nincs szükségünk négy egyenletre:

Az egyenletrendszer megoldása ; ekkora valószínűséggel nyer J az egyes mezőkről indulva.

b) A lépésszámokra teljesül az L2 = L3 és L1 = L4 szimmetria (a várható lépésszámok szempontjából azonos szerepűek a 2-3, illetve 1-4 mezők). A felírható egyenletrendszer:

Az egyenletrendszer megoldása L1 = 4, L2 = 6, L3 = 6, L4 = 4.

5.4. feladat: Vizsgáljuk meg a ferdefoci alapjáték valószínűségeit a h = 5 hosszúságú pályán!

a) Mekkora valószínűséggel győz J, ha a korong kezdetben az első (második, ..., ötödik) mezőn van?

b) Mekkora az átlagos lépésszám az egyes esetekben?

B           J
  1 2 3 4 5  
Megoldás:

a) A játék szimmetriája miatt p1 = 1 – p5, p2 = 1 – p4 és . A felírható egyenletek:

Az egyenletrendszer megoldása ; ekkora valószínűséggel nyer J az egyes mezőkről indulva.

b)Ha a lépésszámokat vizsgáljuk, az L1 = L5, L2 = L4 összefüggést vehetjük észre. A felírható egyenletrendszer:

Az egyenletrendszer megoldása L1 = 5, L2 = 8, L3 = 9, s innen L5 = 5, L4 = 8.

Megjegyzés:

A fenti feladatok eredményei alapján sejthető, hogy a h = 2k – 1 hosszúságú pályán  és Lk = k2. Ennek a másodrendű lineáris rekurziók segítségével történő bizonyítása megtalálható a következő fejezetben; s ugyanitt az átlagos lépésszámokra az Li = i(h + 1 – i) általános eredményt kaptuk.

5.5. feladat: A ferdefoci játék egy újabb változata, amikor a korong nem egyforma valószínűséggel lép a két irányba (ez az „igazi” ferdefoci). Legyen például a balra lépés valószínűsége p = , a jobbra lépés valószínűsége q = , a pálya hossza h = 3.

a) Mekkora valószínűséggel győz J, ha a korong kezdetben a második (első, harmadik) mezőn van?

b) Mekkora az átlagos lépésszám az egyes esetekben?

Megoldás: Rajzoljuk fel a szokásos jelölésekkel a játék folyamatábráját, például ha kezdetben a korong a 2. mezőn áll.

Az állapotdiagramhoz tartozó egyenletrendszer:

Az egyenletrendszer megoldása  

Az átlagos lépésszámokra felírható egyenletrendszer:

Ennek megoldása pedig

Megjegyzések: Balra a korong kétszer akkora valószínűséggel lép, mint jobbra; emiatt még a 3. mezőről indulva is J-nek előnyös a játék. Az 5.2. feladat 3, 4, 3 lépésszámai 2,2; 3,6; 3,4-re módosultak. Ha a játék kezdetekor a korongot a három mező egyikére véletlenszerűen helyezzük el, akkor az 5.4. játék átlagban hamarabb ér véget, mint az 5.2.

5.6. feladat:Az előző játékot annyiban módosítjuk, hogy most a korong adott valószínűséggel helyben is maradhat. (Ilyen esetben tehát a lépésszám 1-gyel nő, de a korong nem mozdul el.) Legyen a balra lépés valószínűsége p = , a jobbra lépés valószínűsége q = , a helyben maradás valószínűsége R = 1 – pq = ; a pálya hossza h = 3.

a) Mekkora valószínűséggel győz J, ha a korong kezdetben a második (első, harmadik) mezőn van?

b) Mekkora az átlagos lépésszám az egyes esetekben?

Megoldás:

a) A felírható egyenletrendszer

Ennek megoldása  

b) A lépésszámokra vonatkozó egyenletrendszer:

Ennek megoldása

Megjegyzés:

A kapott értékekkel kapcsolatban észrevehetjük, hogy az egyes mezőkhöz tartozó nyerési valószínűségek nem változtak, a lépésszámok pedig -szorosra nőttek. Mindkét eredmény szemléletesen magyarázható:

A helyben maradás nem befolyásolja a nyerési valószínűségeket. Ha tehát az esetek  részében a korong helyben marad, akkor elég az esetek maradék  részét vizsgálni; ezen maradék esetek  részében balra,  részében pedig jobbra mozdul el a korong.

A lépésszámokkal kapcsolatban pedig azt állapíthatjuk meg, hogy mivel a korong átlagosan 5 lépésből 2-szer helyben marad, így a maradék 3 tényleges elmozduláshoz tartozó várható lépésszámokhoz átlagosan további 2 „helybenmaradási lépést” kell hozzáadnunk; így kapjuk az átlagos lépésszámok -szorosát.

6. A ferdefoci játék általános vizsgálata

Az általános tárgyalás során felhasználjuk a lineáris rekurziók elméletének tételeit.

6.1. feladat (általánosítás a pálya hosszára és a lépési valószínűségekre):Vizsgáljuk meg a ferdefoci játékot tetszőleges h hosszúságú pályán! Mekkora valószínűséggel győz J, ha a korong kezdetben az első (második, ...) mezőn van? Érdemes rögtön a feladat általánosítását vizsgálni: tegyük fel, hogy a korong nem egyforma valószínűséggel lép balra, illetve jobbra. Legyen a balra lépés valószínűsége p, a jobbra lépés valószínűsége q = 1 – p.

Megoldás:

Legyen pi annak a valószínűsége, hogy az i. mezőn tartózkodó bolyongó pont balról hagyja el a pályát. (Azt is mondhatjuk, hogy ekkora valószínűséggel nyer J.)

A bolyongó pont vagy p valószínűséggel balra, vagy q valószínűséggel jobbra lép egy mezőt, és innen a későbbiekben pi–1, illetve pi+1 valószínűséggel hagyja el balról a pályát. Ennek megfelelően a pi = p ×pi–1 + q ×pi+1 valószínűségi egyenletet írhatjuk fel. Célszerű a 0. és (h + 1). fiktív mezőket felvenni, ekkor p0 = 1, ph+1 = 0.

Adott p, q és h értékek esetén megoldhatjuk a h darab egyenletből álló pi = p ×pi–1 + q ×pi+1 (i = 1, 2, … , h) egyenletrendszert. (Ha h értéke nagy, használhatunk számítógépet.)

Az általános eset vizsgálatakor a pi = p ×pi–1 + q ×pi+1 (i = 1, 2, … , h) rekurzió explicit alakját keressük a p0 = 1, ph+1 = 0 peremfeltételek mellett. (Vagy átalakítva: .)

A qx2x + p = 0 karakterisztikus egyenlet vizsgálatát két részletben végezzük el.

Első eset: Ha p = q = , akkor az egyenlet gyökei egybeesnek, x1,2 = 1, ezért a (p) sorozat pi = a + bi alakú. A p0 = 1 feltétel miatt a = 1, a ph+1 = 0 feltétel miatt . A (p) sorozat explicit alakja .

Második eset: Ha pq, akkor legyen p < q. Ekkor a karakterisztikus egyenlet két gyöke . Helyettesítsünk: ha , akkor pi = aci + b alakban írható. A p0 = 1 feltétel miatt a + b = 1, a ph+1 = 0 feltétel miatt ach+1 + b = 0. Innen  és . A (p) sorozat explicit alakja tehát .

Megjegyzések:

1. A kapott  valószínűségek szép lineáris csökkenést mutatnak, az 5.1 - 5.3. feladatok eredményeinek megfelelően.

2. A  képlet egyszerű ellenőrzését 5.4. alapján végezhetjük. Itt  = 2, h = 3 volt; az i = 0, 1, 2, 3, 4 értékeket rendre behelyettesítve , , , , . Az 5.4. feladattal megegyező értékeket kaptunk.

6.2. feladat: Legyen a h hosszúságú pályán a balra lépés valószínűsége p ( ≠) a jobbra lépés valószínűsége q = 1 – p. Melyik mezőre kell kezdetben helyezni a korongot, hogy a játék közelítőleg igazságos legyen?

Megoldás: Az előző feladat eredménye alapján az i értékét kell úgy meghatároznunk, hogy  legyen. A  egyenletből . (Az 5.5. játékban, ahol p = , q =  volt, i ≈ 3,087 érték adódik. Kár, hogy csak 3 hosszú a pálya. A játék így nem tehető igazságossá; még a 3. mezőről indulva is , a játék J-nek előnyös.)

6.3. feladat (a lépésszámok általános vizsgálata):Legyen a h hosszúságú pályán a balra lépés valószínűsége p, a jobbra lépés valószínűsége q = 1 – p. Melyik mezőre kell kezdetben helyezni a korongot, hogy a játék a lehető legtovább tartson?

Megoldás Jelölje Li az átlagos lépésszámot, ha a korong az i. mezőn van. A feladat Li maximumhelyének meghatározása.

A várható lépésszámra az Li = p(1 + Li–1) + q(1 + Li+1) egyenletet írhatjuk fel. (Az egyenlet első tagja hagyományosan úgy értelmezhető, hogy a pont p valószínűséggel az
(i – 1). mezőre kerül, tehát lép egyet, plusz még annyit, amennyi átlagosan az (i – 1). mezőn állva várható, vagyis Li–1-et. Hasonlóan a második tag a jobbra lépés folyamatát írja le.) Ha a pont a fiktív mezőkre kerül, a játéknak vége lesz, tehát L0 = Lh+1 = 0. Az egyenletet átalakítva az Li = 1 + pLi–1 + qLi+1 (i = 1, 2, … , h) rekurzív összefüggést írhatjuk fel, L0 = Lh+1 = 0 a peremfeltételek.

Az egyenlet átrendezésével kapott qLi+1 = LipLi–1 – 1 inhomogén másodrendű rekurzió megoldásához először meg kell oldanunk a különbségsorozat által kapható homogén másodrendű rekurziót. Ezután a peremfeltételeket illesztjük; ez a lépés valamivel bonyolultabb lesz, hiszen most nem a sorozat első két tagja az adott.

Definiáljuk az (L) sorozat (d) különbség-sorozatát: di = Li Li–1, (i = 1, 2, …). Ekkor a (d) sorozatra érvényes összefüggés qdi+2 = di+1pdi. Ha meg tudjuk adni (d) tagjait, akkor a

d1 = L1L0,

d2 = L2L1,

d3 = L3L2,

di = LiLi–1,

dh+1 = Lh+1Lh

egyenletrendszer összegzéséből következne Lh+1L0 = , és mivel L0 = 0, Li = , például Lh+1 =.

A qx2x + p = 0 karakterisztikus egyenlet vizsgálatát ismét két részletben végezzük el.

Első eset: Ha p = q = , akkor az egyenlet két gyöke x1,2 = 1, ezért a (d) sorozat di = a + bi alakú. Most a (d) sorozat peremfeltételeit nem ismerjük, a két állandó, a és b az (L) sorozat kezdeti feltételeinek felhasználásával határozható meg.

Először is, Lh+1 = 0, és Lh+1 =  miatt , vagyis .

Mivel L0 = 0, L1 = d1 = a + b, L2 = L1 + d2 = a + b + a + 2b = 2a + 3b. A másik egyenletet a és b meghatározásához (L) rekurzív alakjának felhasználásával kapjuk. Eszerint   = 2L1 – 2, így 2a + 3b = 2a + 2b – 2.  Az

,

2a + 3b = 2a + 2b – 2
egyenletrendszer megoldása b = –2, a = h + 2, tehát di = h + 2 – 2i, s mivel Ln = , így Ln =  = –n2 + n + nh = n(h + 1 – n).

A –n2 + nh + n kifejezést teljes négyzetté alakítva, a maximumot  helyen kapjuk, ami a pálya közepe, s amit a szemléletünk is sugall. Ha h = 2k – 1 alakú páratlan szám, akkor n = k, és Lk = k2 a maximum.

Megjegyzés: Érdemes hangsúlyozni, hogy ha h = 2k – 1 alakú, és n = k (a pálya közepe), akkor a várható lépésszám Lk = k2. Ez a nevezetes eredmény az egyenes mentén történő bolyongási modellben azt jelenti, hogy ha a pálya széléig k mező van, akkor először átlagosan k2 lépés után ér el ide a bolyongó pont. Hasonlót kaptunk a „fej vagy írás” érmedobálási modellben is: ahhoz, hogy a fejek és írások számának eltérése (először) k legyen, átlagosan k2 dobásra van szükség (lásd 3.6. feladat). Megfordítva annyit mondhatunk, hogy k2 dobás esetén az eltérés arányos k-val.

Azon is elgondolkodhatunk, hogy ez az eredmény mit is jelent azzal kapcsolatban, amit úgy szoktunk nevezni, hogy „a véletlen számok kiegyenlítődési hajlama” (lásd 10.1. feladat).

Második eset: Ha p q, akkor legyen p < q. Ekkor a karakterisztikus egyenlet két gyöke . Alkalmazzuk a  helyettesítést, ekkor di = aci + b alakban írható. Az egyik feltétel ismét az Lh+1 = összefüggésből adódik: Lh+1 =  + b(h + 1) = 0. Továbbá  mivel L0 = 0, L1 = d1 = ac + b, L2 = L1 + d2 = ac + b + ac2 + b = ac(c + 1) + 2b

A másik egyenletet (L) rekurzív alakjából kapjuk. Eszerint ,  tehát  ac(c + 1) + 2b = .  Az

qac(c + 1) + 2bq = ac + b – 1
egyenletrendszer megoldása . Mivel Ln =, ezért .

A kapott eredmény meglehetősen "csúnya",  legegyszerűbb - adott h, p, q, c érték esetén - számítógép segítségével meghatározni a kifejezés szélsőértékét.

Konkrét példák:

Például h = 4 hosszúságú pályán,    értékeket választva annak valószínűsége, hogy a pont az i. mezőről indulva balról hagyja el a pályát, rendre . Látható, hogy még az első mezőről indulva is, a játék B-nek kedvező. Az "igazságos hely"  képletébe behelyettesítve i 0,96.

A lépésszámok: . A maximális lépésszámot i = 2 esetén kapjuk (a képlettel i 1,84, Li = 5,64).

Az alábbi táblázat az  függvény szélsőértékét tartalmazza különböző h értékek mellett. A paraméterek:   (és persze ).

Pálya hossza ( h )

Szélsőértékhely ( x )

Felvett szélsőérték ( L(x) )

     
2 1,25 2,21
3 1,56 3,78
4 1,84 5,64
5 2,08 7,72
6 2,29 9,97
7 2,48 12,34
8 2,64 14,79
9 2,79 17,32
10 2,93 19,89
20 3,86 47,08
30 4,43 75,40
40 4,83 104,19
50 5,14 133,24
60 5,40 162,47
70 5,62 191,81
80 5,81 221,24
90 5,98 250,73
100 6,13 280,28
Megjegyzés:

Érdekes, hogy az "igazságos hely" és a "maximális lépésszámú hely" általában nem egyezik meg.

A bolyongásos feladatnak több általánosítása lehetséges. Megengedhetjük speciális lépésként a helyben maradást; lehetséges, hogy a bolyongó pont nem egy egységgel mozdul el; felvehetünk gátakat, melyekről a pont visszaverődik; a bolyongás történhet egyenes helyett síkban, előírt alakzaton stb.

6.4. feladat (helyben maradási valószínűség):

A ferdefoci játék egy újabb változata, amikor a korong R valószínűséggel helyben marad. Ekkor a lépésszám eggyel nő, de a korong nem változtatja helyét. Rögtön általánosan tárgyaljuk a feladatot: balra p, jobbra q legyen az elmozdulási valószínűség; ekkor p + q + R = 1 teljesül. A kérdések ugyanazok:

a) Mekkora valószínűséggel győz J, ha a korong kezdetben az első (második, ...) mezőn van?

b) Mennyi a játék átlagos lépésszáma?

Megoldás:

A tetszőlegesen sok egyenletből álló egyenletrendszerek megoldása helyett most is a rekurzív sorozatok elméletét hívhatjuk segítségül.

a) A pi = ppi–1 + Rpi + qpi+1 (i = 1, 2, … , h) rekurziót kell megoldanunk a p0 = 1, pk+1 = 0 peremfeltételek mellett. Mivel p + q + R = 1, a qx2 – (p + q)x + p = 0 karakterisztikus egyenletet vizsgáljuk két részletben.

Első eset:

Ha p = q, akkor x1,2 = 1, ezért a (p) sorozat pi = a + bi alakú. A p0 = 1 feltétel miatt a = 1, a pk+1 = 0 feltétel miatt . A (p) sorozat explicit alakja .

Ez az eredmény megegyezik azzal, amit a korábbi 6.1. - 6.2. feladatokban, r = 0 esetben kaptunk; vagyis az egyes nyerési esélyeket nem befolyásolja az, ha a korong helyben maradhat.

Második eset:

Ha pq, akkor legyen például p < q. Ekkor a karakterisztikus egyenlet két gyöke x1 = , x2 = 1. Legyen c = , ekkor pi = aci + b alakban írható. A p0 = 1 feltétel miatt a + b = 1, a pk+1 = 0 feltétel miatt ach+1 + b = 0. Innen  és . A (p) sorozat explicit alakja .

Szintén ugyanazt az eredményt kaptuk, mint az r = 0 esetben.

Vagyis: az R = 0 eset együtt tárgyalható az R > 0 esettel, az egyes nyerési valószínűségek csak a  aránytól függnek (és nem függnek például csak pusztán p-től).

Az eredmény szemléletesen is indokolható (lásd 5.6. megjegyzés).

b)Az Li = 1 + pLi–1 + RLi + qLi+1 (i = 1, 2, … , h) rekurzív összefüggést kell megoldanunk az L0 = 0, Lh+1 = 0 peremfeltételek mellett.

Az egyenlet átrendezésével kapott qLi+1 = (p + q)Li pLi–1 – 1 inhomogén másodrendű rekurzió megoldásához először meg kell oldanunk a különbségsorozat által kapható homogén másodrendű rekurziót.

Definiáljuk az (L) sorozat (d) különbség-sorozatát: di := LiLi–1, (i = 1, 2, …). Ekkor a (d) sorozatra az érvényes összefüggés qdi+2 = (p + q)di+1pdi. Ha meg tudnánk adni (d) tagjait, akkor a

d1 = L1L0,

d2 = L2L1,

d3 = L3L2,

dh+1 = Lh+1Lh

egyenletrendszer összegzéséből következne Lh+1L0 = , és mivel L0 = 0, , például Lh+1 = .

A qx2 – (p + q)x + p = 0 karakterisztikus egyenlet vizsgálatát ismét két részletben végezhetjük el.

Első eset:

Ha p = q, akkor x1,2 = 1, ezért a (d) sorozat di = a + bi alakú. Most a (d) sorozat peremfeltételeit nem ismerjük, a két állandó, a és b az (L) sorozat kezdeti feltételeinek felhasználásával határozható meg.

Először is, Lh+1 = 0, és Lh+1 =  miatt , vagyis  .

Mivel L0 = 0, így L1 = d1 = a + b, L2 = L1 + d2 = a + b + a + 2b = 2a + 3b. A másik egyenletet a és b meghatározásához (L) rekurzív alakjának felhasználásával kapjuk. Eszerint  , így 2a + 3b = 2a + 2b. Az

,

2a + 3b = 2a + 2b

egyenletrendszer megoldása b = – , , tehát , s mivel , így .

Második eset:

Ha pq, akkor legyen például p < q. Ekkor a karakterisztikus egyenlet két gyöke x1 = , x2 = 1. Legyen c = , ekkor di = aci + b alakban írható. Az egyik feltétel ismét az  összefüggésből adódik: . Továbbá  mivel L0 = 0, így L1 = d1 = ac + b, L2 = L1 + d2 = ac + b + ac2 + b = ac(c + 1) + 2b. A másik egyenlet (L) rekurzív alakjából adódik. Eszerint  , tehát a másik összefüggés  ac(c + 1) + 2b = . Az

qac(c + 1) + 2bq = (p + q)(ac + b) – 1

egyenletrendszer megoldása . Mivel  , ezért .

Megjegyzések:

1. Ha p = q = , R = 0, akkor természetesen visszakapjuk a 6.3. feladat eredményét, míg ha p = q < , akkor az átlagos lépésszám -szeresére nő.

2. Formailag hasonló egyenletet kaptunk, mint a 6.3. feladatban, de adott c és R érték mellett a qp eltérés megváltozott.

6.5. feladat (különböző lépéshossz):

A ferdefoci játék egy másik változata, amikor a korong nem egyforma nagyot lép jobbra, illetve balra. A következő játékban legyen a balra lépés valószínűsége  a jobbra lépés valószínűsége ; viszont ha a korong jobbra lép, egy lépésben egyszerre két mezőt halad. Határozzuk meg az egyes nyerési valószínűségeket a h = 5 hosszúságú pályán!

Megoldás:

Rajzoljuk fel a szokásos jelölésekkel a játék folyamatábráját, például ha kezdetben a korong a 2. mezőn áll.

A változatosság kedvéért most qi jelentse B nyerési esélyét az i. mezőről indulva. Ekkor az állapotdiagramhoz tartozó egyenletrendszer:

Valójában a   rekurzív összefüggést írtuk fel az i = 1, 2, ..., 5 értékekre (ekkor a fiktív 0. mező esetén q0 = 0, a 6. és 7. mező esetében q6 = q7 = 1). Az egyenletrendszer megoldása  ; ekkora valószínűséggel nyer B az i. mezőről indulva. (Ugyanezek a valószínűségek, ha J győzelmét vizsgáljuk: ; B és J győzelmi esélyei persze nem „szimmetrikusak”.)

Megjegyzés: A rekurzió általános megoldása . Ennek bizonyítása a korábbiakhoz hasonlóan történhet; csakúgy, mint az átlagos lépésszámok meghatározása.
6.6. feladat (egyirányú ferdefoci - kitűzés):A ferdefoci játék egy másik lehetséges változata, amikor a korong a pálya egyik széléről, például a jobb kapuról visszaverődik. (Ekkor természetesen mindig J győz.) Vizsgáljuk meg a játék átlagos lépésszámát!

Útmutatás: Az, hogy J kapuja helyén akadály van, azt jelenti, hogy a korong a h. mező után visszapattan, és a (h – 1). mezőn folytatja útját. A lépésszámokra felírható rekurzív összefüggés nem változik meg, csak a h. mező után lévő akadály a peremfeltételt módosítja: Lh = 1 + Lh–1.

Ügyesebben is eljárhatunk a p = q =  speciális esetben. Tükrözzük a h. mezőre az 1., 2., … , (h – 1). mezőket, kapjuk a (h + 1)., (h + 2)., … , (2h – 1). mezőt. Tegyük fel, hogy a korong visszapattanás helyett továbblép a (h + 1). mezőre, s a (2h – 1) hosszúságú pályát két oldalról hagyhatja el, mint a hagyományos ferdefociban! Látható, hogy ha most a (h – 1)-es és (h + 1)-es, a (h – 2)-es és (h + 2)-es stb. mezőpárokat ekvivalenseknek tekintjük, akkor a korong átlagosan ugyanannyi ideig fog ezen a (2h – 1) hosszúságú pályán tartózkodni, mint a h hosszúságú, egyirányú pályán.

Vagyis az akadállyal ellátott ferdefoci játék tárgyalása a p = q esetben visszavezethető az alapjáték vizsgálatára. (A feladat lényegesen nehezebb, ha pq.)

6.7. (kitűzött) feladat ([7], 16.43.)

X-nek x, Y-nak y forintja van. Szabályos érmével játszanak: feldobják egymás után, és ha fejre esik, X kap Y-tól egy forintot; írás esetén viszont Y kap X-től egy forintot. A játék addig tart, amíg valamelyikük fizetésképtelenné nem válik.

a) Mekkora a valószínűsége, hogy X megy tönkre?

b) Átlagosan hány dobásra van szükség a játék befejezéséhez?

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.