Szakdolgozat
Miskolci Egyetem
A szentpétervári paradoxon
Készítette: Botos Imre 3. Évfolyam, Programtervező Informatikus Szak Témavezető: Dr. Karácsony Zsolt egyetemi docens
Miskolc, 2013
Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Matematikai Tanszék
Szám:
Szakdolgozat Feladat Botos Imre (L7CHQV) programtervező informatikus jelölt részére. A szakdolgozat tárgyköre: Valószínűségszámítás és matematikai statisztika A szakdolgozat címe: A szentpétervári paradoxon A feladat részletezése: Irodalomkutatás és az elmélet összefoglalása, a paradoxon bemutatása illetve a problémakör fejlődése a XVII-XIX. század között. Alkalmazási területek bemutatása, a programban használt tételek kimondása. A probléma számítógépes implementációja tetszőleges programban. Mind a grafikus, mind a szöveges eredményeknek nyomtathatóaknak kell lenniük. Leghosszabb szériák vizsgálatára irányuló szimulációs program elkészítése, szabályos és nem szabályos pénzérmére. Szabályos érme esetén rekurziós képletek alkalmazása a programban. Egyszerű duplázásos teknika leprogramozása kezdő tőke és cél nyeremény megadásával a program írja ki, hogy hányszor értük el illetve nem értük el a célnyereményt, valamint átlagosan hány játék volt. Továbbá egy olyan program elkészítése, ami megbecsüli a szentpétervári játék egy játékra eső díját.
Témavezető: Dr. Karácsony Zsolt, egyetemi docens A feladat kiadásának ideje: 2010.09.28.
................................. szakfelelős 2
Eredetiségi Nyilatkozat
Alulírott Botos Imre; Neptun-kód: L7CHQV a Miskolci Egyetem Gépészmérnöki és Informatikai Karának végzős Programtervező Informatikus szakos hallgatója ezennel büntetőjogi és fegyelmi felelősségem tudatában nyilatkozom és aláírásommal igazolom, hogy A szentpétervári paradoxon című szakdolgozatom/diplomatervem saját, önálló munkám; az abban hivatkozott szakirodalom felhasználása a forráskezelés szabályai szerint történt. Tudomásul veszem, hogy szakdolgozat esetén plágiumnak számít: • szószerinti idézet közlése idézőjel és hivatkozás megjelölése nélkül; • tartalmi idézet hivatkozás megjelölése nélkül; • más publikált gondolatainak saját gondolatként való feltüntetése. Alulírott kijelentem, hogy a plágium fogalmát megismertem, és tudomásul veszem, hogy plágium esetén szakdolgozatom visszautasításra kerül.
Miskolc, . . . . . . . . . . . .év . . . . . . . . . . . .hó . . . . . . . . . . . .nap
................................. Hallgató
3
1. szükséges (módosítás külön lapon) A szakdolgozat feladat módosítása nem szükséges ......................
...........................
dátum
témavezető(k)
2. A feladat kidolgozását ellenőriztem: témavezető (dátum, aláírás):
konzulens (dátum, aláírás):
..............
.............
..............
.............
..............
.............
3. A szakdolgozat beadható: ......................
...........................
dátum
témavezető(k)
4. A szakdolgozat . . . . . . . . . . . . . . . . . . . szövegoldalt . . . . . . . . . . . . . . . . . . . program protokollt (listát, felhasználói leírást) . . . . . . . . . . . . . . . . . . . elektronikus adathordozót (részletezve) ................... . . . . . . . . . . . . . . . . . . . egyéb mellékletet (részletezve) ................... tartalmaz. ......................
...........................
dátum
témavezető(k)
5. bocsátható A szakdolgozat bírálatra nem bocsátható A bíráló neve: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................
...........................
dátum
szakfelelős
6. A szakdolgozat osztályzata a témavezető javaslata:
................
a bíráló javaslata:
................
a szakdolgozat végleges eredménye: . . . . . . . . . . . . . . . . Miskolc, . . . . . . . . . . . . . . . . . . . . . . . .
................................. a Záróvizsga Bizottság Elnöke 4
Tartalomjegyzék 1. Bevezetés 2. A szentpétervári paradoxon 2.1. A paradoxon leírása . . . . . . . . . . . . . . 2.2. A paradoxon történeti áttekintése . . . . . . 2.3. A leghosszabb szériák vizsgálata . . . . . . . 2.3.1. Szabályos pénzérme esete . . . . . . 2.3.2. Szabálytalan pénzérme esete . . . . . 2.3.3. A halmozási vagy duplázásos teknika
6
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
3. Fejlesztői dokumentáció 3.1. Követelmény definíció . . . . . . . . . . . . . . . . . . . . . 3.1.1. A program célja, alapvető feladata . . . . . . . . . 3.1.2. A fejlesztőkörnyezet . . . . . . . . . . . . . . . . . . 3.1.3. A futtatáshoz szükséges környezet . . . . . . . . . . 3.1.4. Felhasználói felület . . . . . . . . . . . . . . . . . . 3.1.5. A program elkészítésének a lépései . . . . . . . . . 3.2. A programban használt grafikus objektumok . . . . . . . . 3.3. A programban használt függvények leírása . . . . . . . . . 3.3.1. A kezdő oldal függvényei . . . . . . . . . . . . . . . 3.3.2. Leghosszabb szériák programrész függvényei . . . . 3.3.3. Egy játék ára programrész fügvényei . . . . . . . . 3.3.4. Játék (duplázásos teknikát alkalmazva) programrész
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . fügvényei
. . . . . .
8 8 10 16 17 21 24
. . . . . . . . . . . .
26 26 26 26 26 26 26 27 27 27 28 29 29
4. Összefoglalás
31
Irodalomjegyzék
33
Adathordozó használati útmutató
34
5
1. fejezet Bevezetés Szakdolgozatom a matematika tudományának számomra egyik legérdekesebb paradoxonjával a szentpétervári paradoxonnal foglalkozik. A paradoxon szó jelentése, állítások egy olyan halmaza, amelyek látszólag ellentmondásra vezetnek, vagy a józan észnek ellentmondó következtetés vonható le belőlük, valamint a mögöttük megbujó kétértelműségek következtetési hibák és ki nem mondott, hibás feltételezések tudatosodása számos tudományos, filozófiai és matematikai felfedezéshez vezettek. Igen jelentős matematikusok foglalkoztak a szentpétervári problémával, mint például (II.) Nicolaus, Buffon, Feller és még lehetne folytatni a felsorolást. Ennek eredményeként a paradoxon feloldására több, érdekes megoldás született, amelyek kidolgozása során az eredmények alkalmazási köre egyre bővült. A valószínűségszámítás iránti érdeklődésem már gimnáziumi éveim során elkezdődött és az egyetemi éveim alatt ez az érdeklődés csak fokozódott, hiszen további fogalmakkal is megismerkedtem, mint például a várható érték, szórás vagy a nagy számok törvénye. Ezért választottam a szakdolgozatom témájaként a szentpétervári paradoxont, amely lényegében egy valószínűségszámítási paradoxon. A szentpétervári paradoxonról szóló első cikk az 1700-as évek elején a Pétervári Tudományos Akadémia folyóiratában jelent meg. A cikket Daniel Bernaulli írta, de a paradoxon valójában már korábban megszületett, mégpedig Daniel Bernaulli unokabátyjának, Nicolaus Bernaulli nak 1713. szeptember 9-én Pierre Montmort-hoz írt levelében. A szakdolgozatom három fejezetből áll. Az első fejezetben a paradoxon létrejöttének és fejlődésének ismertetése után a hozzá szorosan kapcsolódó leghosszabb szériák vizsgálatával foglalkozom és a hozzá kötődő eredményeket tárgyalom különböző esetekben. Minden egyes főbb témakör tartalmaz program futási eredményeket, amelyek képek formájában kerültek a dolgozatba. A második fejezetben az általam MATLAB környezetben elkészített programrészek fejlesztői dokumentációja található meg. A fejlesztői dokumnetációban a program célját, a benne található függvényeket ismertetem. Ez a fejezet a felhasználói dokumentációt nem tartalmazza, utóbbi a CD mellékleten kapott helyet. Az utolsó fejezetben az egyes témakörök főbb gondolatait emelem ki, valamint a szakdolgozat elkészítése során milyen nehézségekbe ütköztem.
6
Végül szeretnék köszönetet mondani témavezetőmnek: Dr. Karácsony Zsoltnak, aki tárgyi tudásán kívül, szakirodalommal és technikai tanáccsal is ellátott.
„A kutató munka a Miskolci Egyetem stratégiai kutatási területén működő Fenntartható Természeti Erőforrás Gazdálkodás Kiválósági Központ / Alkalmazott Anyagtudomány és Nanotechnológia Kiválósági Központ / Mechatronikai és Logisztikai Kiválósági Központ / Innovációs Gépészeti Tervezés és Technológiák Kiválósági Központ keretében valósult meg.” 7
2. fejezet A szentpétervári paradoxon 2.1. A paradoxon leírása A szentpétervári paradoxon egy játékból, illetve annak vizsgálatából született meg. A játékban két szereplő vesz részt Péter (aki a bankár szerepét játsza) és Pál. A paradoxon megfogalmazását Csörgő Sándor [1] cikkéből idézem. Péter addig dobál egy szabályos pénzérmét, amíg az fej nem lesz, és 2k dukátot (vagy forintot, vagy dollárt, vagy eurót, vagy bármilyen pénznem) ad Pálnak, ha az első fej a k-dik dobásra jelenik meg, k = 1, 2, . . . . Ez alapján felvetődik az a kérdés, hogy mekkora részvétlei díjat fizessen Pál a játékért, hogy a játék igazságos legyen? Ez tehát a szentpétervári paradoxon, amely évszázadokon át foglalkoztatta nemcsak a matematika tudósait, hanem később közgazdászokat, pszichológusokat és egyéb más tudományterület művelőit is. Igazságos játékon azt értjük, hogy egyik játékos sem gazdagodhat meg a másik rovására. Tehát, ha X jelöli Pál nyereményét, akkor X lehetséges értékei 2, 4, 8, 16, 32, . . ., vagyis a 21 , 22 , 23 , 24 , 25 , . . . számok, mindig duplázódva a következő kísérletre ha adott dobásig nem jön ki fej és bármely k ∈ N esetén a P{X = 2k } valószínűség annak a valószínűsége, hogy egymásután (k − 1)-szer írást dob Péter és végül k-adikra fejet, te( )k hát P{X = 2k } = 21 , feltéve természetesen, hogy a dobások függetlenek egymástól. ∞ ∞ ∑ ∑ Ez így teljesen megállja a helyét, hiszen P{X = 2k } = 2−k = 1, ami azt jelenti, k=1
k=1
hogy a játék véges számú lépésben véget fog érni majdnem biztosan, azaz 1 valószínűséggel. Továbbá Pál nyereménye is majdnem biztosan véges lesz. Péter (a bankár) úgy gondolja, hogy Pálnak végtelen sok dukátot kell befizetnie, mert végtelen nagy a várható nyereményösszege is. Vagyis X várható értéke E(X) =
∞ ∑ k=1
2 P{X = 2 } = k
k
∞ ∑
1 = ∞.
k=1
Pál azonban úgy vélekedik erről, hogy ez azért túlzás lenne, mert tetszőleges x ≥ 2 esetén, annak a valószínűsége, hogy a nyereménye legfeljebb x lesz: ( )[log2 x] [log2 x] ( )k [log2 x]−1 ( )j ∑ 1 ∑ 1 1 ∑ 1 1 = = =1− , P{X ≤ x} = k 2 2 2 2 2 k j=0 k=1 k:2 ≤x
ahol [y] jelenti az y szám egészrészét, vagyis [y] = max{j ∈ Z : j ≤ y}. Tehát X nyereményének (jobbról folytonos) eloszlásfüggvénye a következő: 8
{ F (x) = P{X ≤ x} =
, ha x < 2,
0 −[log2 x]
1−2
, ha x ≥ 2.
Tehát várhatóan végtelen nagy lesz a nyereménye, így mivel, P{X > x} = 2−[log2 x] , vagyis a nyeremény kis eséllyel fogja meghaladni az x ≥ 2 össszegnél csak egy kicsivel is nagyobb összeget. Például egy 40 dukátnál nagyobb nyeremény valószínűségére, azt 1 kapjuk, hogy P{X > 40} = 32 = 0, 03125, hameg Pál ettől sokkal több dukátot szeretne nyerni akkor látja, hogy ennek a valószínűsége P{X > 32000} = 2−14 ≈ 0, 00006. Ezért, még egy elég nagy véges összeget is félve kockáztatna Pál, nem beszélve végtelen nagy összeget. (Ráadásul amúgy se rendelkezik végtelen sok dukáttal). Mint, ahogy Nicolaus Bernaulli 1728. augusztus 27-én írta unokaöccsének, Daniel Bernaullinak: „még a féleszű ember is eladná a játékhoz való jogát negyven dukátért”. Nicolaus fentebb említett kijelentése, megragadta a figyelmem és ennek hatására elkészítettem egy olyan MATLAB programot, amely megbecsüli, hogy mennyi egy játék igazságos ára. Buffon szerint, ha n játékot játszunk, akkor ennek a részvételi díja n · log2 n, vagyis egy játék ára log2 n. Tehát, ha 2048 játékot játszunk, akkor ennek a díja egy játékra log2 2048 = 11. Az alábbi ábra a program által adott eredményeket mutatja 2048 játékra 50, 100, 1000, 10000, 50000, 100000 ismétlés számra.
2.1. ábra. Egy játék becsült ára Látható a fenti ábrán, hogy 2048 játék esetén az egy játékra eső dukát díja 11 körül ingadozik. A program a következőképpen számol: először is az egyszerűség kedvéért legyen most az ismétlés számunk kettő és most csak 10 játékot akarunk játszani. Tehát egy 10 hosszúságú 0-ákból és 1-ekből álló sorozatot, ahol a 0 jelöli a fejet és az 1 az írást. Legyen az első sorozat a {1, 1, 0, 1, 1, 0, 0, 1, 1, 1} a második sorozat pedig a {0, 1, 1, 0, 1, 0, 0, 1, 1, 1}. Most pedig vizsgáljuk meg az első sorozatot a játékos nyereményeinek a szempontjából. A következő {0, 0, 8, 0, 0, 8, 2, 0, 0, 0} sorozat mutatja a játékos rész nyereményeit (a 0-k jelölik azt amikor nem nyer semmit). Tehát, mivel első két alkalommal írás volt és a fej a harmadik dobásra következett be, ezért Pál első nyereménye 8, a második nyereménye ismét 8, hiszen fej ismét csak harmadik dobásra jelent meg és végül kettőt nyer. Összeadva Pál résznyereményeit megkapjuk, hogy 8+8+2=18, ezt elosztva a játék számával, azaz 10-el megkapjuk egy játék részvételi = 1, 8. Ez a szám az első részeredményünk. Ugyan ezt az díját az első esetre, vagyis 18 10 elvet követve a második sorozatnál is hasonlóképpen járunk el, így azt kapjuk, hogy a játékos résznyereményei {2, 0, 0, 8, 0, 4, 2, 0, 0, 0}, ezek összege 2 + 8 + 4 + 2 = 16 9
2.2. A paradoxon történeti áttekintése és végül a második esetben a játék ára 16 = 1, 6, ami a második részeredményünk. A 10 rész eredményeket összeadva és elosztva az ismétlés számával, ami jelen esetünkben 2 = 1, 7. A 2.1. ábrán látható legkisebb megkapjuk egy játék igazságos árát, azaz 1,8+1,6 2 illetve legnagyobb nyeremény összege, az ismétlések során kapott össszeg nyeremények közül a legkisebb illetve a legnagyobb. A mi példánk esetében a legkisebb nyeremény összege a 16, a legnagyobb nyeremény összege pedig 18. Természetesen az ismétlés szám növelésével jobb közelítő eredményt kapunk. Buffon szerint 10 játék esetén egy játék igazságos ára log2 10 = 3, 3219, most pedig nézzük a program által adott eredményeket, amelyet a lenti ábra mutat.
2.2. A paradoxon történeti áttekintése A paradoxon eredetének történetét és a témában elért fontos eredményeket vázlatosan fogom ismertetni, bővebben megtalálható [1]. A több híres tudóssal is büszkélkedő Bernoulli családnak nagy szerepe volt a paradoxon felismerésében, a megoldáskeresésben és ezek másokkal való megismertetésében. A probléma gyökerei azonban korábbra nyúlnak vissza. A tudománytörténészek úgy tartják, hogy a valószínűségszámítás Blaise Pascal és Pierre de Fermat híres levelezésével született meg 1654-ben. Levelezésükben lényegében a kockázáshoz és egyéb játékokhoz kapcsolódó problémákat, feladatokat („pontosztozkodási probléma” ill. „de Méré lovag problémája”), tárgyalnak és oldanak meg, amelyben sikerült lefektetniük a valószínűségszámítás alappilléreit. Ezekre és ezek kiegészítéseire épült Huygens appendixe, az első nyomtatott munka ebben a témában, amely fél évszázadra meghatározóvá vált. A tárgy e kezdeti időszakában a várható érték sokkal nagyobb jelentőségű fogalom volt, mint a legfeljebb intuitív szinten jelen lévő valószínűség fogalma. Szövegkörnyezettől függően a latin „æqutias” szó jelenthetett egyenlőséget, igazságosságot vagy részrehajlás nélküli részesedést is. A korabeli klasszikus matematikai kérdéseket általában a fizikai problémák motiválták, ezzel szemben a valószínűségszámítási legelső paradoxonokat a széles körben elterjedt szerencsejátékok szülték. A tárgy fejlődésében a Bernoulliak neve kiemelkedő szerepet játszik. Jacob és az öccse Johannes, aki tanítványa volt bátyjának rövid időn bleül egymás riválisaivá váltak. A köztük lévő rivalizálás odáig fajult, hogy Jacobnak az Ars Conjectandi című könyve csak halála után 8 évvel, 1713-ban jelent meg. Kettőjük között született Nicolaus testvérük, aki szakmáját tekintve festőművész volt és az ő fia (szintén Nicolaus), a közös unokaöccs adta ki végül is a könyvet. (II.) Nicolaus Bernoulli az, - matematika, jogi és filozófia professzor is volt -, akinek a nevéhez a paradoxon felvetése fűződik. Először 1713. szeptember 9-én, Pierre Montmortnak írott levelében szól a paradoxonról. 10
2.2. A paradoxon történeti áttekintése A probléma itt még az első hatosig történő kockadobálás formájában szerepel, amelyre a következő megfogalmazást adja: „A fizet B-nek 1 koronát, ha a szabályos kockával dobva az első dobásra 6-ost sikerülni dobni. 2 koronát fizet, ha a második dobásra jön ki 6-os, 3 koronát, ha a harmadikra és így tovább. Kérdése, mekkora lesz B várható nyereménye? Mi történik akkor ha az A által fizetett összegek rendre nem 1, 2, 3, . . . korona, hanem mondjuk 1, 2, 4, 8, . . . vagy 1, 3, 9, 27, . . . vagy mondjuk 1, 4, 16, 64 . . . korona? ”. Levelezőtársát nem igazán foglalkoztatta a probléma (talán meg se értette igazán), a következőt válaszolta Nicolausnak: „Senki sincs, aki nagyobb szakértelemmel tudna a problémával foglalkozni, mint Nicolaus.” Viszont levelezésüket megjelenteti az Essay d’Analyse sur les Jeux de Hazard című könyvének 1713-ban megjelent második kiadásában, így a kor tudósai értesülhettek a feladatról. Ennek hatására kapcsolódik be Gabriel Cramer is a kutatásba. Az első lépésként az eredeti problémát átfogalmazza kockadobálásról érmedobálásra, így valójában a paradoxon ma ismert megfogalmazása tőle származik. (Természetesen az első hatosig történő kockadobálásból eredő bajok ugyanazok mint akkor, ha pénzt dobálunk.) A megoldásra vonatkozóan két ötlettel állt elő. Az első szerint bármilyen jóérzésű embernek ugyanannyi örömet okoz egy kb. 20 milliós összeg megnyerése, mint egy ennél nagyobb összegé. Mivel 224 = 16.777.216, így a játék értéke szerinte 24 ∑ 2k k=1
2k
+
∞ ∑ 224 = 24 + 1 = 25. k 2 k=25
Általánosan megfogalmazva nagy k ∈ N esetén egy 2k -nál nagyobb összeg sem okoz nagyobb örömet, mint a 2k , így a méltányos összeg a következő formulával adódik ∞ ∞ ( )m ∑ 2k 1∑ 1 + =k+ = k + 1. 2j j=k+1 2j 2 m=0 2
k ∑ 2j j=1
A másik ötletében is szerepel, hogy nagy nyereménynél az összeg növekedésével nem egyenesen arányos az általa okozott örömérzet. Cramer négyzetgyökös összefüggést feltételezett, vagyis egy x összeg örömértéke egyenlő az x négyzetgyökével. Másrészt a „a játék értékének olyan összegnek kell lenni, amelynek elvesztésével okozott fájdalom ugyanannyi, mint az elnyerésével szerzett öröm morális várható értéke. Így a játék értéke az alábbi képlettel adható meg: [ ∞ √ ]2 [ )j ]2 ∞ ( ∑ 2k √ √ 2 2 1 ∑ 1 √ = √ [E( X)] = = [ 2 + 1] . k 2 2 j=0 2 k=1 Ezek alapján a Cramer által meghatározott összeg a játékba való belépéshez 5,8 vagy kerekítve 6 forint lenne. Cramer ötletei viszont nem nyerték el Nicolaus tetszését, ezért írt Szentpétervárra unokatestvérének, Danielnek, aki Johannesnek a fia volt. Levelezéseik után Daniel a szentpétervári akadémiára benyújtott dolgozatában (a Commentarii 1730-1731-es kötetében, amely csak 1738-ban jelent meg), a Crameréhez hasonló megoldást ad, amelyhez megjegyzésként hozzáteszi Nicolaus kritikáit is. (Sokan tévesen azt gondolják, hogy a paradoxon innen kapta a nevét. Később látni fogjuk, hogy más tényező játszott sze-
11
2.2. A paradoxon történeti áttekintése repet a névadásban.) Daniel Bernoulli felhasználva és tovább fejlesztve Cramer gondolatait, bevezeti a „utilitas”, hasznosság fogalmát, amellyel a közgazdaságtan és a pszichológia is elkezd foglalkozni. Úgy gondolja, hogy egy x összeg dx-szel való növekedése csak du = b·dx x hasznosság (örömérzet) növekedéssel jár, ahol b > 0 valamilyen konstans. (Minél több pénze van a játékosnak, annál kisebb egy kis növekedés feletti öröme.) Tehát, ha egy játékosnak eredetileg ( α+x ) α > 0 forintja van, egy x > 0 nyeremény morális haszna tehát várható haszna a játékból u(x) = b · ln α . Ebből következik, hogy Pál morálisan ( ( α+X )) nem az E(X) = ∞, hanem E(X) = E(u(X)) = b · E log α . Ez az átlagos haszon viszont a következőképpen számolható. Az x nyeremény 2k alakú összegeket jelent, melyekhez 2−k valószínűségek tartoznak. Felhasználva a logaritmus azonosságait valamint, ∞ ∑ hogy 2−k = 1, kapjuk, hogy az átlagos haszon a következő alakban írható. k=1 (∞ ) ∞ ∑ ∏ −k ln(α + 2k ) − ln α 2 E(X) = b = b ln (α + 2k ) − b ln α. k 2 k=1 k=1 ( ) Ez viszont megegyezik a morális haszonnal, (u(x) = b · ln α+x kifejezéssel) amiből α rendezéssel azt kapjuk, hogy x(α) =
∞ ∏
2 −k
(α + 2k )
− α,
k=1
ahol tehát x(α) az eredeti α tőke, morális értékének játékból hozzáadódó növekedését jelenti. Néhány kezdőtőke-nagyságra az alábbi értékek adódnak. Ha a kezdőtőke α = 0, akkor 4 forint (felmerül az a kérdés, hogy ha nincs kezdőtőkéje, akkor miből fizetné be a 4 forintot), míg például 1000 forint kezdőtőke esetén is csak 11 forint a játék díja. Daniel Bernoulli a matematikai problémát pszichológiai és gazdasági síkra is terelte, feltételezve, hogy a különböző gazdasági és pszichológiai magatartásokban szintén törvények uralkodnak, amelyek esetleg különböznek a matematikában megfogalmazottaktól. Hasonló megoldásra jutott Euler is, de mivel nem akart a Bernoulliak ügyeibe beavatkozni, - hiszen Daniel apja volt a tanára és Daniel szerezte neki a szentpétervári munkahelyét - eredményeit nem hozta nyílvánosságra. Halála után 81 évvel jelent csak meg a témával kapcsolatos dolgozata. Nicolaus nem volt megelégedve Daniel megközelítésével sem, amint kritikájában is írja, a morális várhatóság „nem az egyenlőségnek és igazságosságnak megfelelően értékeli ki minden játékos esélyét egyaránt”. Az ő meglátása szerint mindenki számára egyformán k forintot kell, hogy érjen a játék, a játékos általános diszpozíciójától függetlenül. De mekkora legyen ez a k? Nicolaus elfogadhatóbb megoldásnak tartja azt, ha azt mondjuk, hogy nagy k ∈ N esetén már olyan kicsi a hozzá tartozó valószínűség, hogy gyakorlatilag 0-nak tekinthető. De ki mondja meg, hogy mekkora ez a kis valószínűség, amitől már nem foglalkozunk vele? Mondhatjuk, hogy pl. a k = 200-hoz olyan nagy pénzösszeg és olyan kicsi valószínűség tartozik, ami már elképzelhetetlen, de ez nem tűnik igazán egzakt megoldásnak. A probléma megoldására vonatkozóan a Bernoulliak részéről további eredmények nem születtek. A kérdés a francia forradalom idején 1754-ben került újra középpontba d’Alembert Fej vagy Írás című cikkében, amely a francia Enciklopédiában jelent meg. Ezután hosszú ideig foglalkoztatja a téma és legalább hat alkalommal tárgyalja a problémát. Mivel 12
2.2. A paradoxon történeti áttekintése Daniel Bernoullival nem voltak baráti viszonyban, ezért a paradoxonról írott munkáiban egyetlen egyszer sem említi a Bernoulli nevet. A problémát először körülményesen: „probleme proposé dans le Tome V des Mémoires de l’académie de Petersbourg” néven említi, majd a továbbiakban elhagy egy-egy szót (feltehetőleg nem tudatosan tette), míg végül kialakul a problême de Petersbourg elnevezés. Többek érdeklődését felkelti munkáival, de említésre méltó eredmény nem születik. Így a paradoxon elnevezése sokkal valószínűbben innen ered. A megoldással kapcsolatban Lagrange-nak írott levelében sajnálattal valja be, hogy „a pétervári probléma megoldása számomra a jelenleg ismert fogalomkörben lehetetlennek tűnik”. Többek érdeklődését is felkelti munkái, de érdemleges eredmény nem születik. Megemlíthetjük pédául Whitworth érdekes elgongondolását a probléma megoldásával kapcsolatban. Szerinte nem egy állandó összeget, hanem minden játékban az adott, aktuális tőkének egy fix hányadát kell kifizetni, de ezzel együtt azt is belátja, hogy megoldása nem tökéletes. Érdemes még megemlíteni Fontaine-t, aki először veszi figyelembe Pétert, a bankost, akiről eddig senki sem nyilatkozott, a következő kérdéseket teszi fel: mi van akkor, ha már nem akarnak ennyit adni neki, ha neki sincs végtelen dukátja, hogy akármilyen nagy nyereményeket kifizethessen? A különböző megoldások legfőbb hibáit az okozta, hogy a valószínűség matematikai törvényeit megpróbálták egyedi véletlen eseményekre alkalmazni. A törvényekből arra akartak következtetni, hogy mi fog történni legközelebb, egy teljesen konkrét egyedi esetben. A nagy számok egy kicsit is általánosabb törvényének intuitív jelentése nem volt jelen még a matematikusok gondolkodásában sem. Egyedül a francia Marie-Jean-Antoine-Nicolas Caritat de Condorcet márki, a neves matematikus, enciklopédista és republikánus volt az, aki ráérzett a probléma lényegére. Szerinte Pálnak végtelen sok játékot kellene játszania ahhoz, hogy végtelen várható értéke realizálódjon. „A probléma maga nem értelmes, hanem hasonnemű még értelmes kérdések limesze.” Amikor n játékot játszunk, akkor a válaszunk függni fog n-től, így a kérdés az, hogy milyen n-re lehet a két játékos egyenlőségét elérni. Ez volt az egyedüli jó irány vonal, ennek ellenére kortársai mégis figyelmen kívül hagyták. A következő matematikus, aki eredményesen foglalkozott a kérdéssel, Georges-Louis Lecrerc de Buffon. Ő az első, aki (lejegyzetten) a játékot ténylegesen lejátszatta egy gyerekkel 2048-szor. Ekkor Pál összes nyereménye 20104 forint volt, amiből egy játékra átlagosan 20104/2048 ≈ 9, 82 vagyis körülbelül 10 forint jutott. Ez Buffon szerint „érvényes és jó, mivel nagyszámú kísérletre alapul, továbbá megyegyezik egy olyan gondolatmenet eredményével is, amely matematikai és kikezdhetetlen”. Tehát matematikailag is alátámasztható. A 2048 játék során észlelt eredményeket mutatja az alábbi táblázat: Az első fej (k)
1
2
3
4
5
6
7
8
9
A gyakorisága
1061
494
232
137
56
29
25
8
6
A nyeremény (2k )
2
4
8
16
32
64
128
256
512
2.1. táblázat. Buffon által lejátszatott játék adatai Az adatainkat nézve levonható az a következtetés, hogy annak a bekövetkezése, hogy csak a sokadik dobásra kapunk először fejet, egyre kevésbé várható. Buffon matematikai levezetésével arra a következtetésre jutott, hogy n játékért n log2 n forint jár, vagyis, ha n játékot játszunk, játékonként log2 n díjat kell fizetnünk. A gondolatme13
2.2. A paradoxon történeti áttekintése nete a következő volt. Ha n = 2k játékot játszunk, akkor az esetek felében (vagyis 2k−1 ) esetben lesz elsőre fej. A nyeremény minden esetben 2 forint, így ez összesen 2 · 2k−1 = 2k forintot eredményez. 2k−2 esetben a második dobásra lesz első fej, ez 4 forintjával 22 · 2k−2 = 2k forintot ad szintén. A gondolatmenetet folytatva és felhasználva, hogy 2k−1 + 2k−2 + · · · + 2 + 1 = 2k − 1, marad még egy játék, ami folytatódhat, de ennek már kicsi a valószínűsége (főleg, ha n nagy). Összesen tehát n játék lejátszása után kapunk k · 2k forintot, ami (felhasználva az n = 2k kifejezést,) egyenlő n · log2 n. Ez azt jelenti, hogy játékonként log2 n forint nyeremény lesz. Méltányos játéknál tehát tekinthető ez az összeg a játék játékonkénti díjának is. Eszerint a 2048 játék játszásakor log2 2048 = 11 forint fizetendő játékonként, ami a kísérletével 1/11 pontossággal megegyezik. Saját maga észreveszi, hogy ha sok, pl. 1048575 játékot játszunk, akkor az összeg 20 körülire jön ki, de mivel ennyi játék lejátszása kb. 30 évig tartana, így szerinte ezzel a realitás szintjén nem kell foglalkozni. Buffon szerint tehát 10 forint az az ár, melyet játékonként fizetni kell, ha igazságosak akarunk lenni. A Felvilágosodás korának utolsó nagy matematikusa, Pierre Simon de Laplace, aki a paradoxon megoldásához nem jutott közelebb, de egyéb eredményei, melyet A valószínűségek analitikus elmélete című művében közölt, nagy technikai előrelépést jelentettek. Összegezte mindazt, amit a tárgyban tudott arról, hogy adott feltételek mellett valószínűségeket, várható értékeket és eloszlásokat hogyan lehet számolni és közelíteni. A paradoxon tekintetében számottevő új eredmény sokáig nem születik, a már meglévő eredményeket próbálják fejlesztgetni, bizonyítani. Többen is azzal próbálkoznak, hogy valamilyen ésszerű, emberi léptékű határok közé akarják szorítani a megnyerhető összeget pl. úgy, hogy feltételezhetjük, hogy a banknak nincs végtelen sok pénze. Módosítsuk pl. a játékszabályt úgy, hogy a megnyerhető összeg maximum 1 millió forint (akárhányadik dobásra is kapjuk az első fejet, vagyis még ha több járna a játékosnak akkor is csak ennyit kap). Mivel a 220 már több, mint 1 millió, így a nyeremény várható értéke a következő lesz. ( ) 1 1 1 1 1 19 · 2 + · 4 + · · · + 19 · 2 + + + . . . · 106 ≈ 21, 4768 . . . 2 4 2 220 221 Ezek szerint 22 forintos árral még kicsit jól is jár a bank. 1872-ben A Budget of Paradoxes című könyvében de Morgan beszámol arról, hogy ő is lejátszatta a játékot (Buffonhoz hasonlóan) és mint írja, arra a következtetésre jutott, hogy „Ha Buffon ezerszer többször próbálta volna, akkor az eredmény nem csak több lett volna, de játékonként több. A nagyobb háló nem csak több halat, hanem több fajta halat fogott volna, és kétmillió játékban szt is várhatnánk, hogy néhány esetben a fej huszadik dobásig sem mutatkozik.” Többen is a Buffon féle gondolatmenetet követik, például Lupton szintén az n játékért n log2 n forint megoldást tartja helyesnek. A Daniel Bernoulli-féle utilitási vonal két ágra szakad. Az egyik Fechner, a kísérleti pszichológia megalapítója nevéhez fűződik. Felállította az ún. Weber-Fechner féle empirikus törvényt, mely szerint az S stimulus által kiváltott R reakció nagysága R = C · ln S, ahol C a vizsgált érzékeléstől függő pozitív konstans. A másik vonal az elméleti közgazdaságtan területén hozott új eredményeket. Menger vizsgálatai az u(x) hasznosság-függvényra vonatkozóan - melyben belátta, hogy az u(x) = C · ln x nem jó - vezették el Neumann Jánost a hasznosság axiomatizálásáig, amely a modern közgazdaságelmélet egyik pilléréhez vezetett. Számos kísérlet születik az u(x) ésszerű megválasztására. Nagyon sok népszerű-tudományos mű is megjelenik, boncolgatva a paradoxont különböző oldalairól. 14
2.2. A paradoxon történeti áttekintése
A következő nagy áttörés Feller 1945-ös eredményei szolgáltatták. Az már korábban is egyértelmű volt, hogy a játszmánként fix összeg nem lehet jó, hiszen akármilyen nagy is ez az összeg, a bank mindig rosszul járna, hiszen a nyeremények várható értéke végtelen nagy. A részvételi díj tehát nem egy konstans, hanem n növekedésével nő, mégpedig a többek által megadott log2 n kapcsolat szerint. Feller szintén erre a megállapításra jut vizsgálataiban. Ha X1 , X2 , . . . Pál nyereményei az első, második, . . . pétervári játékban, és Sn = X1 + X2 + · · · + Xn Pál össznyereménye az n játék során, akkor az X várható értékének végességét feltételezve, egy játékot akkor nevezünk igazságosnak, ha nagy n esetén az Sn össznyeremény a várható érték n-szerese körüli lesz. Vagyis nE(X) ≈ Sn , amiből azt kapjuk, hogy a játékonkénti nyeremény a várható érték körüli lesz, vagyis nagy n-re Snn ≈ E(X), illetve Snn → E(X) majdnem biztosan. Feller belátja, hogy ha még X szórása is véges, akkor a centrális határeloszlás tétele miatt: 1 ← P(Sn − nE(X) < 0), 2 vagyis nagy n esetén az esetek kb. felében az egyik játékos, míg a másik felében a másik nyer és a nyeremények is körülbelül szimmetrikusan oszlanának el. Feller belátSn ja, hogy n log sztochasztikusan tart 1-hez, amiből következik, hogy n játékért n log2 n 2n összeg a méltányos. Sajnos azonban a problémában sem a szórás, de még a várható érték sem véges, éppen ez volt a gond eddig is. P(Sn − nE(X) > 0) →
Az előző tételt és Feller dolgozatát felhasználva Steinhaus teszi meg a következő lépést. A következőt írja: „a paradoxon feloldásához nem egy egyedi játékot, hanem játékok egy sorozatát kell nézni ”. Egy determinisztikus sorozattal próbálja imitálni Pál véletlen nyereményeit. Ehhez vegyünk először 2-eseknek és üres helyeknek egy alternáló sorozatát: 2_2_2_2_2_2_2_2_2_2_2_2_2_2_2 . . . Most írjunk az első, majd minden második üres helyre 4-est: 242_242_242_242_242_242_242_242 . . . Majd hasonlóan írjunk 8-asokat, aztán 16-osokat és így tovább: 242824216242824232242824216242824 . . . Ezt azért gondolhatjuk helyesnek, mert a játékban az esetek felében (mondjuk minden második esetben) 2 forint a nyeremény, a megmaradtak felében 4, az ezután megmaradtak felében 8, és így tovább. Felírva ezen sorozat n-edik empirikus eloszlásfüggvényét, kiderül, hogy ez igen gyorsan (egyenletesen) tart a szentpétervári eloszlásfüggvényhez. Ha ♯A-val jelöljük az A halmaz elemeinek a számát, akkor a Steinhaus sorozat n-edik eloszlásfüggvénye a következő: ♯{xj ≤ x|1 ≤ j ≤ n} . n Ez a függvény tehát azt fogja megmutatni minden valós x-nél, hogy a sorozat első n elemének hányad része nem nagyobb, mint x. Ha F (x) a szentpétervári játékban Fn (x) =
15
2.3. A leghosszabb szériák vizsgálata szereplő nyeremények eloszlásfüggvénye, akkor Steinhaus törvénye a következő formát ölti: Dn∗ = sup |Fn (x) − F (x)| → 0. x∈R
Vagyis Steinhaus szerint a játék akkor lesz igazságos, ha az egyes játszmákért a fenti sorozat elemei szerinti összegeket fizetjük. Ez azt jelenti, hogy ha Fn (x) jelöli a legfeljebb x nagyságú befizetések relatív gyakoriságait, akkor Fn (x) annak a valószínűségéhez konvergál, hogy Péter (a bankos) legfeljebb x nagyságú összeget fizet ki. A további eredmények tekintetében Csörgő Sándor, a korán elhunyt szegedi matematikus és csapata dolgozott tovább a kérdésen nagy sikerrel. Az alábbi tételeket sikerült bebizonyítaniuk: lim inf
n→∞
Sn Sn = 1 lim sup = ∞ majdnem biztosan. n→∞ n · log2 n n · log2 n
Ez azt jelenti, hogy Péter halmozott nyereményeinek Sn sorozata determinisztikus sorozatokkal nem egyensúlyozható ki úgy, hogy véges pozitív határértéket kapjunk majdnem biztosan. Eszerint egyik díjsorozat sem lehet elég nagy. Ennek oka az időnként (nagyon kis valószínűséggel ugyan, de mégis) előforduló nagyon nagy nyeremény. Tekintsük n játék esetén Pál nyereményeinek nagyság szerinti sorbarendezését (rendezett mintáját) Xn,1 ≤ · · · ≤ Xn,n . Rögzített m esetén n > m játékot játszva Pál nyereménye n−m ∑ Xn,j vagyis Pál lemond az elvileg létező m legnagyobb nyeremélegyen Sn (m) = j=1
nyéről (Xn,n + · · · + Xn,n−m+1 forintról) és így az eddigi Sn forint helyett Sn (m) forintot kap n játszmáért. Azt gondolnánk, hogy minél nagyobb az m, annál kevesebbet kell fizetnie Sn (m)-ért, mint korábban Sn -ért, azonban Csörgő és Simons bebizonyították, hogy Sn (m) → 1 majdnem biztosan minden rögzített m ∈ N esetén. n log2 n Tehát a nagy számok törvényei csak annyit mondanak, hogy az Sn és az Sn (m) véletlen nyeremények értéke is n log2 n körül lesz. A megoldáshoz tehát Sn eloszlásának a megismerése fog közelebb vinni. Csörgőék azt is belátták, hogy határeloszlás nincs, valamint összetartás tételére vonatkozóan további vizsgálatokat is végeztek. Továbbá megjegyezték, hogy n játéknál átlagosan log2 n forint játékonként még akkor is kevés, ha Pál lemond a legnagyobb nyereményéről, de már túl sok, ha a legnagyobb kettőről mondd le.
2.3. A leghosszabb szériák vizsgálata Szakdolgozatom legfontosabb témaköre a leghosszabb szériák vizsgálata, amely feldolgozásában [2], [3] és [4] forrásanyagok szolgáltak segítségül. Első lépésként vizsgáljuk meg azt, hogy mit értünk leghosszabb szérián, hiszen ezen a téren nem alakult ki egységes szóhasználat. Vannak egyes szerzők, akik leghosszabb futamnak vagy sikersorozatnak, vagy egyszerűen leghosszabb sorozatnak nevezik egy adott véletlen kísérletsorozatban az egymást követő azonos jelek leghosszabb előfordulását. Dolgozatomban az érmedobás kísérletben az egymás után következő - vagyis írással meg nem szakított 16
2.3. A leghosszabb szériák vizsgálata fejdobások számának a maximumát leghosszabb fejszériának fogja nevezni. Hasonlóan lehet értelmezni a leghosszabb írásszériát, de itt a fejjel meg nem szakított írásdobások számának maximumát értsük. Beszélhetünk még a leghosszabb bármilyen szériáról, itt az akár fejből, akár írásból előálló, a másik jellel meg nem szakított jelsorozat hosszának a maximumát értsük. Ebben az alfejezetben ismert rekurziós és aszimptotikus tételeket, valamint a szimuláció által szolgáltatta eredményeket fogom összehasonlítani. Ebben a fejezetben a rekurziós eljárásokat hangsúlyozom - hiszen ezek adják a pontos eredményeket - ezért ezeket részletesen bizonyítom. Az aszimptotikus eredmények csak hosszú dobássorozat esetén adnak jó közelítést. A szimulációs eredmények pedig véletlenszerűek, és a dobássorozat nagyon sokszori számítógépes legenerálása esetén közelítik a pontos értéket. A szakdolgozatom kiterjed a szabályos és szabálytalan érme esetére is, valamint mindkétféle érménél vizsgálom a leghosszabb fejszéria és a leghosszabb bármilyen (tiszta fej vagy tiszta írás) széria hosszát is. A szimulációk MATLAB programmal történtek 20.000 ismétlést alkalmazva rövid (n = 30, 50), közepesen hosszú (n = 250), hosszú (n = 1000).
2.3.1. Szabályos pénzérme esete Leghosszab fejszéria Mint, ahogy már korábban is említettem, fejszériának nevezzük az egymást követő (tehát írással meg nem szakított) fejek sorozatát. Jelölje Rn a leghosszabb fejszéria nagyságát. Az eloszlásfüggvényünk az ismert definíció alapján: Fn (x) = P(Rn ≤ x). Megjegyzem, hogy Fn (x)-et elegendő nem negatív egész x-ekre megadni (hiszen Fn (x) = 0, ha x < 0; így tehát Fn (x) = Fn ([x]), ha x ≥ 0). Legyen An (x) azon n hosszúságú sorozatok száma, amelyekben a leghosszabb fejszéria nem haladja meg x-et. Szabályos érme esetén egy n elemű sorozatot vizsgálva kapjuk: Fn (x) = P(Rn ≤ x) =
An (x) . 2n
(2.1)
A feladat An (x) értékének meghatározása. Tekintsük először azt az esetet, amikor a leghosszabb fejszéria legfeljebb 3 elemű (x = 3). Ha az n ≤ 3, akkor An (3) = 2n , hiszen minden lehetséges eset megfelel annak a kritériumnak, hogy az egymás utáni fejek száma maximum 3. Az említett esetek a következők: ha n = 0, akkor a 0 hosszúságú sorozatban 0 a leghosszabb fejszéria hossza, ez 1 eset. Ha n = 1, akkor a lehetséges mindkét „sorozat” olyan, hogy a leghosszabb fejszéria legfeljebb 3. Amikor írást dobunk, akkor 0 a fejszéria hossza, illetve ha fejet dobunk , akkor 1 a fejszéria hossza. Ha n = 2, akkor a lehetséges sorozatunk 4 féle lehet (IF, II, FF, FI), mindegyik esetben a leghosszabb fejszéria hossza kevesebb, mint 3. Végül, ha n = 3, akkor szintén a lehetséges sorozatok mindegyike olyan, hogy benne legfeljebb 3 lehet a leghosszabb fejszéria hossza (III, IFF, IFI, IIF, FFF, FII, FIF, FFI). Ha viszont az n > 3, akkor a számunkra kedvező sorozatok kezdődhetnek a következőképpen: I, FI, FFI, FFFI, és utánuk csak olyan jelsorozat van, amelyben nincs háromnál hosszabb fejszéria. Ennek alapján megkapjuk tehát a következő rekurzív formulát: An (3) = An−1 (3)+An−2 (3)+An−3 (3)+An−4 (3), ha az n > 3. Az An (x) értékeire Schilling az alábbi általános rekurziós képletet adja.
17
2.3. A leghosszabb szériák vizsgálata 2.1. tétel. (Schilling, [5])
An (x) =
∑ x An−1−j (x) , ha n > x,
j=0 n
(2.2)
, ha 0 ≤ n ≤ x.
2
Ezt felhasználva An (3)-ra megkapjuk az alábbi táblázat eredményeit: n
0
1
2
3
4
5
6
7
8
...
An (3)
1
2
4
8
15
29
56
108
208
...
2.2. megjegyzés. Ha megnézzük An (1) értékeit, vagyis azon n elemű sorozatok számát, melyekben legfeljebb 1 hosszúságú fejszéria van, éppen a Fibonacci-sorozat (azaz a0 = 0, a1 = 1 és an = an−1 + an−2 , ha n ≥ 2) 2-vel eltolt elemeit kapjuk. A krendű Fibonacci számok segítségével pedig kifejezhető An (k), sőt a k-rendű Fibonacci polinomok felhasználásával a szabálytalan pénzérme esete is kezelhető. A leghosszabb fejszéria nagyságának, Rn -nek aszimptotikus viselkedését Földes Antónia 1979-ben publikált alábbi tétele alapján írhatjuk le: 2.3. tétel. (Földes (1979), [6]). Valamennyi egész k esetén ( [ ] ) ) ( ln n ln n P Rn − < k = exp −2−(k+1−{ ln 2 }) + o(1), ln 2 ahol [a] jelöli az egészrészét a-nak és {a} = a − [a], a törtrésze. (Nyílvánvalóan helyett írható log2 n is.)
ln n ln 2
Leghosszabb bármilyen széria hossza Dobjunk fel egy szabályos pénzérmét n-szer, és jelölje Rn′ a leghosszabb bármilyen széria (akár a tiszta fej, akár a tiszta írás) nagyságát. Legyen Bn (x) azon n hosszúságú sorozatok száma, amelyekben a leghosszabb (tetszőleges) széria nem haladja meg x-et. Szabályos érme esetén egy n elemű sorozatot vizsgálva, kapjuk az eloszlásfüggvényt: Bn (x) . (2.3) 2n A következőkben Schilling ötletét használjuk fel. A fej-írás sorozat minden elempárja alatt jelölje A azt, hogy az elempár azonos jelekből áll, illetve K azt, hogy különböző a két jel. Például: Fn′ (x) = P(Rn′ ≤ x) =
F
F A
F A
I K
F K
I K
F K
I K
I A
I A
I A
F K
F A
Az alsó A, K elemekből álló sorozatban a leghosszabb tiszta A sorozat akkor és csak akkor k − 1 hosszúságú, ha fölötte a leghosszabb tiszta széria (fej vagy írás) k 18
2.3. A leghosszabb szériák vizsgálata hosszúságú. Ha a felső sorozat n hosszú, és ebben a leghosszabb széria k elemű, akkor az alsó sorozat n − 1 hosszú, és a leghosszabb A széria k − 1 elemű. Vagyis Bn (x) = 2An−1 (x − 1). (A 2-es szorzó azért kell, mert minden alsó sorozat pontosan 2 (egy eredeti és egy fej-írás cserével kapott második) felső sorozathoz tartozhat.) Ennek felhasználásával kapjuk: Fn′ (x) = P(Rn′ ≤ x) =
Bn (x) 2An−1 (x − 1) An−1 (x − 1) = = = Fn−1 (x − 1). n n 2 2 2n−1
(2.4)
Beláttuk tehát, hogy Fn′ (x) = Fn−1 (x − 1),
(2.5)
vagyis vissza vezettük az esetünket a tiszta fejszéria esetére. Eloszlásfüggvényünk a tiszta fejszériára felírt eloszlásfüggvényből 1-gyel jobbra történő eltolással adódik. A leghosszabb bármilyen széria nagyságának, Rn′ -nek aszimptotikus viselkedésének vizsgálatához Földes Antónia eredményét használjuk fel. (2.3.) és (2.5.) alapján kapjuk: 2.4. tétel. (Földes (1979), [6]). Valamennyi egész k esetén ] ) ( [ ( ) ln(n−1) ln(n − 1) ′ < k = exp −2−(k−{ ln 2 }) + o(1), P Rn − ln 2 ahol [a] jelöli az egészrészét a-nak és {a} = a − [a], a törtrésze. (Nyilvánvalóan itt is ln(n−1) helyett írható log2 (n − 1).) ln 2 Most pedig ezeket az eredményeket hasonlítom össze a szimulációval kapott értékekkel. Az alábbi (2.2.) és (2.3.) lévő grafikonok mutatják a tiszta fejszéria, tiszta írásszéria és a tiszta bármilyen széria eseteket különböző dobáshosszak esetén. Vizsgálatomhoz MATLAB programot használtam 20.000 ismétlésszámmal. Az alkalmazott számítógép paraméterei pedig a következők: INTEL CORE I5 2,3 GHz processzor, 4Gb, DDR3 memória. A következő ábrákon „x” jelöli a rekurzióval kapott eredményeket, az oszlopdiagram pedig a szimulációval kapott eredményeket mutatja, viszont nem szerepelnek rajta az aszimptotikus eredmények mivel a leprogramozása nem volt része a szakdolgozatomnak. A program által szolgáltatott grafikonok eredményeinek helyeségét [2] és a [4] szereplő grafikonokkal hasonlítottam össze, amelyeken már az aszimptotikus eredmények is szerepelnek. Az első grafikon a rövid (n = 50) sorozat eredményeit mutatja leghosszabb fej (bal felső), írás (jobb alsó), bármilyen széria (jobb oldali) esetén, majd a következő grafikon ugyanez csak (n = 1000) dobás sorozatra vonatkozóan. Mindhárom esetre (leghosszabb fej, leghosszabb írás illetve leghosszabb bármilyen széria vizsgálatára) elmondható, hogy kis n esetén a szimulációs eredmények vannak közelebb a rekurzív eredményekhez, az aszimptotikus tételek n növelésével adják a rekurzióhoz közeli, pontosabb eredményeket. Elmondható továbbá az is, hogy kis n esetén a rekurziós algoritmus gyors, n növelésével azonban rohamosan lassul a számítási eljárás. Jól látható tehát, hogy a rekurzió adja a pontos eredményt, de nagy n esetén 19
2.3. A leghosszabb szériák vizsgálata gyakorlatilag nem tudjuk használni, hiszen a futási idők rohamos növekedése gátat szab az alkalmazhatóságnak. Ezekben az esetekben az aszimptotikus tételek szolgáltatják a jól közelítő eredményeket. Az egymás mellett párba állított grafikonokon jól látható a (2.4.)-ben leírt eredmény, miszerint Rn′ az Rn -ből egy 1 egységgel jobbra való eltolással adódik. Tehát a leghosszabb bármilyen széria esete kezelhető, vizsgálható a leghosszabb fejszériára megismert összefüggésekkel a megfelő transzformációval. A következőkben a kis és a nagy n (n = 50 és n = 1000) esetére mutatom a grafikonokat.
2.2. ábra. Leghosszabb szériák, szabályos érme (p = 0.5), rövid sorozat (n = 50)
2.3. ábra. Leghosszabb szériák, szabályos érme (p = 0.5), hosszú sorozat (n = 1000)
20
2.3. A leghosszabb szériák vizsgálata
2.3.2. Szabálytalan pénzérme esete Ebben az esetben a fejdobás valószínűsége, p értéke bármilyen valós szám lehet természetesen a (0, 1) intervallumból. (Speciális esetként magába foglalhatja a szabályos érme esetét is, azaz amikor (p = 0, 5).) Fontos kérdés, hogy a szabálytalanság ténye milyen hatással van a leghosszabb fej-, írás-, illetve leghosszabb bármilyen széria alakulására. Egyértelmű, hogy nem számolhatunk a klasszikus képlettel, hiszen az elemi eseményeink nem azonos valószínűségűek. A továbbiakban jelölje p a fejdobás valószínűségét és q = 1 − p az írás valószínűségét, ahol tehát mindkettő lehet 0,5 eltérő is.
Leghosszabb fejszéria hossza Ebben az esetben is tekintsük először a leghosszabb fejszéria alakulását. Schilling ötletét felhasználva tekintsük azon n hosszúságú fej-írás sorozatokat, amelyekben k db (k) fej van. Ezek közül jelentse Cn (x) azon sorozatok számát, amelyekben legfeljebb x fej következik egymás után, tehát a leghosszabb fejszéria legfeljebb x hosszúságú. Az adott jelöléseket alkalmazva a következő képletet kapjuk az eloszlásfüggvényre: Fn (x) = P (Rn ≤ x) =
n ∑
Cn(k) (x)pk q n−k .
(2.6)
k=0
Cnk (x) értékeire Schilling az alábbi rekurzív formulát adja. 2.5. tétel. (Schilling, [5]) x ∑ (k−j) C (x) , ha x < k < n, j=0 n−1−j (n) Cn(k) (x) = , ha 0 ≤ k ≤ x. k 0 , ha x < k = n.
(2.7)
Mivel a tétel bizonyítása nem bonyolult és hosszú [4] ismertetett bizonyítás alapján vezetem le. (k)
Bizonyítás. Ha x < k = n, akkor egyértelmű, hogy Cn (x) = 0, hiszen ekkor az összes (x-nél több) elem fej, tehát nincs olyan sorozat, ahol legfeljebb x fej van egymás (k) után. Ha 0 ≤ k ≤ x, akkor Cn (x) éppen a binomiális együtthatókat adja, mivel ez pontosan az az eset, amikor az n elem között legfeljebb x fej van és azon eseteket kell összeszámolni, amikor a leghosszabb fejszéria legfeljebb x. Tehát ekkor az összes lehetséges sorrend ilyen tulajdonságú. ( ) Az összes n elemű sorozat száma pedig, amelyben k db fej és n − k db írás van: nk . Ha x < k < n, akkor a 2.7. képlet helyességének belátásához elegendő belátnia a következőket. A sorozatunk kezdődhet j = 0, 1, 2, . . . , x fejjel, utána biztosan van 1 írás, majd olyan sorozat következik, ahol a maradék n−j −1 elem között k − j db fej van úgy, hogy a leghosszabb fejszéria legfeljebb x hosszúságú. F . . F} | .{z j db fej
I
| ...
F
... {z
I
... }
n − j − 1 elem, melyben k − j db fej van úgy, hogy legfeljebb x hosszú a fejszéria
k−j Ezek száma pedig pontosan Cn−1−j (x). Tehát bizonyítottuk a (2.7.)-t.
21
2.3. A leghosszabb szériák vizsgálata A következő tétel Gordon-Schilling-Waterman nevéhez fűződik, amely az aszimptotikus vislelkedésleírására vonatkozik. 2.6. tétel. (Gordon-Schilling-Waterman, [7]) n Legyen µ(n) = − ln , q = 1 − p és legyen W eloszlása a következő: ln p P(W ≤ t) = exp(− exp(−t)). Ekkor t-ben egyenletesen: ([ ] ) W P(Rn − µ(qn) ≤ t) − P + {µ(qn)} − {µ(qn)} ≤ t → 0, − ln p ha n → ∞ és ahol [a] jelenti az egészrészét a-nak és {a} = a − [a] az a törtrésze. Leghosszabb bármilyen széria hossza Mint, ahogy a szabályos pénzérménél is tettük most is vizsgáljuk a leghosszabb bármilyen széria alakulását. Egy szabálytalan pénzérmét feldobva n-szer, jelölje Rn′ a leghosszabb bármilyen széria (akár fej, akár írás) nagyságát. A (2.6.) képlethez hasonlóan Schilling a következő formulát adja: 2.7. tétel. (Schilling, [5]) Fn′ (x)
=
P(Rn′
≤ x) =
n ∑
(k)
C n (x)pk q n−k ,
k=0 (k)
ahol C n (x) jelenti azon n hosszúságú sorozatok számát, amelyben k db fej van, a leghosszabb bármilyen széria hossza legfeljebb x, és ahol alkalmazva az alábbi átjelölést, (k)
C m+k (x) = Cx+1 (m, k), a Cx (m, k) mennyiségek pedig kielégítik a (2.8.) és (2.9.) rekurziókat. Itt Cx (m, k) jelöli azon esetek számát, hogy m egyik és k másik féle tulajdonságú elemet visszatevés nélkül kihúzva nem lesz x hosszúságú széria. Cx (m, k) értékeire Bloom az alábbi két rekurzív képletet adta. 2.8. tétel. (Bloom, [8]) Ha m = k = 0, akkor definíció szerint legyen Ct (0, 0) = 1. Ha m vagy k negatív, akkor pedig definíció szerint Ct (m, k) = 0. Ct (m, k) =
t−1 ∑ i=0
Ct (m − 1, k − i) −
t−1 ∑
Ct (m − t, k − i) + et (m, k),
(2.8)
i=1
ahol tehát Ct (m, k) jelenti az m db piros és k db fekete elem olyan sorbarendezéseinek a számát, ahol nincs t hosszúságú széria (t ≥ 2), valamint , ha m = 0 és 0 ≤ k < t, 1 et (m, k) = −1 , ha m = t és 0 ≤ k < t, 0 , különben.
22
2.3. A leghosszabb szériák vizsgálata 2.9. tétel. (Bloom, [8]) t ≥ 2 esetén Ct (m, k) = Ct (m − 1, k) + Ct (m, k − 1) − Ct (m − t, k − 1)− − Ct (m − 1, k − t) + Ct (m − t, k − t) + e∗t (m, k), , ha m = 0 és 0 ≤ k < t, 1 ahol e∗t (m, k) = −1 , ha m = t és 0 ≤ k < t, 0 , különben.
(2.9)
Peremfeltételeink pedig ugyanazok, mint (2.8.)-nál vagyis: Ha m = k = 0, akkor definíció szerint legyen Ct (0, 0) = 1. Ha m vagy k negatív, akkor pedig definíció szerint Ct (m, k) = 0. A leghosszabb bármilyen széria nagyságának, az Rn′ -nek az aszimptotikus viselkedését vizsgálva Muselli tételét alkalmazzuk, amelyben Vn (p) jelöli annak a valószínűségét, hogy a leghosszabb széria n dobás esetén a fejekből adódik. 2.10. tétel. (Muselli, [9]) { lim Vn (p) =
n→∞
0 , ha 0 ≤ k < 21 , 1 , ha
1 2
< p ≤ 1.
A kapott eredményeket ismét grafikonon szemléltetem, mint ahogy azt a szabályos érme eseténél is tettem. A szimulációk ugyanolyan hardver és szoftver eszközökkel történtek mint a (2.3.1)-ben leírtam. Az ábrákon a rekurzív és az aszimptotikus eredmények nem szerepelnek, hiszen itt csak a szimuláció volt a feladatom. Ismét 20000 ismétlés számmal dolgoztam. A következő grafikonokon szabálytalan érme (p = 0, 6) esetén mutatom a leghosszabb fej (bal felső), a leghosszabb írás (bal alsó) illetve a leghosszabb bármilyen szériák esetét, rövid (n = 50) és hosszú (n = 1000) dobássorozatra.
2.4. ábra. Leghosszabb szériák, szabálytalan érme (p = 0, 6), rövid sorozat (n = 50)
23
2.3. A leghosszabb szériák vizsgálata
2.5. ábra. Leghosszabb szériák, szabálytalan érme (p = 0, 6), hosszú sorozat (n = 1000) A program szimulációs eredményeinek helyeségét a [4] grafikonokkal hasonlítottam össze, ahol már a rekurzív és aszimptotikus eredmények is szerepelnek az ábrákon. Itt is elmondható az, mint a szabályos pénzérménél, hogy kis n esetén az aszimptotikus eredmények távol esnek a pontos (rekurziós) értékektől. A rekurzió még rövid futás idő esetén jól számolható, gyors, de nagy n esetén a rekurziós algoritmus egyre lassul, számolásra gyakorlatilag nem használható. Az aszimptotikus eredmények viszont n növelésével egyre közelebb kerülnek hozzájuk.
2.3.3. A halmozási vagy duplázásos teknika A pétervári paradoxonnal és a leghosszabb szériákkal szoros kapcsolatban áll a gyakran alkalmazott halmozási vagy más néven martingál stratégia, amelyben sok szerencse játékos a mai napig hisz (és megy is tönkre). A halmozási stratégia lényegét [10] leírtak alapján ismertetem. Itt is a bank ellen játszunk egy olyan igazságos játékot, amelyeben 50% − 50% az esélye a nyerésnek és a vesztésnek is. A stratégia a következő: ha az első játszmában vesztünk, akkor megkétszerezzük a tétet, ha a másodikban is vesztünk akkor ismét megkétszerezzük a tétet és mindaddig tesszük ezt amíg végre nem nyerünk. Tehát ha a legelső tétünk 1 Ft és az első n − 1 játékban vesztettünk, de az n-dikben már nyerünk, akkor összesen 1 + 2 + 4 + · · · + 2n−1 = 2n − 1 forintot vesztettünk és 2n -et nyertünk, így 1 forint tiszta nyereségre tettünk szert. A duplázásos teknika hatásos nyerő módszernek látszik, mivel 1 valószínűséggel valamikor csak nyerünk. A látszat azonban csal, mert általában még mielőtt bármit is nyernénk, már rég elvesztettük az összes pénzünket. Továbbá a kaszinók is ismerik ezt a stratégiát, éppen ezért maximalizálják a tétek nagyságát (tehát a végtelenségig nem folytatható ez a stratégia) és bár ez a maximum összeg csillagászatinak tűnik, mégis teljesen hatástalanná teszi a martingál stratégiát. MATLAB program segítségével leszimuláltam a duplázásos teknikát, ami megmutatja, hogy egy adott kezdő tőke és cél nyeremény megadásával hányszor értük el és hányszor nem értük el a nyereményt. Arra is választ ad a program, hogy hány játékból értük el és hány játékból nem értük el a célként kitűzött nyereményt. 24
2.3. A leghosszabb szériák vizsgálata A programot két esetre futattam az egyik amikor a kezdő tőkénk 100000 Ft és a cél nyereményünk 120000 Ft vagyis 20000 Ft-ot szeretnénk nyerni. A másik esetben ismét 100000 Ft kezdő tőkével indulunk és 200000 Ft a cél nyereményünk, vagyis 100000 Ft-ot szeretnénk nyerni. A tét 1 Ft-ról indul, ha vesztünk akkor a tét növekszik és a dupláját rakjuk fel az előző tétnek. Ha nyerünk akkor a tét nem változik azaz 1 Ft marad. Program által adott eredményeket az alábbi képek mutatják.
2.6. ábra. Halmozási stratégia (futási eredmények) Ha megfigyeljük a két ábra adatait, akkor azt a következtetést vonhatjuk le, hogy 100000 Ft kezdő tőkével (bal oldali) indulva megéri játszani 120000 Ft-ért hiszen a program szerint 1000 esetből 757-szer, azaz p = 0, 757 valószínűséggel eltudjuk érni a kívánt nyereményt. Továbbá, ha 200000 Ft szeretnénk nyerni (jobb oldali), akkor nem érdemes kockáztatni a pénzünket, hiszen nagyobb annak a valószínűsége, hogy nem érjük el. Tehát annak a valószínűsége, hogy elérjük elég kicsi ebben az esetben p = 0, 27.
25
3. fejezet Fejlesztői dokumentáció 3.1. Követelmény definíció 3.1.1. A program célja, alapvető feladata A program célja a korábban ismertetett elméleti anyagrészek számítógépes szimulációja. Továbbá oktatási és demostrációs segéd eszközként is hazsnálható, amely által a hallgatók és a téma iránt érdeklődők szemléletesen láthatják a leghosszabb szériák témakört vagy a halmozási teknikát.
3.1.2. A fejlesztőkörnyezet A programrészek MATLAB R2011a-val készültek. Az elkészült forráskód fordításához, illetve a forráskód szerkesztéséhez MATLAB program szükséges.
3.1.3. A futtatáshoz szükséges környezet A program futattássához szükséges a MATLAB, illetve egy olyan számítógép, amely ezt futtatni képes. A MATLAB 2011, 2012, 2013 rendszerkövetelményei a következők: 1 GB üres hely a merevlemezen, de 3-4 GB az ajánlott. Továbbá 1024 MB RAM, de 2048 az ajánlott és bármilyen INTEL vagy AMD processzor, amely támogatja a SSE2 utasítás készletet. A MATLAB elérhető 32 és 64 bites kiadásban is. Magának a programnak nincs nagy memória igénye.
3.1.4. Felhasználói felület A program végső változata grafikus felhasználói felülettel rendelkezik, hogy a program használatát megkönnyítse és áttekinthetőbbé tegye a felhasználók számára. A programot a felhasználó az egér segítségével vezérelheti.
3.1.5. A program elkészítésének a lépései 1. A program megtervezése. 2. A program prototípusának elkészítése. Ez már tartalmazza a teljes elkészült programot, leszámítva a grafikus részt. A programnak ebben az állapotában könnyen 26
tesztelhetőnek kell lennie, hogy a programozási és funkcionalitási logikai hibák könnyen felismerhetők legyenek. 3. Ha a prototípus megfelelő, akkor kezdődhet a grafikus felület megvalósítása. Itt is fontos a tesztelés és a kiértékelés. Ha ennek a kifejlesztése is sikeres, készen van a program első teljes változata.
3.2. A programban használt grafikus objektumok – Push Button (gomb), – Radio Button (rádió gomb), – Edit Text (szöveg mező), – Static Text (címke), – axis (ábra), – Button Group (panel a rádió gomboknak).
3.3. A programban használt függvények leírása A program vezérlése grafikus felületen történik, vagyis a felhasználó a grafikus felhasználói felülettel az egér segítségével kommunikál. A grafikus felület elkészítése során a MATLAB grafikus objektumait és a hozzájuk rendelhető esemény függvényeket használtam. Ezek közül a callback, amely az egérgomb lenyomásához rendel aktivitásokat hajtja végre valamint a createfcn függvényt, amely a grafikus objektumok létrehozásakor hajtódik végre. Természetesen a MATLAB további akció függvényeket is tartalmaz. Az objektumok tulajdonságai közül a ’string’, ’tag’, ’visible’ tulajdonságokat használtam a leggyakrabban. A ’string’ az objektumon található szöveg megadására szolgál, a ’tag’ tulajdonság segítségével hivatkozhatunk az obejktumra, a visible tulajdonsággal pedig az obejktum láthatóságát lehet állítani. A ’get’ és a ’set’ beépített függvények segítségével lekérdezhetjük az objektumok paramétereinek aktuális beállítását és meg is változatathatjuk azok értékét. Továbbá a ’plot’ és a ’bar’ beépített függvényt használom az ábrák kirajzolására. A programrészekben található függvények feladatai egyenként kerülnek ismertetésre.
3.3.1. A kezdő oldal függvényei Ebben a programrészben öt függvény található. Név szerint a következők: – pushbutton1_Callback, – pushbutton2_Callback, – pushbutton3_Callback, – axes6_CreateFcn, 27
– pushbutton4_Callback. Az első három függvény feladata a programrészek közti navigáció megvalósítása, azaz ezekkel dönthetjük el, hogy a leghosszabb szériák vagy egy játék értékének a megbecsülése, vagy a halmozási stratégiát bemutató programrészek közül melyiket választjuk. Az axes6_CreateFcn függvény tölti be a képet a megfelelő helyre. A utolsó függvény csak annyit csinál, hogy kilép a programból.
3.3.2. Leghosszabb szériák programrész függvényei Ebben a programrészben is öt függvény található, amelyek a következő néven találhatók meg a programban: – pushbutton1_Callback függvény feladata: navigációs feladatot lát el, bezárja a programrész ablakát és ennek segítségével léphetünk vissza a kezdő oldalra. az utolsó, ezt részletesebben is ismertetem. – pushbutton3_Callback függvény feladata: navigációs célt szolgál a programrész súgó ablak megnyitásáért felelős. – axes4_CreateFcn függvény feladata: az axes4 objektum létrejöttekor, a képet betölti a megfelelő helyre. – uipanel2_SelectionChangeFcn feladata: hogy, ha a szabálytalan érme esete van kiválasztva aktivizálja a fej dobás valószínűségének beviteli mezőjét valamint inaktivvá teszi, ha a szabályos érme esete van kiválasztva. – A program rész legfontosabb függvénye pushbutton2_Callback, itt történnek a főbb számítások. A függvény első lépésként a beviteli mezőkben megadott értékeket kiolvassa változókba a ’get’ függvény meghívásával. A ’get’ függvény két paramétert kap az első az objektum azonosítója, a második az objektum ’string’ tulajdonsága. Ebben az esetben az objektum ’string’ tulajdonágát vesszük ki, majd ezt az értéket az str2num beépített függvény meghívásával stringből numerikus adattá konvertálja. A változókba beolvasott értékek ellenőrzéseken megy át és ha nem megfelelő adatok kerültek be hibaüzenetet dob. Ilyen például, hogy 0-tól kisebb számot nem fogad el az ismétlés számának illetve a játék számának. Továbbá szabálytalan érme esetén a valószínűségnek 0 és 1 között kell lennie, ha nem szintén hiba üzenetet dob a program. Ha a megfelelő értékeket kapott a függvény az m változóban eltárolja az ismétlés számát, az n változóban pedig a játék számát. Következő lépésként a függvény m-szer n hoszúságú 0-ból és 1-ből álló sorozatokat generál. A 0 jelenti a fejet az 1 pedig az írást. Ezekben nézi a leghosszabb fej, írás illetve bármilyen szériát és ezeket az értékeket három tömben tárolja, amelyekre a kirjzolásnál lessz szükségünk. Ezek az eredmények adják a szimulációs eredményeket a grafikonon. Ezután a függvény a rekurziós képlet alapján kiszámolja a rekurziós értékeket, amelyeket szintén tömbökben tárol. Végül a rendelkezésre álló adatokat felhasználva meghívja a beépített ’bar’ és a ’plot’ függvényeket, amely kirajzolja az ábrákat. A függvény úgy van megírva, hogy szabálytalan érme esetén csak a szimulációt ábrázolja.
28
3.3.3. Egy játék ára programrész fügvényei Ez a programrész három függvényt tartalmaz. Ezek név szerint a következők: – pushbutton1_Callback feladata: navigációs célt szolgál, bezárja a programrész ablakát és segítségével vissza léphetünk a kezdő oldalra. – pushbutton3_Callback feladata: navigációs feladatot lát el, megnyitja a programrész súgó ablakát. – pushbutton2_Callback feladata: ez a függvény végzi a főbb számításokat. A függvény az ismétlés számokat egy n tömben tárolja. A tömb a következő ismétlés számokat tartalmazza: 50, 100, 1000, 10000, 50000, 100000. Az m változóba a ’get’ függvény meghívásával beviteli mezőbe kiolvassa a játék számát. A ’get’ függvény két paramétert kap az első az objektum azonosítója a második az objektum ’string’ tulajdonsága. Az ’str2num’ függvény meghívásával stringből numerikus adatot állít elő és ezt tárolja az m változóban. Ha nem megfelelő adatot adtunk meg, akkor a függvény hibaüzenetet dob. Ha a számoláshoz szükséges adatok rendelkezésre állnak, akkor ezután a függvény elvégzi a szükséges számításokat. A függvény minden egyes ismétlés számon végig megy és m hosszúságú 0-ból és 1-ből álló sorozatokat állít elő, ahol 0 a fej és 1 az írás. Ezeket egy mátrixban tárolja és végül a ’set’ függvény meghívásával betölti a táblázatba az adatokat. A ’set’ függvény három paramétert kap első a táblázat azonosítója, a táblázat tulajdonsága (konkrétan a ’data’ tulajdonsága) valamint a mátrixot, amely a kiszámolt értékeket tartalmazza.
3.3.4. Játék (duplázásos teknikát alkalmazva) programrész fügvényei – pushbutton1_Callback feladata: navigációs célt szolgál, bezárja a programrész ablakát és segítségével vissza léphetünk a kezdő oldalra. – pushbutton3_Callback feladata: navigációs feladatot lát el, megnyitja a programrész súgó ablakát. – pushbutton2_Callback feladata: ennek a függvények a feladata a szükséges számítások elvégzése. A beviteli mezőkből a ’get’ függvény segítségével beolvassa a szükséges adatokat a változókba. A ’get’ függvény két paramétert kap az első az objektum azonosítója, a második az objektum tulajdonsága. Ha helytelen adatokat adunk meg a program hibaüzenetet dob, ha helyes adatokat adtunk meg akkor a program az ’str2num’ függvénnyel stringből numerikus adattá konvertálja. A függvény három adatot tárol el az ismétlész számot az m változóban, akezdő tőkét a kezdo változóban és a cél nyereményt a celosszeg változóban. A tet változó kezdő értéke 1. A függvény egy ciklus segítségével vizsgálja, hogy a tétet megtudjuk-e tenni, ha igen akkor generál véletlenszerűen egy számot 0 és 1 között. Ha a generált szám 0, 5-től kisebb akkor az 0-nak felel meg, tehát nyertünk és a tet változót beállítja 1-re. Ellenkező esetben vesztettünk és a tet változó a duplájára nő. A ciklus, akkor fejeződik ba ha már nem tudjuk felrakni a tétet vagy elvesztettük az összes pénzünket. A függvény azt, hogy hányszor értük és hányszor nem tömben tárolja. Tárolásra kerül az is, hogy átlagosan hány játékot 29
játszottunk ahoz, hogy elérjük a nyereményt valamint hogy hány játék kellett ahoz, hogy elveszítsük a pénzünket. A ’set’ függvény meghívásával a rendelkezésre álló adatok bekerülnek a megfelelő helyre. A ’set’ függvény három paramétert kap az első az objektum azonosítója, a második az objektum ’string’ tulajdonsága és végül egy változót, amely a kiszámolt értéket tartalmazza.
30
4. fejezet Összefoglalás Dolgozatomban sikerült elmélyülnöm a szent pétervári paradoxonhoz tartozó leghosszabb szériák vizsgálatában valamint ennek programmal történő megvalósításában. A dolgozat elején bemutattam a paradoxon létrejöttét valamint a fejlődésének történetét. Szeretném még megemlíteni, hogy a híres „Legyen Ön is milliómos!” televíziós játéknak is a paradoxon egyik változata adta az alapgondolatát. Továbbá a paradoxonnak nem csak matematikai, hanem gazdasági vonatkozásai is vannak. Ezt követően a leghosszabb szériákat tárgyaltam részletesen szabályos és szabálytalan pénzérme esetére. Továbbá ismertettem az ehez a témkörhöz tartozó rekurzív, aszimptotikus eredményeket illetve a program szimulációs eredményeit különböző dobáshosszak esetén. A lenti ábrához hasonló grafikonokon vizsgáltuk, hogy miként alakultak a leghosszabb fej, leghosszabb írás illetve leghosszabb bármilyen széria szabályos és szabálytalan pénzérme esetén.
4.1. ábra. Leghosszabb szériák, szabályos érme (p = 0, 5), (n = 250)
31
4.2. ábra. Leghosszabb szériák, szabálytalan érme (p = 0, 6), (n = 250) Az utolsó főbb témakör a halmozási stratégia volt, amely a leghosszabb szériákhoz és a paradoxonhoz szorosan kapcsolódik. Láthattuk, hogy a duplázásos teknika a szerencsejátékoknál egy hatékony stratégiának látszik éppen ezért a kaszinók maximalizálták a tétek nagyságát, amellyel hatástalanná teszik ezt a módszert. Végül a fejlesztői dokumentációba került ismertetésre a programrészek függvényeinek leírása valamint, hogy milyen fejlesztő környezetben készültek a programok. A szakdolgozat elkészítése során a legnagyobb nehézséget a programrészek grafikus felületének elkészítése okozta, hiszen ezelőtt még soha nem foglalkoztam MATLABban grafikus felületekkel. Ezekben a nehézségekben részben a YOUTUBE-on található videók illetve [11] volt segítségemre. Néha a LATEX-ben is segítsére szorultam ilyenkor a témavezetőmhöz fordultam segítségért valamint az interneten található forrásokhoz. Visszatekintve úgy gondolom, hogy a dolgozat írása és a programrészek elkészítése során, hasznos matematikai és programozási tapasztalatokkal gazdagodtam, amelyeket a későbbiekben nagy mértékben hasznosítani tudok.
32
Irodalomjegyzék [1] Csörgő Sándor: A szentpétervári paradoxon, Polygon, V. kötet 1.szám (1995). [2] Fazekas István, Karácsony Zsolt, Libor Zsuzsa: Longest runs in coin tossing. Comparison of recursive formulae, asymptotic theorems and computer simulations, Acta Universitatis Sapientiae, Mathematica, 2, 2, (2010), 215-228. [3] Fazekas István, Karácsony Zsolt, Libor Józsefné: A leghosszabb szériák vizsgálata, Alkalmazott Matematikai Lapok 27, (2010), 135-156. [4] Libor Józsefné: Rekurziós eljárások, Monte Carlo módszerek és aszimptotikus eredmények oktatási célú összehasonlító elemzése, Doktori (PhD) értekezés, Debreceni egyetem, Debrecen, 2011. [5] M. F. Schilling: The Longest Run of Heads, The College Mathematics Journal, 21, no. 3 (1990), 196-207. [6] Földes A.: The limit distibution of the length of the longest head-run, Period. Math. Hungar. 10, no. 4 (1979), 301-310. [7] Gordon L., Schilling M. F., Waterman M. S.: An extreme value theory for long head runs, Probab. Theory Relat. Fields, 72, no. 2 (1986), 279-287. [8] Bloom D. M.: Probabilities of Clumps in a Binary Sequence, Mathematics Magazine, 69, no. 5 (1996). [9] Muselli M.: Useful inequalities for the longest run distribution, Statist. Probab. Lett. 46, (2000). [10] Székely J. Gábor.: Paradoxonok a véletlen matematikájában, Typotex, (2004). [11] Stoyan Gisbert: MATLAB, Typotex, (2005). [12] TEX Catalogue, www.ctan.org/tex-archive/help/Catalogue/catalogue.html
33
Adathordozó használati útmutató A CD-n a szakdolgozat mappán belül kettő mappa található. Az első mappában a felhasználói kézikönyv, amely kezikonyv.pdf néven szerepel a CD-n. Ez a dokumentum a programot használni kívánó felhasználóknak nyújt segítséget a program megfelelő és célirányos használatához. A dokumentum lépésről lépésre végig vezeti a felhasználót az egyes programrészek használatában. A második a Program forráskódjai mappa, amelyben 17 fájl helyezkedik el. A (*.jpg) kiterjesztésű fájlok a programrészekben lévő képek megjelenítéséhez kellenek. A (*.fig) fájlok szolgának arra, hogy a grafikus felületet később is szerkeszteni tudjuk az egyes programrészeknél. A (*.m) kiterjesztésű fájlok tartalmazzák a programrészek függvényeit illetve a grafikus objektumokhoz rendelt akciókat. Ezen fájlok szerkesztéséhez illetve megtekintéséhez mindenképp szükség van a MATLAB fejlesztői programra. A program illetve a programrészek elindításához, futatásához szükség van a MATLAB R2011a vagy attól újabb változatára. 1. Nyissa meg a MATLAB programot. 2. Kattintson a jobb felső sarokban a File azon belül az Open opcióra, majd válassza ki a CD-n található (kezdo.m) fájlt. 3. A fenti fülek közül válassza a Debug fület azon belül pedig a Run opciót. 4. Ha a program fut választhat az 1-3 témakörök közül vagy a kilépés gombra kattintva kiléphet a programból. Az 1. témakör a leghosszabb szériák programrészre lép tovább, a 2. témakör az egy játék ára programrészt nyissa meg és végül a 3. témakörre kattintva a játék duplázásos teknikát alkalmazva programrész ablaka jelenik meg. Ha a programrészek forrását szeretnénk megtekinteni, akkor az előzőekben leírt 1. illetve 2. lépést kell végrehajtani.
34
Köszönetnyilvánítás Szeretnék köszönetet mondani témavezetőmnek, Dr. Karácsony Zsoltnak, aki észrevételeivel és tanácsaival segítette munkámat, valamint rendelkezésemre bocsátotta a dolgozat elkészüléséhez szükséges szakirodalmat. Köszönöm szüleimnek és testvéreimnek, hogy szeretetükkel támogattak egyetemi tanulmányaim alatt, valamint a kislányomnak azt, hogy minden nap erőt adott nekem egyetemi tanulmányaim során. Végül, de nem utolsó sorban szeretném hálásan megköszönni a Miskolci Egyetem Gépészmérnöki és Informatikai Kara valamennyi oktatójának, dolgozójának azt a lelkiismeretes munkáját, amivel a hallgatók képzését, tanulását és a versenyképes tudás megszerzését támogatják.
35
