Valószínűségszámítás programozási feladatok (BMETE91AM46/T1 - 2019/20/1)

Oktató: 
Kurzus típus: 
Gyakorlat
Nyelv: 
magyar
Félév: 
2019/20/1

A tárgyról

A tárgy célja a Valószínűségszámítás 1 című tárgy tematikájához kapcsolódó programozási feladatok megoldásán keresztül a hallgatók programozási képességeinek szinten tartása, és egyúttal a valószínűségszámítás alapfogalmainak véletlen események szimuláción keresztül való jobb megértésének elősegítése.

  • A tárgy 1 kredites, ami összesen 30 óra, azaz heti 2-3 óra programozási munka elvégzését kívánja. Olyan feladatokat igyekszünk adni, melyek érdekesek lesznek mindenki számára, és amelyek megoldása sok haszonnal fog járni.
  • A feladatok száma 12, összpontszáma 50. Követelmény a feladatok határidőre való leadása (illetve 1 pont elvesztése mellett legföljebb 1 héttel későbbi, késedelmes leadása) és a feladatokra kapható maximális összpontszám legalább 50%-ának elérése (50%–60% elégséges, 60%-70% közepes, 70%-80% jó, 80%- jeles).
  • A hibásan megoldott feladat az eredmény kihirdetése utáni 1 héten belül javítható.
  • A feladatok megoldásának Python kódját a valszam.prog@gmail.com címre csatolmányként kell elküldeni. A programfájl neve a feladat sorszámával kezdődjön, folytatásul a hallgató neve legyen szóközök nélkül, pl. Kovács Jutka 5-dik házi feladatát 5KovacsJutka.py néven küldje el. Ha Python3-ban oldja meg, a program nevének vége 3 legyen, példánkban 5KovacsJutka3.py.
  • A levél tárgya 5. HF Kovács Jutka, az esetleges javításé 5. HF javítás Kovács Jutka legyen.
  • A program kódját mindenkinek magának kell megírnia, a kódot másnak nem adhatja át. Minden házi feladat kísérő levelébe az alábbi szöveget kell írni:

     

    E programot magam kódoltam, nem másoltam vagy írtam át más kódját, és nem adtam át másnak.
    Aláírás

    Az, hogy az otthoni feladat kódját mindenkinek magának kell beírnia, programkódot átadnia, mástól kérnie és elfogadnia nem szabad, nem zárja ki az együtt gondolkodás vagy a segítségkérés lehetőségét! Konzultáció is kérhető.

  • Az eredményekről Neptun értesítést kap mindenki.

A program kódjáról

  • Gyakran lesz szükség véletlen számok generálására. Ehhez a random csomag használható (betöltése: import random). A random.random() hívással egy 0 és 1 közé eső véletlen számot kapunk (egyenletes eloszlás szerint). A kockadobás szimulálására a random.randint(1,6) függvény használható, ami  egy 1 és 6 közé eső egészt ad vissza.
  • A Python 2-ben egészek osztása egész eredményt ad. Python 3-ban ez megváltozott. Python 2-ből kérhetőek a jövő (a 3-as) egyes új tulajdonságai, például az osztás e tulajdonsága megváltoztatható a kód elejére írt from __future__ import division paranccsal.
  • Python 2 kódban csak akkor használjunk ékezetes betűket, ha a kód elejére beírtuk a
    # -*- coding: utf-8 -*-
    

    sort. Erre akkor is szükség van, ha csak megjegyzésbe írunk ékezetes betűt. Viszont Python 3-ban e sor hozzáadása szükségtelen, ott az utf-8 kódolás az alapértelmezett.

  • A kód legyen egyszerű, áttekinthető, rövid függvényekkel, és néhány világos megjegyzéssel. Például a függvények elején egy docstring-ben röviden adjuk meg, mit csinál a függvény. Például így
    def hatvany(arg1, arg2): 
        """ 
        Kiszámítja az arg1 az arg2-ediken hatvány értékét. 
        """ 
    
        return arg1**arg2
    

    Bonyolultabb függvényeknél a paramétereket és a return értékét is megmagyarázhatjuk (ld. bővebben például a Geek for geeks oldalán).

  • Minden programunkhoz írjunk main() függvényt, ahol meghívjuk a korábban megírt függvényeket. A kód utolsó sorainak szerkezete a következő legyen:
    def main():
        # itt hívjuk meg a korábban megírt függvény(eke)t.
    
    if __name__ == "__main__":
        main()
    

    A main() függvény lényegéről és értelméről egy ismertető található például a Real Python oldalán.

Feladatok listája

  1. Rizikó (19-09-22, 4 pont)
  2. Monthy Hall háromajtós problémája (19-09-29, 4 pont)
  3. Szentpétervári paradoxon (19-10-06, 3 pont)
  4. Binomiális eloszlás (19-10-13, 6 pont)
  5. Diszkrét valószínűségi változókat kezelő osztály (19-10-22, 5 pont)
  6. Bertrand-paradoxon (19-10-27, 5 pont)
  7. Adott eloszlásfüggvényű véletlen számok generálása (2019-11-03, 3 pont)
  8. Indul a parti (2019-11-10, 5 pont)
  9. Buffon-féle tűprobléma (2019-11-17, 3 pont)
  10. „U” súlyfüggvényű kocka konvolúciója (2019-11-24, 4 pont)
  11. Többdimenziós normális eloszlás (2019-12-08, 5 pont)
  12. Zipf-törvény (2019-12-08, 3 pont)

Feladatok

1. feladat: Rizikó (határidő 2019-09-22 24:00, 4 pont)

  • A Rizikó (Risk) nevű társasjátékban egyszerre egy játékos maximum három katonájával tud támadni, míg a védekező játékos legföljebb kettővel tud védekezni. Pontosan három támadó és két védő esetén az összecsapás a következőképpen zajlik. A támadó játékos három piros kockával míg a védekező játékos két kék kockával dob. Ezután összehasonlítjuk a támadó és a védő legnagyobb dobását. A kisebb érték birtokosa veszít egy katonát, a döntetlen a védőnek kedvez, vagyis ekkor a támadó veszít egyet. Ezután a két fél második legnagyobb dobását is összehasonlítjuk ugyanilyen módon. Így az összecsapásnak három kimenetele lehet: a támadó veszít két katonát, döntetlen, azaz mindkét fél veszít 1-1 katonát, a védő veszít két katonát.
    1. Szimulálja 1000-szer a kísérletet és ebből határozza meg a három esemény relatív gyakoriságát.
    2. Szimulálja 1000000-szor a kísérletet és ebből határozza meg a három esemény relatív gyakoriságát.
    3. Számolja ki a három kimenetel pontos valószínűségét az összes lehetséges eset megvizsgálásával. A valószínűséget a kedvező esetek és az összes esetek hányadosa adja. Ezeket az eredményeket is 5 tizedes pontossággal írja ki, köztük 3 szóközzel! A program kimenete így nézzen ki (természetesen más számadatokkal)
                      Tamado    Dontetlen Vedo
    1000 kíserlet:    0.35200   0.44400   0.20400
    1000000 kíserlet: 0.33988   0.43011   0.23001
    Valoszinuseg:     0.34000   0.43000   0.23000
    
  • A feladat célja: ismerkedés a klasszikus valószínűségi mezővel, a relatív gyakoriság és a valószínűség fogalmával és az elméleti valószínűség kísérleti megközelítésével.
  • Programozási cél: a Python programozás alapelemeinek felidézése, véletlen számok generálása.
  • A Wikipédián található egy rövid leírás a játékról, vannak a weben online játszható változatok is. Egy részletes leírás a feladatunk kiterjesztésének Matlab (Octave) kódjával a MIT ezen az oldalán található.

2. feladat: Monthy Hall háromajtós problémája (határidő 2019-09-29 szerda 24:00, 4 pont)

  • Egy egykori televíziós játék (USÁ-ban Let's Make a Deal volt a címe és Monthy Hall volt a műsorvezető, Magyarországon Zsákbamacska néven futott) utolsó fázisában a játékost 3 csukott ajtó elé állítják, melyek egyike mögött egy értékes jutalom (pl. gépkocsi) van, míg a másik kettő mögött valami értéktelen. A játékos kiválaszt egy ajtót, de mielőtt azt kinyitnák, a műsorvezető a másik két ajtó közül egyet kinyit megmutatva, hogy nem ott van az értékes ajándék, és fölajánlja a játékosnak, hogy még meggondolhatja magát és megváltoztathatja a döntését, választhatja a másik ajtót. A kérdés az, hogy ilyenkor mit érdemes tennie a játékosnak:
    1. tartson ki eredeti döntése mellett, vagy
    2. változtassa meg döntését, vagy
    3. mindegy, pl. 0.5 valószínűséggel kitart eredeti döntése mellett, 0.5 valószínűséggel megváltoztatja.

    Írjunk programot, mely szimulálja e három játékstratégiát, mindegyiket 1000-szer. A program

    1. véletlen módon jelöljön ki egy ajtót, amely mögött az értékes ajándék van,
    2. a játékos szerepében véletlenül válasszon egy ajtót (nem tudva az előző választásról),
    3. a műsorvezető szerepében (véletlenszerűen) válasszon egy ajtót, mely különbözik a játékos által választottól és amely mögött nem az értékes jutalom van,
    4. a játékos szerepében az első 1000-ben maradjon meg az eredeti döntése mellett, a második 1000 esetben változtassa meg döntését, a harmadik 1000 esetben 0.5 valószínűséggel változtasson eredeti döntésén, végül
    5. eredményül írjuk ki a játékos nyerésének relatív gyakoriságát a három esetben szóközzel elválasztva.
  • A feladat célja: a relatív gyakoriság szimuláción keresztül való megtapasztalása és a feltételes valószínűség fogalmának előkészítése egy paradoxonnak tűnő problémán keresztül.
  • Programozási cél: szimuláció programozása, véletlen szám generálása, ciklus írása.
  • A feladat a példatárban 2.20 sorszámmal szerepel.
  • Az Interneten sok információ található e problémáról, de azt javaslom, először töprengjünk el mindenki a feladaton, majd írja meg a programot, és ezzel ellenőrizze a saját teóriáját, és csak utána keressen rá.

3. feladat: Szentpétervári paradoxon (határidő 2019-10-06 24:00, 3 pont)

  • Egy kaszinó a következő játékot ajánlja: egy érmével addig dobunk, míg a fej oldalára nem esik. Ha ez az \(n\)-edik feldobáskor történik meg, akkor a játékos \(2^n\) forintot nyer (ld. Wikipédia). Szimuláljunk \(m\) játékot (azaz \(m\) fej dobásig játszunk). Mennyi a nyeremény átlaga \(m=100\), \(m=10000\) és \(m=1000000\) esetén?
  • A program kimenete e három átlag három tizedesjegy pontossággal megadva és szóközzel elválasztva.
  • A feladat célja egy végtelen várható értékű valószínűségi változóval való tapasztalatszerzés. A kérdés az, hogy vajon mennyiért adjon egy ilyen játékot a kaszinó, hogy ne járjon rosszul (e kérdésre nem kell válaszolni).
  • A feladat a példatárban 3.21 sorszámmal szerepel.

4. feladat: Binomiális eloszlás (határidő 2019-10-13 szerda 24:00, 6 pont)

  • Az e heti feladatban három oszlopdiagramot kell kirajzolni egyetlen ábrában. Az első ábra egy \((n,p)\) paraméterű binomiális eloszlás valószínűségeloszlását mutatja, a második ábra e binomiális eloszlást szimulálva tapasztalati valószínűségeloszlást mutat, míg a harmadik ábra a binomiális eloszlást közelítő \(\lambda=n\cdot p\) paraméterű Poisson-eloszlás valószínűségeloszlásának első \(n+1\) oszlopát ábrázolja.
  • A program eredményeként valami hasonló ábrát fogunk kapni (a színek, skálázás,... nem lényeges része a feladatnak):
  • A program bemenete \(n\), \(p\), \(k\), ahol \(n\) és \(p\) a binomiális eloszlás paraméterei, és \(k\) a szimulációk száma. A program például parancssorból így indítható:
    python 4KovacsJutka.py 12 0.3 1000

    vagy Python 3 esetén:

    python3 4KovacsJutka3.py 12 0.3 1000

    Ehhez a sys modult kell betölteni, ekkor az első paramétert a sys.argv[1] tartalmazza karakteres formában, tehát számoláshoz még konvertálni kell. Konverzióhoz például az int vagy a float függvény használható. (A kész programot futtassuk le különböző számhármasokon, pl. 20 0.05 100040 0.02 1000 vagy 40 .5 1000.)

  • A binomilás eloszlás értékeinek listájához a binomiális együtthatókra szükség lehet, amihez a math modul használható. Az első ábrán e valószínűségeloszlást ábrázoljuk oszlopdiagrammal.
  • A binomiális eloszlás szimulációja megvalósítható úgy, hogy $n$ kísérletet végzünk egy $p$ valószínűségű esemény bekövetkezéseinek számára. A valószínűségi változó értéke $m$, ha az esemény az $n$ kísérletből $m$-szer következett be. Ezt az $n$ kísérletet $k$-szor megismételjük, így a valószínűségi változó $k$ darab értékét kapjuk. A második diagram $m$-edik oszlopa $i/k$ magas legyen, ha a valószínűségi változó $i$-szer vette föl az $m$ értéket. (A feladat e pontja egyszerű ciklusokkal és a random modul random függvényével megvalósítható, de a numpy.random.binomial függvény is használható.)
  • A harmadik ábra egy Poisson-eloszlású $X$ valószínűségi változó első $n+1$ értékét mutatja, ahol \[ P(X=m)=\frac{\lambda^m}{m!}e^{-\lambda}, \quad m=0, 1, 2,\dots, \] ahol $\lambda=np$.
  • Az ábrák kirajzolásához a matplotlib csomag használható. Érdemes egy kis időt eltölteni megismerésével: nagyon egyszerűen használható. Betöltése a import matplotlib.pyplot as plt paranccsal történhet, ami után
    plt.bar(lista1,lista2,oszlopszelesseg) 
    plt.show()
    

    egy olyan oszlopdiagramot rajzol ki, ahol az oszlopok bal alsó sarkának $x$-koordinátája a lista1-ben, az oszlopok magassága a lista2-ben, az oszlopok szélessége az oszlopszelesseg változóban van. Ha három részábrát akarunk egyben ábrázolni, akkor az első előtt egy

    plt.subplot(311)

    parancsot kell kiadni, ahol a 311 jelentése: 3 sorban 1 oszlopban az első részábra jön. A következőbe 312, az utolsóba 313 kerül. (A plt.show() parancsot csak a legvégén adjuk ki, elég egyszer, de ne felejtsük el.)

  • A feladat célja binomiális eloszlású valószínűségi változó szimulálása, Poisson-eloszlásúval való közelítése, és ezeknek az elméleti eloszlással való összehasonlítása.
  • Programozási célok: program parancssorból való indítása, paraméterek átadása parancssorból, oszlopdiagram és részábra kirajzolása, véletlen események szimulálása.

5. Diszkrét valószínűségi változókat kezelő osztály (határidő 2019-10-22 24:00, 5 pont)

  • Írjunk egy Drv (discrete random variable) nevű osztályt a véges értelmezési tartományú diszkrét valószínűségi változók kezelésére. Az osztály konstruktora két azonos hosszúságú listát vár, az első az $X$ valószínűségi változó $x_k$ értékeit, a második a $p_k=\mathbb{P}(X=x_k)$ valószínűségeket tartalmazza. Írjuk meg a következő metódusokat:
    • __init__: konstruktor, melyben az xk és pk tulajdonságok (attribútumok) tárolják a valószínűségi változó értékei és a valószínűségei listáját.
    • e: $X$ várható értéke.
    • is_nonneg: igaz értéket ad vissza, ha a valószínűségi változó nem negatív, egyébként hamis.
    • reweighting: a 4.1 feladat általánosításaként visszaad egy $Y$ valószínűségi változót, mely az eredeti $X$ valószínűségi változóból a következő „átsúlyozással” kapható: \[\mathbb{P}(Y=x_k)=\frac{x_kp_k}{\mathbb{E}(X)},\] feltéve hogy $X$ nemnegatív és nem azonosan 0.
    • Binomial: A Drv leszármazott osztálya, a binomiális eloszlás. Paraméterei \(n\) és \(p\). Ebben az osztályban írjuk újra az e és az is_nonneg metódusokat.
    • Uniform: egyenletes eloszlású valváltozót adó osztály, a Drv leszármazott osztálya, paramétere \(n\), értékeinek listája \([1,2,\dots,n]\). Itt is írjuk újra az előbb említett metódusokat.
  • A program írása közben interaktív módban tesztelve azt például a következőt kaphatjuk:
    In [2]: y = Drv( [40, 33, 25, 50], [1/4]*4 )
    
    In [3]: y.xk
    Out[3]: [40, 33, 25, 50]
    
    In [4]: y.pk
    Out[4]: [0.25, 0.25, 0.25, 0.25]
    
    In [5]: y.is_nonneg()
    Out[5]: True
    
    In [6]: y.e()
    Out[6]: 37.0
    
    In [7]: x = y.reweighting()
    
    In [8]: x.xk
    Out[8]: [40, 33, 25, 50]
    
    In [9]: x.pk
    Out[9]: 
    [0.2702702702702703,
     0.22297297297297297,
     0.16891891891891891,
     0.33783783783783783]
    
    In [10]: x.e()
    Out[10]: 39.28378378378378
    
    In [11]: z = Binomial(5, .4)
    
    In [12]: z.xk
    Out[12]: [0, 1, 2, 3, 4, 5]
    
    In [13]: z.pk
    Out[13]: 
    [0.077759999999999982,
     0.25919999999999999,
     0.34560000000000002,
     0.23040000000000005,
     0.076800000000000021,
     0.010240000000000003]
    
    In [14]: z.e()
    Out[14]: 2.0
    
    In [15]: z = Uniform(3)
    
    In [16]: z.xk
    Out[16]: [1, 2, 3]
    
    In [17]: z.e()
    Out[17]: 2.0
    
  • Ha már elkészítettük a kódot egy külön fájlba (segítségül egy hiányosan megírt kód Python2-ben, illetve Python3-ban), akkor a következőképp tölthetjük be Python2-ben:
    from __future__ import division
    execfile("5YourName.py")
          

    Python3-ban a betöltés:

    exec(open("5YourName3.py").read())
          

    Ezután a fenti függvényhívásokkal kísérletezhetünk és tesztelhetjük a kész programot.

  • Néhány segítség: elevenítsük fel az objektum orientált programozás alapjait, jól jöhet a listaértelmezés, a binomiális együtthatókhoz használható a from scipy.special import comb utasítással betöltött comb függvény, de akár saját függvény is írható.
  • A feladat célja egy több funkciót is kezelni képes rendszer megírása a diszkrét valószínűségi változók kezelésére objektumorientált programozási stílusban az öröklődést is használva.

6. Bertrand-paradoxon (határidő 2019-10-27 vasárnap 24:00, 5 pont)

  • A Bertrand-paradoxon (valójában nem paradoxon) arra példa, hogy egy látszólag egyszerű valószínűségi változó milyen sokféleképp valósítható meg, ha a definíciója nem elég egyértelmű. E paradoxon klasszikus változata azt kéri, hogy számítsuk ki annak valószínűségét, hogy egy adott körbe véletlenül berajzolt húr mekkora valószínűséggel lesz rövidebb, mint a körbe rajzolható egyenlő oldalú háromszög oldala (ld. Wikipédia). Paradoxonnak azért tűnik e probléma, mert három különböző, egyaránt józan feltevés mellett az $1/2$, a $2/3$ és a $3/4$ is helyes válasz lehet.
    1. Az első feltevés az, hogy választunk egy véletlen irányt (ez szimmetria okokból lehet bármelyik, így akár a vízszintes is) és a húrt a rá merőlegesek közül választjuk ki, véletlenül választva egy pontot a kör vízszintes átmérőjén.
    2. A második feltevés az, hogy választunk a kör kerületén egy pontot és a húr másik végpontja a kör kerületének egy másik, véletlenül választott pontja lesz.
    3. A harmadik feltevés az, hogy választunk a körlapon (egyenletes eloszlás szerint) egy pontot, és azon keresztül húzunk egy húrt úgy, hogy az merőleges legyen a pontot a középponttal összekötő egyenesre.

    Mindhárom feltevést és a megoldást is (kicsit más megfogalmazásban) ötletes és élvezetes animációkkal szemlélteti az MIT egy oldala (a megoldás elolvasása előtt érdemes kicsit töprengeni rajta!)

    A továbbiakban legyen a kör egységsugarú, tehát az átmérője 2, és jelölje a húr hosszát egy kísérletben $X$, azaz $X$ egy valószínűségi változó, melynek értéke $0$ és $2$ közé esik. A feladat az lesz, hogy írjunk egy bertrand(N) paranccsal hívható függvényt, mely mindhárom modellben szimulál $N$ kísérletet a húr kiválasztására, följegyzi a hosszakat egy listába, és annak alapján kirajzolja mindhárom esetben a tapasztalati eloszlásfüggvényt. A tapasztalati eloszlásfüggvény értéke az $x$ helyen azt mondja meg, hogy mennyi a relatív gyakorisága az $\{X\lt x\}$ eseménynek. E függvény lépcsős függvény. (Az eloszlásfüggvényt becsüljük vele, melynek definíciója $F_X(x)=\mathbb P(X\lt x)$.) Ha például három kísérletet végezve a húrok hossza $1.5$, $0.4$ és $1.2$, akkor a tapasztalati eloszlásfüggvény ábrája így néz ki (ha azt a matplotlib.pyplot grafikai könyvtár step függvényével rajzoljuk; tekintsünk el a lépcsős függvénybe berajzolt függőleges szakaszoktól, és a szakadási helyeken gondoljuk a lépcsős függvényt balról folytonosnak):
    B1.png

    A feladat kimenete legyen a három tapasztalati eloszlásfüggvény grafikonja egyetlen ábrán. A függvényeket elég a $[0,2]$ intervallum fölött ábrázolni. Nyilván mindhárom függvény monoton növekvő, értéke $0$-ban $0$, $2$-ben $1$, és a paradoxon megoldásából tudjuk, hogy a $\sqrt3\approx1.732$ helyen közelítőleg $1/2$, $2/3$, illetve $3/4$ a modelltől függően.

  • Segítség a megoldáshoz (nem kell követni a tanácsokat, de segíthetnek):
    • Az első modellhez: válasszunk egy véletlen $r$ számot a $[-1,1]$ intervallumból, és számítsuk ki az $(r,0)$ pontba állított, $x$-tengelyre merőleges húr hosszát (ehhez a math modul acos és sin függvényei kellenek).
    • A második modellhez: legyen az egyik pont az $(1,0)$, a másik pont legyen a kör kerületének egy véletlen pontja, azaz $(\cos\alpha,\sin\alpha)$, ahol $\alpha$-t válasszuk egyenletes eloszlás szerint a $[0,2\pi)$ intervallumból (itt ki kell számítani e két pont távolságát).
    • A harmadik modellhez: válasszunk először egy tetszőleges pontot a $[-1,1]\times[-1,1]$ négyzetből (azaz válasszunk két véletlen számot a $[-1,1]$ intervallumból, és képezzünk belőlük számpárt), és ellenőrizzük, hogy a körbe esik-e. Ha nem, válasszunk még egyet addig, míg egy körbe esőt nem találunk. Ha találtunk, az origótól való távolságából az első modellhez hasonlóan számolható a húr hossza.
    • A tapasztalati eloszlásfüggvény kirajzolásához: ha szimuláltunk $N$ kísérletet, egy sort() metódussal rendezzük, írjunk az elejére egy $0$-t, végére egy $2$-est. Ez a lista adja a rajz vízszintes tengelyén a beosztásokat, amely pontok felett a lépcsős függvény „ugrik”. Minden egyes ilyen helyen a függvény értéke $1/N$-nel nő. Ha a legrövidebb húr hossza $r$ (ez $1$ valószínűséggel nagyobb $0$-nál), akkor a függvény a $[0,r]$ intervallumon $0$, így a függvényértékek listáját érdemes $y=[0,0,1/N,2/N,...,1]$-nek választani. A kirajzoláshoz a matplotlib.pyplot.step(x,y) függvény használható, ahol $x$ és $y$ az előbb konstruált két lista. (E Python függvény a grafikonba függőleges vonalakat is berajzol.) Egy megoldást mutat a következő ábra $N=1000$ esetén:
      B2.png
    • A program elkészülte után végezzünk kísérleteket különböző $N$ értékekkel és cseréljük ki a step függvényt plot-ra.
    • A program legyen terminálból hívható, ahol az $N$ értéke átadható. Például $N=100$ esetén legyen a parancs
      python 6KovacsJutka.py 100

      vagy Python 3 esetén:

      python3 6KovacsJutka3.py 100
  • A feladat célja a következő fogalmak megértésének elősegítése: folytonos valószínűségi változó, eloszlásfüggvény és annak tapasztalati közelítése.
  • Programozási szempontból a feladat nem tartalmaz új elemeket, célja az eddig megszerzett ismeretek gyakorlása.

7. feladat: Adott eloszlásfüggvényű véletlen számok generálása (határidő 2019-11-03 vasárnap 24:00, 3 pont)

  • Egy \(X\) valószínűségi változó eloszlásfüggvénye a \([0,2]\) intervallumon a következő: \(F_X(x)=x^2\), ha \(x\in[0,0.5]\), és \(F_X(x)=(x+1)/3\), ha \(x\in(0.5,2]\). Írjunk Python függvényt, mely szimulál egy ilyen eloszlásfüggvényű valószínűségi változót, azaz amely minden meghívására visszaad egy \(F_X\) szerinti véletlen számot. Írjunk programot, mely \(1000\) ilyen véletlen számot generál, és kiírja ezek átlagát, és azt, hogy az \(1000\) szám között hány volt egyenlő \(0.5\)-del.
  • A feladat célja valószínűségi változó függvényének, például az $F_X(X)$ valószínűségi változónak a megértése, és ezt használva adott eloszlású valószínűségi változó szimulálása.

8. feladat: Indul a parti (határidő 2019-11-10  24:00, 5 pont)

  • Móricka este 10 órára egy bulit szervez, meghívja 10 barátját. Egy különleges játékot talált ki amihez rajta kívül legalább 8 emberre van szükség. Mindenki izgatott, így amint befut a 8-adik barátja már kezdik is a játékot. Tegyük fel, hogy a barátai egymástól függetlenül 10 és 11 óra között egyenletes eloszlás szerint érkeznek (beleértve azt is, hogy 10 előtt senki sem érkezik, viszont 11-ig mindenki befut). Jelölje \(X\) azt, hogy a 10 és 11 közötti időintervallum hányad részénél kezdődik a játék (vagyis \(X\) egy 0 és 1 közötti értéket felvevő valószínűségi változó).
    1. Írjunk egy \(X\)-et szimuláló függvényt!
    2. Tekintsük a következő két sűrűségfüggvényt: \begin{align*} f_a (x) = \frac{10!}{7! \cdot 2!}x^7 (1-x)^2,\quad 0\le x \le1,\\ f_b (x) = \frac{10!}{6! \cdot 3!}x^6 (1-x)^3,\quad 0\le x \le1. \end{align*}

      Szimuláljuk \(X\) értékét 5000-szer, ezekből rajzoljuk meg a hisztogramot 50 oszloppal, és a két sűrűségfüggvényt, majd ennek alapján döntsük el, hogy közülük melyik lehet \(X\) sűrűségfüggvénye!

    3. Felhasználva az előzőleg generált 5000 adatot, \(X\) mindegyik szimulált értékét helyettesítsünk be mindkét sűrűségfüggvénybe és a helyettesített értéket szorozzuk meg egymástól és minden korábbi valószínűségi változótól független, \([0,1]\)-en egyenletes eloszlású véletlen számmal. Végül ezeket az értékeket pontokként ábrázoljuk az eredeti szimulált értékek függvényében. Egy ábra két részábráján legyen a két függvényhez tartozó ,,pontfelhő''. Döntsük el a két ábra alapján, hogy a két lehetőség közül melyik \(X\) sűrűségfüggvénye! A választ indokoljuk is!
  • A feladat kimenete két ábra. Az elsőn két \([0,1]\)-en értelmezett függvény grafikonja, és egy 50 oszlopból álló hisztogram látható. A második ábra két részábrából áll, a fölsőn az első sűrűségfüggvény alatti területet fedő ponthalmaz, az alsó részábrán a második sűrűségfüggvény alatti területet fedő ponthalmaz látható. A kísérőlevélben adjunk rövid magyarázatot arra, hogy a második ábráról hogyan és miért olvasható le, hogy melyik lehet a valódi sűrűségfüggvény.
  • Segítség, tanácsok:
    1. Függvény grafikonjának kirajzolásához a következő kódot lehet használni (más jó megoldás is van!):
      from __future__ import division # Python 2 eseten
      import numpy as np
      import matplotlib.pyplot as plt
      
      # t egy olyan tomb lesz, mely a 0, .02, .04,... 1 szamokat tartalmazza
      lepeskoz = 1/50
      t = np.arange(0, 1 + lepeskoz, lepeskoz)
      plt.plot(t, sfv(t), color = "red")
      

      Itt a plot függvény első argumentuma az értelmezési tartomány értékeit, a második argumentum a hozzájuk tartozó értékeket adja meg, ahol sfv a sűrűségfüggvény, amit előtte definiálni kell.

    2. A hisztogram kirajzolása azt jelenti, hogy egy intervallum fölé olyan magas oszlopot rajzolunk, mely arányos az intervallumba esett szimulált értékek számával. Ennek kirajzolására van egyszerű függvény, ahol kiserletek az \(X\) értékeinek listája, bins az intervallumbeosztás, normed azt jelenti, hogy az oszlopok összterülete mennyi legyen:
      plt.hist(kiserletek, bins=t, normed=1)
      
    3. A pontok rajzolásához meg kell adni a plt.plot harmadik argumentumaként, hogy milyen stílusú legyen, oda elég egy "r." sztringet írni, ami azt jelenti, hogy a megadott pontok nem lesznek összekötve, és a pontfelhő színe piros lesz (r=red).
  • A feladat célja a sűrűségfüggvény szemléltetése és a béta eloszlás szimulációja. Programozási cél: elemi programozási és grafikai ismeretek gyakorlása.

9. feladat: Buffon-féle tűprobléma (határidő: 2019-11-17 24:00, 3 pont)

  • A Buffon-féle tűprobléma egy klasszikus feladat, megismerhető például Vetier András jegyzetének 28. oldalán. Ezt fogjuk általánosítani. Vegyünk egy megfelelően nagy papírt, amelyen egymástól egységnyi távolságra párhuzamos egyenesek vannak. Egy \(L\) hosszúságú tűt véletlenszerűen dobjunk a papírra. Legyen \(X\) a tű által metszett egyenesek száma. Írjuk ki \(N\) kísérlet alapján \(X\) tapasztalati súlyfüggvényének értékeit a 0, 1, 2, …, \(\lfloor L\rfloor+1\) helyeken.
  • A program parancssori bemenete egy pozitív egész \(N\) szám és egy pozitív valós \(L\) szám, kimenete egy \(\lfloor L\rfloor+2\) egész számból álló számsorozat.
  • Megjegyezzük, hogy ha \(L=0.5\), akkor a kísérletet fizikailag sokszor elvégezve a metszés relatív gyakoriságának reciproka \(\pi\)-t közelíti.
  • A szimuláció szimmetria okok miatt többféleképp is egyszerűsíthető. Például a fent említett jegyzetbeli gondolatot követve a tű egyenesekkel bezárt hegyes szögét és középpontjának a közelebbi egyenestől való távolságát tekinthetjük a \([0,\pi/2]\), illetve a \([0,0.5]\) intervallumon egyenletes eloszlásúnak. Próbálkozhatunk úgy is, hogy a tű „bal” végpontját a \([0,1]\) intervallumon egyenletes eloszlásúnak tekintjük, stb.
  • Akik szeretik a kihívásokat megpróbálkozhatnak az elméleti levezetéssel valamely konkrét \(L\) esetén (pl. \(L=2\) vagy \(L=5\)) kiszámítva az egyes metszésszámok elméleti valószínűségét, majd a végeredményt összevethetik a tapasztalati értékekkel. (Ez nem része a beadandó feladatnak!)

10. feladat: „U” súlyfüggvényű kocka konvolúciója (határidő: 2019-11-24 24:00, 4 pont)

  • Egy dobókocka úgy van cinkelve, hogy az $1$, $2$, $3$, $4$, $5$, $6$ értékek rendre $0.35$, $0.10$, $0.05$, $0.05$, $0.15$, $0.30$ valószínűségekkel adódnak. Számoljuk ki (programmal, de ne szimuláljuk hanem a konvolúciós képletet használva pontosan számoljuk ki) egy, kettő, három, négy, tíz és húsz kockadobás összegének eloszlását, majd ábrázoljuk a súlyfüggvényeket. A húsz kockadobás összegéhez tartozó ábrára másik színnel rajzoljuk rá az összeget jól közelítő normális eloszlás sűrűségfüggvényét is.
  • A feladat célja: Konvolúció számolása, a centrális határeloszlás-tétel szemléltetése (a normáliséra nagyon nem hasonlító súlyfüggvény esetén).
  • Segítség: $k$ darab kocka súlyfüggvényének konvolúciója egy $6^k$ méretű adathalmazból is meghatározható, azonban az így megírt program nem fog tudni időben lefutni. Tanácsunk az, hogy $k$ súlyfüggvény konvolúcióját rekurzívan számolják: 2 kockáé egy $6\times6$-os mátrix diagonálisan összegzett értékeiből kapható meg, ahol a valószínűségeloszlás 11 elemű. 3 kocka esetén ezt a súlyfüggvényt konvoláljuk a kocka súlyfüggvényével, amihez egy $6\times11$-es mátrix diagonális összegei használhatók, stb.

11. feladat: Többdimenziós normális eloszlás (határidő: 2019-12-08 24:00, 5 pont)

  • E feladatunk a többdimenziós és az egydimenziós normális eloszlás egy fontos kapcsolatát szemlélteti. A feladat az, hogy állítsunk elő 1000 darab adott várható értékű, adott kovarianciamátrixú 2-dimenziós normális eloszlású pontot és ábrázoljuk őket a síkon. Az előállítást kétféleképp is meg kell valósítani! Először két független normális eloszlású párjából képzett vektorváltozó lineáris transzformációjával, amihez a numpy.random csomag normal függvénye használható (és pl. a numpy.linalg csomag). A transzformáció mátrixát jelölje \(\mathbf M\), ekkor a kovarianciamátrix \(\mathbf{M}\mathbf{M}^T\) lesz. Másodszor a numpy.random csomag multivariate_normal függvényével generáljuk a véletlen pontokat. E függvény argumentumai közt a kovarianciamátrix is szerepel. Végül mindkét ábrára rajzoljuk ki azt az ellipszist is, mely az adatok nagy részét tartalmazza. Az ellipszis félnagytengelyei a kovarianciamátrix szinguláris értékeinek 6-szorosai legyenek (a szinguláris érték itt a kovarianciamátrix pozitív szemidefinit volta miatt egybe esik a sajátérték négyzetgyökével). Az egyszerűség kedvéért a várható érték 0, illetve \((0,0)\) legyen.
  • A program parancssorból fusson, parancssori bemenete a transzformációmátrix 4 eleme legyen sorfolytonosan megadva, kimenete két ábra. Például a python 11KovacsJutka.py 2 5 3 0 bemenetre a program eredményeként a \[ \begin{bmatrix}2&5\\3&0\end{bmatrix} \] transzformációmátrixszal számolva a következőhöz hasonló két ábrát kapunk:
  • Az ellipszis kirajzolása nehézséget okozhat. Ehhez a tengelyek mérete és a nagytengely hajlásszöge szükséges, aminek kiszámításához a np csomag rad2deg és arctan függvényei is használhatók. Néhány ötlet (nem kell követni, más út is lehetséges):
   from matplotlib.patches import Ellipse    # csomag a rajzoláshoz

   ax = plt.subplot(111, aspect='equal')     # egyetlen részábra
   ell = Ellipse(xy=(0,0),...                # kitöltendő
   ell.set_facecolor('none')                 # legyen üres
   ax.add_artist(ell)
   plt.plot(x, y, 'x')                       # ezek már a pontok
   plt.axis('equal')
  • A feladat célja a 2-dimenziós normális eloszlás kovarianciamátrixának és a független normális eloszlásokból álló vektorváltozó lineáris transzformáltja kapcsolatának szemléltetése.

12. feladat: Zipf-törvény (határidő: 2019-12-08 vasárnap 24:00, 3 pont)

Az utolsó feladat egy érdekes megfigyelésről szól, a Zipf-törvényről, melyről a Wikipedia a következőt írja: „A Zipf-törvény azt állítja, hogy egy természetes nyelv egyes részeiben egy szó előfordulási gyakorisága fordítottan arányos a gyakorisági (előfordulási) táblában levő rangjával. Így, a leggyakoribb szó közel kétszer gyakoribb, mint a második leggyakoribb szó, és háromszor gyakoribb, mint a harmadik helyen lévő, stb.”

Amennyiben e szabály fennáll egy szövegre, akkor a gyakorisági függvény grafikonja egyenes egy olyan koordinátarendszerben ábrázolva, melyben mindkét koordinátatengely beosztása logaritmikus. A feladat az lesz, hogy egy természetes szövegre ellenőrizzük e szabályt grafikusan, azaz rajzoljuk ki a gyakoriságokat loglog koordinátarendszerben. Teszteléshez néhány szövegminta található a http://sandbox.hlt.bme.hu/~gaebor/zipf/ oldalon. E szabályt tökéletesen megvalósítja a szövegminták közt található tokeletes.txt fájl. Kisebb minták vannak az ember tragédiájából és nagyobb méretű angol szövegek.

A program kódolásához ezúttal (az utolsó hétre való tekintettel) nagy segítséget adunk, a program kódjának nagy részét mellékeljük, csak a hiányzó kódot kell pótolni. Hogy mit kell csinálni, az kitalálható a környezetből és a megjegyzésekből. A kód úgy van megírva, hogy Python2 és Python3 alatt egyaránt futtatható, de a Python2 kimenetében az ékezetes betűk utf8 kódja jelenik meg, Python3-ban olvashatóan maga a betű.

from __future__ import print_function  # print meghivasa fuggvenykent

import matplotlib.pyplot as plt
import sys

filename = sys.argv[1]

def plot_zipf(filename):
    """
    Kirajzolja a rang-gyakoriság grafikont 
    egy loglog koordinátarendszerben.
    """

    d = {}                                           # szotar letrehozasa 
    with open(filename, "r") as f:                   # fájl megnyitása olvasásra
        for line in f:
            for word in line.strip().split():        # szavakra bont 
                word = word.strip(',.-_?! ').lower() # irasjelet torol
                if word != '':
                    ...........                   # a nem ures szavak szamolasa,
                                                  # es beirasa a d szotarba, ahol
                                                  # a szo a kulcs es 
                                                  # a gyakorisag az ertek
    data = sorted(d.values(), reverse=True)          # a gyakorisagok
    plt.loglog(range(..............), data)          # kirajzolasa
    plt.show()                                       # loglog skalaval

    # a szotar konvertalasa parok listajava, majd rendezese a
    # a parok masodik eleme mint kulcs szerint, vegul az elso 10
    # par kiirasa
    print(sorted(d.items(), key=lambda x:x[1], reverse=True)[0:10])

def main():
    plot_zipf(filename)

if __name__ == "__main__":
    main()

A kódot így, parancssorból futtatható alakban kérjük, de ha valaki a jupyter-ben ír és tesztel, betehet egy

%matplotlib inline

sort második sorként a kódba, de az elküldendő fájlból azt vegye ki!

  • A feladat célja egy tapasztalati eloszlás megismerése, a megfelelő ábrázolás kiválasztása.
  • Programozási cél: ismerkedés a természetes nyelvi adatok feldolgozásának alapjaival.