4. domáca úloha - riešenie Úloha 1 (0.5b). Uvažujme nasledujúcu hru. Hráč hádže kockou tak dlho, dokiaľ nepadnú dve hodnoty šesť v dvoch po sebe idúcich hodoch. Nech náhodná veličina X udáva celkový počet hodov kockou. Určite pravdepodobnostnú generujúcu funkciu náhodnej veličiny X a pomocou nej určite charakteristiky E(X) a D(X). Riešte za predpokladu, že kocka je férová t.j. každá z hodnôt 1 až 6 môže padnúť s pravdepodobnosťou |. Riešenie. Najskôr poznamenajme, že pravdepodobnostná funkcia nx(k) je nenulová iba pre k E N. Pre inšpiráciu si určíme niektoré počiatočné hodnoty nx- ttx(1) 7Tx(2) 7TX(3) 7Tx(4) = 0, 1 _ 5 6-5 5 Budeme uvažovať postupnosti bodov kocky reprezentované prvkami množiny {a, 6}. Pričom 6 bude značiť jav, že v danom ťahu padla hodnota šesť, a jav a bude doplnok javu 6 pre daný ťah. Formálne takáto postupnosť vyjadruje prienik javov, že v i-tom hode padla 6 alebo nepadla 6, cez všetky uvažované hody i. Teda pre pravdepodobnosti týchto javov platí P(a) = | a P(6) = |. Preto jav {X = 3} ide vyjadriť iba pomocou postupnosti aQQ. Na druhú stranu jav {X = 4} získame ako zjednotenie aa66 a 6a66 z postupnosti a66. Jav {X = n + 3} pre n > 2 vieme získať z výrazov aab(n + 1), 6ab(n + 1) a a6ab(n), kde b{k) je ľubovolná postupnosť pre {X = k}. Všimnite si, že fixná časť takejto postupnosti musí končiť na a. Preto postupnosti aab{n +1) a a6ab(n) vieme reprezentovať ako postupnosť ab{n + 2), celkovo máme 2 typy postupností pre tento prípad, a to ab(n + 2) a Qab(n + 1). Preto platí 5 1 nx(n + 3) = -(7TX(n + 2) + -nx(n + 1)) pre n > 0. o o Zostáva odvodiť generujúcu pravdepodobnostnú funkciu G x (t) = J2k=onx(k)tk pre X. Bude aplikovať jednoduché algebraické úpravy na predošlú rekurentnú formulku. nx(n + 3)r+3 = \t>KX{n + 2)tn+2 + ^-t\x(n + l)tn+1, b ób ^7rx(n + 3)r+3 = -í ^(7rx(n + 2)r+2) + -í2 ]>>x(n + n=0 n=0 n=0 OO p, oo r OO n=3 n=2 n=l J_/2 -2 |ŕ-4ŕ2 36 - 30ŕ-5ŕ2' o 36 1 Zostáva spočítať číselné charakteristiky E (X) a D (X). 2ŕ(36 - 30ŕ - 5ŕ2) - ŕ2(-30 - 10í) E(X) = G'x(l) (36 - 30ŕ - 5ŕ2)2 42, _ (72 - 60ŕ)(36 - 30ŕ - 5ŕ2)2 + (72í - 30í2)2(36 - 30í - 5í2)(30 + 10í) x( ^ ~ (36 - 30ŕ - 5ŕ2)4 E(X2) = G"x(l) + G^(l) = 12 + 42 • 81, D(X) = E(X2) - (E(X))2 = 12 + 42 • 81 - 422 = 42 • 40 - 30 = 1650. □ Úloha 2 (0.5b). Hráč má k dispozícii n identických kociek, kde n je pevné prirodzené číslo, a hodí každou kockou práve raz. Určite pravdepodobnostnú a distribučnú funkciu náhodnej veličiny X, ktorá údava súčet hodnôt na všetkých n kockách. Aplikujte pre prípad n = 6 a X = 16. Riešte za predpokladu, že každá kocka je férová t.j. každá z hodnôt 1 až 6 môže padnúť s pravdepodobnosťou |. ŕíz'nŕ: Použite generujúcu pravdepodobnostnú funkciu náhodnej veličiny. Riešenie. Náhodnú veličinu X je možné popísať ako X^ľ=i ^/ kde Xj popisuje bodovú hodnotu jednej kocky a náhodné veličiny X« sú po dvoch nezávislé. Generujúca funkcia náhodnej veličiny Xi je zrejme GxXť) = |(í + í2 + • • • + í6). Z vlastností konvolúcie náhodných veličín máme n / 1 \ n GX{t) = \{GxXt) = Vn{t+ŕ + ...+ŕr = ¥tna - tr — • i=l ^ 7 V ďalšom kroku použijeme binomickú vetu a súčet geometrickej rady, aby sme našli koeficient n x (m) pri tm. *>- F** &-)"í><ľ>M - ^"ž p::; >*£< \i=0 / 1=0 v 7 fc=0 v 7 z=o oo n w » 6Z k + n-1^ (n^n+el+k k=o i=o ® \ n 1 Koeficient pri tk sme našli ako počet riešení z No rovnice k\ + k2 H-----h A;n = /c, čo sa dá ľahko odvodiť úvahou „stars and bars". Označíme m = n + 6/ + k a nahradíme A; písmenom m, potom nutne m —n —61 = k > 0 t.j. L^^pJ > ^ Keďže má byť tiež n > l a vieme, že 7rx (m) > 0 iba pre m E [n, 6n]. Potom stačí uvažovať iba podmienku L^ipJ > l- Celkovo máme m=n 1=0 v / \ / Takže sme ukázali, že pravdepodobostná funkcia X je {I m~n I ľL6 ^(-lyr^1) (?) me[n,6n]nN, 0 inak. Zostáva odvodiť distribučnú funkciu Fx (x) náhodnej veličiny X. Keďže ixx je nenulová na N, stačí nám určiť postupnosť čiastočných súčtov ap = Yľm=n71x (m)- Generujúca funkcia A (í) 2 postupnosti {ap} bude A(t) = Gx{ť)Y^=Q^ = Gx(t)-^-j_. Takže ap dostaneme obdobným postupom, ako sme odvodili n x (m), len mocnina ^ nebude n, ale n + 1. m=n Z=0 v / \ / EL6 J^(-l)r(mľr)(ľ) m€[n,6n]nN, 0 m < n, 1 m > 6n. Preto distribučná funcia Fx{x), ktorá je sprava spojitá, je Elo6 J^(-l)r(L^6r)(ľ) x<=[n,&n], x < n, x > 6n. Keď je n = 6, potom je Na druhú stranu distribučná funkcia v bode 16 je □ Bonusová úloha pre tých, ktorým prišli úlohy jedna a dva jednoduché. Úloha 2019. Uvažujme nekonečne veľký hrací stôl tvorený nekonečne veľa za sebou idúcimi políčkami očíslovanými vzostupne prirodzenými číslami. Postavíme figúrku na jeho počiatok (hodnota 0) a v každom ťahu hodíme kockou a posunieme figúrku o hodnotu na kocke. Nech bk označuje pravdepodobnosť, že sa niekedy dostaneme na políčko k. Určite bk a linifc^oo bk (nie je to |). Riešte pre klasickú férovú kocku. Riešenie. Jednoduché pozorovanie je, že na ľubovolné políčko sa vieme dostať iba z predošlých šesť políčok, ak sú samozrejme k dispozícii. Takže pre pravdepodobnosti bk bude platiť obdobný rekurentný vzťah pre k e Z: Íl k = 0 0 k < 0 + h-2 + h-3 + h-4 + h-5 + h-e) k>0. Najskôr predpokladajme, že lim^oo bk existuje a označme túto hodnotu ako b e [0,1]. Pokúsime sa určiť túto hodnotu. Ak dosadíme b do predošlej rekuretnej formulky, tak dostaneme iba pravdivé tvrdenie: b = lim bk = \ (lim + lim 6fc_2 + Hm 6fc-3 + lim bk_A + lim 6fc_5 + lim 6fc_6) = 7(66). 3 Preto potrebujeme nájsť vhodný trik na výpočet b. Napíšeme si pod seba n > 6 poupravených rekurentných vzťahov. 66i = b0 Qb2 = h- 663 = b2- I-61 - hb0 664 = h ~ l-Ďl " h b0 665 = 64- h h ~ F&2 " h&i - 6&6 = h- h&4" F&3 " h&2 " h6l - 667 = h ~ VbA- h&3" h&2 " l-Ďl 6&8 = h- h&6 " - h&4" h&3 " Vb2 Qbn — bn-l + &n_2 + &n-3 + + &n-5 + ^n-6 Súčtom týchto rovníc obdržíme: 6bn + 56n_i + 46n_2 + 36n_3 + 26n_4 + 6n_5 = 6b0 = 6. Potom dostávame: lim 6bn + lim 56n_i + lim 46n_2 + lim 36n_3 + lim 26n_4 -r nm un_5 n—>oo n—>oo n—>oo n—>oo n—>oo n—>oo lim = 6 216 = 6. Zostáva ukázať, že zmienená limita existuje. Môžeme si všimnúť, že platí (vlastnosť aritmetického priemeru) min(6n_i, bn-2, bn-3, bn-4, &n_5, bn-e) < bn < max(6n_i, 6n_2, &n-3> &n-5> ^n-ô) a rovnosť nastáva iba v prípade 6n_i = 6n_2 = &n-3 = &n-4 = &n-5 = &n-6- Takže každé bn E [an,dn] má vlastnosť [an,dn] D [an-i,^n-i] 3 a teda podľa Cantorovej vety o prieniku je r\^=1 [an, dn] ý 0- Aby limita existovala, potrebujeme tento prienik jednoprvkový. To ukážeme pomocou rekurentného predpisu. Máme lineárnu diferenčnú rovnicu: 1 bk ~ -p(h-i + bk-2 + frfc-3 + bk-4 + &fc-5 + 6fc-e) = 0. o Jej riešenie je tvaru bn = X^=i c«(-^)n/ kde A« sú komplexné korene polynomu 1 = x6--(x5 + x4 + x3 + x2 + x + l). 6 Polynom p(rr) je charakteriským polynómom matice /111111X '666666» 1 0 0 0 0 0 A 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 \ 0 0 0 0 1 0 J 4 Platí, že Ae je tvorená kladnými prvkami11, j. matica A je primitívna, a naviac je aj stochastická. Potom podľa Perronovej-Frobeniovej vety má takáto matica práve jedno vlastné číslo 1 a všetky ostatné vlastné čísla A« splňujú |Aj| < 1 pre i > 1. Preto limita lim^oo 6n existuje a je rovná |. □ 1 Prvky bn pre n > 6 sú lineárnou kombináciou prvkov 6i, 62, ■ ■ ■, &6 s kladnými koeficientami, lebo vždy počítame priemer šiestich pravdepodobností.