Počítanie s pravdepodobnosťou

  1. Minca
    1/21/2-hlava
    1/21/2-znak
    Hádžeme 100x
    Očakávaný počet hláv?

X1,…,X100X_1, \dots, X_{100}
Xi=X_i = 1 ak padla v ii-tom hode hlava, inak 0
E[X1+⋯+X100]=100⋅1/2=50E[X_1 + \dots + X_{100}] = 100 \cdot 1/2 = 50

  1. Tá istá minca. Hádžeme, kým nemáme 10 hláv. Koľko to v očakávanom prípade bude trvať?
    • Čo ak hádžeme, iba kým nehodíme prvú hlavu?
      • Čo ak hádžeme hlavu so šancou 1/3?

Pre prípad jednej hlavy:
YY = počet hodov, kým hodíme hlavu
Ak v prvom hode hodíme hlavu, máme hotovo. Ak hodíme znak, sme v rovnakej situácii ako pred hodom, teda potrebujeme v priemere ešte E[Y]E[Y] ďalších hodov.

E[Y]=1/2⋅1+1/2(1+E[Y])E[Y] = 1/2 \cdot 1 + 1/2 (1 + E[Y])
E[Y]−1/2E[Y]=1/2+1/2E[Y] - 1/2 E[Y] = 1/2 + 1/2
E[Y]=2E[Y] = 2

Vo všeobecnosti, ak hádžeme hlavu s pravdepodobnosťou pp:
E[Y]=p⋅1+(1−p)(1+E[Y])E[Y] = p \cdot 1 + (1-p) (1 + E[Y])
E[Y]−(1−p)E[Y]=p+(1−p)E[Y] - (1-p) E[Y] = p + (1-p)
pE[Y]=1p E[Y] = 1
E[Y]=1/pE[Y] = 1/p

Naspäť k pôvodnej úlohe:
Postupnosť hodov môžeme rozdeliť na 1010 častí: pokým nehodíme prvú hlavu, od hodenia prvej hlavy po hodenie druhej, atď.
ZZZZH H ZH H ZZZH H H ZH ZH H
ZiZ_i = dĺžka ii-tej časti
E[Zi]=2E[Z_i] = 2
E[Z1+⋯+Z10]=10⋅2=20E[Z_1 + \dots + Z_{10}] = 10 \cdot 2 = 20

  1. [coupon collector]Existuje 100 rôznych druhov strašidielok. V každom jogurte je jedno náhodné strašidielko. Kupujeme jogurty, kým nemáme všetky druhy. Koľko jogurtov v priemere kúpime?

YiY_i = koľko trvá nájsť ii-tu rôznu príšerku, ak som už našiel i−1i-1
(koľko jogurtov trvá dostať sa zo stavu “mám i−1i-1 rôznych príšeriek” do stavu “mám ii rôznych príšeriek”)
ZZ = koľko trvá nájsť všetky príšerky
Z=Y1+⋯+Y100Z = Y_1 + \dots + Y_{100}

100−(i−1)100\frac{100-(i-1)}{100} = pravdepodobnosť, že otvoríme novú príšerku, ak ich už máme i−1i-1
Ak minca padne s 1/x1/x, hodiť ju trvá v priemere xx

E[Yi]=100100−(i−1)E[Y_i] = \frac{100}{100-(i-1)}
E[Z]=E[Y1+⋯+Y100]=E[Y1]+E[Y2]+⋯+E[Y100]E[Z] = E[Y_1 + \dots + Y_{100}] = E[Y_1] + E[Y_2] + \dots + E[Y_{100}]
E[Z]=100/100+100/99+100/98+⋯+100/1E[Z] = 100/100 + 100/99 + 100/98 + \dots + 100/1
E[Z]=100(1/1+1/2+1/3+⋯+1/100)=518.7377517639619E[Z] = 100 (1/1 + 1/2 + 1/3 + \dots + 1/100) = 518.7377517639619
∑i=1n1i≈ln⁡n\sum_{i=1}^{n} \frac{1}{i} \approx \ln n

  1. Náhodné prechádzky. Začneme v bode 0. V každom kroku sa posunieme o +1, alebo -1 (s pravdepodobnosťami 1/2).

SnS_n = číslo, v ktorom sme po nn krokoch
E[Sn]=0E[S_n] = 0
E[∣Sn∣]=???E[|S_n|] = ???
E[Sn2]=???E[S_n^2] = ???

E[S02]=0E[S_0^2] = 0
E[S12]=1E[S_1^2] = 1
E[S22]=1/2⋅02+1/2⋅22=2E[S_2^2] = 1/2 \cdot 0^2 + 1/2 \cdot 2^2 = 2
E[S32]=3E[S_3^2] = 3

Urobili sme nn krokov a sme v čísle KnK_n. Z nášho pohľadu teda
E[Sn2∣Kn]=Kn2E[S_n^2 | K_n] = K_n^2.
Kde budeme po ďalšom kroku?
E[Sn+12∣Kn]=1/2(Kn−1)2+1/2(Kn+1)2E[S_{n+1}^2 | K_n] = 1/2 (K_n - 1)^2 + 1/2 (K_n + 1)^2
E[Sn+12∣Kn]=1/2Kn2−1/2⋅2Kn+1/2⋅12+1/2Kn2+1/2⋅2Kn+1/2⋅12E[S_{n+1}^2 | K_n] = 1/2 K_n^2 - 1/2 \cdot 2 K_n + 1/2 \cdot 1^2 + 1/2 K_n^2 + 1/2 \cdot 2 K_n + 1/2 \cdot 1^2
E[Sn+12∣Kn]=Kn2+1E[S_{n+1}^2 | K_n] = K_n^2 + 1

Hodnota E[Sn2]E[S_n^2] rastie každým krokom o 1.

E[Sn2]=nE[S_n^2] = n
E[∣Sn∣2]=nE[|S_{n}|^2] = n
E[∣Sn∣]2=???E[|S_n|]^2 = ???

Známa nerovnosť (viď https://cs.wikipedia.org/wiki/Nerovnosti_mezi_pr%C5%AFm%C4%9Bry)
Štvorec priemeru ≤\leq Priemer štorcov

E[∣Sn∣]2≤nE[|S_n|]^2 \leq n
E[∣Sn∣]≤n=O(n)E[|S_n|] \leq \sqrt{n} = O(\sqrt n)

Intuícia, prečo je štvorec priemeru ≤\leq priemeru štvorcov

Ak sú všetky čísla rovnaké, nastáva rovnosť:
15 15 15 15 15 15 15 15 15 15
(15+15+15+…10)2=152=152+152+152+…10(\frac{15 + 15 + 15 + \dots}{10})^2 = 15^2 = \frac{15^2 + 15^2 + 15^2 + \dots}{10}

Ak jedno z rovnakých čísel zmenšíme o hh a druhé zväčšíme o hh, súčet sa nezmení, ale súčet ich štvorcov sa zväčší o 2h22h^2:
x2+x2x^2 + x^2
(x−h)2+(x+h)2=x2−2xh+h2+x2+2xh+h2(x-h)^2 + (x+h)^2 = x^2 - 2xh +h^2 + x^2 + 2xh + h^2
(x−1)2+(x+1)2=2x2+2h2(x-1)^2 + (x+1)^2 = 2 x^2 + 2h^2

Takže priemer (a tým pádom ani štvorec priemeru) sa nezmení, ale súčet (a tým pádom aj priemer) štvorcov sa zväčší.