\input ../lecnotes.tex

\def\E{{\bb E}}

\prednaska{4}{Prùmìrná èasová slo¾itost}{(zapsali R. Cinkais a R. Barczi)}

\h{První pomoc z~teorie pravdìpodobnosti}

\s{Definice:} {\I Diskrétní pravdìpodobnostní prostor} je uspoøádaná dvojice
$(\Omega,P)$, kde $\Omega$ je nejvý¹e spoèetná mno¾ina {\I elementárních jevù}
a $P:\Omega\rightarrow[0,1]$ je funkce, pro kterou platí:
$$\sum_{x\in\Omega}P(x)=1.$$
Hodnotám $P(x)$ budeme øíkat {\I pravdìpodobnosti} jednotlivých elementárních jevù.

\s{Pøíklad:} Mno¾ina elementárních jevù pøi vrhu kostkou je $\Omega=\{1,2,3,4,5,6\}$ a pokud je kostka spravedlivá, platí $\forall x\in\Omega:P(x)=1/6$.

\s{Definice:} {\I Jevem} $A$ rozumíme libovolnou mno¾inu $A\subseteq\Omega$. {\I Pravdìpodobnost}
jevu $A$ poèítáme jako: $$\Pr[A]=\sum_{a\in A}P(a).$$

\s{Pøíklad:}
Jaká je pravdìpodobnost slo¾eného jevu \uv{na kostce padne sudé èíslo}? Oznaèíme
$A=\{2,4,6\}\subseteq\Omega$. Hledanou pravdìpodobností je pak
$P(A)=1/6+1/6+1/6=1/2$.

\s{Definice:} {\I Náhodná promìnná} $X$ je funkce $X:\Omega\rightarrow{\bb
R}$. {\I Støední hodnotou} náhodné promìnné $X$ rozumíme výraz
$$\E{}X=\sum_{x\in\Omega}P(x)\cdot X(x).$$

\s{Pøíklad:} Nech» $H$ je náhodná promìnná pøiøazující vrhu kostkou dosa¾enou
hodnotu, tedy $\forall x\in\Omega:H(x)=x$. Støední (oèekávanou) hodnotou této
promìnné je $\E{}H= 1/6\cdot1 +1/6\cdot2 +1/6\cdot3 +1/6\cdot4 +1/6\cdot5
+1/6\cdot6=7/2$.

\s{Vìta:} ({\I Linearita støední hodnoty})
Nech» $A,B:\Omega\rightarrow\bb R$ jsou náhodné promìnné a $\alpha\in\bb R$ je libovolná konstanta. Potom:
\numlist\ndotted
\:$\E{}(A+B)=\E{}(A)+\E{}(B)$,
\:$\E{}(\alpha\cdot A)=\alpha\cdot\E{}(A)$.
\endlist

\proof
\numlist\ndotted
\:Podle definice støední hodnoty je:
$$\eqalign{
\E{}(A+B)&=\sum_{x\in\Omega}(A(x)+B(x))\cdot P(x)=\sum_{x\in\Omega}(A(x)\cdot P(x)+B(x)\cdot P(x))=\cr
         &=\sum_{x\in\Omega}A(x)\cdot P(x)+\sum_{x\in\Omega}B(x)\cdot P(x)=\E{}A+ \E{}B.
}$$
\:Opìt pøímo z definice støední hodnoty:
$$\E{}(\alpha\cdot A)=\sum_{x\in\Omega}\alpha\cdot A(x)\cdot P(x)=\alpha\cdot \sum_{x\in\Omega}A(x)\cdot P(x)=\alpha\cdot\E{}A.$$
\endlist
\qed

\s{Pøíklad:}
Házíme dvìmi odli¹nými hracími kostkami. Uva¾ovaný prostor elementárních jevù
je proto $\Omega=\{(1,1),(1,2),\dots, (6,5),(6,6)\}$ a $\forall
(a,b)\in\Omega:P((a,b))=1/36$. Mìjme náhodnou promìnnou $S$ pøiøazující vrhu
kostkami souèet dosa¾ených hodnot, tedy $\forall (a,b)\in\Omega:S((a,b))=a+b$.
Chceme urèit $\E{}S$.

Oznaème $A$ náhodnou promìnnou, která pøi vrhu kostkami vrací hodnotu na první
kostce, tedy $\forall (a,b)\in\Omega:A((a,b))=a$. Podobnì oznaème $B$ náhodnou
promìnnou, která vrací hodnotu na druhé kostce, tedy $\forall
(a,b)\in\Omega:B((a,b))=b$. V~pøedcházejícím pøíkladì jsme si ukázali, ¾e
$\E{}A=\E{}B=7/2$. Proto¾e $S((a,b))=a+b=A((a,b))+B((a,b))$, pou¾itím vìty
o linearitì støední hodnoty dostáváme $\E{}S=\E{}(A+B)=\E{}A+\E{}B=7/2+7/2=7$.

\s{Poznámka:}
Pro ka¾dou náhodnou promìnnou $Y$ platí: $$\E{}Y=\sum_{x\in{\bb R}}x\cdot\Pr[Y=x].$$
\proof
Uvedený vztah plyne okam¾itì z definice støední hodnoty, slouèíme-li dohromady v¹echny èleny $x\in\Omega$ se stejnou hodnotou $Y(x)$.
\qed

\s{Prùmìrná slo¾itost algoritmu}

Prùmìrnou slo¾itost algoritmu mù¾eme poèítat pøes v¹echny vstupy nebo pøes náhodné
volby vstupù. V prvním pøípadì je algoritmus pravdìpodobnostní (\uv{hází mincí}) a slo¾itost poèítáme jako prùmìr pøes v¹echny vstupy.
Ve druhém je zase algoritmus deterministický a zajímá nás pouze slo¾itost v nejhor¹ím pøípadì.
Pokud jde o koneèný výsledek, jsou oba uvedené zpùsoby ekvivalentní.

Na¹im cílem bude odvodit prùmìrnou slo¾itost algoritmu $\<Select>(k,X)$ z~minulé pøedná¹ky.
K~tomu si uká¾eme algoritmus slou¾ící k výbìru pivota pro $\<Select>(k,X)$ ($\<Select>(k,X)$ jej pøi svém bìhu
bude spou¹tìt jako podprogram). Bez újmy na~obecnosti pøedpokládejme,
¾e v¹echny prvky mno¾iny $X$ jsou navzájem rùzné.

\s{Algoritmus:} ({\I Hledání l¾imediánu v mno¾inì $X$})
\algo
\:Zvol náhodnì $x\in X$ (v¹echna~$x$ se stejnou pravdìpodobností).
\:Spoèítej $A=\vert \{y\in X:y<x\} \vert$ a $B=\vert\{y\in X: y>x\}\vert$.
\:Pokud $A\geq \vert X\vert/4$ a~zároveò $B\geq \vert X\vert/4$, vra» $x$, jinak skoè na~1.
\endalgo

\s{Pozorování:}
Uva¾ujme, ¾e házíme spravedlivou mincí. Aby nedo¹lo k ¾ádnému mezinárodnímu sporu, oznaème strany mince jako tuèòák ($T$) a ryba ($R$). Tedy pravdìpodobnost pádu na nìjakou stranu je $1/2$.
Budeme zkoumat, jaká je støední hodnota èekání na pád tuèòáka $\E{}T$. Mno¾inu v¹ech jevù (posloupností vrhù), které mohou nastat, oznaème jako $\Omega=\{T,RT,RRT,\dots,RRR\dots\}$. Platí:
$$\Pr[T]={1\over 2}, \Pr[RT]={1\over 4}, \Pr[R^{k}T]={1\over 2^{k+1}}, \Pr[RRR\dots]=\lim_{k\rightarrow\infty}{1\over 2^k}=0.$$
Podle pozorování máme: $$\E{}T=\sum_{k=1}^{\infty}k\cdot\underbrace{\Pr[T=k]}_{1\over 2^k}=\sum_{k=1}^{\infty}{k\over 2^k}.$$
Tuto sumu je v¹ak trochu obtí¾né spoèítat (kdo chce si to mù¾e zkusit), proto provedeme následující trik:
$$\E{}T=1+{1\over 2}\cdot0+{1\over 2}\cdot\E{}T,$$
to znamená, ¾e po jednom tahu jsme s polovièní pravdìpodobností vyhráli
a s polovièní pravdìpodobností se situace nezmìnila. Jednoduchou úpravou tedy
zjistíme, ¾e: $$\E{}T=2.$$

\s{Lemma:}
Èekání na jev, který nastane s pravdìpodobností $p$, trvá prùmìrnì $1/p$.

\proof
$\E{}T=1+(1-p)\E{}T$, tedy $\E{}T=1/p$.
\qed

Pøi hledání l¾imediánu máme polovièní ¹anci, ¾e se trefíme pøi náhodném výbìru
do prostøedních dvou ètvrtin -- prùmìrnì tedy vykonáme dva prùchody cyklem, pøièem¾
jeden prùchod trvá $\Theta(n)$. Celkem bude tedy hledání l¾imediánu trvat prùmìrnì
$\Theta(n)$.

\s{Vìta:}
\<Select> s~náhodnou volbou pivota má v prùmìru èasovou slo¾itost $\Theta(n)$.

\proof
Rozdìlíme algoritmus na {\I fáze} $\equiv$ posloupnosti iterací konèící dobrou
volbou pivota (jako l¾imedián). V¹imneme si, ¾e jedna fáze zmen¹í vstup na nejvý¹e ${3\over 4}\cdot n$
a~trvá v~prùmìru $\Theta(n)$ (prùmìrnì 2~iterace po $\Theta(n)$).
Tedy $\E{}T=\E{}T_1+\E{}T_2+{\dots}=\Theta(n)$, kde $\E{}T_i$ oznaèuje $i$-tou fázi.
\qed

\s{Vìta:}
\<Select> s~pivotem rovným prostøednímu prvku má v~prùmìru pøes permutace na vstupu èasovou slo¾itost $\Theta(n)$.

\proof
Uká¾eme, ¾e algoritmus s~pevnou volbou pivota se na~náhodném vstupu chová
stejnì, jako algoritmus s~náhodnou volbou pivota na~pevném vstupu, jeho¾
prùmìrnou slo¾itost odhaduje pøedchozí vìta.

Pokud je na~vstupu náhodná permutace~$\pi$, jsou v¹echny hodnoty pivota~$p$ stejnì pravdìpodobné.
Zbývá ukázat, ¾e dal¹í iterace algoritmu dostane na vstupu prvky vìt¹í nebo men¹í ne¾~$p$
opìt v~náhodném poøadí (s~rovnomìrným rozdìlením pravdìpodobností).
K~tomu sestrojíme bijekci mezi mno¾inou v¹ech permutací na~$\{1,\ldots,n\}$ a mno¾inou ètveøic $(m, L, \pi_M, \pi_V)$, kde:

\itemize\ibull
\:$p\in\{1,\ldots,n\}$ je prostøední prvek permutace~$\pi$ (pivot), tedy $\pi[l]$ le¾ící na~pozici $l=\lfloor {(1+n)/2} \rfloor$,
\:$L\in{{\{1,{\dots},l-1,l+1,{\dots},n\}} \choose {p-1}}$ je mno¾ina pozic, na~nich¾ jsou
  umístìny prvky men¹í ne¾~$p$ (ty, které ná¹ algoritmus umístí do~mno¾iny~$M$),
\:$\pi_M$ permutace na~$\{1,\ldots, p-1\}$ popisující poøadí men¹ích prvkù a
\:$\pi_V$ permutace na~$\{p+1,\ldots, n\}$, tedy poøadí vìt¹ích prvkù.
\endlist

Jakmile zvolíme~$p$, jsou volby~$L$, $\pi_M$ a $\pi_V$ navzájem nezávislé. Ka¾dé volbì~$\pi_M$
tedy odpovídá stejný poèet permutací~$\pi$, a~proto jsou v¹echny~$\pi_M$ stejnì pravdìpodobné.
Analogicky pro~$\pi_V$.

\qed

\bye
