Diplomamunka. Miskolci Egyetem. Leghosszabb szériák vizsgálata. Készítette: Selling István Mérnök Informatikus MSc jelölt

Diplomamunka

Miskolci Egyetem

Leghosszabb szériák vizsgálata

Készítette: Selling István Mérnök Informatikus MSc jelölt Témavezető: Dr. Karácsony Zsolt egyetemi docens

Miskolc, 2013

Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Informatikai Tanszék

Szám:

Diplomamunka Feladat Selling István (MNJOHS) Mérnök Informatikus MSc jelölt részére. A szakdolgozat tárgyköre: Valószínűség-számítás A szakdolgozat címe: Leghosszabb szériák vizsgálata A feladat részletezése: A valószínűség-számítás rövid történeti áttekintése. MATLAB programcsomag rövid bemutatása, története, alkalmazási területeinek rövid ismertetése. Leghosszabb szériák témakörébe tartozó tételek, állítások ismertetése, bemutatása, ezen témakörön belül írt alkalmazások bemutatása. Rekurzív, aszimptotikus és szimulációs módszerek, összefüggések ismertetése. Két módszer bemutatása rekurzív programok gyorsítására MATLAB programcsomagban. Szentpétervári paradoxon ismertetése, történetének áttekintése, alkalmazás bemutatása. GUI készítés MATLAB programcsomag segítségével.

Témavezető: Dr. Karácsony Zsolt, egyetemi docens A feladat kiadásának ideje: 2012. 09. 30.

................................. szakfelelős 2

Eredetiségi Nyilatkozat

Alulírott . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ; Neptun-kód: . . . . . . . . . . . . . . . . . . . a Miskolci Egyetem Gépészmérnöki és Informatikai Karának végzős . . . . . . . . . . . . . . . . . . . szakos hallgatója ezennel büntetőjogi és fegyelmi felelősségem tudatában nyilatkozom és aláírásommal igazolom, hogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 diplomamunka 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 diplomamunka beadható: ......................

...........................

dátum

témavezető(k)

4. A diplomamunka . . . . . . . . . . . . . . . . . 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 diplomamunka bírálatra nem bocsátható A bíráló neve: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................

...........................

dátum

szakfelelős

6. A diplomamunka osztályzata a témavezető javaslata:

..............

a bíráló javaslata:

..............

a diplomamunka végleges eredménye: . . . . . . . . . . . . . . Miskolc, . . . . . . . . . . . . . . . . . . . . . . . .

................................. a Záróvizsga Bizottság Elnöke 4

Tartalomjegyzék 1. Bevezetés

8

2. Rövid áttekintés 2.1. Történeti áttekintés . . . . . . . . . . . . . . . . . 2.1.1. Valószínűség-számítás történeti áttekintése 2.1.2. MATLAB történeti áttekintése . . . . . . 2.2. Néhány szükséges fogalom . . . . . . . . . . . . . 2.3. A feladatok megoldása során használt eloszlások . 2.3.1. Bernoulli-eloszlás . . . . . . . . . . . . . . 2.3.2. Egyenletes eloszlás . . . . . . . . . . . . . 2.3.3. Normális eloszlás . . . . . . . . . . . . . . 2.4. Fogadásos feladat . . . . . . . . . . . . . . . . . . 2.4.1. A feladat leírása . . . . . . . . . . . . . . . 2.4.2. A feladat szimulációja . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

10 10 10 11 11 12 12 13 13 14 14 15

3. Leghosszabb szériák vizsgálata 3.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Független kísérletsorozat . . . . . . . . . . . . . . . . . . . . 3.2.1. Szabályos pénzérme esete . . . . . . . . . . . . . . . 3.2.2. Alkalmazás bemutatása szabályos pénzérme esetében 3.2.3. Szabálytalan pénzérme esete . . . . . . . . . . . . . . 3.2.4. Alkalmazás bemutatása szabálytalan pénzérme esetén 3.2.5. Alkalmazás bemutatása, elért gyorsulások . . . . . . 3.2.6. Hibaszámításos alkalmazás bemutatása . . . . . . . . 3.3. Nem független kísérletsorozat . . . . . . . . . . . . . . . . . 3.3.1. Szimuláció bemutatása . . . . . . . . . . . . . . . . . 3.4. Néhány matematikai alkalmazás . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

17 17 18 18 21 25 27 32 34 36 38 38

4. Szentpétervári paradoxon 4.1. A szentpétervári paradoxon . . . . . . . 4.2. A paradoxon előtörténete . . . . . . . . . 4.3. A paradoxon módosítási lehetőségei . . . 4.4. Alkalmazás bemutatása . . . . . . . . . . 4.5. További alkalmazások . . . . . . . . . . . 4.5.1. Martingál szerencsejáték stratégia 4.5.2. Egyék alkalmazások . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

40 40 41 47 48 50 50 50

. . . . . . .

. . . . . . .

5. GUI tervezés MATLAB programcsomagban

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

52

5

6. Összefoglalás

57

Irodalomjegyzék

59

Adathordozó használati útmutató

61

6

Köszönetnyilvánítás Ezúton szeretnék köszönetet nyilvánítani azoknak, akik segítsége nélkül ez a diplomamunka nem készülhetett volna el. Elsősorban témavezetőmnek, Dr. Karácsony Zsoltnak, a sok segítségért, türelemért, figyelemért és ötleteiért, amikkel előresegítette a diplomamunkám haladását. Köszönettel tartozom a Miskolci Egyetem Alkalmazott Matematikai Tanszékének, hogy támogattak a tanulmányaim során. Elsősorban Dr. Fegyverneki Sándort és Dr. Raisz Pétert szeretném kiemelni, akik megismertették, és megszerettették velem a matematikának ezt a területét. Ugyancsak szeretném megköszönni szüleimnek és barátaimnak a segítséget, támogatást és türelmet, amit nyújtottak. Végül, de nem utolsó sorban pedig szeretném megköszönni a kedves Olvasónak, amiért idejét és figyelmét diplomamunkámra áldozza.

7

1. fejezet Bevezetés A valószínűség-számítás matematikájának eredeti motivációját a véletlen tömegjelenségek (más néven kísérletek) mennyiségi, gyakorisági viszonyainak vizsgálata adta, melyek egyrészt tetszőlegesen sokszor megismétlődhetnek, viszont megismétlődésük többféle eredménnyel járhat, és nem tudjuk pontosan megmondani, kiszámítani, hogy melyik ismétlődés alkalmával melyik kimenetel következik be. A valószínűség-számítás legelső problémái szerencsejátékok elemzésén alapultak, annak kimeneteleit próbálták megállapítani. Ilyen problémák közé tartozik például egy érme feldobása esetén, hogy fej vagy írás lesz a dobás eredménye. Szerencsejátéknak az olyan játékokat nevezzük, amikben nagy szerepet játszik valamilyen véletlenszerű esemény, és aminek eredményére játékosok fogadhatnak. A játék célja az esemény kimenetelének eltalálása, és további pénz nyerése. A szerencsejátékok a legősibb játékformák közé tartoznak, végigkísérték az emberiség történelmét. Rengeteg különböző szerencsejáték típust lehet megkülönböztetni, és ezeket a játékokat különböző eszközök segítségével lehet játszani. Ilyen játékok közé tartoznak péládul az érmedobásos, kockadobásos játékok, kártyajátékok. A szerencsejátékok között is vannak olyan játékok, amelyek kimenetelében szerepet játszhatnak a játékosok képességei, viszont a szerencse nagyobb szereppel bír a játék kimenetelének meghatározásában. A valószínűség-számítás kezdeti problémái mind szerencsejátékok köré épültek, ahogy a legtöbb értekezés címében is megjelentek a véletlenek törvényszerűségeihez hasonló fogalmak. A klasszikus valószínűség-számítás alapjait lerakó matematikusok (Cardano, Fermat, Pascal, Jacob Bernoulli, Huygens) munkái is különböző szerencsejátékok (kockadobás, érmedobás) elemzéseiből indultak ki, és váltak tudományággá. Diplomamunkámban ilyen szerencsejátékok elemzéséből kiinduló matematikai következtetéseket szeretnék bemutatni, és szimulálni. A diplomamunka legelején szeretném röviden bemutatni a valószínűség-számítás kialakulásának történetét, és bemutatni, hogy milyen problémák köreivel bővült az eltelt idők során. Ezután bemutatnám a programokhoz használt MATLAB szoftvercsomag kialakulásának történetét. Ennek a fejezetnek a végén szeretnék bemutatni egy egyszerű programot, ami egy fogadásos feladathoz köthető, egy olyan játékhoz, aminek két kimenetele van, és ezek a kimenetelek csakis a szerencsétől függnek. A játékos ilyen játékokból álló sorozatot játszik, és minden játék során fogad a játék értékére. A feladat lényege, hogy bemutassa, hogy adott kezdőösszeg, tét és valószínűségi érték során adott játékszám mellett milyen nyereményeket milyen relatív gyakorisággal érhet el a játékos. Ez a feladat egy egyszerű bevezetésként szolgál diplomamunkám további részeihez. Harmadik fejezetemben a leghosszabb szériák vizsgálatára térnék ki, azaz például

8

egy érmedobásos kísérletet egymás után sokszor végrehajtva, milyen hosszúságú sorozatok várhatóak az eredmények között. Ebben a fejezetben kitérnék először a független kísérletek esetére, azaz az érmedobásra, amikor az aktuális kísérlet eredménye nem függ az előző kísérletek eredményétől. Itt ismertetem mind a szabályos, mind a szabálytalan pénzérme esetét. Ebben az alfejezetben ismertetem azokat a rekurzív és aszimptotikus tételeket, amelyek ezen véletlen események eredményére adnak összefüggéseket, és ezekhez az eredményekhez hasonlóan bemutatom a MATLAB programcsomag segítségével megírt szimulációs eredményeket. Ehhez az alfejezethez kapcsolódóan bemutatok egy olyan szimulációs programot, aminek az a célja, hogy elemezze azokat a változásokat, amik akkor következkeznek be, ha megengedünk különböző számú hibát egy érmesorozatban. Ezen szimulációval vizsgálom a korábban is bemutatott leghosszabb fej, illetve leghosszabb bármilyen szériák változását hibák esetén. A szimuláció során alkalmazott algoritmus segítségével bemutatom az egy, kettő, illetve három megengedett hiba esetét, viszont az alkalmazott algoritmus segítségével több hibához tartozó sorozatok eredményei is kiszámíthatóak kevés változtatással. Ugyanebben a fejezetben kitérek a függő kísérletek esetére is, amikor az aktuális kísérlet eredménye függ az előző kísérletek eredményétől. Ilyen kísérletre adok példát olyan játékban, ahol egy pakli kártyából egyesével húzunk kártyákat, és a kihúzott kártyákat nem tesszük vissza a pakliba. Ebben a problémakörben is a leghosszabb szériákat (leghosszabb piros, illetve leghosszabb bármilyen színű) vizsgálom, és ezeket mutatom be szimuláció segítségével. A negyedik fejezetben egy háromszáz évvel ezelőtt megfogalmazott feladatot mutatok be, a szentpétervári paradoxont. A paradoxon ismertetése után bemutatom a paradoxon történetét is, kiemelve azokat a matematikusokat, akik érdemben foglalkoztak a problémával. Kiemelem a paradoxon néhány érdekes tulajdonságát, majd bemutatom az erre a feladatra írt szimulációs programot, aminek segítségével lehetőség van a szentpétervári játékot játszani, és megvizsgálni azt, hogy milyen kezdőtét mellett lesz igazságos a játék, illetve hogy a játék elején megadott kezdőtétek mellett milyen kifizetődés várható a játéktól. A szentpétervári paradoxon után bemutatom a probléma további változatait, illetve hogy milyen alkalmazásai vannak a problémának. Itt bemutatok egy szimulációs feladatot, ami az ún. martingál-stratégiához kapcsolódik. A stratégia bemutatása során igyekszek bemutatni azon tényezőket, amik miatt ez a stratégia nagyon kiszámíthatlan lehet, és hiába tűnik biztosnak a nyerés, rengeteg pénzt lehet veszíteni az alkalmazásával. Diplomamunkám legutolsó fejezetében egy rövid bemutatást adnék a MATLAB szoftvercsomagba épített GUIDE nevű fejlesztőkörnyezetről, aminek segítségével könnyen lehet grafikus felhasználói felületeket szerkeszteni. Erre a környezetre azért térek ki, mert a diplomamunkához készült programok közös grafikus felülete ezzel a környezettel készült. Ebben a rövid leírásban bemutatom, milyen lehetőségeket nyújt ez a környezet, és jellemzem ezeket. A kutató munka a Miskolci Egyetem stratégiai kutatási területén működő Fenntartható Természteti Erőforrás Gazdálkodás Kiválósági Központ / Alkalmazott Anyagtudomány és Nanotechnológiai 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. 9

2. fejezet Rövid áttekintés 2.1. Történeti áttekintés 2.1.1. Valószínűség-számítás történeti áttekintése A valószínűség-számítás elméletének megalapozói közül első sorban a francia Pierre Fermat (1601-1665) és Blaise Pascal (1623-1662) említésre méltó, bár néhány ilyen tárgyú mű már előttük is megjelent. A legfontosabb példa a De ludo aleae (A kockajátékról) c. könyv, amit Cardanonak (1501-1576) tulajdonítanak. A legtöbb értekezés a véletlen törvényszerűségeiről hasonló címet viselt, a matematikának ez az ága ugyanis a szerencsejátékok elméleteként indult. Pascal és Fermat is lényegében a kockázáshoz és egyéb játékokhoz kapcsolódó problémákat, feladatokat tárgyalnak, és oldanak meg, valamint lerakják a „klasszikus” valószínűség-számítás alapjait. A valószínűség-számítás, mint matematikai elmélet születési évének az 1654-es esztendőt szokás tekinteni (Fermat és Pascal egyik ilyen tárgyú levelének kelte), maga a valószínűség szó Jacob Bernoulli (1654-1705) Ars conjectandi (A találgatás művészete, 1713) című munkájában fordul elő először. Ha sokszor elvégezzük ugyanazt a kísérletet, és lejegyezzük, hogy az adott esemény ennek során hányszor következett be, akkor a kísérletet egyre többször végezve az adott esemény relatív gyakorisága egyre inkább megközelít egy számot: az esemény valószínűségét. A szerencsejátékok elmélete később biztosítási, népesedési és sztochasztikus (véletlen) geometriai problémákkal bővült. A következő matematikusok, akik ilyen problémákkal foglalkoztak: Moivre, Legendre, Bayes, Poisson, Gauss, Buffon. A XIX. században a valószínűség-számítás a matematika önmagában is hatalmas, önálló ágává vált. A „modern kori” (XIX. század második fele - XX. század első fele) valószínűség-számítást orosz matematikusok vitték tovább: Csebisev, Markov, Kolmogorov. Kolmogorov végezte el az elmélet axiomatikus megalapozását. E lépéssel a valószínűség-számítás a modern matematika többi ágával teljesen egyenrangú formális elméletté vált. A valószínűség-számítás nemcsak megalapozódott a huszadik században, hanem folyamatosan újabb területekkel bővült, például egy részecske bolyongásának leírása többdimenziós euklideszi térben (Brown-mozgás). A huszadik század második felében született meg önálló tudományként műszaki, mérnöki és statisztikai problémák termékeként a valószínűség-számítás két fontos új ága: a folyamat-statisztika, illetve az információelmélet.

10

2.2. Néhány szükséges fogalom

2.1.2. MATLAB történeti áttekintése A MATLAB egy speciális programrendszer, amely numerikus számítások elvégzésére lett kifejlesztve. A The MathWorks által kifejlesztett programrendszer képes mátrix számítások elvégzésére, függvények és adatok ábrázolására, algoritmusok implementációjára és felhasználói interfészek kialakítására. A MATLAB-ot (Matrix Laboratory) az 1970-es évek elején Cleve Moler kezdte el fejleszteni, az akkori Új-Mexikói Egyetem Számítástudományi intézetének elnöke. Kezdetben csak a diákjai munkáját tervezte megkönnyíteni, hogy ezen keresztül el tudják érni a LINPACK és EISPACK csomagokat Fortran tudás nélkül. Hamarosan elterjedt más egyetemek hallgatói és munkatársai között is, és így erős érdeklődésre tett szert az alkalmazott matematikával foglalkozók körében. Jack Little 1983-ban, Molernél tett látogatása során felismerte a MATLAB-ban lévő lehetőségeket. Nem sokkal ezután csatlakozott Molerhez és Steve Bangert-hez, majd újraírták a MATLAB-ot C nyelven, és megalapították a The MathWorks-öt 1984-ben. Ezek az újraírt könyvtárak JACKPAC néven váltak ismertté. 2000-ben a MATLAB-ot ismét újraírták, hogy újabb módszereket alkalmazzon a mátrixokkal való műveletekre, ebből született a LAPACK csomag. A MATLAB először az irányítástechnikával foglalkozók körében lett alkalmazva, ami Little szakterülete volt, de gyorsan elterjedt más területeken is. Manapság szintén használatos még az oktatásban, különösen a lineáris algebra és numerikus analízis szemléltetésében, és népszerű a képfeldolgozással foglalkozó kutatók között is. 2004-ben a hivatalos források alapján a MATLAB több, mint 1 millió felhasználóval rendelkezett.

2.1. ábra. MATLAB logó

2.2. Néhány szükséges fogalom 2.1. definíció. Ha n számú kísérlet közül az A esemény k-szor következett be (k = k = 0, 1, . . . , n) akkor a k számot az A esemény gyakoriságának, a hányadost pedig az n A esemény relatív gyakoriságának nevezzük. 11

2.3. A feladatok megoldása során használt eloszlások 2.2. definíció. Olyan meghatározott körülmények mellett vizsgált véletlen eseménynél, amely esemény relatív gyakorisága viszonylagos stabilitást mutat, az illető esemény valószínűségén azt a számértéket értjük, amely körül az illető esemény relatív gyakorisága ingadozik. 2.3. definíció. Egy ξ diszkrét valószínűségi változó lehetséges értékei legyenek x1 , x2 , . . . , xn , . . . a megfelelő valószínűségek legyenek p1 , p2 , . . . , pn , . . . , ekkor a ∞ X

pn x n

n=1

értéket, amely nem más, mint a ξ valószínűségi változó lehetséges értékeiből ezek valószínűségeivel, mint súlyokkal képzett középérték, ξ várható értékének nevezzük. A várható érték diszkrét esetben pontosan akkor létezik, ha ez a sor abszolút konvergens. Jelölése : E(ξ) Ha a ξ valószínűségi változó folytonos eloszlású, és sűrűségfüggvénye f (x), akkor Z∞ xf (x)dx

E(ξ) = −∞

integrál alakjában írható fel a várható érték. Folytonos esetben a várható érték pontosan akkor létezik, ha ez az integrál létezik, és véges. Ez az integrál akkor létezik, ha az eloszlásfüggvény az egész intervallumon deriválható. 2.4. definíció. Egy ξ valószínűségi változó ingadozásának mértékéül E(ξ − E(ξ))2 várható értéknek pozitív négyzetgyökét tekintik, és ezt a mennyiséget a ξ valószínűségi változó szórásának nevezik. 2.5. definíció. Legyenek A és B tetszőleges események, amelyek valószínűségeit jelöljük P (A) és P (B)-vel. Ha P (AB) = P (A)P (B), akkor a két esemény bekövetkezése nem befolyásolja egymást, azaz A és B esemény független. Három esemény teljesen független egymástól, ha páronként függetlenek, és P (ABC) = P (A)P (B)P (C) teljesül.

2.3. A feladatok megoldása során használt eloszlások 2.3.1. Bernoulli-eloszlás A véges Bernoulli kísérletsorozatban jelölje ξ az i-edik kísérletben az A esemény bekövetkezései számát. Ekkor ξi Bernoulli-eloszlású P (ξi = 1) = p, P (ξi = 0) = 1 − p, ahol p az A esemény bekövetkezésének valószínűsége. A Bernoulli-eloszlás várható értékére és szórásnégyzetére igaz, hogy E(ξi ) = p, D2 (ξ) = p(1 − p). 12

2.4. Fogadásos feladat Bernoulli-eloszlás generálása: MATLAB környezetben lehetőségünk van egyenletes eloszlású véletlenszámok generálására. Alapértelmezetten a rand() függvénnyel [0,1] intervallumon generáltatunk véletlen eloszlású számokat. Ahhoz, hogy ebből Bernoulli-eloszlást képezzünk, meg kell vizsgálnunk, hogy az egyenletes eloszlással generált véletlen szám hogyan viszonyul a p valószínűség értékéhez, és ennek megfelelően döntést hozni. Ha nagyobb, mint a p valószínűség, akkor az ellentétes esemény következett be, ha kisebb vagy egyenlő a véletlenszám a p valószínűséghez képest, akkor pedig bekövetkezett az A esemény. Ha P (ξ = 0.5) valószínűségű véletlen számokat akarunk létrehozni, akkor a [0,1] zárt intervallumon generált véletlenszámokat a 0.5 érték alapján kell szétválasztani, ha a véletlenszám kisebb, mint 0.5, akkor az A esemény, különben az A¯ esemény következett be.

2.3.2. Egyenletes eloszlás MATLAB programcsomagban alapértelmezetten egyenletes eloszlású véletlenszámokat generálunk [0,1] zárt intervallumon. Egy [a,b] intervallumon egyenletes eloszlású ξ valószínűségi változó várható értéke az intervallum két szélső értékének számtani közepe, azaz a+b , E(ξ) = 2 szórásnégyzete pedig (b − a)2 , D2 (ξ) = 12 azaz a MATLAB rand() függvénye [0,1] intervallumon 0.5 várható értékű, és √112 szórású véletlen számokat generál.

2.3.3. Normális eloszlás 2.6. definíció. A ξ valószínűségi változót normális eloszlásúnak nevezzük, ha sűrűségfüggvénye: (x−E(ξ))2 − 1 2 2D(ξ) √ e , f (x) = D(ξ) 2π ahol E(ξ) ∈ R és D(ξ) > 0. Jelölés: ξ → N(E(ξ), D(ξ)). 2.7. definíció. Ha a ξ valószínűségi változó normális eloszlású, E(ξ) = 0 és D(ξ) = 1, akkor standard normális eloszlásúnak nevezzük. Jelölése: N(0,1); MATLAB programcsomagban a normrnd(m,d) alakú függvénnyel tudunk normális eloszlású véletlenszámot generálni, aminek várható értéke m, és szórásnégyzete d. Ahhoz, hogy standard normális eloszlású legyen a véletlenszámunk, normrnd(0,1) alakban kell meghívni a függvényt.

13

2.4. Fogadásos feladat

2.2. ábra. Standard normális eloszlás sűrűségfüggvénye

2.4. Fogadásos feladat 2.4.1. A feladat leírása Vegyünk egy olyan játékokból álló sorozatot, amely játékoknak két kimenetele van, és ezen játékok függetlenek és azonos eloszlásúak! Tételezzük fel, hogy ismerjük ezeknek a játékoknak a pozitív kimenetelhez (nyeréshez) tartozó p valószínűségét! Ebből következően a másik kimenet valószínűsége q = 1 − p lesz. Az ilyen játékok lehetnek 1 tetszőlegesek, például ha p értéke pontosan , akkor ez a játék lehet egy egyszerű 2 szabályos pénzérme feldobása, vagy egy kockajátéknál az az eset, hogy párost vagy 1 páratlant dob a játékos. Ha a p értéke nem , akkor ez lehet egy olyan játék, ahol már 2 a szerencsén kívül számítanak a játékot játszó emberek képességei is. Ilyen esetben a játékhoz kapcsolódóan csak az az egyetlen feltételünk van, hogy a játéknak csak két kimenete legyen. Ilyen játék lehet például egy csapatjáték (labdarúgás, kézilabda, stb.) az ún. egyenes kieséses szakaszban, azaz a döntetlen már nem engedélyezett. Vagy ilyen játék lehet egy olyan szerencsejáték is, ahol a két esemény kimenetelének valószínűsége nem egyezik meg, például egy hamis pénzérme feldobásának esete. Vegyünk egy játékost, aki ilyen játékok kimenetelére akar fogadni! Minden fogadás legyen „dupla vagy semmi”, azaz a játékos vagy megnyeri a játék tétjének kétszeresét, vagy elveszti a tétet! A játékos ilyen játékokból n számú játékra szeretne fogadni adott kezdőösszegből indulva. A felmerülő kérdés az, hogyha n játékra ugyanannyi téttel fogad egymás után ismert p valószínűséggel, akkor milyen összegváltozásra számíthat a játékok lejátszása után. Tekintsünk meg egy egyszerű példát! Legyen n értéke 5, p értéke 0.7 és a játékos kezdőösszege 100 forint, és játékonként 10 forintnyi tétet tegyen fel! Tekintsük meg az eredmények valószínűségének alakulását! Könnyedén belátható, hogy ebben az esetben a nyeremények értékei 50, 70, 90, 110, 130 és 150 lesz, mivel 50 lesz a végösszege a játéknak, ha a játékos ötször veszít, 70 lesz akkor, ha 4-szer veszít, és egyszer nyer, és így 14

2.4. Fogadásos feladat tovább az öt győzelem értékét jelentő 150 forintig. Az elméleti értékeket a binomiális eloszlás szolgáltatja. Nyeremény értéke

Szöveges magyarázat

50

0 győzelem, 5 vereség

70


90


110


130


150


Kiszámítás képlete p0 q 5 50 p1 q 4 51 p2 q 3 52 p3 q 2 53 p4 q 1 54 p5 q 0 55

Nyeremény valószínűsége 0.00243 0.02835 0.1323 0.3087 0.36015 0.16807

2.4.2. A feladat szimulációja Tekintsük meg a MATLAB programcsomagban készült szimulációt! Először használjuk ugyanezen értékeket, azaz 5 játékot játszunk, 100 forintról indulva, a nyerés valószínűsége 0.7, és tíz forintot teszünk fel minden játék során! Hajtsuk végre ezt a kísérletsorozatot 100 000-szer, és tekintsük meg a szimuláció eredményeit! A program futása elején tűzzük ki elérendő összegnek 140 forintot! Fontos megjegyezni, hogy ezt az összeget csak akkor érheti el a szimuláció, ha 5-ször bejön a tippünk, azaz a valós nyeremény 150 forint lesz itt. Az ábrán piros körökkel lesz ábrázolva az elméleti érték, amit a binomiális eloszlás képlete alapján számolunk. Az ábra tetejéről leolvas-

2.3. ábra. A fenti példa szimulációs eredménye 15

2.4. Fogadásos feladat ható, hogy százezerszer megismételve a kísérletet annak a relatív gyakorisága, hogy a 140 forintos célösszeget elérjük 0.16652, ami eléggé megközelíti a korábban kiszámított 0.16807 nagyságú elméleti értéket. Végezzük el a feladatot más adatokkal is! Legyen a játékszám 100, a kezdőöszegünk 1 1000 forint! A játék legyen szabályos érmedobás, azaz p = legyen, a tét maradjon 2 az előző feladatbeli 10 forint! Célösszegnek tűzzünk ki 1100 forintot, és hajtsuk vége a kísérletet 200 000-szer!

2.4. ábra. 0.5 valószínűséggel 100 játék játszása 1000 forint kezdőöszegről 10 forintos téttel

16

3. fejezet Leghosszabb szériák vizsgálata 3.1. Bevezetés Diplomamunkám ezen fejezetében ismertetésre kerülő témával ezt megelőzően számos cikk foglalkozott már, bár ezen cikkek szóhasználatában eltérések figyelhetőek meg. Vannak olyan szerzők, akik leghosszabb futamnak, vagy siker-sorozatnak, vagy egyszerűen csak leghosszabb sorozatnak nevezik egy adott kísérletsorozatban az egymást követő azonos – azaz csak fej, vagy csak írás az érmedobásos kísérletben – jelek leghosszabb szériáját. Ebből következően az érmedobásos kísérletsorozatban az egymás után következő – azaz írással meg nem szakított – fejdobások számának a maximumát leghosszabb fejszériának fogom nevezni. Ebben a fejezetben ismert rekurziós és aszimptotikus tételeket, valamint az adott feladathoz tartozó szimulációs eredményeket fogom összehasonlítani. Ezek közül a rekurziós eljárásokra helyezem a hangsúlyt, mivel ezek szolgáltatják a pontos eredményeket. Az aszimptotikus eredmények csak hosszú dobássorozat esetén adnak jó közelítést, míg a szimulációs eredmények véletlenszerűek, és a kísérlet sokszori számítógépes megismétlése során közelítik meg a pontos értékeket. Emellett szeretnék kitérni mind a szabályos, mind a szabálytalan pénzérme esetére is, és mindkét féle érménél a leghosszabb fejszéria, és a leghosszabb bármilyen széria (legyen az tiszta fej vagy tiszta írás) hosszát vizsgálom meg. A szimulációt MATLAB programcsomag segítségével valósítottam meg, és ezen eredményeket ismertetem. Ezen fejezetben szeretnék kitérni mind a független kísérletsorozatra – visszatevéses mintavétel –, és a nem független kísérletsorozatra is – visszatevés nélküli mintavétel –, például francia kártya csomagból történő húzások során a leghosszabb bármilyen (fekete vagy piros) lapszéria hosszának szimulációjára is. Mivel a rekurziós eljárások által szolgáltatott pontos eredmény sajnos lassú sebességgel jár, így szeretnék ismertetni két módszert, amivel felgyorsíthatóak ezek a módszerek MATLAB programcsomagon belül. Mivel a MATLAB függvényhívások időigényesek, így az első megoldás során úgy gyorsítom fel a rekurziós függvény értékeinek kiszámítását, hogy az adott rekurziót átalakítom iteratív alakra, azaz kifejtem a képletet, és szükségtelenné teszem, hogy a függvény rekurzívan meghívja önmagát. A másik módszer során bemutatok egy módszert, ami segítségével MATLAB környezetből meghívhatóak C, C++ és Fortran rutinok, amely programnyelveknél a rekurziós függvényhívások nem olyan időigényesek, mint MATLAB esetében, így ezen rutinok meghívásával jelentős mértékben gyorsíthatóak a rekurzív függvények végrehajtásai. 17

3.2. Független kísérletsorozat

3.2. Független kísérletsorozat Bevezetésül tekintsük meg Varga Tamás kísérletét, amelyet Révész Pál 1978-ban ismertetett Helsinkinben egy nemzetközi matematikai konferencián [22], és később Schilling [25] cikkének bevezetőjeként is publikálásra került. Varga egy tanulócsoportot két részre osztott, majd az egyik csoportnak azt adta feladatul, hogy mindenki dobjon fel 200-szor egy pénzérmét, és jegyezze le a kapott eredményeket. A csoport másik részének pedig ugyanezt a kísérletet kellett elvégeznie gondolatban, és a gondolati eredményeket lejegyezni. Vagyis egy olyan 200 elemű fej-írás sorozatot kellett írniuk, amilyen egy 200 elemű dobássorozat lesz szerintük. A munka végeztével a két csoport lejegyzett eredményeit összekeverték, és átadták Vargának, aki majdnem 100%-osan megmondta, hogy az adott lapon valós, vagy kitalált eredmények szerepelnek. A megoldás onnan adódott, hogy amíg a valós sorozatokban nem volt ritka a 7, esetleg 8 egymást követő fej – Rényi Alfréd log2 200-as eredménye szerint –, addig a gondolati sorozatokban a hallgatók maximum öt azonos jelet mertek egymás után leírni. A kísérlet továbbvitelét megtalálhatjuk Fazekas István, Karácsony Zsolt és Libor Józsefné [8] közös cikkében, miszerint Révész Pál, miután ismertette a Varga-féle kísérletet, és megbeszélte az eredményt a hallgatóival, újra elvégeztette az eredeti kísérletet. Az összegyűjtött papírlapokat újra sikerült majdnem teljes pontossággal szétválogatni Révésznek. A megoldás ebben az esetben abból a tényből következett, hogy a hallgatók többsége csakis az egyikféle jelre koncentrált (például a leghosszabb fejszéria), és nem figyelt a másikfélére. Ez alapján került feltevésre a [8] cikkben a következő két kérdés: Egy n hosszúságú sorozat esetén hogyan alakul a leghosszabb fejszéria hossza? Egy n hosszúságú sorozat esetén mekkora a leghosszabb bármilyen széria hossza?

3.2.1. Szabályos pénzérme esete Leghosszabb fejszéria vizsgálata Schilling [25] cikke nyomán vizsgáljuk meg a következő kísérletet. Dobjunk fel egy szabályos pénzérmét n-szer. Fejszériának nevezzük el az egymást követő, azaz írással meg nem szakított fejdobások sorozatát. Jelölje Rn a leghosszabb fejszéria nagyságát. Az eloszlásfüggvény így felírható a következő alakban: Fn (x) = P (Rn ≤ x). Fn (x)-et elegendő nemnegatív egész x-ekre megadni, mivel Fn (x) = 0, ha x < 0, és Fn (x) = Fn (|x|), ha x ≥ 0. ahol |x| jelöli x egészrészét. Jelölje An (x) azon n hosszúságú sorozatok számát, amelyekben a leghosszabb fejszéria nem haladja meg x-et. Szabályos pénzérme esetén egy n elemű sorozatot vizsgálva kapjuk, hogy Fn (x) = P (Rn ≤ x) =

An (x) . 2n

Felmerül ekkor a kérdés, hogy hogyan határozható meg An (x) értéke. Ehhez vizsgáljuk meg először azt az esetet, amikor a leghosszabb fejszéria legfeljebb 3 elemű lehet, azaz x = 3. Ha n ≤ 3, akkor An (3) = 2n , mivel minden lehetséges eset megfelel annak a feltételnek, hogy az egymás utáni fejek száma legfeljebb 3 lehet. Viszont ha n > 3, akkor a vizsgálat szempontjából kedvező sorozatok kezdődhetnek a következőképpen: I, FI, FFI, FFFI, ahol F a fejet, I pedig az írást jelöli, és utánuk csak olyan sorozat szerepel, amelyben nincs háromnál hosszabb fejszéria. Így felírható a következő: An (3) = An−1 (3) + An−2 (3) + An−3 (3) + An−4 (3), ha az n > 3. 18

3.2. Független kísérletsorozat Ugyanezzel a módszerrel felírható az általános rekurziós képlet. 3.1. tétel. (Schilling [25], 198. o.) P x  An−1−j (x), ha n > x, An (x) = j=0  n 2 , ha 0 ≤ n ≤ x. Rn aszimptotikus viselkedését Földes Antónia [12] alábbi tétele írja le. 3.2. tétel. (Földes [12]) Valamennyi egész k esetén n log n −(k+1−{ log }) log 2 P Rn − < k = exp − 2 + o(1), log 2 ahol [a] jelöli az egészrészét a-nak, és {a} = a - [a], azaz a törtrésze. Leghosszabb bármilyen széria vizsgálata Vegyük itt is kiindulási alapként Schilling [25] cikkét. Dobjunk fel egy szabályos pénzérmét n-szer, és jelölje Rn0 a leghosszabb széria nagyságát, amely lehet tiszta fej vagy tiszta írás sorozat. Jelölje Bn (x) azon n hosszúságú sorozatok számát, amelyekben a leghosszabb tetszőleges széria nem haladja meg x-et. Szabályos érme esetén egy n elemű sorozatot vizsgálva felírhatjuk az eloszlásfüggvényt: Fn0 (x) = P (Rn0 ≤ x) =

Bn (x) . 2n

Használjuk fel Schilling [25] 199. oldalon leírt ötletét! A fej-írás sorozat minden eleme alatt jelölje A azt, hogy az utána következővel azonos a vizsgált elem, és K azt, hogy különböző. Például: F

F A

I K

I A

F K

F A

F A

Az alsó A, K elemekből álló sorozatban a leghosszabb tiszta A sorozat akkor és csakis akkor k − 1 hosszú, ha a felső sorban a leghosszabb tiszta széria k hosszúságú. Ha a felső sorozat n hosszú, és ebben a leghosszabb széria k elemű, akkor az alsó sorozat n − 1 elemű, és a leghosszabb A széria k − 1 elemű. Azaz fennáll a következő: Bn (x) = 2An−1 (x − 1), mivel minden alsó sorozat pontosan kétféle felső sorozathoz tartozhat. Ezt felhasználva kapjuk: Fn0 (x) = P (Rn0 (x) ≤ x) = és

Bn (x) 2An−1 (x − 1) An−1 (x − 1) = = , 2n 2n 2n−1

An−1 (x − 1) = P (Rn−1 ≤ x − 1) = Fn−1 (x − 1). 2n−1 Ezzel beláttuk, hogy Fn0 (x) = Fn−1 (x − 1), 19

3.2. Független kísérletsorozat vagyis visszavezettük esetünket a tiszta fejszéria esetére. Vizsgáljuk meg most azt az esetet, amikor a leghosszabb széria pontosan k hosszúságú. Vezessük be a következő jelöléseket: bn (k): n dobásból hányszor lesz a leghosszabb széria pontosan k hosszúságú, an (k): n dobásból hányszor lesz a leghosszabb fejszéria pontosan k hosszúságú. A bn (k) viselkedésére Szászné Simon Judit a doktori értekezésében [29] ad rekurzív képletet. 3.3. lemma. (Szászné [29].) Minden n = 1, 2, . . . esetén bn (1) = bn (n) = 2, bn (r) = 0, ha r > n vagy r ≤ 0 bn (r) =

r−1 X

bn−h (r) +

r X

bn−r (i), ha 1 < r < n.

i=1

h=1

Bizonyítás. (Fazekas-Karácsony-Liborné [8], 4. oldal) Vizsgáljuk meg, mit jelent a lemma jobb oldalán levő két összeg. Bontsuk fel az eseményteret aszerint, hogy milyen hosszú széria szerepel elől. Ha a sorozatunk h (h = 1, 2, . . . , r − 1) hosszúságú szériával kezdődik, akkor a maradék n − h dobásból kell a leghosszabb szériának r hosszúságúnak lennie. Ha a kezdő h széria fej, akkor a (h + 1)-edik elemnek írásnak kell lennie. Ha a kezdő h széria írás, akkor a (h + 1)-edik elemnek fejnek kell lennie. . . . F . .}. F . . F} I| . . . F {z | .{z

h db fej n − h elem között r hosszú széria (1 ≤ h < r)

vagy: . . . I . .}. I| .{z . . I} F | . . . I{z

h db írás n − h elem között (1 ≤ h < r) r hosszú széria

De ennek a kettőnek a száma megegyezik, és az összegük éppen: r−1 X

bn−h (r).

h=1

Ha r hosszúságú szériával kezdődik a sorozat, akkor a maradék n − r elemből i = 1, 2, . . . , r hosszú széria lehet. Ha az első r elem fej, akkor az (r + 1)-edik elemnek írásnak kell lennie, míg ha az első r elem írás, akkor az (r + 1)-ediknek fejnek kell lennie. F . . F} I| . . . F {z . . . F . .}. | .{z r db fej

n − r elem között legfeljebb r hosszú széria

I| .{z . . I}

F . . . I . .}. | . . . I{z

vagy r db írás

n − r elem között legfeljebb r hosszú széria

Ezen két részeset száma egyenlő, összegük pedig a következő alakban írható fel: r X

bn−r (i).

i=1

20

3.2. Független kísérletsorozat A bn (r)-rel tehát megadtuk azon sorozatok számát, amelyekben az n dobás során a leghosszabb bármilyen széria hossza pontosan r. Rn0 aszimptotikus viselkedésének vizsgálatához Földes [12] idézett eredményének segítségével eljuthatunk a következő tételig. (Fazekas-Karácsony-Liborné [8]) 3.4. tétel. Valamennyi egész k esetén log(n−1) log(n − 1) −(k−{ log 2 }) 0 < k = exp − 2 + o(1), P Rn − log 2 ahol [a] az a szám egészrészét, {a} pedig az a törtrészét jelöli.

3.2.2. Alkalmazás bemutatása szabályos pénzérme esetében Ezen alfejezetben szeretném bemutatni az alkalmazásom által kiszámított rekurzív, aszimptotikus, és szimulációs eredményeket, illetve ismertetném az itt alkalmazott két rekurziós képlet iteratív alakra való hozatalát és az iteratív algoritmust, illetve összehasonlítanám sebesség alapján a két megoldási módszert. Alkalmazott gyorsítás bemutatása leghosszabb fejszéria esetén Ebben a szakaszban használjuk fel Schilling [25] már korábban ismertetett tételét (3.1. tétel.), és fejtsük ki ennek alakját. Tekintsük először az n = 1 esetet. Ebben az esetben egy hosszúságú sorozatokat vizsgálunk, azaz a 0 és az 1 sorozatot. Az x értéke ilyenkor legyen egy, azaz legfeljebb egy hosszúságú sorozatot keresünk. Ekkor Schilling tétele alapján: A1 (1) = 21 = 2, mivel n = x. Ezután vizsgáljuk meg az n = 2 esetet, amikor kettő hosszúságú sorozatokat (00, 01, 10, 11) vizsgálunk. Ekkor x változó értéke felveheti az egyet, illetve a kettőt. Írjuk fel ezeket a tétel alapján: A2 (1) = A1 (1) + A0 (1) = 21 + 20 = 3, A2 (2) = 22 = 4. Ugyanilyen módon vizsgáljuk meg n = 3 esetet, ahol x = 1, 2, 3. A3 (1) = A2 (1) + A1 (1) = 3 + 21 = 5, A3 (2) = A2 (2) + A1 (2) + A0 (2) = 4 + 21 + 20 = 7, A3 (3) = 23 = 8. Ezt a módszert folytatva felépíthetjük azt a fát, amely n mélységű, és n szélességű, és tartalmazza az n. szinten az adott n és az összes x = 1, 2, . . . n értékpárokhoz tartozó értékeket a következő alakban:

21

3.2. Független kísérletsorozat 2

144

3

4

5

7

8

8

13

15

16

13

24

29

31

32

21

44

56

61

63

64

34

81

108

120

125

127

128

55

149

208

236

248

253

255

256

89

274

401

464

492

504

509

511

512

504

773

912

976 1004

1016

1021

1023

1024

Ebből a táblázatból lehet képezni először egy adott n-hez tartozó eloszlásfüggvényt, amit a legegyszerűbben úgy képezhetünk, hogy a táblázat minden sorát elosztjuk az adott sor utolsó elemével. Például n = 5 esetén: 1

13 32

8 16 24 32

5 8 13 16 29 32

3 4 7 8 15 16 31 32

1 1 1 1

Ebből az eloszlásfüggvényből pedig könnyedén képezhetünk sűrűségfüggvényt numerikus deriválással. Mivel diszkrét értékekkel van dolgunk, így mindegyik elemből kivonhatjuk az előtte lévő elemet, így megkapjuk a sűrűségfüggvényeket tartalmazó táblázatot. Maradva n = 5 eseténél: 1

13 32

8 16 11 32

5 8 5 16 5 32

3 4 2 8 2 16 2 32

1 4 1 8 1 16 1 32

3.5. megjegyzés. Ha a legelső táblázatot megvizsgáljuk, akkor megfigyelhető, hogy minden n esetén a legelső elem az n+1. Fibonacci elemmel, az n. elem pedig 2n hatvány értékével egyezik meg. Elért sebességjavulás Vizsgáljuk meg az előbb ismertetett iteratív átírás és Schilling rekurzív tétele alapján megírt rekurzív függvény egymáshoz viszonyított sebességét. A méréshez használjuk a MATLAB programcsomag beépített függvényeit (tic, toc). A következő táblázatban közlöm az értékeket különböző n esetekre. Az alkalmazott számítógép paraméterei: AMD Athlon 64 X2 Dual Core Processor 6000+, 4 GB, DDR2 memória. 22

3.2. Független kísérletsorozat n

Rekurziós képlet

Iteratív átírás

5

0.004116 seconds

0.000043 seconds

10

0.020726 seconds

0.000073 seconds

15

0.407710 seconds

0.000107 seconds

19

5.383905 seconds

0.000152 seconds

20

10.400094 seconds

0.000171 seconds

21

19.938068 seconds

0.000182 seconds

Alkalmazott gyorsítás bemutatása leghosszabb bármilyen széria esetén Ebben a szakaszban alkalmazzuk Szászné [29] korábban ismertetett lemmáját (3.3. lemma.), és fejtsük ki az alakját. Tekintsük először az n = 1 esetet, azaz egy hosszúságú sorozatokban keresünk legfeljebb x hosszúságú szakaszokat. Szászné állítását alkalmazva: b1 (1) = 2, mivel bn (1) = 2. Számoljuk ki az n = 2 esetet: b2 (1) = 2, b2 (2) = 2. Tekintsük az n = 3 esetet, amikor az x értéke lehet egy, kettő, illetve három! b3 (1) = 2, b3 (2) =

1 X

b3−h (2) +

2 X

b1 (i) = b2 (2) + b1 (1) + b1 (2) = 2 + 2 + 0 = 4,

i=1

h=1

b3 (3) = 2. Ezt a módszert folytatva felírhatunk egy n mélységű és szélességű fát, amelynek n. szintjéről kiolvashatjuk adott n mellett adott x-ekhez tartozó értékeket a következő alakban: 2

2

2

2

2

4

2

2

8

4

2

2

14

10

4 2

2

24

22

10

4

2

2

40

46

24

10

4

2

2

66

94

54

24

10

4

2

2

108

188

118

56

24

10

4

2

176

370

254

126 56

24

10

4

2 23

3.2. Független kísérletsorozat 3.6. megjegyzés. A táblázatot megfigyelve megállapítható, hogy minden sor összege megegyezik 2n , n = 1, 2, . . . értékével. Ez azért igaz, mivel x = 1, 2, . . . n számokra összegezzük azon eseteket, amelyekben a leghosszabb bármilyen széria pontosan x, így valójában az összes n hosszúságú, két jelből álló sorozatokat kapjuk, amiknek számossága 2n . A táblázatban ebben az esetben nem eloszlásértékek, hanem sűrűségértékek találhatóak, így itt nem szükséges numerikus deriválás, mindössze minden sorozatbeli értéket le kell osztani 2 sorszámadik hatványával. Így megkapjuk a következő táblázatot, n = 5 esetnél: 1

2 32

2 16 14 32

2 8 8 16 10 32

2 4 4 8 4 16 4 32

2 4 2 8 2 16 2 32

Elért sebességjavulás Vizsgáljuk meg az előbb ismertetett iteratív átírás és Szászné állítása alapján megírt rekurzív függvény sebességeinek egymáshoz való viszonyát. Méréshez itt is használjuk a MATLAB programcsomag beépített függvényveit. A következő táblázatban közlöm különböző n esetekre az értékeket. n

Rekurziós képlet

Iteratív átírás

5

0.000964 seconds

0.000013 seconds

10

0.018185 seconds

0.000030 seconds

15

0.592443 seconds

0.000072 seconds

19

9.546739 seconds

0.000156 seconds

20

19.722337 seconds

0.000173 seconds

21

39.007926 seconds

0.000179 seconds

Alkalmazás bemutatása A következő ábrákon pirox „x” jelöli az aszimptotikus, fekete „o” a rekurzióval kapott eredményeket, az oszlopdiagram pedig a szimulációval kapott eredményeket mutatja. Mindkét ábrán a bal oldalon szerepelnek a leghosszabb fejsorozatok eredményei, míg a jobb oldalon a leghosszabb bármilyen szériák eredményei. Mindkét esetre 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 eredményeket. Nagy n értékere a rekurziós, aszimptotikus és a szimulációs értékek gyakorilatilag egybeesnek. Míg kis n esetén a rekurziós algoritmus gyors, n növelésével rohamosan lassul a számítási eljárás, ezért célszerű alkalmazni a fentebb ismertetett gyorsító eljárás. Futassuk le n = 50 esetre, 0.5-ös valószínűséggel, 10000-es kísérletszámra! Ezután

24


3.1. ábra. Leghosszabb szériák, n = 50, p = 0.5, 10000-es kísérletszám futassuk le ugyanilyen n esetre, de 100000-s kísérletszámmal! Ebben az esetben már megfigyelhető, hogy a szimulációs eredmények sokkal jobban megközelítik a rekurzióból adódó pontos eredményeket.

3.2. ábra. Leghosszabb szériák, n = 50, p = 0.5, 100000-es kísérletszám

3.2.3. Szabálytalan pénzérme esete Ebben az esetben a fejdobás valószínűsége, azaz p értéke bármilyen valós szám lehet a (0, 1) intervallumon. Kérdés, hogy ez a tény milyen hatással van a leghosszabb fej-, illetve a leghosszabb bármilyen széria alakulására. Ebben az esetben nyilvánvalóan nem lehet alkalmazni a klasszikus kedvező/összes formulát. 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.

25

3.2. Független kísérletsorozat Leghosszabb fejszéria vizsgálata Schilling [25] cikke alapján tekintsük azon n hosszúságú fej-írás sorozatokat, ame(k) lyekben k darab fej szerepel. Ezek közül jelentse Cn (x) azon sorozatok számát, amelyekben legfeljebb x fej következik egymás után, azaz a leghosszabb fejszéria legfeljebb x hosszúságú. Az adott jelölésekkel az eloszlásfüggvény a következő alakban írható fel Fn (x) = P (Rn ≤ x) =

n X

Cn(k) (x)pk q n−k .

k=0

3.7. lemma. (Schilling [25], 200. o.)  x P (k−j)    j=0 Cn−1−j (x), ha x < k < n. Cn(k) (x) = n ha 0 ≤ k ≤ x,  k,   0, ha x < k = n. Bizonyítás. (Fazekas-Karácsony-Liborné [8], 8. o.) Ha x < k = n, akkor nyilvánvalóan Cnk (x) = 0, hiszen ekkor az összes x-nél több elem fej, így nincs olyan sorozat, ahol legfeljebb x fej van egymás után. Ha 0 ≤ k ≤ x, akkor Cnk (x) éppen a binomiális együtthatókat adja, hiszen ez az az eset, amikor az n elem között legfeljebb x fej van, és azon eseteket kell összeszámlálni, amikor a leghosszabb fejszéria legfeljebb x. Márpedig ekkor az összes sorrend ilyen tulajdonságú. Ha x < k < n, akkor az állítás helyességének belátásához elegendő átgondolnunk a következőket. A sorozatunk kezdődhet j = 0, 1, 2, . . . , x fejjel, utána biztosan van egy írás, majd olyan sorozat következik, ahol a maradék n − j − 1 elem között k − j darab fej van úgy, hogy a leghosszabb fejszéria legfeljebb x hosszúságú. F . . F} I | .{z j db fej

... |

F

... {z

I

... }

n − j − 1 elem, melyben k − j darab fej van úgy, hogy legfeljebb x hosszú a fejszéria

(k−j)

Ezek száma pedig éppen Cn−1−j (x). Ezzel az állítás helyességét beláttuk.

Vizsgáljuk meg, hogy mi lesz annak a valószínűsége, hogy n dobásból a leghosszabb fejszéria pontosan k hosszúságú? Jelölje ezt p(n, k), amelyre Kopocinski [16] cikkében ad két formulát. Ezen két formula alkalmazhatóságához jegyezzük meg, hogy:   0, ha k < 0,    ha k ≥ n, Fn (k) = 1, k  P   p(n, i) egyébként. i=0

3.8. tétel. (Kopocinski [16], Theorem 1, (2), (3).) Legyen p(n, k) = 0, ha k < 0, vagy k > n, p(k, k) = pk , ha k = 0, 1, 2, . . . . Ekkor p(n, k) =

k−1 X

pj qp(n − j − 1, k) + pk qFn−k−1 (k).

j=0

26


k

p(n, k) = p qFn−k−1 (k) +

n−k−2 X

Fj (k − 1)q 2 pk Fn−j−k−2 (k) + Fn−k−1 (k − 1)qpk ,

j=0

ha n = k + 1, k + 2, . . . , k = 0, 1, 2, . . . , és Fn (k) jelöli annak a valószínűségét, hogy n esetből legfeljebb k hosszúságú fejszéria adódik. Az aszimptotikus viselkedés leírását Gordon-Schilling-Waterman [15] cikkében adják meg a következő tétellel. log n , q = 1 − p és 3.9. tétel. (Gordon-Schilling-Waterman [15].) Legyen µ(n) = − log p legyen W olyan, hogy teljesüljön rá: P (W ≤ t) = exp(− exp(−t))), ekkor t-ben egyenletesen: W P (Rn − µ(qn) ≤ t) − P + {µ(qn)} − {µ(qn)} ≤ t → 0, − log p ahol n → ∞. Leghosszabb bármilyen széria vizsgálata Egy szabálytalan pénzérmét feldobva n-szer, jelölje Rn0 a leghosszabb bármilyen széria – akár fej, akár írás – nagyságát. Ilyen esetben adódik a következő összefüggés. 3.10. lemma. (Schilling [25].) Fn0 (x)

=

P (Rn0

≤ x) =

n X

C¯n(k) (x)pk q n−k ,

k=0 (k)

ahol C¯n (x) jelenti azon n hosszúságú sorozatok számát, amelyekben k darab fej van, a leghosszabb bármilyen széria hossza legfeljebb x, és ahol C¯n(k) (x) = Cx+1 (m, k), valamint a Cx (m, k) mennyiségek kielégítik Bloom [3] két állítását. Itt Cx (m, k) jelöli, hogy m piros és k fekete folyót visszatevés nélkül kihúzva nem lesz x hosszúságú széria. Ct (m, k) értékeire Bloom [3] adott két rekurzív képletet, amelyeket a Fazekas-Karácsony-Liborné [8] cikkében megjelent bizonyításaikkal együtt a következő alfejezetben ismertetek. Rn0 aszimptotikus viselkedését vizsgálva Muselli [21] tételét lehet felhasználni, melyben 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: ( 0, ha 0 ≤ p < 1/2, lim Vn (p) = n→∞ 1, ha 1/2 < p ≤ 1. Azaz egyhez tart annak a valószínűsége, hogy a leghosszabb széria az esélyesebb kimenetelből, azaz jelen esetben fejekből áll.

3.2.4. Alkalmazás bemutatása szabálytalan pénzérme esetén Ebben az alfejezetben szeretném bemutatni az alkalmazásom által kiszámított rekurzív, aszimptotikus és szimulációs eredményeket, illetve ismertetném az itt alkalmazott két rekurziós képlet gyorsításának egy másik megoldását, és összehasonlítanám a hagyományos rekurzióval sebesség alapján. 27

3.2. Független kísérletsorozat MEX-fájlok A MATLAB M programozási nyelven írt programjai kitűnőek arra, hogy olyan függvényeket és szkripteket írjunk, amelyek gyorsan futnak a MATLAB beépített függvényeinek köszönhetően. Ennek a programozásnak az egyik nagy előnye, hogy ezeket a fájlokat nem kell lefordítani, és futnak bármilyen rendszeren, amin már fut a MATLAB programcsomag. A MATLAB ezt úgy éri el, hogy a fájlokat minden egyes futáskor soronként interpretálja. Ennek a módszernek az a hátránya, hogy nagyon lassúvá válhat a végrehajtás nagy méretű, bonyolult függvények esetén, főleg azoknál, ahol nagyon sok ciklus van a megvalósításban, mivel a MATLAB a ciklus minden egyes végrehajtásakor a ciklus összes sorát újrainterpretálja, ami jelentősen lassítja a végrehajtást. Ezeket a legegyszerűbben úgy kerülhetjük el, hogy alkalmazzuk a beépített függvényeket, illetve a vektorműveleteket. Viszont ez nem elég minden helyzetben. Ennek a problémának a kiküszöbölésére kibővítették a MATLAB programcsomagot, hogy képes legyen C, C++ és Fortran nyelvekben írt függvények futtatására. Azokat a fájlokat nevezzük MEX-fájloknak (Matlab EXecutable), amelyek ezen nyelvekben íródott függvényeket tartalmazzák. Az így íródott MEX-függvények nem helyettesíthetik a MATLAB beépített függvényeit, viszont jelentős sebességjavulást lehet velük elérni ciklusoknál és olyan feladatoknál, amiknél a MATLAB lehetőségei nem megfelelőek. Ez a kiegészítés lehetővé teszi rendszerspecifikus API-k hívását, hogy kiegészítse a MATLAB lehetőségeit. Ebben a szakaszban szeretnék ismertetni pár egyszerűbb programkódot C nyelven, amelyek segítségével megérthetőek a MEX használatának alapjai. Az itt ismertetett programrészletek Jason Laska [17] programjai alapján készültek. MATLAB felé való interfész Amikor C nyelven írunk programokat, akkor mindig feltételezzük, hogy a program végrehajtása a main() függvényben kezdődik. A MEX-fájlok felépítése hasonló, itt a végrehajtás mindig egy különleges függvényből indul, aminek mexFunction a neve. Ez a függvény valósítja meg az „átjárót” a MATLAB függvényhívás és a C kód között. # include "math.h" # include "mex.h"

// Ez a sor szükséges

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) { //Minden kód, és belső függvény idekerül return; } Ahhoz, hogy elkészítsünk egy MEX függvényt, szükséges a "mex.h" könyvtár, ami tartalmazza az API-t, amit a MATLAB nyújt. A mexFunction függvénynek négy bemeneti paramétere van, amik a MATLAB függvényhívásnak felelnek meg: • nlhs: Ez a paraméter jelképezi a „baloldali” argumentumok számosságát, azaz hány kimeneti értéke lesz a függvénynek. • plhs: Ez a paraméter egy tömb, amibe a tényleges kimeneti argumentumok kerülnek. Az mxArray típus egy MATLAB struktúra adatok tárolására. 28

3.2. Független kísérletsorozat • nrhs: Ez a „ jobboldali” argumentumok számosságát jelenti, azaz hány bemeneti értéke van a függvénynek. • prhs: Ez a tömb tárolja a tényleges bemeneti értékek mutatóit. Adatok átvétele, és készítése Mint korábban említésre került, a fő MATLAB struktúra adatok tárolására MEXfájlokban az mxArray. Ebben a struktúrában tárolhatunk valós, komplex számokat, tömböket, mátrixokat, sztringeket és az összes egyéb MATLAB struktúrát. Ebben a paragrafusban szeretném bemutatni, hogyan kell egyszerűbb adattípusokat kezelni. Tételezzük fel, hogy a példafüggvényeünknek három különböző bemeneti értéke van, amik legyenek x egy kétdimenziós mátrix, y egy sztring és z egy szám. Ahhoz, hogy a x értékéhez hozzáférjünk, szükségünk lesz egy mutatóra, amit a prhs tömbben találhatunk meg. Ezt a mutatót átmásoljuk egy xData nevű változóba. //A mexFunction-ön belül //Deklarációk mxArray *xData; double *xValues; int i, j; int rowLen, colLen; double avg; //Másoljuk át az xData-ba x mutatóját xData = prhs[0]; //Tároljuk le az x mátrixot xValues = mxGetPr(xData); rowLen = mxGetN(xData); colLen = mxGetM(xData); //Írassuk ki a matlab konzolba minden oszlop átlagát for(i = 0; i < rowLen; i++) { avg = 0; for(j = 0; j < colLen; j++) { avg += xValues[(i * colLen) + j]; } avg = avg / colLen; printf("Az %d sor átlaga: %d ", i, (int)avg); } Az mxGetPr függvényt használjuk, hogy kinyerjük a valós adatot onnan, ahova az xData mutató mutat. Ehhez hasonló az mxGetPi függvény, ami a komplex értékek kinyerésénél használatos. Az mxGetN és mxGetM függvények a sorok, és oszlopok nagyságát adják vissza. Ha ez egy tömb lenne, akkor a kettő közül az egyik nullát adna vissza. MATLAB mátrixon belüli mozgás során ahhoz, hogy az x. sor y. elemére ugorjunk a 29

3.2. Független kísérletsorozat x*colLen+y képletet kell használnunk. A printf() függvény a MATLAB prompt-jára írja ki a szöveget. A sztringek kinyerése is hasonló módon történik, de vannak sajátosságai. //A mexFunction-ön belül //Deklarációk mxArray *yData; int yLength; char *TheString; //Másoljuk át az y bemeneti mutatóját yData = prhs[1]; //Készítsük el a "TheString" nevű változót yLength = mxGetN(yData) + 1; //mxCalloc hasonló a C-ben használt malloc parancsnhoz TheString = mxCalloc(yLength, sizeof(char)); mxGetString(yData ,TheString ,yLength); Most pedig nézzük meg, hogyan kell egy egyszerű valós számértéket feldolgozni. //A mexFunction-ön belül //Deklarációk mxArray *zData; int Num; //Másoljuk át z bemeneti mutatóját zData = prhs[2]; //Nyerjük ki a szám értékét Num = (int)(mxGetScalar(zData)); //és írassuk ki printf("Az átadott szám %d", Num); Most vizsgáljuk meg, hogyan kell az értékeket visszaadni a MATLAB-nak. Ez a módszer nagyon hasonló az adatok kinyeréséhez. Itt annyi különbség van, hogy memóriaterületet előre le kell foglalni az adatstruktúránknak. A mostani példában vizsgáljuk meg egy kétdimenziós mátrix esetét, ami az x bemeneti mátrix értékét lemásoljuk z0 változóba, és minden értéket megdupláz. //A mexFunction-ön belül //Deklarációk mxArray *xData; double *xValues, *outArray; int i, j; int rowLen, colLen; 30


//Másoljuk át az x bemeneti mutatóját xData = prhs[0]; //Nyerjük ki a mátrixot xValues = mxGetPr(xData); rowLen = mxGetN(xData); colLen = mxGetM(xData); //Foglaljuk le a memóriaterületet a kimenetnek plhs[0] = mxCreateDoubleMatrix(colLen, rowLen, mxREAL); //mxReal az adattípus, amit használunk //Szerezzük meg az újonnan lefoglalt területünk mutatóját outArray = mxGetPr(plhs[0]); //Másoljuk át a mátrixot, és duplázzuk meg az értékét for(i = 0; i < rowLen; i++) { for(j = 0; j < colLen; j++) { outArray[(i * colLen) + j] = 2 * xValues[(i * colLen) + j]; } } MATLAB függvények hívása Míg jelentős gyorsulást lehet elérni C függvények írásával, rengeteg hatékony, gyors MATLAB függvény van, amiket felesleges újraírni. Szerencsére a MATLAB programcsomagon belül van lehetőség ezen függvények meghívására egy MEX-fájlból, mivel a beépített függvények paraméterszignatúrája hasonló ahhoz, amit a mexFunction megírásakor alkalmaztunk. Példánk során használjuk a következő függvényt: z=conv(x,y);. //A mexFunction-ön belül //Deklarációk mxArray *result; mxArray *arguments[2]; //Hozzunk létre tetszőleges bemeneti adatokat arguments[0] = mxCreateDoubleMatrix(1, 20, mxREAL); arguments[1] = mxCreateDoubleMatrix(1, 10, mxREAL); //Hívjuk meg a függvényt mexCallMATLAB(1, &result, 2, arguments, "conv"); Fordítás menete A MEX-fájlok fordítása hasonló ahhoz, mint amikor parancssoros fordítókat haszná31

3.2. Független kísérletsorozat lunk (például gcc, lcc). A MATLAB parancsfelületen módosítsuk a munkakönyvtárunkat a MEX forrásfájl könyvtárára, majd adjuk ki a következő parancsot mex fájlnév.c. A MATLAB ezután fordítót kér, amit kiválaszthatunk a számítógépre telepített fordítók közül. A függvény neve az lesz, ami a MEX-fájl neve. Miután lefordítottuk, és létrejön a MEX-bináris, a függvényünk ugyanúgy hívható, mint egy MATLAB beépített függvény. A bináris fájl neve operációs rendszertől függ, így minden különböző operációs rendszerre le kell fordítani a MEX-fájlunkat.

3.2.5. Alkalmazás bemutatása, elért gyorsulások Először vizsgáljuk meg, hogyan alakul a rekurziós képlet átírása fejsorozatok esetén. A következő táblázatban megtalálhatóak a rekurziós függvények futási idői, a rekurzió megvalósítása MEX segítségével C nyelven, az eredeti rekurziós képlet átírása iterált alakká MATLAB, majd pedig MEX segítségével. Minden oszlopban addig szerepelnek a futási adatok, amíg nem távolodnak el túlságosan a többi eredmény értékétől. n

Rekurziós képlet

Rekurzió MEX

Iterált alak MATLAB

Iterált alak MEX

5

0.004197 seconds

0.003268 seconds

0.003545 seconds

0.000099 seconds

10

0.074732 seconds

0.000170 seconds

0.022365 seconds

0.000151 seconds

15

1.831641 seconds

0.000787 seconds

0.069216 seconds

0.000191 seconds

20

46.103427 seconds

0.018086 seconds

0.154397 seconds

0.000280 seconds

25

x

0.455444 seconds

0.296737 seconds

0.000446 seconds

30

x

12.527989 seconds

0.496011 seconds

0.000732 seconds

35

x

x

0.781636 seconds

0.001465 seconds

50

x

x

2.256716 seconds

0.004180 seconds

75

x

x

14.026925 seconds

0.020407 seconds

100

x

x

47.924833 seconds

0.067935 seconds

A táblázat adataiból jól látható, hogy míg a MATLAB rutin C nyelvre való átirata jelentős sebességgyorsulást ért el, viszont láthatóan önmagában nem megfelelő, mivel ugyanúgy igaz rá, hogy n növelésével körülbelül duplázódik a végrehajtási ideje a rekurzió miatt. Ezért célszerű itt is megvalósítani iterált alakban a számítást, viszont a legjobb sebességet az iteratív alak C nyelven történő megírása adja, így célszerű elvégezni mindkét átalakítást. Ezután vizsgáljuk meg a bármilyen sorozat hosszára vonatkozó adatokat ugyanúgy, mint az előző módon.

32


n

Rekurziós képlet

Rekurzió MEX

Iterált alak MATLAB

Iterált alak MEX

5

0.003633 seconds

0.000150 seconds

0.002834 seconds

0.000076 seconds

10

0.028432 seconds

0.000133 seconds

0.003553 seconds

0.000160 seconds

15

1.7317445 seconds

0.001297 seconds

0.012953 seconds

0.000421 seconds

20

73.444427 seconds

0.044313 seconds

0.027736 seconds

0.000896 seconds

25

x

1.760836 seconds

0.053723 seconds

0.001324 seconds

30

x

60.236106 seconds

0.089415 seconds

0.002622 seconds

35

x

x

0.140080 seconds

0.003842 seconds

50

x

x

0.433712 seconds

0.013997 seconds

75

x

x

1.502445 seconds

0.058515 seconds

100

x

x

3.783460 seconds

0.169286 seconds

Ezen táblázat adataiból is ugyanolyan jól látható, hogy bár a MEX-es átírás jelentős gyorsulást ér el, viszont egy rekurzív algoritmus megvalósításához jó sebességgel önmagában még kevés, ezért itt is meg kell valósítani az iterált alakká való átírást. Tekintsük meg a program által adott szimulált eredményeket, összehasonlítva a rekurziós eljárásból származó pontos eredményekkel! Mivel a rekurziós eljárás pontos eredményeket szolgáltat, és az iteratív átírásainak sebessége már használhatóvá teszi, így ezen ábrákon mellőzöm az aszimptotikus képletek megjelenítését, mivel azokról már korábban megállapítottuk, hogy csak nagy n esetén közelítik meg a pontos eredményt. Tekintsük meg az eredményeket n = 50, p = 0.25 esetére, a szimulációt 100000-szer végrehajtva!

3.3. ábra. Leghosszabb szériák, n = 50, p = 0.25, 100000-es kísérletszám Ismételjük meg ezt a kísérletet p = 0.85 értékre. Az első ábrán jól látható, hogyha a 1 fejek valószínűsége kisebb, mint , akkor a fejsorozatok, és bármilyen sorozatok alakja 2 jelentős mértékben eltérhet egymástól, míg ha a valószínűség az egy értéket közelíti meg, akkor eltűnik az az egy oszlopos különbség, ami megfigyelhető p = 0.5 esetén, 33


3.4. ábra. Leghosszabb szériák, n = 50, p = 0.85, 100000-es kísérletszám mivel p = 0.85 valószínűség mellett nagyon kevés esetben lesz a leghosszabb bármilyen sorozat értéke különböző, mint az adott sorozatban a leghosszabb fejsorozat értéke, így az ábrázolás során a két ábra nagyon hasonló alakot vesz fel.

3.2.6. Hibaszámításos alkalmazás bemutatása A pénzfeldobásos kísérlet során felmerülhet az a kérdés, hogy mi történik abban az esetben, ha az érmék eredményei között történik egy sérülés. Ilyen eset lehet például az, hogy amikor a jelsorozatot zajos csatornán küldjük, akkor megváltozhatnak az értékek, vagy olyan értéket kaphatunk, amiről nem lehet eldönteni, hogy az fejet vagy írást jelentett eredetileg. Így lehet beszélni hibákról a sorozatokban. Érdemes megvizsgálni, hogy mi történik, ha az érmedobásos kísérlet során 1, 2, . . . hibát megengedünk. Ennek a problémának a vizsgálatára készült el a hibás szériákat vizsgáló programrész, ami egy hisztogramon egymás mellett ábrázolja a hibátlan, egy, kettő illetve három hibát elfogadó eseteket. Fontos megemlíteni, hogy a program megírására használt algoritmus nemcsak ezekre a hibaszámokra szolgáltat eredményt, hanem nagyobb hibaszámokra is – a hibaszámok határa maga a játékszám lehet, viszont ha játékszámnyi hibát engedünk meg, akkor a maximális sorozatok egyértelműen játékszám hosszúak lesznek, de ez ugyanígy igaz a játékszám - 1 értékre, mivel ha egy fej, vagy egy írás található, ami nem sérült, amellé lehet írni játékszám - 1 megegyező jelet (természetesen, ha a nem sérült érménk írás volt, akkor csak játékszám - 1 nagyságú lehet a maximális fejszéria). Arra, hogy a program három hibáig jelenítse meg ezeket a hisztogramokat, azért esett a választás, mert négy egymás mögött található hisztogram egy ábrán még átlátható. Vizsgáljuk meg hogyan alakulnak ezek a hisztogramok kísérletenkénti 100 játékot feltételezve, a kísérletet 10000-szer megismételve. Először tekintsük meg a fejszériák alakulását! És tekintsük meg ugyanennek az ábrának a hátulról tekintett változatát, ahol jobban lehet látni a hibásak eredményeit! Ezeken az eredményeken jól látható, hogy az egyre növekvő megengedett hibaszámmal együtt változnak az eredmények várható értékei, szórásai. Jól megfigyelhető, hogy a különböző eredmények relatív gyakoriságai közötti különbségek is folyamatosan csökkennek. Ezután vizsgáljuk meg ugyanúgy 100 játékra, 10000-szeres kísérletszám mellett a 34


3.5. ábra. Leghosszabb hibás fejszériák, n = 100, 10000-es kísérletszám

3.6. ábra. Leghosszabb hibás fejszériák, n = 100, 10000-es kísérletszám leghosszabb bármilyen szériák alakulását! Ezek az ábrák alapján itt is ugyanazt a következtetést vonhatjuk le, mint a fejszériák esetében, azaz a hisztogram egyre jobban szétterül, azaz egyre nagyobb tartományt fog le a lehetséges hosszakból, míg a hibátlan futások esetén tapasztalt görbe magassága is folyamatosan csökken.

35

3.3. Nem független kísérletsorozat

3.7. ábra. Leghosszabb hibás bármilyen szériák, n = 100, 10000-es kísérletszám

3.8. ábra. Leghosszabb hibás bármilyen szériák, n = 100, 10000-es kísérletszám

3.3. Nem független kísérletsorozat Gardner [13] könyvében szerepel az alábbi állítás: „Az 52 lapos összekevert kártyacsomagban majdnem mindig lesz 6 egyforma színű egymás után.” Ahogyan ez Bloom [3] művében is szerepel, elvégezve többször is ezt a kísérletet nem ezt az eredményt tapasztaljuk, hanem hatnál általában kevesebb elemű szériák adódnak. Felmerül a kérdés, hogy nem volt szerencsénk, vagy pedig Gardner tévedett? Ha egy halmaz kétféle tulajdonságú elemet tartalmaz, az egyikből m, a másikból k darabot, mi a valószínűsége, hogy m + k elemet sorban egymás után kihúzva visszatevés nélkül, lesz t hosszúságú széria, vagyis akármelyik tulajdonságú elemből legalább t következik egymás után? Az egyszerűség kedvéért a két tulajdonságú elem legyen piros (ebből m darab van) és fekete (ebből k darab), és jelölje a keresett valószínűséget Pt (m, k). Meghatározásához

36

3.3. Nem független kísérletsorozat vizsgáljuk az esemény komplementérének valószínűségét, vagyis annak az eseménynek, hogy nincs t hosszúságú széria az m + k elem sorozatában. Ez legyen P¯t (m, k), aminek a segítségével a Pt (m, k) = 1 − P¯t (m, k) képlet alapján adódik a válasz a kérdésünkre. P¯t (m, k)-nek klasszikus képlettel való kiszámításához vizsgáljuk először az összes elemi esemény számát: az m + k elemet kell sorbarendezni, melyek között m darab piros és k darab fekete található. Az ilyen sorozatok száma nem más mint: m+k . m Ezután a keresett hányados számlálójának meghatározásához össze kell számolnunk azon sorozatok számát, amelyben nincs t hosszúságú széria. Jelöljük ezt Ct (m, k)-val. 3.11. lemma. (Bloom [3], 369. o.) 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 X

Ct (m − 1, k − i) −

i=0

t−1 X

Ct (m − t, k − i) + et (m, k),

i=1

ahol Ct (m, k) jelenti az m darab piros és k darab fekete elem olyan sorbarendezéseinek 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. Az eredeti kérdésünkre a választ a Pt (m, k) = 1 −

Ct (m, k) képletbe való behelyetm+k k

tesítés szolgáltatja. A Ct (m, k) értékére Bloom [3] könyvének 371. oldalán egy olyan formulát is ad, amely az m, k és t értékétől függetlenül mindig hat tagból áll. 3.12. tétel. (Bloom [3] 371. o.) 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), ahol

  ha m = k = 0, vagy m = k = t, 1, ∗ et (m, k) = −1, ha m = 0 és k = t vagy m = t és k = 0,   0, különben.

A peremfeltételeink megegyeznek az előző állításéival, azaz ha m = k = 0, akkor definíció szerint Ct (0, 0) = 1, ha m vagy k negatív, akkor pedig definíció szerint Ct (m, k) = 0. Bizonyítás. (Fazekas-Karácsony-Liborné [8] 16. o.) Kezdődhet a sorozatunk 1 piros vagy 1 fekete elemmel: P

.|. . P .{z . . F . .}.

m − 1 piros és k fekete

ezek száma: Ct (m − 1, k); F

.|. . P .{z . . F . .}.

m piros és k − 1 fekete

37

3.4. Néhány matematikai alkalmazás ezek száma pedig: Ct (m, k − 1). Ezekből le kell vonni azokat, melyekben az első jel után is ugyanolyan következik összesen t hosszan, utána egy másmilyen, és utána nincsen t széria: P . . P} F | .{z t piros

.|. . P .{z . . F . .}.

m − t piros és k − 1 fekete

ezek száma: Ct (m − t, k − 1); F . . F} P | .{z t fekete

.|. . P .{z . . F . .}.

m − 1 piros és k − t fekete

ezek száma: Ct (m − 1, k − t). De ezekben benne szerepelnek a következő sorozatok is. A t piros, t fekete, utána pirossal kezdődően olyan m − t piros és k − t fekete elemű (p) sorozat, melyben nincs t széria. Ezek száma Ct (m − t, k − t). Illetve – fordítva – t fekete, t piros, utána feketével kezdődő olyan sorozat, melyben nincs t széria. Ezek (f ) száma Ct (m − t, k − t). Ezen két tag összege éppen Ct (m − t, k − t). Összegezve tehát megkapjuk az állítást. A szakasz elején említett kártyás példát megvizsgálva azt tapasztaljuk, hogy míg P6 (26, 26) = 0, 464, (annak a valószínűsége, hogy az 52 lapos kártyacsomag lapjait egymás után kirakva lesz benne egymás után 6 egyforma színű csak 0, 464), addig a P4 (26, 26) = 0, 974. Vagyis sokkal valószínűbb a négyes széria, így Gardner tévedett [13] könyvében, amikor azt állította, hogy majdnem mindig kapunk hatos szériát.

3.3.1. Szimuláció bemutatása A fent említett kísérletre diplomamunkám keretében készítettem egy programot, ami egy pakli kártyából (52 lap) szimulál adott számú kártya kihúzását, és ezt hajtja végre sokszor. Ahhoz, hogy Gardner fentebbi állításának hamis voltát belássuk, szimuláljuk 52 kártya húzását, és ezt a kísérletet ismételjük meg 20000-szer! Ezen az ábrán (3.9. ábra.) láthatóak mind a maximális piros szériák, mind a maximális bármelyik szériák eredményei. A független esethez hasonlóan itt is megfigyelhető, hogy a leghosszabb bármely szériák ábrája nagyon hasonílt a leghosszabb fejszériákéhoz, csak 1 értékkel nagyobb helyen vannak a megfelelő oszlopok. Az ábrából jól leolvasható, hogy 52 kártyát kihúzva a legnagyobb valószínűséggel 4 piros kártyát húzunk egymást után, és 5 hosszúságú lesz a leghosszabb bármelyik széria nagysága, ha a pakli kártya 26 fekete és 26 piros kártyát tartalmaz, azaz a szimuláció segítségével is belátható, hogy Gardner tévedett.

3.4. Néhány matematikai alkalmazás Az eredmények felhasználhatóak a különböző gazdasági, sorbanállási problémák, Markov-láncok (lásd Samarova [24], Schuster [26] vagy Schwager [27] cikkét), tőzsdei eseménysorok vizsgálatában (lásd Binswanger és Embrechts [2] cikkének 4.2. fejezetét). Az alkalmazásnak jelentős szerepe van a műszaki és a biológiai folyamatokban, kutatásokban. Sok egyéb területén, például a grafológiában is felhasználhatóak ezek az eredmények (lásd Arazi [1] cikkét). Révész [23] a számítástechnikában felmerülő, 38

3.4. Néhány matematikai alkalmazás

3.9. ábra. 52 kártya kihúzása, 20000-es kísérletszám véletlen számsorozat számítógép általi létrehozását említi hasznos alkalmazási területként. Már több módszert is kidolgoztak, melyek véletlen fej-írás sorozatokat generálnak valamilyen módon. Nehéz azonban eldönteni, hogy a kapott véletlen sorozat valóban olyan-e, mintha igazi dobássorozatot írtunk volna. A legtöbbször attól kell tartani, hogy valamilyen számunkra esetleg ismeretlen periódus van a felírt sorozatban. A legtöbb statisztikai módszer nem alkalmas ennek a hibának a kiszűrésére. Egy, a leghosszabb fejszéria hosszán alapuló próba alkalmas arra, hogy a sorozatnak a periodicitás okozta nem véletlen voltát kimutassa.

39

4. fejezet Szentpétervári paradoxon 4.1. A szentpétervári paradoxon Két játékos (nevezzük őket Péternek és Pálnak) a következő játékot játszák. Péter addig dobál egy szabályos pénzérmét, amíg az fej nem lesz, és 2k dukátot kap Páltól, ha az első fej a k-adik dobásra jelenik meg. A kérdés, hogy mennyit kell Péternek fizetnie, hogy a játék igazságos legyen, azaz egyik fél se gazdagodjon a másik kárára. A megoldás erre végtelen sok dukát lenne, de „még a féleszű ember is eladná a játékhoz való jogát negyven dukátért”, ahogy ezt Nicolaus Bernoulli írt 1728. augusztus 27-én az unoköccsének, Daniel Bernoullinak. (ld. Csörgő Sándor cikke [4]) Ezt a problémát nevezik szentpétervári paradoxonnak. Ha Péter nyereményét vizsgáljuk, ahol jelölje ξ a nyereményt, akkor ξ lehetséges értékei 2, 4, 8, 16, . . . , vagyis 21 , 22 , 23 , 24 , . . . számok. Bármely k ∈ N esetén a P (ξ = 2k ) a valószínűsége annak, hogy egymás után (k − 1)-szer írást dob Péter, és végül k-adikra fejet, azaz P {ξ = 2k } = 0.5k , feltételezve a dobások függetlenségét. Mivel ∞ X

k

P (ξ = 2 ) =

k=1

∞ X

2−k = 1

k=1

teljesül, így majdnem biztosan, azaz 1 valószínűséggel a játék véges számú lépésben véget ér, azaz Péter nyereménye majdnem biztosan véges. Pál ötlete, ami alapján Péternek végtelen számú dukátot kellene fizetnie a játékról onnan jön, hogy ξ várható értéke a következőképpen írható fel. E(ξ) =

∞ X k=1

k

k

2 P (ξ = 2 ) =

∞ X

1 = ∞.

k=1

Péter szempontjából figyelve ez túlzás lenne, mert tetszőleges x ≥ 2 esetén, [log x] [log x]−1 x X 1 X 1 X 1 1 1 = = = 1 − [log x] , P (ξ ≤ x) = k k j 2 2 2 j=0 2 2 k k=1 k:2

ahol [y] az y ∈ R szám egészrésze, és [log y] az y > 0 szám kettes alapú logaritmusa. Ezek alapján felírható a ξ nyeremény jobbról folytonos eloszlásfüggvénye: ( 0, ha x < 2, F (x) = P (ξ ≤ x) = −[log x] 1−2 , ha x ≥ 2. 40

4.2. A paradoxon előtörténete Azaz a nyeremény várhatóan végtelen nagy lesz, a nyeremény kis eséllyel halad meg egy x ≥ 2 összeget. Például, a Bernoulli családhoz visszatérve P (ξ > 40) = 1 = 0, 03125. Ha Péter nagyobb összegekre gondolna, akkor beláthatja, hogy P (ξ > 32 3000) = 2−11 = 0, 00048828125, azaz nemhogy végtelen sok dukátot nem adna egy ilyen nyereségért, amivel amúgysem rendelkezik, hanem egy elég nagy véges összeg is nagy kockázattal járna.

4.2. A paradoxon előtörténete A valószínűség-számítás kezdeteinek Blaise Pascal és Pierre de Fermat híres levelezését tekinthetjük. A leveleikben tárgyalt kérdések mind szerencsejátékokra vonatkoztak, és ezen témák ismeretében írt Christiaan Huygens egy tizenhat oldalas füzetet, amiben a saját maga, Pascaléval megegyező megoldásait jelentette meg holland nyelven. Huygens ismertette Pascal és Fermat levelezésében előforduló feladatokat, illetve kibővítette olyan feladatokkal, amikben a játékosok esélyei számának aránya a kérdése. A valószínűség-számítás ebben a kezdeti állapotában főleg a várható érték fogalma játszott fontos szerepet. A következő nagy lépés Jacob Bernoulli 1713-ban megjelent Ars conjectandi című könyve jelentette. Ennek a könyvnek az első része teljes egészében tartalmazta Huygens füzetét kommentárokkal és általánosításokkal. A második rész a permutációk és kombinációk elmélete volt, a harmadik része pedig ezek alkalmazása a legkülönbözőbb, főleg kockával és kártyával játszott szerencsejátékokra. Nagy jelentősége van ennek a műnek, mivel itt található meg az első kijelentése és bizonyítása a Bernoulli-féle törvénynek, azaz a nagy számok gyenge törvényének. Jacob Bernoulli unokaöccse, Nicolaus Bernoulli fogalmazta meg először a ma szentpétervári paradoxonnak nevezett problémát. A feladat első megfogalmazása Bernoulli egy Pierre Rémond de Montmort nevű matematikusnak írott levelében (1713. szeptember 9.) jelenik meg öt hasonló probléma mellett, az egyik probléma aleseteként. A probléma itt még az első hatosig történő kockadobásra vonatkozik, viszont az ebből fakadó feladat ugyanaz, mint amikor pénzt dobálunk. Ebben az esetben a nyeremény P 5k−1 5k−1 = ∞. bármely k ∈ N esetén k valószínűséggel veszi fel a 2k értéket, és ∞ k=1 6 3k (lásd Csörgő [4]) A kérdés tovább foglalkoztatta Bernoullit, aki megismertette a feladatot Gabriel Cramer tanítványával. Cramer 1728. május 21-én írt levelében egyszerűség kedvéért a kérdést kockadobásról érmedobásra fogalmazta át, tehát a paradoxon ismertetett alakja tőle ered. A levélben azt az ötletet veti fel, hogy nagy k ∈ N esetén bármilyen 2k -tól nagyobb nyereményről van szó, az már a 2k dukát által szolgáltatott örömtől nagyobb örömöt nem tud nyújtani, így a hétköznapi ember becslése a játék értékére ∞ X 1 1 2k j = k + 1 2 j + 2 2 j=1 j=k+1

k X

j

dukát. Cramer a k = 24 érték választást javasolta, mivel 224 = 16777216 dukátnál nagyobb nyeremény a hétköznapi embernek ugyanannyi hasznot hoz, mint 16777216 dukát. Vagyis az értéket 25-re becsülte. A felvetett ötlet nem nyerte el Nicolaus Bernoulli tetszését, aki az unokaöccsének, 41

4.2. A paradoxon előtörténete Daniel Bernoullinak Szentpétervárra írt levelében megfogalmazta, hogy Cramer már adott egy megoldást, viszont ő ezzel nem ért egyet. Levelezéseik után Daniel a szentpétervári akadémiára benyújtott dolgozatában (Commentarii 1730-31-es kötet, 1738-ban jelent meg) a Crameréhez hasonló megoldást ad, melyhez megjegyzésként hozzáteszi Nicolaus kritikáit. Daniel Bernoulli továbbfejlesztette Cramer gondoltait, bevezette a hasznosság fogalmát, mellyel a közgazdaságtan és a pszichológia is elkezdett foglalkozni. Véleménye b ∗ dx hasznosság növekedéssel szerint egy x összeg dx-szel való növekedése csak du = x jár, ahol b > 0 valamilyen kontans. Azaz minél több pénze van a játékosnak, annál kisebb egy kis növekedés feletti öröme, haszna. Így ha a játékosnak eredetileg α dukátja α+x van, egy x nyeremény morális haszna (hasznossága) u(x) = b ∗ ln . Így Péter moα α+x rális várható haszna nem E(x) = ∞, hanem M (X) = E(u(X)) = b ∗ E(ln ). Ez α az átlagos haszon a következőképpen számolható. Az x nyeremény 2k alakú összegeket jelent, melyekhez 2−kP valószínűségek tartoznak. Felhasználva a logaritmus azonossá−k gait, valamint, hogy ∞ = 1 azt kapjuk, hogy az átlagos haszon a következő k=1 2 alakban írható fel: M (X) = b

∞ X ln(α + 2k ) − ln α k=1

2k

= b ∗ ln(

∞ Y

−k

(α + 2k )2 ) − b ∗ ln α.

k=1

Ez viszont egyenlő a morális haszonnal, amiből rendezéssel azt kapjuk, hogy: x(α) =

∞ Y

−k

(α + 2k )2

−α

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őkére így például az alábbi értékek adódnak. Ha a kezdőtőke α = 0, akkor 4 dukát, míg például 1000 dukátból álló kezdőtőke esetén is csak 11 dukát a játék díja. Így Daniel Bernoulli a matematikai problémát pszichológiai és gazdasági síkra is átvitte, és felvetette, 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 (lásd Liborné [18] értekezése). Erre a problémára hasonló megoldást adott Euler is, de mivel nem akart a Bernoulli család ügyeibe beavatkozni (hiszen Daniel apja volt a tanára, és Daniel szerezte neki a szentpétervári munkahelyét), eredményeit nem hozta nyilvánosságra. Halála után 81 évvel jelent csak meg a témáról szóló dolgozata. Nicoulaus Bernoulli-nak Daniel megközelítése sem tetszett, mivel szerinte 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” (lásd Csörgő [4] cikke). Szerinte mindenki számára egyformán k dukátot 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 érték? Elfogadhatóbbnak tartja, ha azt mondjuk, hogy nagy k 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? Erre a kérdésre nem született több eredmény a Bernoulli család részéről. A kérdés csak 1754-ben került újra elő d’Alembert Fej vagy írás című, az Enciklopédiában megjelent cikkében. Mivel d’Alembert és Daniel Bernoulli között nem volt jó 42

4.2. A paradoxon előtörténete viszony, a paradoxonról írott munkáiban egyszer sem említi meg a Bernoulli nevet. A problémát először elég 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 ezt egyszerűsítve eljut a „probleme de Petersbourg” elnevezésig. A paradoxon elnevezése valószínűleg innen eredeztethető. A megoldással kapcsolatban Lagrange-nak írott levelében bevallja, hogy a „a pétervári probléma megoldása számomra a jelenleg ismert fogalomkörben lehetetlennek tűnik” (lásd [4]) Többek érdeklődését is felkeltik munkái, de érdemleges eredmény nem születik. Megemlíthető Whitworth érdekes elgondálása 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 fizetni. Erről a gondolatról saját maga is belátta, hogy nem tökéletes. 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özvetkeztetni, hogy mi fog történni legközelebb egy teljesen konkrét egyedi esetben. A nagy számok törvényének valódi jelentése nem volt jelen még a matematikusok gondolkodásában sem. Erre egyedül de Condorcet francia márki érez rá, szerinte Péternek végtelen sok játékot kellene játszani 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” [4]. Amikor n játékot játszunk, a válaszunk függni fog n értéké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, viszont a kortársai figyelmen kívül hagyták. A következő matematikus, aki érdemben foglalkozott a kérdéssel, Buffon volt. Ő az első, aki lejegyzetten a játékot ténylegesen lejátszatta egy gyerekkel 2048-szor. Ekkor 20104 = 9, 82, Péter összes nyereménye 20104 dukát volt, vagyis egy játékra átlagosan 2048 vagyis körülbelül 10 dukát jutott. Ez szerinte „érvényes és jó, mivel nagyszámú kísérletre alapul, továbbá megegyezik egy olyan gondolatmenet eredményével is, amely matematikai és kikezdhetetlen” [4]. 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

A táblázatban szereplő adatainkat szemléltetve látható, 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 dukát jár, vagyis ha n játékot játszunk, játékonként log2 n díjat kell fizetnünk. Gondolatmenete a következő volt. Ha n = 2k játékot játszunk, akkor az esetek felében (2k−1 ) lesz elsőre fej. A nyeremény minden esetben 2 dukát, így ez összesen 2k dukátot eredményez. 2k−1 esetben a második dobásra lesz az első fej, ez 4 dukát nyereményt jelent, így ez is 2k nyereményt hoz. Folytatva a gondolatmenetet, és felhasználva a 2k−1 + 2k−2 + · · · + 2 + 1 = 2k − 1 összefüggést, marad még egy játék, ami folytatódhat, de ennek már kicsi a valűszínűsége. Összesen tehát n játék lejátszása után kapunk k ∗2k dukátot, ami egyenlő n ∗ log2 n értékével, mivel n = 2k . Ez azt jelenti, hogy játékonként log2 n dukát lesz a nyeremény. 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. Buffon észrevette, hogy ha sok, például 1048575 játékot játszunk, akkor ez az összeg már 20 körülire adódik, de mivel ennyi játék lejátszása körülbelül 30 évig tartana, így szerinte ezzel a realitás szintjén nem kell foglalkozni. Szerinte tehát 10 dukát az az ár, amelyet játékonként fizetni kell, ha igazságosak aka43

4.2. A paradoxon előtörténete runk lenni. Laplace a paradoxon megoldásához nem jutott közelebb, de egyéb eredményei, melyeket A valószínűségek analítikus 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 az adott feltételek melletti valószínűségeket, várható értékeket és eloszlásokat hogyan lehet számolni, közelíteni. A paradoxon tekintetében számottevő, új eredmény sokáig nem született, a már meglévő eredményeket próbálták fejlesztgetni, bizonyítani. Többen is valamilyen ésszerű, emberi léptékű határok közé próbálták szorítani a megnyerhető összeget, például úgy, hogy feltételezték, hogy a banknak nincs végtelen sok pénze. Módosítsuk a játékszabályt úgy, hogy a megnyerhető összeg maximális 1 millió dukát. Mivel 220 már több, mint 1 millió, így a nyeremény várható értéke a következő alakban írható fel: 1 1 1 1 1 ∗ 2 + ∗ 4 + 19 ∗ 219 + ( 20 + 21 + . . . ) ∗ 106 ≈ 21, . . . 2 4 2 2 2 Vagyis 22 dukátos árral még jól jár a bank. 1872-ben A Budget of Paradoxes című könyvében de Morgan beszámol arról, hogy Buffonhoz hasonlóan ő is lejátszotta a játékot, és arra a megállapításra jutott, hogy „Ha Buffon ezerszer többször probálta volna, akkor az eredmény nemcsak 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 azt is várhatnánk, hogy néhány esetben a fej a huszadik dobásig sem mutatkozik” [4]. A Daniel Bernoulli-féle utilitási vonalat ebben a korban több kutató is felhasználta. Ilyen volt Fechner, a kísérleti pszichológia megalapítója, aki felállította a Weber-Fechner féle empirikus törvényt, mely szerint az S stimulus által kiválasztott R reakció nagysága R = C ln S, ahol C a vizsgált érzékeléstől függő pozitív konstans. Az utilitási vonal másik felhasználása az elméleti közgazdaságtan területén hozott új eredményeket. Menger vizsgálatai során az u(x) hasznosság-függvényre belátta, hogy az u(x) = C ln x megoldás nem helyes. Ezek a vizsgálatok alapozták meg Neumann János munkásságát a hasznosság axiomatizálásáig, mely a modern közgazdaságelmélet egyik megalapozása volt (ld. [18].) A szentpétervári paradoxon vizsgálatában a következő nagy áttörést Feller 1945-ös eredményei jelentetté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 már többek által megadott log2 n kapcsolat szerint. Feller szintén erre az összefüggésre jutott vizsgálatai során. Ha X1 , X2 , . . . Péter nyereményei az első, második, . . . szentpétervári játékban, és Sn = X1 +X2 +. . . Xn Péter össznyereménye 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ül lesz. Vagyis nE(X) ≈ Sn , amiből azt kapjuk, hogy a Sn ≈ E(X), illetjátékonkénti nyeremény a várható érték körüli lesz, vagyis nagy n-re n Sn ve → E(X) majdnem biztosan. Feller belátja cikkeiben ([10],[11]), hogy ha még X n szórása is véges, akkor a centrális határeloszlás tétel miatt: 1 P (Sn − nE(X) > 0) → ← P (Sn − nE(X) < 0), 2 vagyis nagy n esetén az esetek kb. felében az egyik játékos, míg az esetek másik felében a másik nyer, és a nyeremények is körülbelül szimmetrikusan oszlanának el. Feller beSn sztochasztikusan tart 1-hez, amiből következik, hogy n játékért látja, hogy n ∗ log2 n 44

4.2. A paradoxon előtörténete n ∗ log2 n összeg a méltányos. Sajnos azonban a problémában sem szórás, sem a várható érték nem véges, éppen ez volt a probléma eddig is. Az előző tétel és Feller dolgozata alapján Steinhaus teszi meg a következő nagy lépést. A [28] cikkében írja, hogy „a paradoxon feloldásához nem egy egyedik játékot, hanem játékok egy sorozatát kell nézni”. Egy determinisztikus sorozattal próbálja imitálni Péter véletlen nyereményeit. Ehhez vegyük 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_ . . . Ezután írjunk az első, majd minden második üres helyre 4-est: 242_242_242_242_242_242_242_24 . . . Ehhez hasonlóan írjunk 8-asokat, majd 16-osokat, és így tovább: 242824216242824232242824216242824 Ezt azért gondolhatjuk helyesnek, mert a játékban az esetek felében 2 dukát a nyeremény, a megmaradtak felében 4, az ezután megmaradtak felében 8, és így tovább. Felírva ezen sorozatok n-edik empirikus eloszlásfüggvényét, kiderül, hogy ez igen gyorsan (egyenletesen) tart a szenpétervári eloszlásfüggvényhez. Ha #A-val jelöljük az A halmaz elemeinek számát, akkor a Steinhaus sorozat n-edik eloszlásfüggvénye a következő: #{xj ≤ x|1 ≤ j ≤ n} . Fn (x) = 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 szenpétervári játékban szereplő nyeremények eloszlásfüggvénye, akkor Steinhaus törvénye a kövekező alakú lesz: 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ál legfeljebb x nagyságú összeget fizet ki. A további eredmények tekintetében ki kell emelnünk Csörgő Sándor, és csapata munkásságát, akik a problémán sikerrel dolgoztak tovább. Az alábbi tételeket sikerült bizonyítaniuk: Sn lim inf = 1, n→∞ n log2 n lim sup n→∞

Sn =∞ n log2 n

majdnem biztosan. 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 előforduló nagy nyeremény (lásd [5].) Tekintsük n játék esetén Péter nyereményeink

45

4.3. A paradoxon módosítási lehetőségei nagyság szerinti sorbarendezését Xn,1 ≤ · · · ≤ Xn,n . Rögzített m esetén n > m játékot játszva Péter nyereménye legyen: Sn (m) =

n−m X

Xn,j

j=1

vagyis Péter lemond az elvileg létező m legnagyobb nyereményeiről, és így az eddigi Sn dukát helyett Sn (m) dukátot kap n játékért. Azt gondolnánk, hogy minél nagyobb az m, annál kevesebbet kell fizetnie Sn (m)-ért, mint korábban Sn -élrt. Azonban Csörgő és Simons [6]-ben bebizonyítják, hogy Sn (m) →1 n log2 n majdnem biztosan minden rögzített m ∈ N eseté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 vihet közelebb. Csörgő Sándor belátta, hogy határeloszlás nincs ([4]). Sn − Cn Akárhogyan is választunk Cn , An > 0 konstansokat, a P ≤ x sorozat nem An konvergál egy olyan G(x) eloszlásfüggvényhez, amely nem egy konstans eloszlásfüggvénye, így a szentpétervári eloszlás nem tartozik bele semmilyen eloszlás vonzástartományába. Martin-Löf [19] cikkében {2k }∞ esetére megad egy határk=1 ⊂ N részsorozat S2k ≤ x + k valószínűségek eloszlástételt. Bebizonyítja, hogyha k → ∞, akkor a P 2k konvergálnak egy G1 (x) nemdegenerált eloszlásfüggvény értékeihez. Közelítőformulát 1, 8 is ad, miszerint nagy k és nagy m esetén P {S2k > 2k (2k + k)} ≈ 1 − G1 (2m ) ≈ m . 2 Tehát ha Péter 2k játékért 2k (2m +k) dukátot fizet, akkor Pál nagy valószínűséggel nem megy csődbe. Csörgő és Simons munkássága alapján ([6]) független, egyforma eloszlású véletlen változók részletösszegeinek létezhet határeloszlása a természetes számok végtelenbe tartó részsorozatai mentén úgy, hogy minden n ∈ N számot érintve ilyen nincs. Azt mondjuk, hogy az illető eloszlás benne van a részsorozat mentén nyert határeloszlás parciális vonzástartományában. Vagyis Martin-Löf tétele szerint a szentpétervári eloszlásfüggvény benne van a G1 eloszlásfüggvény paricális vonzástartományában. Egy eloszlásfüggvényre három állítás valamelyike teljesülhet: • semmilyen eloszlás parciális vonzástartományában nincs benne, azaz még részsorozatok mentén sincs határeloszlás, • pontosan egy típus parciális vonzástartományában van benne, ez a típus szükségképpen stabilis, • benne van egy nem stabilis eloszlás parciális vonzástartományában, mely esetben szükségképpen benne kell legyen eloszlások kontinuum számosságú különböző típusának parciális vonzástartományában. Mivel a G1 függvény nem stabilis, így a szentpétervári eloszlásfüggvény a harmadik kategóriába esik. Ebből viszont az következik, hogy kontinuum számosságú határeloszlás létezik, vagyis azért nincs határeloszlás, mert végtelenül sok van. 46

4.3. A paradoxon módosítási lehetőségei

4.3. A paradoxon módosítási lehetőségei Liborné [18] cikkében a szenpétervári paradoxonnak több módosított változata is ismertetésre kerül. Ezek közül az egyik eset az, amikor több játékos játszik a bankkal szemben. Kezdetben legyen két játékos, akik megegyeznek abban, hogy a megnyert összeget fele-fele arányban osztják el a játék végén. Vagyis, ha az egyik játékos nyer X1 dukátot, a másik pedig X2 dukátot, akkor a játék végén mindkettőjük nyereménye X1 + X 2 dukát lesz. Belátható erről, hogy az együttes stratégia mindkettőjük szá2 mára nagyobb nyereményt eredményez, mintha X1 és X2 összeget kapnának a játék végén. Ezt az esetet nevezik a szakirodalomban „két-Péteres paradoxonnak”. Célszerű megvizsgálni, hogy mennyivel jobb ez az átlagoló stratégia. k−1 X 1 2 1 P {X1 ≥ 2 |X2 = 2 } = P {X1 ≥ 2 } = 1 − = 1 − 1 − k−1 = k j 2 2 2 j=1 k

k

k

minden természetes k esetén, ezért viszont P {X1 ≥ X2 |X2 } =

2 X2

amivel pedig a várható érték a következő lesz: 2 E(X2 I{X2 ≤ X1 }) = E(X2 P {X1 ≥ X2 |X2 }) = E X2 = 2. X2 Vagyis ha ezt megfelezzük, akkor 1-1 dukáttal lesz jobb ez az átlagoló stratégia a külön-külön elért eredményekhez képest. A következő vizsgálandó eset legyen az, hogy hárman játszanak a bank ellen, és vizsgáljuk azt, hogy így is jó ez az átlagoló stratégia. Csörgő és Simons munkásságából kiderül, hogy az előző átlagoló stratégiát kiszámítva nem lesznek összehasonlíthatóak a várható értékek, viszont ha mindegyik játékos átadja a nyereményét a másik két játékosnak fele-fele arányban, akkor szintén 1-1 dukáttal jobb lesz a nyereményük. Ha ezt a stratégiát követjük, akkor megállapítható, hogyha mindegyik játékos a nyereményének a felét osztja csak szét a másik két játékos között fele-fele arányban, akkor már 1.5 dukáttal lesz több minden játékos nyereménye. Általános felírva, ha P = (p1 , p2 , p3 ) úgy, hogy p1 + p2 + p3 = 1, akkor az osztozkodó stratégiával a három játékos nyereménye a következő módon alakul: (lásd [18]) p1 X1 + p2 X 2 + p3 X 3 , p3 X1 + p1 X 2 + p2 X 3 , p2 X1 + p3 X 2 + p1 X 3 . Ez a játék természetesen kiterjeszthető több játékosra is, mint három. Ha speciálisan n = 2k játékos játszik, a nyereményük X1 , X2 , . . . Xn dukát, vagyis az átlag, X1 + X2 + · · · + Xn dukátot. Az átlagoamit a végén külön-külön mindegyikük nyer n Sk ló stratégiával minden k ∈ N esetén E 2 , X1 = k adódik. Ha a játékosok száma 2k bármilyen pozitív egész n szám, akkor a következőket lehet állítani. A háromjátékos 47

4.4. Alkalmazás bemutatása esethez hasonlóan legyen Pn = (p1 , p2 , . . . , pn ), ami a játékosok közötti osztozkodási arányokat jelenti, azaz mindegyik játékos külön-külön a nyereményének hányad részét adja a többi játékosnak. Ezt akkor tekintjük elfogadhatónak, ha minden komponense vagy 0 vagy 2 negatív egész hatványa. Ilyen Pn esetén kimondható, hogy a hozzáadott érték egyenlő lesz Pn entrópiájával, vagyis H(Pn ) = −{p1 l log2 p1 + · · · + pn log2 pn } Továbbá belátható, hogy ezen entrópia felső határát a következő kifejezés adja. Hn = [log2 n] + 2{log2 n} − 1.

4.4. Alkalmazás bemutatása A szentpétervári paradoxonból ismertetett kétszemélyes játék elkészült szimulációját szeretném ismertetni ebben az alfejezetben. Az alkalmazás során kezdetben megadjuk azt, hogy hány játékot szeretnénk lejátszani egy kísérlet során, majd megadjuk, hányszor kívánjuk megismételteni a játéksorozatot. Mivel a játékok esetén nem egyértelmű, mennyi egy játék pontos hossza, így a program véletlenszámgenerátora minden játéksorozatra több véletlenszámot generál, hogy nagyon magas valószínűséggel befejeződjön mindegyik játék. A program futása elején megadunk egy dukát értéket, ami azt jelenti, hogy mennyi dukáttal óhajtunk játszani, azaz mennyi dukát értéket fizetünk be mindegyik játékért. Ezek után megadunk egy elérendő célösszeget. A program megállapítja, hogy pontosan hány dukátnál lesz igazságos a játék. Ezt úgy számítjuk ki, hogy minden egyes sorozat lefuttatásakor a végösszeget leosztjuk a játékszámmal, és a végén ezeket az értékeket átlagoljuk. Ezeknek az értékeknek az ábrázolása megtörténik hisztogramon is. Ezen ábrához meg kell jegyezni, hogy előfordulnak értékek 2 magasabb hatványai körül is, viszont ezek relatív gyakoriságai egyre alacsonyabbak, ezért került az egytől százig tartó tartomány ábrázolása. A program ezen kívül két relatív gyakorisági értéket is megjelenít, az egyik az, hogy az előre megadott dukát alapján mennyi a nyereséges játékok relatív gyakorisága (nyereséges játék az, ahol a végösszeg nulla vagy pozitív). A második érték az adott dukát mellett a célnyeremény elérésének relatív gyakoriságát vizsgálja. A megjelenített grafikus felületen található még egy ábra, ami az adott dukát melletti kifizetődés (payout) mértékét óhajtott szimulálni. Ennek a szimulációjához minden egyes kísérletnél a végösszegeket összeadjuk, és szakaszosan ábrázoljuk az összes kísérletre. Az ábrán piros vonallal van jelölve az x tengely, azaz hogy a kísérletsorozat kifizetődő-e (nyereséges), vagy nem kifizetődő. Vizsgáljuk meg először 100 játék esetére, tízezres kísérletszámra 40 dukátos értékkel. A célnyeremény legyen 1000. Ekkor a következő eredmények tapasztalhatóak:

48

4.4. Alkalmazás bemutatása

4.1. ábra. Szentpétervári kísérlet, 100 játék, 10000 kísérlet, 40 dukát Ezen az ábrán jól látható, hogy az igazságos dukát értéke 23.9157-re adódik, azaz tekintsük meg ugyanígy száz játékra, 10000 kísérlet esetére, 24-es dukát értékkel. Többször lefuttatva a programot lehet látni, hogy az a dukát, amely mellett a játék

4.2. ábra. Szentpétervári kísérlet, 100 játék, 10000 kísérlet, 24 dukát

49

4.5. További alkalmazások igazságos, nem választható ki egyértelműen, mivel ez nem egy egzakt érték, amihez tart a szimulált érték.

4.5. További alkalmazások 4.5.1. Martingál szerencsejáték stratégia A szentpétervári paradoxonnal áll szoros kapcsolatban a martingál (halmozási) stratégia. Ebben a stratégiában a mai napig rengeteg szerencsejátékos hisz, és ennek hatására mennek tönkre. A probléma alapját egy olyan játék szolgálja, hogy a játékos a bank elleni játszik, és a játékban ötven-ötven százalék esélye van a nyerésnek és a vesztésnek is. Ha az első játékban veszít a játékos, akkor megduplázza a tétet. Ha a másodikban is veszít, akkor ugyanígy megduplázza az előző tétet, és így tovább, amíg nem nyer a játékos. Ha a legelső tét A forint, és az első n − 1 játszmában nem nyert a játékos, de az n.-ben már igen, akkor összesen kifizetett A(1 + 2 + 4 + · · · + 2n−1 ) = A(2n − 1) forintot, míg a nyeremény összege A2n forint lesz. Így tehát összesen A nyereségre tett szert a játékos. Mivel 1 valószínűséggel valamikor nyert a játékos, ez a stratégia biztosnak látszik. Viszont fontos megemlíteni, hogy ez csak látszat. Mivel lehet, hogy csak a sokadik játékban nyer a játékos, így lehet még azelőtt elveszíti az összes pénzét, mielőtt lett volna lehetősége nyerni. Másik irányból nézve, ha korlátlan sok pénze van a játékosnak, akkor ahhoz képest elenyésző az A forintnyi nyereség. Ezenkívül fontos megemlíteni, hogy a kaszinók már ismerik ezt a stratégiát, és a használatát úgy korlátozzák, hogy maximalizálják a tétek nagyságát, tehát akármeddig nem folytatható ez a stratégia, és igaz, hogy ez a maximumösszeg nagyon nagy, mégis teljesen használhatatlanná teszi ezt a stratégiát. Ezen korlátozó tényezőket szeretném bemutatni az általam készített szimulációban, ami egy olyan helyzetet mutat be, hogy a játékos a martingál stratégiát követve adott kezdőösszegről adott számú játékot játszik, és korlátozva van a maximális tét, amit a játékos egy játék során feltehet. Tekintsük meg a szimulációt! Induljunk ki 1000 forint kezdőösszegről, és játszunk 100 játékot! Ismételjük meg ezt a kísérletsorozatot 10000-szer úgy, hogy a kaszinó által meghatározott maximális tét legyen 250 forint. Jól látható az ábrán, hogy 0.903 lesz a relatív gyakorisága a nyertes kimeneteleknek, azaz az esetek körülbelül 10%-ában ez a módszer ilyen paraméterek mellett veszteséges. A maximális nyeremény értéke pedig 67 forintra adódik, ami az 1000 forintos kezdőösszeg mellett nagyon kicsi növekedés, azaz belátható, hogy egyrészt nem biztos módszer a martingál stratégia, másrészt az elért nyeremény csekély a kezdőösszeghez képest. A program futása során ábrázolja a kísérletek végén elért nyeremények hisztogramját, amin ebben az esetben jól látható, hogy az értékek, amelyek nem 1000 körül találhatóak, azok rendszerint 0, 250, 500, és 750 környékén találhatóak, azaz nagy valószínűség szerint már elvesztettek egy vagy több maximális tét értékű játékot. Az ábráról ezen kívül leolvasható, hogy mennyi a kísérletenkénti átlagnyeremény értéke, ami 0.35-re adódik, azaz nagyon csekély a várható nyeremény játékonként.

4.5.2. Egyék alkalmazások Ha a játékok körében vizsgálódunk, akkor kiderül, hogy a „Legyen Ön is milliomos!” televíziós vetélkedő is egy módosított szentpétervári paradoxon alkalmazásának 50

4.5. További alkalmazások

4.3. ábra. Martingál stratégia, 100 játék, 10000 kísérlet, 1000 forint kezdőöösszeg, 250 maximális tét tekinthető. Itt minden kérdésnél négy válaszlehetőség közül kell az egyetlen helyeset kiválasztani, és a játékos dönthet, hogy helyes válasz esetén tovább játszik, vagy eltávozik az addig megnyert összeggel. Ha tovább játszik, és veszít, akkor az összes addigi nyereményét elveszítheti, viszont ha nyer, akkor a pénze megduplázódik. A paradoxon gazdasági alkalmazásai közül több említésre kerül Libor Józsefné doktori disszertációjában ([18]). Ilyen alkalmazások között meg kell említeni, hogy Daniel Bernoulli a szentpétervári paradoxonból kiindulva jutott el a hasznosság formulájá x , ahol k egy pozitív konstans, c pedig a létezéshez minimálisan hoz (U = k ∗ ln c szükséges vagyon nagysága). Bernoulli munkássága a paradoxonnal kapcsolatban két alapgondolatot tartalmazott, amiből az egyik a csökkenő határhaszon törvényéhez vezetett, a másik pedig arra vonatkozott, hogy bizonytalan vagyoni körülmények között az egyén várható helyzetét nem a várható vagyonhoz tartozó egyéni értékelés, hanem az egyes vagyoni helyzetekhez tartozó egyéni értékelések várható nagysága határozza meg. Szintén a szentpétervári paradoxon volt az alapja több olyan pénzügyi ötletnek is, amelyek szinte minden esetben csődbe juttatták az adott vállalatot, céget. Ilyen például egy gazdasági társaság nagy arányú növekedése, amelynek olyan kilátásai vannak, hogy szinte végtelennek tűnnek az elérhető nyereségek. Felmerül a kérdés, hogy ha képesek vagyunk korlátlanul előre jelezni a vállalat bevételeit, akkor mennyit érhet a vállalat részvénye. Végtelen összeget? Ezeket az álmokat sok befektető követte a 60-as, 70-es években. Úgy gondolták, hogy a jövendő nyereség és osztalék igazolni fogja a befektetést, bármekkora is a vételár. A valóságban azonban a nyereség jóval kisebbnek bizonyult, mint a várt végtelenül nagy összeg. Ennek a problémának részletes leírását, példákkal és matematikai levezetéssel együtt megtalálhatjuk [18] értekezésében.

51

5. fejezet GUI tervezés MATLAB programcsomagban A MATLAB programcsomag segítségével lehetőségünk van GUI (Graphical User Interface) készítésére. Egy GUI egy grafikus ablak vagy ablakok, amelyeken vezérlő elemek vannak, amik segítségével a felhasználónak lehetősége van interaktív feladatok végrehajtására, és ehhez nincs szüksége szkriptek készítésére, vagy parancsok beírására a parancssorba. Ehhez a GUIDE-t (Graphical User Interface Design Environment) használjuk. Ennek segítségével lehetőségünk van GUI létrehozására, illetve szerkesztésére .fig típusú fájlokból, és ezen felületek kezelésére. A funkció eléréséhez egyszerűen gépeljük be a parancssorba a guide parancsot. Ezzel meghívódik a guide függvény, és a MATLAB feldob egy ablakot (Quick Start Dialog), ahol lehetőségünk van kiválasztani, hogy milyen új GUI-t készítsünk, illetve mely már korábban elkészítettet nyissuk meg. A MATLAB több mintát biztosít GUI létrehozására, illetve létrehozhatunk egy GUI-t teljesen önállóan is. Ha a guide parancs paraméterébe megadjuk a már korábban elkészített interfészünk nevét, akkor megnyitja a MATLAB, ha a megfelelő munkakönyvtárban van. Ha nincs ott, akkor lehetőségünk van a guide parancs paraméterének teljes elérési útvonalat megadni. Például a guide(proba) parancs megnyitja a proba.fig interfészünket. Ismerkedjünk meg a GUI-k működésével! A legtöbb GUI a felhasználótól függ, a felhasználótól várja a vezérlők kezelését, és erre ad válaszokat. Minden egyes vezérlőnek, és magának a GUI-nak is van legalább egy rutinja, ami gyakorlatilag egy végrehajtható MATLAB kód. Ezek a rutinok callback néven ismertek, mivel gyakorlatilag egy hívást intéznek a MATLAB felé, hogy az végrehajtsa a megfelelő feladatot. Ezen callback rutinok mind a felhasználó tevékenységétől függően aktiválódnak, például a felhasználó megnyom egy gombot, kattint az egérrel, kiválaszt egy elemet egy legördülő menüből, begépel egy értéket, vagy csak egyszerűen egy vezérlő felett elhúzza az egeret. Ezeket eseményeknek nevezzük, és ezek bekövetkezésekor a GUI válaszeseményt generál. Ezt a típusú programozást eseményvezérelt programozásnak nevezzük. A callback rutinok aszinkron működésűek, a szoftvertől független események váltják ki őket. MATLAB esetében a legtöbb esemény a felhasználó GUI-val való interakciójának eredménye, de van lehetőségünk úgy megírni az interfészünket, hogy az más események hatására váltódjon ki, például egy fájl létrehozására, megnyitására. MATLAB-ban kétféle módon írhatjuk meg ezeket a rutinokat. Az egyik lehetőség MATLAB függvényekként, amik a MATLAB nyelvén íródtak, és .m kiterjesztésű fájlokban tárolódnak le. A másik lehetőség sztringekben tárolt MATLAB kifejezések,

52

parancsok formájában történhet. Például: ’c=sqrt(a*a+b*b);’. A két módszer közül a függvények használása az ajánlottabb, mivel függvények használatával több paramétert tudunk kezelni, több lehetőségünk van, és sokkal rugalmasabb. Mielőtt elkezdenénk elkészíteni az interfészünket, meg kell terveznünk azt. El kell döntenünk, hogy milyen felhasználók fogják használni a GUI-t, pontosan milyen feladatok ellátására akarjuk használni, hogyan használják a felhasználók a GUI-t, és milyen vezérlőkre van szükségünk a használatához. Pontosan meg kell tervezni, hogy milyen bemeneti adatokra van szükségünk, illetve milyen kimenetet akarunk belőle készíteni, hogyan kérjük be az adatokat, illetve milyen formában jelenítsük meg a kimenetet, hogyan viselkedjen a GUI a különböző vezérlőkön kiváltott eseményekre. Miután a tervezéssel készen vagyunk, kezdhetjük meg ténylegesen az interfészünk elkészítését, leprogramozását. Kétféleképpen lehet felépíteni a MATLAB grafikus interfészünket, ennek egyik módja a GUIDE használata, a másik pedig a GUI programozása. Mindkét módszernek vannak előnyei, illetve hátrányai, így a legcélszerűbb a kettőt együtt, egymás mellett használni. Első megközelítésként használjuk a GUIDE-t. A GUIDE létrehoz nekünk egy alap interfészt, ha a blank GUI lehetőséget választottuk. A felugró ablak jobb oldalán található egy eszköztár, ahonnan lehetőségünk van vezérlők létrehozására. Tekintsük meg ezeket! • Push button: egy nyomógombot hoz létre. • Slider: az interfészen való navigálásra „csúszkát” hozhatunk létre. • Radio button: több választási lehetőség esetén ezzel tudunk egyet kiválasztani. • Check box: több választási lehetőség esetén ezzel többet is kiválaszthatunk. • Edit text: szöveges beviteli mezőt hozunk létre. • Static text: felhasználó által nem változtatható szöveges mezőt hozunk létre. • Pop-up menu: felnyit egy választási listát, ahonnan a felhasználó az egérrel választhat egyet. • Listbox: egy elemlistát hozunk vele létre, ahonnan a felhasználónak lehetősége van több elem kiválasztására is. • Toggle button: létrehoz egy nyomógombot, aminek két állapota van. Ha a felhasználó rákattint, benyomódik, és így is marad, míg a felhasználó nem kattint rá megint. • Table: egy táblázatot tudunk ezzel a paranccsal létrehozni. • Axes: képek és MATLAB által készített függvények megjelenítésére szolgáló vezérlő. • Panel: ezen vezérlő segítségével tudunk más vezérlőket egy csoportba rendezni. Ha a vezérlő elemeket panelekbe rendezzük, akkor egyszerűbben értelmezhető, és átláthatóbb GUI-t készíthetünk. • Button group: ezen vezérlő hasonlít a Panel vezérlőhöz, viszont az külön Radio button és Toggle button vezérlők összefoglalására használható. 53

• ActiveX control: ActiveX vezérlőket hozhatunk vele létre. Nézzük meg pár általános használható tulajdonságát ezeknek a vezérlőknek! Ha létrehoztunk egy vezérlőt, és kétszer kattintunk rajta, felnyílik a property inspector nevű menü, ahol lehetőségünk van a vezérlő tulajdonságait módosítani. Lehetőségünk van a vezérlők háttérszínének megváltoztatására, ahol választhatunk a MATLAB által előredefiniált színek közül, vagy RGB komponenseit megadva a színnek létrehozhatjuk saját színünket. Lehetőségünk van itt megírni a függvényeket, amik az adott vezérlő eseményeit kezelik, vagy ha alapértelmezetten hagyjuk, akkor a GUIDE létrehoz egy függvénykeretet, amit később szerkeszthetünk. Beállíthatjuk, hogy az adott vezérlő elérhető legyen a felhasználó számára, vagy sem, továbbá a gombokon megjelenő feliratok esetében a betűtípust, betűméretet, betűk színét, a szöveg dőltségét, félkövérségét, illetve beállíthatjuk, hogyan helyezkedjen el a szöveg horizontálisan, illetve vertikálisan. Lehetőségünk van beállítani, hogy az adott vezérlő mikor legyen látható, például egy feladat leírása csak akkor legyen látható, ha a felhasználó azt a feladatot választotta ki. Lehetőségünk van a vezérlők elhelyezkedését is beállítani, illetve a méretüket. A vezérlőknek adhatunk saját nevet, amivel könnyebben tudjuk megkeresni programozás során, illetve a feliratot is be lehet állítani, ami egy vezérlőn megjelenik, pl. egy gombon, vagy egy szöveges mezőn. Ha mindent beállítottunk itt, akkor tekintsük meg a programozás részét! Ehhez annyit kell tenni, hogy rákattintunk az M-file Editor gombra. Ha még nem mentettük el az interfészünket, a MATLAB most felajánlja a mentést. Ha elmentettük, akkor megjelenik az eddig elkészített GUI kódja. Használjuk a függvény ikont, és tekintsük meg a MATLAB által létrehozott függvényeket! A MATLAB minden vezérlőhöz, és magához a GUI-hoz is létrehoz egy OpeningFcn nevezetű függvényt, ami még azelőtt fut le, hogy az adott vezérlőnk láthatóvá válik. Itt tudjuk megadni legegyszerűbben, hogy mi legyen látható, amikor az adott vezérlő megjelenik, például ha rákattintunk egy gombra, akkor ennek hatására jelenjenek meg más vezérlők, vagy váljanak nem láthatóvá a felhasználó számára. A MATLAB ezenkívül minden vezérlőhöz létrehozza a callback rutint. Ideírva a megfelelő kódrészleteket, tudjuk vezérelni az eseményeket, hogy mi történjen, ha az bekövetkezik. Például ha egy gombot lenyomunk, akkor olvassa be a megfelelő értékeket, ellenőrizze őket, és az ellenőrzés eredménye alapján váltson ki új eseményeket. A MATLAB nyelvben a vezérlők értékek bekérésére, illetve beállítására a get és set parancspáros szolgál. A get parancs lekéri az adott objektum paramétereit. Ezt értékek beolvasására szokás felhasználni. Ezt egy kis példával illusztrálom. Tegyük fel, hogy van egy szövegbeviteli mező, amibe a felhasználó különböző értékeket írhat be. Legyen ez a mező mellett egy gomb, aminek lenyomására a program beolvassa az adott beviteli mező értékét. Ezt úgy valósítjuk meg, hogy a gomb callback függvényében végrehajtjuk a beviteli mező lekérését a következőképpen: a=get(handles.bevitelimezo,’String’); Ekkor az a változó értékébe letároltuk a beviteli mező aktuális értékét, szövegként. Ha ezt nem szöveg formában akarjuk letárolni, akkor típuskonverziós függvényeket kell használnunk. Például, ha ez az érték, amit beolvasunk valós szám, akkor a beolvasást a következő módon kell végrehajtanunk: a=str2double(get(handles.bevitelimezo,’String’)); Ezzel az a változóba letároltuk a beviteli mező értékét, ami valós szám volt. Viszont, a programot fel kell készíteni arra az esetre is, hogy a felhasználó hibás értéket ad meg, például egy szöveget ír oda, ahol valós számot várunk, vagy valós számot oda, ahol 54

csak egészeket fogadunk el. Ezeket az ellenőrzéseket a bekérés után tudjuk végrehajtani, azaz jelen példánkban a gomb lenyomása után, így a gomb callback függvényének meghívásakor. Minden beviteli mező esetén, ahol vannak értékmegkötéseink, írnunk kell egy hibaellenőrzést. Például, ha egy pozitív egész számot akarunk bekérni, akkor ellenőriznünk kell, hogy az adott szám pozitív-e, és azt, hogy egész szám-e. Egy egyszerű ellenőrzés kinézhet a következőképpen is: if(a<10) msgbox({’Az a változó értéke nem lehet tíznél kisebb’},’Hiba1’); end Ebben az esetben a MATLAB egy felugró ablakot fog létrehozni, ha a változó értékét rosszul állítottuk be. Fontos, hogy a programunkat ne engedjük hibás paraméterekkel futtatni, azaz a hibaellenőrzésnek hamarabb kell megtörténnie, mint a program lefuttatásának. Erre egy egyszerű megoldás az, hogy a gomb lenyomásakor végrehajtódnak az ellenőrzések, ha hibát kapunk, felugró ablakban közöljük a felhasználóval, és egy változóban eltároljuk, hogy hibát kaptunk. Ezek után, miután minden ellenőrzés lezajlott, megvizsgáljuk a hibát jelző változók értékeit, és ha nem kaptunk hibát, meghívjuk a feladatot megoldó függvényt. Vezérlők értékének beállítására a set parancs szolgál. Ennek segítségével beállíthatjuk a programunkból egy szöveges beviteli mező értékét, vagy egy statikus szöveg értékét átírhatjuk (a programunk változtathatja a Static text értékét, csak a felhasználó nem), elrejthetünk vezérlőket, vagy megjeleníthetjük őket, megváltoztathatjuk tulajdonságaikat. Tekintsünk meg ezek közül néhányat! Ahhoz, hogy a GUI átlátható legyen, célszerű, hogy a felhasználó ne lássa egyszerre az összes vezérlőt, ha azok nem egy témához tartoznak, a feleslegeseket rejtsük el, mert zavaró lehet. Ezért célszerű a GUI készítésekor létrehozni Panel elemeket, mert ebben az esetben nem kell minden egyes vezérlőt egyesével elrejteni, hanem elég a panelt elrejteni. Ahhoz, hogy felhasználó általa nem láthatóva tegyünk egy panelt, a következő parancsot kell megadnunk: set(handles.panel1,’Visible’,’off’); Ezzel a paranccsal a panel1 nevű panelt, rajta az összes vezérlővel, nem láthatóvá tettük. Ha ugyanezt on értékkel adjuk meg, akkor az adott panel látható lesz. Így ha a panelek megjelenését gombokkal szabályozzuk, akkor minden egyes gomb lenyomására elrejti az összes panelt, ami nem kell, és láthatóvá teszi azokat, amik kellenek. Set parancs használatával tudunk értéket adni egy beviteli mezőnek. Például tudunk adni egy lehetséges kezdőértéket, amit a programból állítunk be, ha a felhasználó csak először használja a programot, akkor legyen lehetősége megfelelő paraméterek mellett megtekinteni a program futását. Hibaellenőrzésnél is hasznos tud ez lenni, ha az egyik beviteli mező értéke nem volt helyes, akkor egyszerűen beállítjuk üresre az adott beviteli mező értékét, így a felhasználó rögtön látja, hol vétett hibát, és a hibaüzenet segítségével tudja javítani. Az értékadásnak a kódja a következőképpen néz ki: set(handles.text1,’String’,’15’); Ezzel a MATLAB beállítja a text1 szöveges mezőnk értékét tizenötre. Ha üresre szeretnénk állítani a mezőt, akkor ’’ legyen az utolsó paraméterünk. A MATLAB programcsomag lehetőséget biztosít többsoros beviteli mező készítésére, aminek segítségével lehetőségünk van többsoros szövegeket létrehozni, például egy leírást. Ez a következőképpen programozható: set(handles.text1,’String’,{’Többsoros bevitel, első sora’;’’; 55

’Kihagytunk egy üres sort, ez már a harmadik sor;}); Ekkor a text1 értéke három sorból fog állni, amiből a második sor egy üres sor. Ezenkívül érdemes megemlíteni, hogy van lehetőség menük létrehozására is. Ehhez a Menu Editor funkciót kell használni, ahol megadhatóak a menük nevei, és a hozzá tartozó azonosító értékek, amik segítségével már lehetőség van programozni. Ennek a fejezetnek a zárásaként szeretnék bemutatni egy egyszerűbb grafikus interfészt, és a rajta szereplő elemeket megnevezni. Ez a minta a Szentpétervári program-

5.1. ábra. Minta GUI részhez elkészült GUI-t mutatja kitöltés nélkül. Az ábra bal oldalán lehet látni három Static Text mezőt és alattuk három Edit Text elemet. Az ábra jobb oldalán látható két Axes objektum, amire a grafikus eredményeket tudjuk megrajzolni. Az ábrán található Kilépés gomb a Menu Editor segítségével létrehozott menüpont, és rákattintva bezárhatjuk a GUI ablakot.

56

6. fejezet Összefoglalás Diplomamunkám témájául leghosszabb szériák vizsgálatát és ehhez a témakörhöz tartozó szentpétervári paradoxonnal kapcsolatos feladatot választottam. Diplomamunkám legelején egy rövid áttekintésben ismertetem a valószínűség-számítás, és a MATLAB történeti hátterét, és definiálok pár alapfogalmat, amiket a diplomamunkám többi fejezetében használok. Emellett bemutatok pár eloszlást, amit szintén felhasználok a szimulációk során. Ezek után bemutatom a fogadásos feladatot, ami egy ismert valószínűségi érték alapján történő játéksorozatra történő fogadás eredményeit mutatja be. Ez a program egyszerűsége és érthetősége miatt jó bevezetést nyújt a diplomamunka többi részéhez. A harmadik fejezetben a címben is szereplő leghosszabb szériákkal foglalkoztam. Ebben a fejezetben ismertetem a független, és függő mintavételezés esetén a leghosszabb fej/piros és a leghosszabb bármely szériák alakulását. A független mintavételezés esetén kitérek mind a szabályos, mind a szabálytalan pénzérme esetére, és ezen esetekre vonatkozó rekurzív és aszimptotikus tételeket ismertetek, amelyek közül néhánynak a bizonyítását is közlöm. Ebben a fejezetben a MATLAB gyorsítási lehetőségeire tértem ki, ezek közül is a kézenfekvőbb, de több számítást igénylő iteratív átírásra, és az egyszerűbb, de önmagában még nem biztos, hogy megfelelő C nyelvű átírásra. A C nyelvű átírás esetén ismertettem a MEX programozás alapjait, aminek segítségével C, C++ és Fortran nyelvű programokat lehet MATLAB függvényekké alakítani. Az iteratív átírás során az átírás menetét is ismertettem, és kitértem az elért sebességjavulásokra. A sebességek alapján jól látható, hogy a szabálytalan pénzérme esetén, ahol megtörtént az iteratív és a MEX átírás is, a legcélszerűbb az iteratív algoritmus C nyelvű megvalósítását választani, mivel azzal érhetőek el a legjobb eredmények. Ebben a fejezetben mind a független, mind a függő mintavételezésre ismertettem programot, és bemutattam azt, hogyan változnak a független mintavételezés értékei akkor, ha engedélyezünk hibákat a jelek között. A negyedik fejezetben ismertettem a szentpétervári paradoxon alapjául szolgáló játékot. Ezután áttekintettem a paradoxon történetét a kialakulásától a jelenig. Ismertettem a paradoxon néhány módosítási lehetőségeit, és kitértem a paradoxon alkalmazásaira is. Itt bemutattam egy szimulációt, ami Bernoulli híres állítását („még a féleszű ember is eladná a játékhoz való jogát negyven dukátért”) hívatott bemutatni. Ezután ismertettem a martingál szerencsejáték stratégia hibáit bemutató programrészt, ami szimulálja, hogy miért nem biztos ez a stratégia. Diplomamunkám utolsó fejezetében kitértem a MATLAB GUI fejlesztési lehetőségeire, és ezt mutattam be egy rövid példával.

57

A diplomamunkám továbbfejlesztésének több lehetőségét is látom. Célszerű megvizsgálni, hogy általános algoritmusok esetén a MEX segítségével történő C nyelvre átírás milyen sebességjavulásokat hoz (a programban használt rekurziónál körülbelül 50-szeresnek nevezhető a gyorsulás), és ennek segítségével gyorsabbá tehetőek egyrészről a szimulációk, másrészről a körülményesen kiszámítandó elméleti értékek. Ezen kívül a hibás szériák esetén érdemes vizsgálódni, hogy milyen aszimptotikus vagy rekurzív elméleti értékeket lehet megállapítani ezekhez az értékekhez. Harmadrészt érdemes megvizsgálni a leghosszabb szériás probléma több dimenzióra való kiterjesztését, legnagyobb terület illetve térfogat vizsgálatát.

58

Irodalomjegyzék [1] Arazi, B.:Handwriting identification by means of run-length measurements. IEEE Tranactions on Systems, Man and Cybernetics, 7 (12), 1977, pp. 878-881 [2] Binswanger, K. - Embrechts, P.:Longest runs in coin tossing. Insurance Math. Econom. 15, no. 2-3,. 1994, pp. 139-149. [3] Bloom, D. M.:Probabilities of Clumps in a Binary Sequence. Mathematics Magazine, 69, no. 5, 1996. [4] Csörgő, S.: A szentpétervári paradoxon, Polygon V. kötet 1. szám 1995. [5] Csörgő, S., Simons, G.:On Steinhaus’Resolution of the St. Petersburg Paradox, Probability and Mathematical Statisctics, Vol. 14, Fasc. 2, 1993, pp. 157-172. [6] Csörgő, S., Simons, G.:A strong law of large numbers for trimmed sums, with applications to generalized St. Petersburg games, Statictics & Probability Letters Vol. 26, issue 1, 1996, pp. 65-73. [7] Fazekas, I.: Valószínűségszámítás, Kossuth Egyetemi Kiadó, Debrecen, 2000. [8] Fazekas, I., Karácsony, Zs., Libor, J.: A leghosszabb szériák vizsgálata, 2010. december 8. [9] Fegyverneki, S.: Valószínűség-számítás és matematikai statisztika, Elektronikus jegyzet, Miskolc, 2007. [10] Feller, W.:Note on the Law of Large Numbers and „Fair” Games, Annals of Mathematical Statistics, Vol. 16, Num. 3 (1945) pp. 301-304 [11] Feller W.:Bevezetés a valűszínűségszámításba és alkalmazásaiba, Műszaki Könyvkiadó, Budapest, 1978. [12] Földes, A.: The limit distribution of the length of the longest head-run, Period. Math. Hungar. 10, no. 4, 1979, pp. 301-310. [13] Gardner, M.:aha! Gotcha, Freeman, New York, 1982. [14] Gisbert, S : MATLAB frissített kiadás, Typotex Kiadó, Budapest, 2005. [15] Gordon, L. - Schilling, M. F. - Waterman, M. S.:An extreme value theory for long head runs. Probab. Theory Relat. Fields, 72, no. 2, 1986, pp. 279-287. [16] Kopocinski, B.: On the distribution of the longest success-run in Bernoulli trials. Roczniki Polsklego Towarzystwa Matematycznego, Seria III, Matematyka Stosowana XXXIV, 1991. 59

[17] Laska, J.:Writing C Functions in MATLAB, cnx.org/content/m12348/latest/ [18] Libor, J.:Rekurziós eljárások, Monte Carlo módszerek és aszimptotikus eredmények oktatási célú összehasonlító elemzése, PhD értekezés, Debreceni Egyetem, 2011. [19] Martin-Löf, A.:A limit theorem which clarifies the ’Petersburg paradox’, Journal of Applied Probality 22, 1985, pp. 634-643. [20] MathWorks: techdoc/

MATLAB

documentation,

http://www.mathworks.com/help/

[21] Muselli, M.: Useful inequalities for the longest run distribution. Statis. Probab. Lett. 46, no. 3, 2000, pp. 239-249. [22] Révész, P.: Strong theorems on coin tossing, Proceedings of the International Congress of Mathematicians, Helsinki, 1978. [23] Révész, P.: Mennyire véletlen a véletlen? Akadémiai székfoglaló, Akadémiai Kiadó, Budapest, 1982. [24] Sararova, S. S.:On the asymptotic behaviour of the marinal sojourn time of and ergodic Markov chain in a fixed state. Russian Math Surveys 35 (6), 1980, pp. 103-104. [25] Schilling, M. F.: The Longest Run of Heads, The College Mathematics Journal 1990. vol. 21. no.3 [26] Schuster, E. F.:On overwhelming numerical evidence in the settling of Kinney’s waiting time conjecture. SIAM Jou4rnal of Statistical Computing, 6 (4), 1985. pp. 977-982. [27] Schwager, S. J.:Run probabilities in sequence of Markow-dependent trials. Journal of the American Statistical Association, 78, 1983. pp. 168-175. [28] Steinhaus, H.:The so-called Petersburg Paradox, Colloquium Mathematicum 2, 1949, pp. 56-58. [29] Szászné Simon, J.: A sztochasztika középiskolai oktatása, PhD értekezés, Debreceni Egyetem, 2005.

60

Adathordozó használati útmutató Az adathordozón álló program több részből tevődik össze. A központi rész a következő két fájlban található: diplomamunka.m és diplomamunka.fig. Ezek a fájlok tartalmazzák a program központi részét és a grafikus felülelet, és ez a program hívja meg a többi fájlt. A diplomamunka.m fájl tartalmazza a tényleges programot, ennek megnyitásával megtekinthető a forráskód, és futtatható az állomány. A program megnyitásához szükséges szoftver: MATLAB Version: 7, vagy újabb. A fejlesztés MATLAB 7.14.0.739 (R2012a) programváltozaton történt. A MEX-es programrészekhez szükséges az adott operációs rendszerre a fordítás. Windows 7 x64 rendszerre a lefordított állományok mellékelése megtörtént, más rendszerekre a Mexfunctions nevű mappában mellékelt két fájlt kell a diplomamunkám 3. fejezetében ismertetett módon kell lefordítani, és a lefordított fájlokat a diplomamunka.m állomány mellé másolni. Fordítók: • 32 bites rendszer esetén a MATLAB beépített lcc fordítója • 64 bites Windows rendszer esetén a Windows SDK 7.1-es vagy újabb változata ingyenesen letölthető • Microsoft Visual C++ 2010, vagy 2008 SP1 és Windows SDK 6.1 • Microsoft .NET Framework SDK 2.0, 3.0, 3.5 A program megnyitása: • Nyissa meg a MATLAB programcsomagot! • File menü Open parancsával, vagy az Open file parancssal nyissa meg az adathordozón található diplomamunka.m fájlt! • Ekkor látható a program kódja, amelyet futtasson le! • Szükség lehet a MATLAB elérési útjának beállítására, válassza az Add path lehetőséget! • Ekkor elindul a program. A menüsorban elérhető egy Súgó menü, amivel megjelenítheti a programokhoz tartozó súgót. A főpanelen válassza ki a megfelelő programot, és adja meg az értékeket, majd kattintson a Számol gombra! • Miután lefut a program, az eredmények a feladatnak megfelelő grafikus ábrán megjelennek. • A program hasonlóan működik mindegyik feladat esetén. • A fenti menüsorban megtalálható a program névjegye. 61

• A programból illetve a felugró GUI ablakokból a Kilépés gombbal léphet ki, ahol ez implementálásra kerül, ahol nem, ott a pirox X segítségével zárható be az adott ablak. A CD-n megtalálható a diplomamunkám teljes szövege pdf állományban, és a report mappában a LATEXforráskódok. Mellékelt MATLAB állományok: • diplomamunka.m : a főprogram forráskódja, • diplomamunka.fig : a főprogram GUI-jának kinézete, • fogadasGUI.m : a fogadásos programrész GUI-jának kódja, • fogadasGUI.fig : a fogadásos program GUI-ja, • martingalGUI.m : a martingál program GUI-jának kódja, • martingalGUI.fig : a marintgál program GUI-ja, • sugo.m : a program súgójának kódja, • sugo.fig : a program súgójának GUI-ja, • szentpetervariGUI.m : a szentpétervári programrész GUI-jának kódja, • szentptervariGUI.fig : a szentpétervári programrész GUI-ja.

62

Diplomamunka. Miskolci Egyetem. Leghosszabb szériák vizsgálata. Készítette: Selling István Mérnök Informatikus MSc jelölt

Recommend Documents