\documentclass[10pt,a5paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[IL2]{fontenc}
\usepackage[margin=2cm]{geometry}

\usepackage[unicode]{hyperref}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

%\newtheoremstyle{plain}{\medskipamount}{\smallskipamount}{\itshape}{}{\bfseries}{.}{0.4em}{}
%\newtheoremstyle{definition}{\medskipamount}{\smallskipamount}{}{}{\bfseries}{.}{0.4em}{}

\newtheorem{veta}{Věta}
\newtheorem{lemma}[veta]{Lemma}
\newtheorem{tvrzeni}[veta]{Tvrzení}
\newtheorem{dusledek}[veta]{Důsledek}
\theoremstyle{definition}
\newtheorem*{definice}{Definice}
\newtheorem*{priklad}{Příklad}
\newtheorem*{fakt}{Fakt}

\setlength{\parindent}{0pt}
\setlength{\parskip}{3pt plus 1pt}

\def\eye{$\ooalign{\raise0.2ex\hbox{$\frown$}\cr$\kern0.25em\bullet$\cr\lower0.2ex\hbox{$\smile$}}$\;}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\E{\mathbb{E}}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\rng}{rng}
\def\faktor#1#2{{^{{#1}}\!/_{{#2}}}}
\def\newtopic{\medskip\hrule\medskip\goodbreak}
\let\eps\varepsilon

\usepackage{enumitem}

\setlist{itemsep=0pt,topsep=3pt plus 2pt minus 1pt}
\setlist[itemize]{label=$\bullet$}

\def\impl{\Rightarrow}
\def\rightimpl{\item[\uv{$\Rightarrow$}]}
\def\leftimpl{\item[\uv{$\Leftarrow$}]}
\def\O{\mathcal{O}}

\def\cc{\mathop{\mathrm{cc}}}
\def\odd{\mathop{\mathrm{odd}}}

\begin{document}

\paragraph{Přehled.}

\begin{definice}
\emph{Pravděpodobnostní prostor} je trojice $(\Omega,\sigma,p)$ kde:
\begin{itemize}
\item $\Omega$ je nosná množina,
\item $\Sigma \subseteq 2^\Omega$, která je $\sigma$-algebra splňující:
\begin{enumerate}
\item $\emptyset \in \Sigma$
\item Pokud $A \in \Sigma$, potom $\Omega \setminus A \in \Sigma$,
\item Pokud $A_i)_{i = 1}^\infty$, kde každá je v $\Sigma$, potom
$\bigcup_{i=1}^\infty \in \Sigma$ a
\end{enumerate}
\item $p$ je funkce $p: \Sigma \to [0, 1]$ splňující:
\begin{itemize}
\item $P[\emptyset] = 0$
\item $P[\Omega] = 1$
\item Pokud $(A_i)_{i = 0}^\infty$ jsou navzájem disjunktní množiny ze
$\Sigma$, potom $P[\bigcup_{i = 1}^\infty A_i] = \sum_{i = 1}^\infty P[A_i]$.
\end{itemize}
\end{itemize}
Prvky $\Sigma$ se nazývají \emph{jevy}, prvky $\Omega$ nazýváme
\emph{elementární jevy} a $p$ se nazývá \emph{pravděpodobnost} na $\Omega$.
\end{definice}


\begin{priklad}
Diskrétní konečný pravděpodobnostní prostor, ve kterém $\Omega$ je konečná
množina, $\Sigma = 2^\Omega$ a $p$ může být jednoznačně definovaná přes
elementární jevy, tedy $p: \Omega \to [0, 1]$, $\sum_{\omega \in \Omega}
p(\omega) = 1$, a tedy $P[A] = \sum_{\omega \in A}, P[\omega] = p(\{\omega\})$.

Rovnoměrný pravděpodobnostní prostor je diskrétní prostor, kde navíc $p(\omega) =
1/|\Omega|\;\forall \omega \in \Omega$.
\end{priklad}

\begin{priklad}
Nekonečný prostor -- $\Omega = [0, 1]^2$, $\Sigma$ je měřitelná podmnožina
$\Omega$. Potom $P[A]$ je obsah $A, (\lambda(A))$.

Příklad jevu v takovém prostoru je $A = [0, 1]^2 \setminus [0.1, 0.9]^2$.
\end{priklad}


\begin{lemma}
Nechť $A_1, A_2, \dots, A_k$ jsou náhodné jevy. Potom \hfil\break
$\sum_{i = 1}^k P[A_i] \geq P[\bigcup_{i = 1}^k A_i]$.
\end{lemma}
\begin{proof}
Uvažme $B_i := A_i \setminus (A_1 \cup A_2 \cup \dots \cup A_{i-1})$. Ty jsou
rovněž jevy. Tudíž $P[\bigcup_{i=1}^k A_i] = P[\bigcup_{i=1}^k B_i]$ (lze
dokázat indukcí přes rovnost jevů nalevo a vpravo).

Tuto pravděpodobnost dále upravíme na $\sum_{i=1}^k P[B_i] \leq \sum_{i=1}^k
P[A_i]$. To platí, protože $B \subseteq A \impl P[B] \leq P[A]$: $P[A] = P[B
\cup (A \setminus B)] = P[B] + P[A \setminus B] \geq P[B]$.
\end{proof}

\newtopic

\begin{definice}
Nechť $n \in \N, p \in [0, 1]$, potom definujeme $G(n, p)$ jako
pravděpodobnostní prostor \emph{náhodných grafů o~$n$ vrcholech
s~pravděpodobností hrany $p$} takový, že $\Omega$ je množina všech grafů o~$n$
vrcholech a pravděpodbnost grafu s právě $m$~hranami je $p^m (1-p)^{\binom n2 -
m}$.
\end{definice}

Intuitivně, chceme $m$~hran, ty získáme s~pravděpodobností $p^m$. Celkem hran
je $\binom n2$. Zbytek hran nechceme, proto vynásobíme pravděpodobnost $(1 -
p)^{\text{zb.}}$.


\paragraph{Aplikace.} Ramseyova věta a čísla:

$\forall k, l \in \N\,\exists N \in \N$, kde každý graf na alespoň
$N$~vrcholech obsahuje buď kliku velikosti~$k$ nebo nezávislou množinu
velikosti~$l$. Nejmenší takové $N$ nazýváme Ramseyovým číslem $R(k, l)$.

Z dřívějška jsme dokázali, že $R(k, k) \leq \binom{2k}k \leq 4^k$.
Ukážeme i~dolní odhad:

\begin{veta}
$R(k, k) \geq 2^{k/2}$.
\end{veta}
\begin{proof}
Pokud $n \leq 2^{k/2}$, chceme najít graf neobsahující kliku ani nezávislou
množinu velikosti~$k$.

Uvažujme náhodný graf $G = G(n, 1/2)$. Pravděpodobnost, že $G$~obsahuje kliku
velikosti~$k$ je nejvýše $p_k = \binom nk 2^{- \binom k2}$ (přes
pravděpodobnosti sjednocení). Pravděpodobnost, že
graf obsahuje nezávislou množinu velikosti~$k$ je taktéž nejvýše $p_k$.

Pravděpodobnost, že nastane jedno z toho je proto nejvýše $2p_k \leq n^k/k!
\cdot 2^{k^2/2 + k/2 + 1}$. Za~$n$ dosaďme $2^{k/2}$. Dostáváme $\leq 2^{k^2/2
- k^2/2 + k/2 + 1 - k + 1} = 2^{-k/2 + 2 < 2^0 = 1}$, jestliže $k \geq 5$.

Pravděpodobnost opačného jevu je proto větší, než 0. Tudíž pro $k \geq 5$
pravděpodobnost grafu bez kliky nebo nezávislé množiny velikosti~$k$ je
nenulová a takový graf existuje. Pro $k \leq 4$ lze ukázat jinak.
\end{proof}

\newtopic

\paragraph{Odhady pro faktoriál a binomické koeficienty.}
\begin{itemize}
\item Existuje zjevný odhad $\left(\frac n2\right)^{n/2} \leq n! \leq n^n$.

Přesnější odhad říká $\left(\frac ne \right)^n \leq n! \leq e \cdot n \cdot
\left(\frac ne\right)^n$.

Stirlingova formule říká, že $n! \approx \sqrt{2 \pi n} \left(\frac ne
\right)^n$.

\item Pro binomy máme jednoduchý odhad $\left(\frac nk \right)^k \leq \binom nk \leq \frac
{n^k}{k!} \leq n^k$.

Přesnější odhad říká $\binom nk \leq \left( \frac{en}k \right)^k$.

Pro střední binom máme ještě lepší odhad: $\frac{2^{2m}}{2\sqrt m} \leq
\binom {2m}m \leq \frac{2^{2m}}{\sqrt{2m}}$.

\item Víme, že $1 + x \leq e^x$, což je ekvivalentní s $1 + x - e^x \leq 0$. To
lze dokázat zderivováním levé strany, čímž dostaneme $1 - e^x$, dosazení $x$
nikdy neporuší.

To můžeme využít na odhad $(1-p)^m \leq e^{-pm}$.
\end{itemize}

\newtopic

\begin{definice}
Řekněme, že dva jevy $A, B$ jsou nezávislé, jestliže $P[A \cap B] = P[A] \cdot
P[B]$.

Obecněji, $A_1,\dots,A_k$ jsou nezávislé, jestliže pro každé $I \subseteq [k]$
platí $P[\bigcup_{i \in I} A_i] = \prod_{i \in I} P[A_i]$.
\end{definice}

\begin{definice}
Nechť $A, B$ jsou jevy. Potom \emph{podmíněná pravděpodobnost $A$ za předpokladu $B$} je definovaná jako
$$ P[A | B] = \frac{P[A \cap B]}{P[B]}. $$
\end{definice}

Pokud jsou jevy $A, B$ nezávislé, potom $P[A | B] = P[A]$.

\newtopic

Mějme booleovské proměnné $x_1,x_2,\dots,x_n$.

\emph{Literál} je proměnná $x_i$ nebo
její negace $\neg x_i$.

\emph{Klauzule} je formule ve formě $(_1 \vee l_2 \vee \dots l_k)$,
kde $l_i$ jsou literály. 

\emph{CNF-Formule} je formule $c_1 \wedge c_2 \wedge \dots \wedge c_m$, kde $c_i$
jsou klauzule.

Formule je \emph{splnitelná}, pokud existuje ohodnocení proměnných takové, že
se formule vyhodnotí pravdivě.

\begin{priklad}
Formule $(\neg x_1) \wedge (x_1 \vee x_2 \vee x_4) \wedge (\neg x_2 \vee x_3)$
je splnitelná, například pro ohodnocení $(x_1,x_2,x_3,x_4) = (0,1,1,1)$.
\end{priklad}

\paragraph{SAT problém} Je daná CNF-formule $\Phi$ splnitelná? Tento problém je
NP-težký.

\begin{tvrzeni}
Nechť $\Phi$ je CNF-formule s $m$ klauzulemi taková, že každá klauzule obsahuje
$k$ různých literálů. Pokud $m \leq 2^k$, potom $\Phi$ je splnitelná.
\end{tvrzeni}

\begin{proof}
Uvažujme náhodné ohodnocení, kde každá $x_i = 1$ s pravděpodobností $1/2$
nezávisle na ostatních proměnných.

Uvažujme klauzuli $c_i$, potom $c_i$ je splněná s~pravděpodobností alespoň $1 -
2^{-k}$: Pokud se v~$c_i$ nachází literál $x_j$ i $\neg x_j$, potom
pravděpodobnost je jistě 1. V~opačném případě, aby klauzule byla nesplnitelná,
musí být každý literál ohodnocen opačně, nastavení je nezávislé.

Pravděpodobnost, že existuje nesplněná klauzule je nejvýše $m 2^{-k}$ podle
Union bound. dle předpokladu $m 2^{-k} < 1$. Pravděpodobnost, že je formule
splnitelná, je tedy větší, než 0.
\end{proof}

\newtopic

\paragraph{Erd\"os-ko-Radova věta.}

\begin{definice}
Rodina množin $\cal F$ je \emph{protinající se}, pokud $A \cap B \neq
\emptyset$ pro každé $A, B \in \cal F$.
\end{definice}

Jaká je maximální protínající se rodina množin velikosti $k$ nad množinou
velikosti $n$?

Nechť $k \leq n/2$. Když zafixujeme jeden prvek, dostáváme rodinu velikosti
$\binom{n-1}{k-1}$.

\begin{veta}
Nechť $n, k$ jsou přirozená čísla taková, že $k \leq n/2$. Potom maximální
velikost protinájící se rodiny $k$-množin nad $n$-prvkovou množinou je právě
$\binom{n-1}{k-1}$.
\end{veta}

\begin{lemma}
Uvažujme množinu $X = \{0,1,\dots,n-1\}$ se sčítáním modulo $n$, definujeme
$A_s = \{s,s+1,\dots,s+k-1\}$ pro $s \in X$. Pokud $\cal F$ je protinající se
rodina $k$-prvkových podmnožin $X$, potom $\cal F$ obsahuje nejvýše $k$ množin
$A_s$.
\end{lemma}

\begin{proof}
Pro nějaké $s$ mějme $A_s \in \cal F$. Množiny protínající $A_s$ jsou mimo jiné
$A_{s-k+1}, \dots, A_{s-1}, A_{s+1}, \dots, A_{s+k-1}$.

Pro páry $A_t, A_{t+k}$, kde $t \in \{s-k+1,\dots,s-1\}$, pouze jedna z~množin
může být ve $\cal F$. To dává celkem nejvýše $k$ množin $A_s$.
\end{proof}

\begin{proof}[Důkaz věty.]
Nechť $X$ je $n$-prvková množina z~předpokladu. BÚNO $X = \{0, \dots,
n-1\}$ se sčítáním modulo $n$.

Pro permutaci $\sigma$ množiny $X$ a $s \in X$ mějme $A_{\sigma, s} =
\{\sigma(s), \sigma(s+1),\allowbreak \dots, \sigma{s + k - 1}\}$. Uvažujme $\sigma, s$,
kde $\sigma$ je náhodná permutace zvolena uniformně a $s$ je náhodně zvolený
prvek $X$, taktéž uniformně. Chceme odhadnout $P[A_{\sigma,s} \in \cal F]$.

Dle lemmatu $P[A_{\sigma,s} \in {\cal F}] \leq k/n$ (volíme $\sigma$, pak $s$).
Na druhou stranu $P[A_{\sigma,s} \in {\cal F}] = |{\cal F}|/\binom nk$ (volíme
$s$, pak $\sigma$).

Tudíž $|{\cal F}| = P[A_{\sigma,s} \in {\cal F}] \binom nk \leq \frac nk \binom
nk = \binom{n-1}{k-1}$.
\end{proof}

\newtopic

\begin{definice}
Nechť $(\Omega,\Sigma,P)$ je pravděpodobnostní prostor. Potom \emph{náhodná
veličina} je měřitelná funkce $X: \Omega \to \R$.
\end{definice}

Měřitelná funkce splňuje $X^{-1}([a,\infty]) \in \Sigma)$.

Zavedeme si ještě zkratku $P[X = a] = P[\{\omega \mid X(\omega) = a\}]$. Podobně
pro $P[X \leq a]$ a další relační operátory.

\begin{definice}
\emph{Střední hodnota} náhodné veličiny $X$ je definovaná jako výraz
$\E[X] = \int_{\Omega} X(\omega) dP(\omega)$ (obecně).

Pro konečný prostor: $\E[X] = \sum_{\omega \in \Omega} X(\omega)
p(\omega) = \sum_{a \in X(\Omega)} a P[X = a]$.
\end{definice}

\begin{lemma}[Linearita střední hodnoty]
Nechť $X_1, X_2$ jsou náhodné veličiny a $\alpha,\beta \in \R$. Potom
$\E[\alpha X_1 + \beta X_2] = \alpha\E[X_1] + \beta\E[X_2]$.
\end{lemma}

\begin{proof}
(pouze pro konečné prostory) $\E[\alpha X_1 + \beta X_2] =
\sum_{\omega\in\Omega} (\alpha X_1(\omega) + \beta X_2(\omega))p(\omega) =
\alpha \sum_{\omega \in \Omega} X_1(\omega)p(\omega) + 
\beta  \sum_{\omega \in \Omega} X_2(\omega)p(\omega)$.
\end{proof}

\begin{definice}
Řekneme, že dvě náhodné veličiny $X,Y$ jsou nezávislé, pokud $P[X \in A \wedge
Y \in B] = P[X \in A]P[Y \in B]$ pro každé $A, B$ měřitelné podmnožiny $\R$.
\end{definice}

Je postačující zkontrolovat, že $P[X \leq a \wedge Y \leq b] = P[X \leq a]P[Y
\leq b]$ pro libovolné $a, b \in \R$.

\begin{tvrzeni}
Nechť $X, Y$ jsou nezávislé náhodné veličiny. Potom platí $\E[XY] = \E[X]\E[Y]$.
\end{tvrzeni}

\begin{proof}
$\E[XY] = \sum_{c \in XY(\Omega)} c \cdot P[XY = c] = \sum_{a \in X(\Omega), y
\in Y(\Omega)} ab \cdot P[X=a \wedge Y=b] = \sum ab \cdot P[X = a]P[Y = b]$. To
můžeme rozdělit na dvě sumy, dostaneme definice $\E[X]\E[Y]$.
\end{proof}

Nechť $A$ je náhodný jev. Indikátor $I_A$ je náhodná veličina definovaná jako $I_A(x) =
|\{x\} \cap A|$. Potom $\E[I_A] = P[A]$.

\paragraph{Očekávaný počet fixních bodů v náhodné permutaci.} Uvažujme náhodnou
permutaci $\sigma \in S_n$ a jevy $A_i$, že $i$ je fixní bod. Vidíme, že
$\E[I_{A_i}] = P[A_i] = 1/n$. Tedy střední hodnota počtu fixních bodů je $n
\cdot \E[I_{A_n}] = 1$.

\paragraph{Hamiltonovské cesty v turnajích.}

\begin{definice}
Turnaj je orientovaný úplný graf.
\end{definice}

Každý turnaj obsahuje orientovanou Hamiltonovskou cestu. Existuje turnaj s
právě jednou; stačí uvažovat lineární uspořádání jako graf. Můžeme mít vysoké
množství cest?

\begin{veta}[Szele]
Pro každé $n$ existuje turnaj na $n$ vrcholech obsahující alespoň $n!/2^{n-1}$
orientovaných hamiltonovských cest.
\end{veta}

\begin{proof}
Postavíme turnaj $T$ na $n$ vrcholech tak, že zvolíme orientaci každé hrany
náhodně rovnoměrně a nezávisle. Spočítáme střední hodnotu počtu OHC.

Zvolme $\sigma$ jako permutaci $V(T)$. Uvažujme jev $A_\sigma$, že $\sigma$
indikuje OHC. Potřebujeme, aby každá hrana byla orientovaná každým směrem. Tedy
$P[A_\sigma] = 1/2^{n-1}$.

Nechť $X$ je počet OHC, potom $\E[X] = \sum_\sigma \E[I_{A_\sigma}] =
n!/2^{n-1}$. To tedy znamená, že existuje hledaný turnaj.
\end{proof}

\paragraph{MAXSAT problém.}

Máme $\Phi$ booleovskou funkci v CNF. Kolik klauzulí může být splněno zároveň
pro dané ohodnocení?

\begin{tvrzeni}
Nechť $\Phi$ je BF v CNF taková, že každá klauzule obsahuje $k$ různých
literálů. Potom alespoň $\frac{2^k - 1}{2^k} \cdot m$ klauzulí může být
splněno, kde $m$ je počet klauzulí.
\end{tvrzeni}

\begin{proof}
Každou proměnnou $\Phi$ nastavíme na 0 nebo 1 náhodně uniformně nezávisle.
Mějme klauzuli $C$. Pak $P[C = 1] \geq \frac{2^{k-1}}{2^k}$. Pak díky
indikátorům
$\E[\text{počet splněných klauzulí}] \geq m \cdot \frac{2^{k-1}}{2^k}$.
\end{proof}

Ukážeme derandomizovaný algoritmus (zhruba), jak toto ohodnocení najít:

Nechť $x_1,\dots,x_n$ jsou proměnné. Předpokládejme, že jsme nastavili
$x_1,\dots,x_i$ a chceme nastavit $x_{i+1}$. Pro $\Phi$ mějme $\Phi'$ takovou,
kde zahodíme splněné klauzule a odstraníme literály patřící $x_1,\dots,x_i$ ze
zbylých klauzulí.

Dále porovnáme $\E[|C=1| \mid x_{i+1} = 1]$ a $\E[\dots \mid x_{i+1} = 0]$ a
zvolíme lepší hodnotu. Toto funguje, jelikož $\E[I_A] = 1/2(\E[I_{A \mid B}] +
\E[I_{A \mid B^C}])$ pro $P[B] = 1/2$.

\paragraph{MAX-CUT problém.}

Máme graf $G$ a chceme znát velikost nejmenšího řezu.

\begin{tvrzeni}
Nechť $G$ je graf s $m$ hranami. Pak obsahuje řez obsahujcí alespoň $m/2$ hran.
\end{tvrzeni}

\begin{proof}
Pro každý vrchol $v \in V(G)$ se rozhodneme, zda jej vložíme do $A$ nebo $B$
uniformně náhodně nezávisle. Tím dostaneme žez $C(A, B)$.

Tudíž $P[e \in C(A, B)] = 1/2$, protože $e = \{u, v\}$, máme 4 možnosti, v
jakých množinách se nacházejí $u, v$ a právě 2 z nich implikují, že $e \in
C(A,B)$.

Nyní sečtením indikátoru dostaneme střední počet hran v řezu.
\end{proof}

Tím dostáváme náhodný algoritmus, který nalezne řez o alespoň $m/2$ hranách s
nenulovou pravděpodobností. Ukážeme však derandomizaci:

Budeme stavět $A, B$ postupně. Zvolme nějakou hranu a rozdělme její koncové
vrcholy do $A$ a $B$. V každém kroku zvolme vrchol $v$, který ještě nemá
přidělení.

Protože chceme maximalizovat počet hran v řezu, podíváme se na počet
hran vycházjící z $v$ do $A$ i do $B$ a zvolíme tu množinu, pro kterou je tento
počet menší. V každém kroku proto přibyde alespoň polovina hran do řezu.

\paragraph{Vyvážené vektory.} Nechť $v_1,\dots,v_n$ jsou jednotkové vektory v
$\R^n$. Chceme najít $\eps_1,\dots,\eps_n \in \{-1,1\}$ tak, že $\| \eps_1
v_1 + \dots \eps_n v_n \|$ je co největší (nejmenší).

\begin{tvrzeni}
Nechť $v_1,\dots,v_n \in \R^n, \|v_i\| = 1$ pro $i \in [n]$. Pak:
\begin{enumerate}
\item Existuje $\eps_1,\dots,\eps_n \in \{-1,1\}$ tak, že $\| \eps_1
v_1 + \dots \eps_n v_n \| \geq \sqrt{n}$,
\item Existuje $\eps_1,\dots,\eps_n \in \{-1,1\}$ tak, že $\| \eps_1
v_1 + \dots \eps_n v_n \| \leq \sqrt{n}$.
\end{enumerate}
\end{tvrzeni}

Odhady jsou nejlepší možné, stačí uvažovat ortonormální bázi.

\begin{proof}
Zvolme $\eps_1,\dots,\eps_n$ uniformně náhodně nezávisle. Nechť $X = \| \eps_1
v_1 + \dots + \eps_n v_n \|^2 = \langle \dots, \dots \rangle$.
Pak $\E[X] = \E[\sum_{i,j = 1}^n \eps_i \eps_j \langle v_i, v_j \rangle] =
\sum_{i,j=1}^n \E[\eps_i\eps_j] \langle v_i, v_j \rangle$.

Uvažujme $\E[\eps_i\eps_j]$. Pokud $i=1$, je to přesně $\E[1] = 1$. Jinak
můžeme použít nezávislost a linearitu součinu, dostáváme $\E[\eps_i]\E[\eps_j]
= 0$. Proto $\E[X] = \sum_{i=1}^n \langle v_i, v_i \rangle = n$. Z toho již
vyplývá tvrzení.
\end{proof}

\newtopic

\paragraph{Metoda alterace}

\begin{veta}[Slabá Turánova]
Nechť $G$ je graf s $n$ vrcholy a $m$ hranami. Nechť $d = 2m/n$ je jeho
průměrný stupeň. Pak $\alpha(g) \geq n/2d$.
\end{veta}

\begin{proof}
Zvolme $S \subseteq V(G)$ náhodnou podmnožinu $V(G)$. Každý vrchol vložíme do
$S$ s pravděpodobností $p$, nezávisle.

Mějme $X$ náhodnou veličinu označující počet vrcholů. Očividně $\E[X] = pn$.
Dále $Y$ je počet hran v grafu indukovaném $S$. Hranu budeme počítat pouze,
když každý koncový vrchol je v $S$. Tudíž $\E[Y] = p^2 m$. 

Nyní $\E[X - Y] = pn-p^2 m = pn(1-pd/2)$. Když zvolíme $p = 1/d$, dostáváme
$\E[X-Y] = 1/d \cdot n \cdot 1/2 = n/2d$. Tedy existuje $S$ taková, kde $X - Y
\geq n/2d$. Pro každou hranu $S$ odstraníme jeden koncový vrchol z $S$. Tím
dostaneme nezávislou množinu správné velikosti.
\end{proof}

\newtopic

\begin{lemma}[Markovova nerovnost]
Nechť $X$ je nezáporná náhodná veličina, $a > 0$. Pak $P[X \geq a] \leq
\E[X]/a$.
\end{lemma}

\begin{proof}
Ekvivalentně $\E[X] \geq P[X \geq a] \cdot a$. Protože $X$ je nezáporná,
nerovnost je platná přímo z definice střední hodnoty.
\end{proof}

\paragraph{Grafy s vysokým [girth] a vysokým barevným číslem.}

Nechť $G$ je graf. Potom $g(G)$ (girth) je délka nejkratšího cyklu v $G$. Pokud
$G$ je les, $g(G) = \infty$.

Graf s vysokým [girth] se lokálně chová jako strom. Avšak\dots{}

\begin{veta}[Erd\"os]
Pro každé kladné celé čísla $k, l$ existuje graf $G$, pro který $g(G) > l,
\xi(G) > k$.
\end{veta}

\begin{proof}
Nechť $G' = G(n, p)$. Nastavíme $p = n^{\eps - 1} = n^{1/(1-\eps)}$,
kde $\eps = 1/2l$.

Uvažujme počet $i$-cyklů v $K_n$ pro $i \in 3,\dots,l$. To je $\binom ni \cdot
i! \cdot 1/2i \leq n^i$. Zvolme veličinu $X$ říkající počet cyklů délky nejvýše
$l$ ve grafu $G'$. Pak $\E[X] \leq \sum_{i=3}^l n^i p^i = \sum_{i=3}^l
n^{\eps i} \leq l \cdot n^{1/2l \cdot l} = l \in o(n)$.

Pokud $n$ je dostatečně velké, pak $\E[X] \leq n/4$. Dle Markovovy nerovnosti
$P[X \geq n/2] \leq 1/2$.

Nyní se přesuňme k barevnému číslu. Nechť $a = \lceil 3/p \cdot \log n \rceil +
1$. Pak pro dostatečně vysoké $n$ platí $3/p \log n \leq a-1 \leq 4/p \log n$.
Uvažujme $\alpha$ velikost nezávislé množiny $G'$. Pak $P[\alpha \geq a] \leq
\binom na (1-p)^{a(a-1)/2} \leq n^a e^{pa(a-1)/2}$. Díky volbě $a$ můžeme
pravděpodobnost odhadnout shora $n^a \cdot n^{-3a/2} = n^{-a/2} \to 0$.

Pokud $n$ je dostatečně velké, pak $P[\alpha \geq a] < 1/2$. Celkově obrácením
$P[X < n/2 \wedge \alpha < a] > 0$. Tudíž existuje $G'$ s méně, než $n/2$ cykly
délky nejvýše $l$. Z každého cyklu délky $\leq l$ odstraňme jeden vrchol.

Dostáváme graf $G$, kde $|V(G)| \geq n/2$ a $\alpha(G) \leq a - 1$, díky
odstranění vrcholů $g(G) > l$. Zbývá odhadnout $\xi(G) \geq |V(G)|/\alpha(G)
\geq \frac{n/2}{4 \log n/p} = \frac{np}{8\log n} = \frac{n^\eps}{\log n} \to
\infty$. Pro každé $k$ existuje $n$, kde $\xi(G) > k$.
\end{proof}

\newtopic

\begin{veta}[Bayesova]
Nechť $A, B_1, \dots, B_n$ jsou neprázdné náhodné jevy prostoru $(\Omega,
\Sigma, P)$, kde $B_1,\dots,B_n$ tvoří disjunktní pokrytí $\Omega$. Pak $P[B_i
\mid A] = \frac{P[A \mid B_i]P[B_i]}{\sum_{j=1}^n P[A \mid B_j] P[B_j]}$.
\end{veta}

\eye $\sum_{j=1}^n P[A \mid B_j] P[B_j] = P[A]$. To platí, protože z definice
platí $P[A \mid B] = P[A \cap B]/P[B]$. Tudíž $P[A] = \sum_{j=1}^n P[A \cap
B_i]$.

\begin{proof}
$\frac{P[A \mid B_i] P[B_i]}{\sum P[A \mid B_j]P[B_j]} = \frac{P[A \cap
B_i]}{P[A]} = P[B_i \mid A]$.
\end{proof}

\paragraph{Testování násobení matic.} Nechť máme na vstupu $n \times n$ matice
$A, B, C$. Platí, že $C = AB$? Chtěli bychom to spočítat rychleji, než prostým
vynásobením $A$ a $B$, nejrychleji to zatím umíme v čase $\Omega(n^{2.37})$.

Ukážeme však algoritmus pracující v čase $\O(n^2 \cdot k)$, kde $k$ je parametr.
Může však zahlásit chybně s pravděpodobností nejvýše $2^{-k}$.

Uvažujme náhodný vektor $r = (r_1,\dots,r_n)^T$, kde $r_i \in \{0,1\}$
nezávisle. Pak spočítáme $A(Br)$ a porovnáme s $Cr$. Vynásobení matice s
vektorem umíme v $\O(n^2)$.

Nechť $D = AB-C$, speciálně $Dr = ABr-Cr$. Pokud $ABr \neq Cr$, pak jistě $AB
\neq C$. Chceme, aby $ABr \neq Cr$, jestliže $AB \neq C$ s pravděpodobností
alespoň $1/2$. Potom můžeme $r$ vygenerovat $k$-krát nezávisle, tím
pravděpodobnost $ABr = Cr, AB \neq C$ klesne na $2^{-k}$.

$AB \neq C \leftrightarrow D \neq 0$. Chceme odhadnout $P[Dr \neq 0]$. Víme, že
$\exists i, j: d_{ij} \neq 0$. Pak $v_i = \sum_{k=1}^n d_{ik} r_k = d_{ij} +
r_j + \sum_{k \neq j} d_{ik}r_k$. Sumu nazvěme $y$, jedná se o náhodnou
veličinu.

$P[v_i = 0] = P[v_i = 0 \mid y = 0]P[y = 0] + P[v_i = 0
\mid y \neq 0]P[y \neq 0]$. Pokud $y = 0$, potom $r_i$ musí být 0. Podobně,
pokud $y \neq 0$, $r_i$ nesmí být $0$. Tedy $P[v_i = 0] \leq 1/2(P[y = 0]+P[y
\neq 0]) = 1/2$.
Tudíž $P[Dr = 0] \leq 1/2$.

\newtopic

Chceme rozmístit $n$ bodů do $[0,1]^2$ tak, abychom nedostali žádný trojúhelník
s malým obsahem.

\begin{tvrzeni}
Pro každé (dostatečně vysoké) $n$ existuje $n$ bodů v $[0,1]^2$ takových, že
každá trojice tvoří trojúhelník s obsahem alespoň $\frac{1}{101n^2}$.
\end{tvrzeni}

S mnohem komplikovanějším argumentem lze získat $c \log n/n^2$.

\begin{proof}
Uvažujme $2n$ náhodných bodů v $[0,1]^2$ nezávisle. Zvolme tři náhodné
body $Q,R,S$, pak $\lambda(QRS)$ bude obsah trojúhelníku daného QRS. Chceme
odhadnout $P[\lambda \leq \eps]$ pro nějaké $\eps$ (rovno výrazu v~tvrzení).

Uvažujme $w = |QR|$, parametr $\Delta > 0$ a událost $B_i: w \in
((i-1)\Delta,i\Delta)$. Pak $P[\lambda \leq \eps] = \sum_{i\Delta < \sqrt 2}
P[\lambda \leq \eps \mid B_i] P[B_i]$.

Nejprve odhadneme $B_i$: aby $w$ bylo v daném intervalu, $R$ se musí nacházet v
mezikruží se středem v $Q$. Proto $P[B_i] \leq \pi(i^2\Delta^2 -
(i-1)^2\Delta^2) = \pi(2i-1)\Delta^2$. Nyní můžeme odnadnout podmíněnou
pravděpodobnost: Protože známe polohy $Q,R$, bod $S$ musí být na dostatečně
blizké rovnoběžce $QR$, konkrétně nejvýše $2\eps/w$ (dostáváme pás). Navíc
délka vzniklého pásu je nejvýše $\sqrt 2$. Tedy $O[\lambda \leq \eps \mid B_i]
\leq 4\eps/(i-1)\Delta \cdot \sqrt{2}$.

$P[\lambda \leq \eps] = P[\lambda \leq \eps \mid B_1] \cdot \pi\Delta^2 +
\sum_{i=2}^{\lfloor \sqrt{2}/\Delta \rfloor} \pi(2i-1)\Delta^2 \cdot
\frac{4\eps\sqrt{2}}{(i-1)\Delta} \leq \pi\Delta^2 + 24 \pi \eps$. Pokud
limitně zvolíme $\Delta \to 0$, pak $P[\lambda \leq \eps] \leq 24\pi\eps$.

Vygenerujeme náhodně $2n$ bodů v $[0,1]^2$. Nechť $X$ je počet trojúhelníků s
obsahem nejvýše $\eps$. Pak pro $\eps = 101n^2$: $\E[X] \leq \binom{2n}3
\frac{24\pi}{101n^2} \leq \frac{8 n^3 24\pi}{6 \cdot 101n^2} \leq n$. Stačí
odstranit bod z každého trojúhelníku obsahu menšího $\eps$, dostáváme alespoň
$n$ bodů z věty.
\end{proof}

\newtopic

\begin{definice}
Nechť $X$ je náhodná veličina, pak \emph{rozptyl} $X$ je definován jako
$\Var[X] = \E[(X-\E[X])^2] = \E[X^2] - \E^2[X]$.
\end{definice}

Směrodatná odchylka $\sigma = \sqrt{\Var[X]}$ je $\E[|X-\E[X]|]$, bohužel kvůli
absolutní hodnotě s ní není jednoduché pracovat.

\begin{definice}
Nechť $X, Y$ jsou dvě náhodné veličiny. Pak \emph{kovariance} $X$ a~$Y$ je
 $\Cov[X,Y] = \E[(X-\E[X])(Y-\E[Y])] = \E[XY] - \E[X]\E[Y]$.
\end{definice}

Pokud $X, Y$ jsou nezávislé, pak $\Cov[X,Y] = 0$.

\begin{lemma}
Nechť $X_1,X_2,\dots,X_m$ jsou náhodné veličiny. Pak platí $\Var[\sum_{i=1}^n X_i] =
\sum_{i=1}^n \Var[X_i] + \sum_{i \neq j} \Cov[X_i,X_j] = \sum_{i,j}
\Cov[X_i,X_j]$.
\end{lemma}

\begin{proof}
Úpravami: $\Var[\sum_{i=1}^n X_i] = \E[(\sum_{i=1}^n X_i)^2] -
\E^2[\sum_{i=1}^n X_i] = \E[\sum_{i,j=1}^n X_iX_j] - (\sum_{i=1}^n \E[X_i])^2 =
\dots$
\end{proof}

\begin{lemma}[Čebyšeova nerovnost]
Nechť $X$ je náhodná veličina a parametr $t > 0$. Pak $P[|X - \E[X]| \geq t]
\leq \frac{\Var[X]}{t^2}$.
\end{lemma}

\begin{proof}
Nechť $Y = (X-\E[X])^2$. Pak dle markovovy nerovnosti $P[Y \geq t^2] \leq
\frac{\E[Y]}{t^2} = \frac{\Var[X]}{t^2}$. Avšak to je též $P[\sqrt{Y} \geq t]$.
\end{proof}

\paragraph{Odhad středního binomického koeficientu.}

Mějme binom $\binom {2m}m$. Je dobře známo, že je
$\theta(\frac{4^m}{\sqrt{m}})$. Ukážeme nerovnost $\binom{2m}m \geq
\frac{4^m}{4\sqrt{m}+2}$.

\begin{proof}
Uvažujme $2m$ náhodných veličin $X_1,\dots,X_{2m}$, které jsou nezávislé a
nabírají hodnot 0 nebo 1 s pravděpodobností $1/2$. Nechť $X$ je jejich součet.
Pak $\E[X] = m$ a $\Var[X] = m/2$.

Použijeme čebyšeovu nerovnost, $P[|X - \E[X]| \geq \sqrt{m}] \leq (m/2)/\sqrt
m^2 = 1/2$. Pak taktéž $P[|X-\E[X]| < \sqrt{m}] \geq 1/2$. Uvažujme parametr
$k: |k| < \sqrt{m}$. Potom $P[X = m+k] = \binom{2m}{m+k} \cdot 1/2^{2m} \leq
\binom {2m}m 1/2^{2m}$.

Tudíž $1/2 \leq P[|X-\E[X]| < \sqrt{m}] =
\sum_{k=-\lfloor\sqrt{m}\rfloor}^{\lfloor\sqrt{m}\rfloor} P[X = m+k] \leq
(2\sqrt{m}+1) \binom{2m}m 1/4^m$. Úpravou nerovnice již dostaneme výsledek.
\end{proof}

\paragraph{Práhové funkce.}

Uvažujme parametr $p \in [0,1]$, k němu graf $G(n,p)$ a náhodnou veličinu $X$
značící počet trojúhelníků v $G$. Pak $\E[X] = \binom n3 p^3 \in \Theta(n^3p^3)$.
V závislosti na $p$, dostaneme alespoň $1$ trojúhelník v $G(n,p)$?

První případ: $p = o(1/n)$. Pak $\E[X] \to 0$, a tedy $P[X \geq 1] \to 0$.

Druhý případ: $p = \omega(1/n)$. Pak $\E[X] \to \infty$. Platí ale, že $P[X
\geq 1] \to 1$?

\begin{definice}
Říkáme, že grafová vlastnost $\cal P$ je monotónní, pokud pro každý pár grafů
$G,H$, kde $H$ je podgraf $G$ platí: Pokud $H$ splňuje vlastnost $\cal P$, pak
$G$ ji splňuje taky.
\end{definice}

Funkci $r: \N \to [0,1]$ nazveme práhovou funkci pro monotónní grafovou
vlastnost $\cal P$, pokud platí:

\begin{enumerate}
\item Pokud $p(n) = o(r(m))$, pak $\lim P[G(n,p(n))\text{ splňuje } {\cal P}] = 0$.
\item Pokud $p(n) = \omega(r(m))$, pak $\lim P[G(n,p(n))\text{ splňuje } {\cal P}] = 1$.
\end{enumerate}

\begin{veta}
Funkce $1/n$ je práhovou funkcí pro obsažení trojúhelníku.
\end{veta}

\begin{lemma}
Nechť $X_1,X_2,\dots$ je posloupnost nezáporných náhodných veličin takových, že
$\lim_{n \to \infty} \frac{\Var[X_n]}{\E^2[X_n]} = 0$. Pak $\lim_{n \to \infty}
P[X_n > 0] = 1$.
\end{lemma}

\begin{proof}
$P[|X_n - \E[X_n]| \geq \E[X_n]] \leq \frac{\Var[X_n]}{\E^2[X_n]}$ dle
Čebyšeovy nerovnosti. Taktéž $P[X_n = 0] \leq \frac{\Var[X_n]}{\E^2[X_n]}$.
Proto $\lim_{n \to \infty} P[X_n = 0] \leq \lim_{n \to \infty}
\frac{\Var[X_n]}{\E^2[X_n]} = 0$. To je opačná událost k $P[X_n > 0]$.
\end{proof}

\begin{proof}[Důkaz věty.]
Pro $p \in o(1/n)$ jsme již dokázali, ukážeme pro $p \in \omega(1/n)$.
Nechť $T_i$ je indikátor pro $G(n,k)$ obsahující $i$-tý trojúhelník. Pak $T =
\sum T_i = \Theta(n^3p^3)$ je počet trojúhelníků.

Rozptyl $\Var[T] = \sum_{i,j} \Cov[T_i,T_j]$. Pokud trojúhelníky $i,j$ nesdílí
hranu, pak jejich kovariance je 0. Tudíž $\Var[T] \leq \sum_{i,j} \E[T_iT_j]$.
Pokud $i=j$, pak $\E[T_i^2] = \E[T_i] = p^3$, pro $i \neq j$ sdílející hranu
$\E[T_iT_j] = p^5$.

Celkem máme $\Theta(n^3)$ trojúhelníků a $\binom n4 \binom 42 \in \Theta(n^4)$
párů sdílejících hranu. Tudíž $\Var[T] \in \O(n^3p^3 + n^4p^5)$.

Nyní $\frac{\Var[T]}{\E^2[T]} \in \O(n^{-3}p^{-3} + n^{-2}p^{-1}) \in o(1)$.
Dle předchozího lemmatu nakonec $P[T > 0] \to 1$.
\end{proof}

\begin{definice}
Nechť $H$ je graf s $v$ vrcholy a $e$ hranami, pak \emph{hustotou} $H$ rozumíme
hodnotu $\rho(H) = e/v$.

Řekneme, že $H$ je \emph{vyvážený}, jestliže pro každý podgraf $H' \leq H$ platí $\rho(H') \leq \rho(H)$.
\end{definice}

\begin{veta}
Nechť $H$ je vyvážený graf. Pak funkce $n^{-1/\rho(H)}$ je práhovou funkcí pro
obsažení $H$ v $G(n,p)$.
\end{veta}

\begin{proof}
Označme $v = |V(H)|, e = |E(H)|, \rho = e/v$. Nechť $a_1,\dots,a_v$ jsou
vrcholy $H$. Pro uspořádanou $v$-tici $\beta = (\beta_1,\dots,\beta_v)$ vrcholů
$G(n,p)$ označíme $A_\beta$ jev, že $b_ib_j \in E(G(n,p))$ kdykoliv $a_ia_j \in
E(H)$. Indikátor $A_\beta$ označíme $X_\beta$.

Součet $X = \sum_\beta X_\beta$ je kladný právě, když $G(n,p)$ obsahuje kopii
$H$. Pak $\E[X] = \sum_\beta \E[X_\beta] = \sum_\beta p^e \in \Theta(n^v p^e)$.

Uvažujme případy podle nastavení $p$. Pokud $p(n) \in o(n^{-v/e})$, pak $\E[X]
\to 0$, proto i $P[X > 0] \to 0$ dle Markova.

Nyní předpokládejme $p(n) \in \omega(n^{-v/e})$, chceme spočítat $\Var[X] =
\sum_{\beta,\gamma} \Cov[X_\beta,X_\gamma]$. Pokud $\beta, \gamma$ sdílejí
nejvýše jeden vrchol, pak $X_\beta, x_\gamma$ jsou nezávislé.

Předpokládejme, že $\beta, \gamma$ sdílejí právě $t \in \{2,\dots,v\}$ vrcholů.
Potom $\Cov[X_\beta,X_\gamma] \leq \E[X_\beta X_\gamma]$. Ve sdílené části je
nejvýše $t\rho$ hran z kopie $H$ pro $\beta$ i $\gamma$ díky balancovanosti
$H$.  Celkový počet hran je alespoň $2(e-e') + e' \geq 2e-t\rho = 2e-te/v$.
Proto $\Cov[X_\beta,X_\gamma] \leq p^{2e-te/v}$.  Takových párů je navíc
$\Theta(n^{2v-t})$.

Tudíž $\Var[X] \leq \O(\sum_{t=2}^v n^{2v-t}p^{2e-te/v}) = \O(\sum_{t=2}^v
(n^vp^e)^{2-t/v})$. Nyní $\frac{\Var[X]}{\E^2[X]} = \O(\sum_{t=2}^v
(n^vp^e)^{-t/v}) \to 0$, protože $p(n) = \omega(n^{-v/e})$. Podle lemmatu pak
$P[X > 0] \to 0$.
\end{proof}

\newtopic

\begin{definice}
Pro kladné celé $n$ označuje $\nu(n)$ počet prvočísel dělících $n$.
\end{definice}

\begin{veta}[Hardy, Ramannujan]
Nechť $f$ je funkce na kladných celých číslech taková, že $f(n) \to \infty$.
Pak počet $x \in \{1,\dots,n\}$ s vlastností $|\nu(x) - \log\log n| > f(n)
\sqrt{\log \log n}$ je $o(n)$.
\end{veta}

Pro důkaz použijeme fakta z teorie čísel:
\begin{enumerate}
\item $\sum_{p \leq n, p\text{ prvočíslo}} 1/p = \log \log n + \O(1)$.
\item Počet prvočísel v $[n]$ je $\O(n/\log n)$.
\end{enumerate}

\begin{proof}
Zvolíme $x$ z $[n]$ rovnoměrně náhodně. Pro $p$ prvočíslo zvolíme $X_p$
indikátor, že $p \mid x$. Pak $\sum_{p} X_p = \nu(x)$.

$\E[X_p] = \frac{\lfloor n/p \rfloor}n = 1/p + \O(1/n)$, $\E[\sum X_p] = \log \log n + \O(1)$.

$\Var[\sum X_p] = \sum_{p,q} \Cov[X_p,X_q]$, rozdělíme na dva případy. Pro
$p=q$: $\Cov[X_p,X_q] \leq \E[X_p^2] = \E[X_p]$, pak $\sum_p \Var[X_p] = \log
\log n + \O(1)$.

Pro $p \neq q$ je $\Cov[X_p,X_q] = \E[X_pX_q] -
\E[X_p]\E[X_q]$. $\E[X_pX_q] = \frac{\lfloor n/pq \rfloor}n$. 
$\Cov[X_p,X_q] \leq \frac{\lfloor n/pq \rfloor}n - \frac{\lfloor n/p \rfloor}n
\cdot \frac{\lfloor n/q \rfloor}n \leq 1/np - (1/p - 1/n)(1/q - 1/n) \leq
1/n(1/p+1/q)$. Pak $\sum_{p \neq q} \Cov[X_p,X_q] \leq 1/n \sum_{p \neq q}(1/p
+ 1/q) \leq 1/n \O(n/\log n) \cdot 2 \sum_p 1/p \in \O(\log\log n/\log n) \to
0$.

Podle Čebyšeovy nerovnosti proto $P[|\nu(X) - \E[X]| \geq f(n) \sqrt{\log \log
n}] \leq \frac{\Var[X]}{f^2(n) \log \log n} \in \O(1/f^2(n)) \to 0$.
\end{proof}

\newtopic

\paragraph{Lovász Local Lemma.}

Mějme špatné události $B_1,\dots,B_n$ u kterých chceme, aby nenastaly všechny:
$\bigcup B_i$ není $\Omega$. Příkladem jsou Ramseyovy věty. Možnosti, jak
počítat:

\begin{enumerate}
\item Pokud podle Union Bound $P[\bigcup B_i] \leq \sum P[B_i] < 1$, pak jsme
hotovi, navíc $B_i$ nejsou nezávislé.
\item Pokud události jsou nezávislé a $P[\bigcap B_i^C] = \prod P[B_i^C] > 0$,
pak $P[\bigcap B_i] < 1$.
\end{enumerate}

Našim cílem bude nějak využít omezenou nezávislost na odhady pravděpodobnosti.

\begin{definice}
Nechť $A,B_1,\dots,B_k$ jsou náhodné jevy. Pak $A$ je vzájemně nezávislý na
$B_1,\dots,B_k$, když $\forall J \subseteq [k]: P[A \bigcap_{j \in J} B_j] =
P[A]$.
\end{definice}

Jevy $B_1,\dots,B_k$ jsou vzájemně nezávislé právě, když $\forall i \in [k]:
B_i$ je nezávislý na zbylých $B_j$.

\begin{definice}
Nechť $B_1,\dots,B_k$ jsou jevy a $D$ je orientovaný graf o $V(D) = [k]$. Pak
$D$ je graf závislostí jevů $B_1,\dots,B_k$ právě, když $\forall i \in [k]:
B_i$ je nezávislý na $\{B_j \mid ij \notin E(D) \wedge i \neq j\}$.
\end{definice}

\begin{priklad}
Pokud jevy $B_1,\dots,B_k$ jsou vzájemně nezávislé, pak prázdný graf na $k$
vrcholech je jejich graf závislostí.
\end{priklad}

\begin{lemma}[LLL symetrické]
Nechť $B_1,\dots,B_k$ jsou náhodné jevy, kde $\forall i\,P[B_i] \leq p$,
existuje graf závislostí s výstupním stupněm nejvýše $d$ a $4pd \leq 1$
($ep(d+1) \leq 1$). Pak $P[\bigcap B_i^C] > 0$.
\end{lemma}

Uvažme extrémní případy. Když $d = 0$, dostáváme vzájemně nezávislé jevy, pak
lemma platí vždy. Pokud $d = k-1$, pak $4p(k-1) \leq 1$, což je varianta $\sum
P[B_i] \leq pk < 1$.

\begin{veta}
Nechť $\cal H$ je hypergraf takový, že každá hrana má alespoň $k$ vrcholů a
protíná nejvýše $d$ ostatních hran. Pokud $e(d+1) \leq 2^{k-1}$, pak $\cal H$
je 2-obarvitelný.
\end{veta}

\begin{proof}
Uvažme náhodně zvolené obarvení $f: V({\cal H}) \to \{0,1\}$. Pro hranu $e \in
E({\cal H})$ mějme jev $B_e = \{f: |f(e)| = 1\}$ -- hrana $e$ je jednobarevná.
Chceme $P[\bigcap B_e^C] > 0$.

Pravděpodobnost $P[B_e] = 2/2^{l} \leq 2^{1-k}$, kde $l$ je počet vrcholů v
$e$. Nyní mějme graf $D$, pro který $V(D) = E(\cal H)$ a $ef \in E(D)$ právě,
když $e \cap f \neq \emptyset$. Tento graf má maximální stupeň nejvýše $d$.

Podle definice je $D$ graf závislosti, pokud $\forall e \in E({\cal H}): B_e$
je nezávislý na $\{B_f \mid e \neq f \wedge e \cap f = \emptyset\}$. To platí,
protože $B_e$ závisí pouze na hodnotách $f(v)$ pro $v \in e$, zatímce $B_f$
závisí pouze na ostatních hodnotách.

Podle LLL, pokud $e2^{1-k}(d+1) \leq 1$, existuje korektní 2-obarvení.
\end{proof}

Podobná věta lze dokázat pomocí Union Bound, pokud zapomeneme na $d$ a omezíme
počet hran pod $2^{k-1}$. Rozdílem je, že v této variantě máme globální
podmínku oproti lokální podmínky protínání $\leq d$.

\paragraph{Routing v grafech.} Chceme propojit $s_i$ do $t_i$ v grafu pro $i
\in [n]$ hranově disjunktními cestami. Pro každé $i$ máme $F_i$ seznam $m$ cest
mezi $s_i$ a $t_i$. Víme, že $\forall i \neq j\,\forall P \in F_i$ nejvýše $k$
cest ve $F_i$ sdílí hranu s $P$.

\begin{veta}
Pokud $8nk/m \leq 1$, pak existuje $P_i \in F_i$ pro každé $i$ takové, že
$P_1,\dots,P_n$ jsou hranové disjunktní.
\end{veta}

\begin{proof}
Pro každé $i$ zvolme $P_i \in_u F_i$ náhodně rovnoměrně nezávisle. Pro $i \neq
j$ mějme špatný jev $B_{i,j}$, kde $P_i, P_j$ sdílí hranu, $P[B_{i,j}] \leq
k/m$, jelikož $P[B_{i,j} \mid P_i = P]$ pro $P \in F_i$ je počet cest ve $F_j$
protínajících $P$ děleno $|F_j|$, což je nejvýše $k/m$.

Nyní uvažujme graf $D = (V,E)$, kde vrcholy odpovídají $\binom n2$ a $E =
\{\{A,B\} \mid A \neq B, A \cap B \neq \emptyset\}$. Chceme, aby $B_{i,j}$ je
nezávislý na $B_{k,l}$ tak, že $k,l,i,j$ jsou po dvou různé. To platí, protože
cesty jsou disjunktní. Jedná se proto o graf závislostí. Jeho maximální stupeň
je $d = 2n-2$.

Potom podle LLL, pokud $4pd \leq 4 \cdot 2n \cdot k/m \leq 8kn/m \leq 1$,
existuje routing.
\end{proof}

\begin{veta}
Nechť $D$ je konečný orientovaný graf s $\delta^+$ minimálním výstupním stupněm
a $\Delta^-$ maximálním vstupním stupněm. Pokud $k \in \N$ a $k \leq
\delta^+/(1 + \log(1+\delta^+\Delta^-))$, pak $D$ obsahuje orientovaný cyklus
délky dělitelné $k$.
\end{veta}

\begin{proof}
Najdeme funkci $f: V(D) \to [k]$ takovou, že $\forall u \exists v \in N^+(u)$
takový, že $f(v) = f(u)+1 \bmod k$. Abychom $f$ našli, můžeme předpokládat, že
$\forall v: \deg^+(v) = \delta^+$. Pak pro každý vrchol zvolíme $f(v)$
uniformně nezávisle náhodně.

Uvažujme jev $B_u: \forall v \in N^+(u): f(v) \neq f(u) + 1 \bmod k$. Pak
$P[B_u] = (1 - 1/k)^{\delta^+}$. Nyní chceme najít $d$ v grafu závislosti,
abychom splnili $ep(d+1) \leq 1$.

Nechť $G_u = \{ w:  N^+(u) \cap (N^+(w) \cup \{w\}) = \emptyset\}$ a pro graf
závislosti $D$ máme $V = V(D)$ a $E = \{uw \mid w \neq u, w \notin G_u\}$. Pak
$d = \delta^+\Delta^-$. Tudíž chceme, aby platilo $e(1-1/k)^\delta(\delta\Delta
+ 1) \leq 1$. Pro volbu $k$ ve větě máme vyhráno.

Proč to je graf závislosti? \dots
\end{proof}

\begin{lemma}[LLL, obecná verze]
Nechť $B_1,\dots,B_n$ jsou (špatné) jevy, $D$ graf závislosti a $x_1,\dots,x_n
\in [0,1]$. Pokud $P[B_i] \leq x_i \prod_{B_iB_j \in E(D)} (1-x_j)$,
potom $P[\bigcap B_i^C] > 0$.
\end{lemma}

\begin{proof}[Důkaz, že obecná $\Rightarrow$ symetrická.]
Máme $B_1,\dots,B_n$, $D, p, d$, kde $ep(d+1) \leq 1$. Zvolíme $x_i
= 1/(d+1) < 1$, pokud $d \neq 0$. Kdyby platilo $d = 0$, pak $D$ nemá hranu a jevy jsou
nezávislé.

Pak $x_i \prod (1-x_j) = 1/(d+1) (1 - 1/(d+1))^{\deg^+(B_i)} \geq 1/(d+1) \cdot
1/e \geq p \geq P[B_i]$. Proto podle obecného LLL jsme hotovi.
\end{proof}

Obvyklý důkaz je nekonstruktivní, ale algoritmická verze existuje: volíme
náhodné proměnné, v případě nastání špatného jevu převzorkujeme proměnné, které
jej ovlivňují.

\newtopic

\paragraph{Chernoffovy meze.} Nechť $X_1,\dots,X_ \in
\{0,1\}$ jsou náhodné veličiny zvolene uniformně nezávisle. Uvažme $S_n =
\sum_{i=1}^n X_i$. Potom $\E[S_n] = \sum \E[X_i] = n/2$. (Jedná se o rozdělení
$Bin(n,1/2)$.)

\begin{priklad}
Uvažme $\Delta(G(n,1/2))$. Pro každý vrchol $v: \deg(v) \sim Bin(n-1,1/2)$.
Tudíž $\E[\deg(v)] = (n-1)/2$.

Nyní $P[\deg(v) > (n-1)/2 + t] < f_n(t)$, pokud $f_n(t) < 1/n^2$, pak $P[\Delta
 > (n-1)/2 + t] \leq n \cdot f_n(t) < 1/n$. Chceme tedy dostat $f_n(t)$ co 
nejníže.
\end{priklad}

\begin{veta}
Nechť $Y_1,\dots,Y_n \in \{+1, -1\}$ jsou uniformně náhodné nezávislé proměnné,
$T_n = \sum_{i=1}^n Y_i$ a $t \geq 0$. Potom $P[T_n \geq t] < e^{-t^2/2n}$ a
$P[T_n \leq -t] < e^{-t^2/2n}$.
\end{veta}

Výraz $e^{-t^2/2n}$ můžeme rovněž zapsat jako $e^{-t^2/2\sigma^2}$, kde $\sigma
= \sqrt{n} = \sqrt{\Var[T_n]}$. Speciálně tedy $P[T_n \geq s\sigma] \leq
e^{-s^2/2}$.

Vraťme se k příkladu. Pokud $Y_i = 2X_i - 1$, pak $T_n = 2S_n - n$ a speciálně
$P[S_n > n/2 + t] = P[T_n/2 > t] < e^{-2t^2/n}$.
Podobně, $P[\deg(v_1) > (n-1)/2 + t] < e^{-2t/(n-1)}$. To bude pod $1/n^2$,
když zvolíme $t > \sqrt{n-1}\sqrt{\log n}$.

Podle Čebyševovy nerovnosti dostáváme $P[|T_n - \E[T_n]| > s\sigma] \leq
1/s^2$. Chernoffovy meze nám dávají $\leq 2e^{-s^2/2}$.

\begin{proof}
$T_n \geq t$ je ekvivalentní $e^{\lambda T_n} \geq e^{\lambda t}$ pro $\lambda
> 0$. Pak $P[T_n \geq t] = P[e^{\lambda T_n} \geq e^{\lambda t}] \leq
\E[X]/e^{\lambda t}$ (podle Markova).

$\E[X] = \E[e^{\lambda \sum Y_i}] = \E[\prod e^{\lambda Y_i}] = \prod
\E[e^{\lambda Y_i}] = ((e^\lambda + e^{-\lambda})/2)^n = \cosh^n \lambda$.
Odhadneme $\cosh \lambda \leq e^{\lambda^2/2}$. Proto $\E[X] \leq e^{\lambda^2n/2}$.

Nakonec tedy $P[T_n \geq t] \leq e^{\lambda^2n/2 - \lambda t}$. Chceme
minimalizovat výraz přes $\lambda$. Když zvolíme $\lambda = t/n$, dostáváme
správnou mez.

Druhou mez dokážeme analogicky pro $-Y_i$.
\end{proof}

\paragraph{Kombinatorický rozpor.}

Mějme množinu $X$ velikosti $n$ a $\mathcal S \subseteq P(X)$. Chceme obarvit
$X$ dvěma barvami vyrovnaně.

Definujme $c: X \to \{-1,1\}$ a nevyrovnanost $S \in \mathcal S: c(S) = \sum_{x
\in S} c(x)$ a rozpor $\disc(\mathcal S, c) = max_{S \in \mathcal S} |c(S)|$ a
$\disc(\mathcal S) = \min_c \disc(\mathcal S, c)$.

\begin{tvrzeni}
Nechť $|X| = n, |\mathcal S| = m$. Potom $\disc(\mathcal S) \leq
\sqrt{2n\log(2m)}$. Pokud $\forall s \in \mathcal S: |S| \leq s$, pak
$\disc(\mathcal S) \leq \sqrt{2s \log(2m)}$.
\end{tvrzeni}

\begin{proof}
Chceme, aby existovalo $c$ takové, že $\disc(\mathcal S, c) \leq \sqrt{2s
\log(2m)} = t$. Zvolme $c: X \to \{-1,1\}$ náhodně. Dále chceme: $\forall S \in
\mathcal S: |c(S)| \leq t$.

Uvažujme špatný jev $B_S = \{c \mid |c(S)| > t\}$. Pak $P[B_S] \leq P[|c(S)|
\geq t] = P[|\sum_{x \in S} c(x)| \geq t]$. Sčítáme $|S|$ nezávislých veličin,
každá $\pm 1$. Proto $P[B_S] < 2e^{-t^2/2|S|} \leq 2e^{t^2/2s} = 2e^{-\log 2m}
= 1/m$.

Pak $P[B_s] < 1/m$, a proto $P[\bigcup_{s \in \mathcal S} B_s] < 1$.
\end{proof}

\begin{veta}[Chernoffovy meze (aditivní)]
Mějme nezávislé náhodné proměnné $X_1,\dots,X_n$, $0 \leq X_i \leq 1$ a $X =
\sum_{i=1}^n X_i$, $\sigma^2 = \Var[X]$. Potom $P[X \geq \E[X] + t]$ a $P[X
\leq \E[X]-t]$ je ostře menší $e^{-t^2/2(\sigma^2 + t/3}$.
\end{veta}

\begin{veta}[Chernoffovy meze (multiplikativní)]
Mějme nezávislé náhodné proměnné $X_1,\dots,X_n$, $X_i \in \{0, 1\}$ a $X =
\sum_{i=1}^n X_i$, $\mu = \E[X]$. Potom $P[X \geq (1 + \delta)\mu < (e^{\delta}
/ (1+\delta)^{1+\delta}))^\mu$ a $P[X \geq (1 - \delta)\mu < (e^{-\delta}
/ (1-\delta)^{1-\delta}))^\mu$.
\end{veta}

První tvar lze zjednodušit na $e^{-\mu\delta^2/3}$ pro $\delta \in (0,1)$,
druhý na $e^{-\mu\delta^2/2}$.

\begin{proof}
Chceme ukázat $P = P[e^{tX} \geq e^{t(1+\delta)\mu}] \leq
\E[e^{tX}]/e^{t(1+\delta)\mu}$ podle Markova pro $t > 0$. Pak $\E[e^{tX}] =
\E[e^{\sum tX_i} = \prod \E[e^{tX_i}]$. Označme $p_i = P[X_i = 1]$.
Dostaneme $\E[e^{tX_i}] = e^tp_i + e^0(1-p) = 1 + p(e^t-1) \leq
e^{p_i(p^t-1)}$.

Tudíž $P \leq (e^{e^t-1}/e^{t(1+\delta)})^\mu$. Pokud dosadíme $t =
\log(1+\delta)$, dostaneme hledaný tvar.
\end{proof}

\begin{dusledek}
$P[| X - \mu | > \delta\mu] < 2e^{c_\delta \mu}$, kde $c_\delta$ je konstanta
závislá na $\delta$.
\end{dusledek}

\begin{dusledek}
Pokud $R \geq 6\mu$, pak $P[X \geq R] \leq 2^{-R}$.
\end{dusledek}

\begin{proof}
Zvolme $\delta = R/\mu - 1 \geq 5$. Pak $P[X \geq R] = P[X \geq (1+\delta)\mu]
\leq (e^{\delta+1}/(1+\delta)^{1+\delta})^\mu = (e/(1+\delta))^(1+\delta)\mu$.
Navíc $(1+\delta)/e \geq 6/e \geq 2$.
\end{proof}

\newtopic

\subsubsection*{Routování v hyperkrychli.}

Budeme modelovat přenos informací v počítačových sítí, kterou budeme uvažovat
jako graf. Jak rychle se přenese informace? Pokud graf je úplný, je vše rychlé,
ale jaksi to chce hodně drátů. Nás bude zajímat graf hyperkrychle $G = Q_n:
V(G) = \{0,1\}^n, E(G) = \{xy \mid d_H (x,y) = 1\}$.

Navíc každý paket může procházet nejvýše jednou hranou najednou a každá hrana
pojme nejvýše jeden paket.

\paragraph{Bit Fixing Algoritmus}\leavevmode\\
Vstup: $a, b \in V(Q_n)$\\
Výstup $a-b$ cesta

Pro $i = 1,\dots,n$: Pokud $a_i \neq b_i$, vypiš
$(b_1,\dots,b_i,a_{i+1},\dots,a_n)$.

Takový algoritmus je jistě nezajímavý a trvá $\O(N)$. Co když chceme posílat
více paketů najednou?

Budeme chtít permutační routování, tedy permutaci $\pi: V \to V$, kde
chceme poslat paket $v \to \pi(v)$, a to najednou.

Triviální postup je sekvenčně, pak máme čas $\O(Nn)$. Existuje dolní odhad
$\sqrt{N}$ pro špatnou permutaci. Jistě existuje lepší způsob.

\paragraph{Dvou fázový algoritmus (TPA)}\leavevmode\\
Vstup: $\pi$\\
Výstup: Routovací schéma

Zvol náhodné $f: V \to V$. V první fázi použij BFA na dopravení paketu $v \to
f(v)$, v druhé pak pošli $v \to \pi(v)$, vše paralelně.

Motivace je následující: Je to nejhůře dvakrát pomalejší, ale hlavně nastane
nějaká randomizace, která může zachránit špatné permutace (podobně jako u
Quicksortu).

\begin{veta}
Pro každou permutaci $\pi$ na $V$ platí:

$P[\text{TFA routuje v $\O(\log N)$ paralelních krocích}] \geq 1 - \O(1/N)$.
\end{veta}

\begin{proof}
Analyzujme fázi 1. Označme náhodnou veličinu $X(e)$ jako počet paketů
procházejících hranou $e$. Dále $p$ bude přípustná cesta $e_1,\dots,p_m$ a
$T(p) = \sum_{i=1}^m X(e_i)$.

\eye První fáze zabere nejvýše $\max_p{T(p)}$ paralelních kroků.

Cílem je $P[\exists P: T(P) \geq 30n] \leq 1/N$. Zvolme fixní $P =
v_0,v_1,\dots,v_m$. Paket z $a$ do náhodného $f(a)$ je aktivní ve $v_{i-1}$,
pokud dosáhne $v_{i-1}$ a může pokračovat do $v_i$. Definujme $H_a$ jako
indikátor, jenž je 1 práve, když paket z $a$ je aktivní v nějakém $v_{i-1}$.
Pak $H = \sum_{a \in V} H_a$ součet nezávislých veličin.

Střední hodnota $\E[H] = \sum \E[H_a]$, kde $\E[H_a] \leq \sum_{i=1}^n
P[\text{$a$ je aktivní ve $v_{i-1}$}]$. Nechť $v_{i-1} =
(b_1,\dots,b_{j-1},a_j,\dots,a_n)$ a $v_i =
(b_1,\dots,b_{j-1},b_j,a_{j+1},\dots,a_n)$. Prvních $j-1$ bitů je stejných,
jako $f(a)$, bity od $j+1$-tého se shodují s $a$.

Tedy $P[a\, \dots\, v_{i-1}]
\leq 2^{j-1}$ a rovná se 0, pokud $v_{i-1}, a$ se neshodují v bitech
$j+1,\dots,n$. Proto $\E[H] = m \leq n$.

Podle Chernoffa pak $P[H \geq 6n] \leq 2^{-6n}$. Dále $P[T(P) \geq 30n] \leq
P[H \geq 6n] + P[T(P) \geq 30n \mid H < 6n]$.  Vyrobíme si $36n$ hodu mincí,
potřebujeme alespoň $6n$ úspěchů. Proto podmíněná pravděpodobnost je nejvýše
$P[Bin(36n,1/2) < 6n] \leq e^{18n(2/3)^2/2} = e^{-4n} \leq 2^{-3n-1}$.

Celková pravděpodobnost je proto nejvýše $2^{-3n}$.
Pak pravděpodobnost, že existuje špatná cesta, je maximálně $2^{-3n} \cdot \#P
\leq 2^{-3n} \cdot 2^{2n} = 1/N$.
\end{proof}

\newtopic

\subsubsection*{Markovovy řetězce.}

\begin{definice}
Stochastický proces $X = \{X(t) \mid t \in T\}$ je množina náhodných veličin,
kde $X(t) = X_t$ je stav $X$ v času $t$.
\end{definice}

Pokug $\rng(X_t)$ je spočetný, je tento proces diskrétním prostorem. Pokud $T$
je spočetná, říká se tomu diskrétní čas.

\begin{definice}
$X_0,X_1,\dots$ je množina náhodných proměnných, pak $X$ je markovovský
řetězec, pokud $P[X_t = a_t \mid X_0 = a_0, X_1 = a_1, \dots, X_{t-1} =
a_{t-1}] = P[X_t = a_t \mid X_{t-1} = a_{t-1}]$ pro každé $t \in \N$.

Této vlastnosti se často říká \emph{memoryless property}.
\end{definice}

Často budeme uvažovat speciální případ, kde $\rng X_0, \rng X_1, \dots
\subseteq \N$. Pak můžeme Markovovský řetězec $X$ definovat jako orientovaný
graf $D = (V, E, w)$ pro $V \subseteq \N, E \subseteq V^2, w: E \to \R$. Smyčky
mohou existovat a pro každý vrchol musí být součet vah přes výstupní hrany
právě $1$.

V takovém grafu pak $X$ odpovídá nějaké náhodné procházce.

Číslo $P_{i,j}$ bude značit $P[X_t = j \mid X_{t-1} = i]$. Budeme předpokládat,
že $P_{i,j}$ nebude záležet na čase. Z toho pak můžeme utvořit čtvercovou
matici přechodu $P$.

Distribuční vektor $p(t) = (p_0(t),p_1(t),\dots)$, kde $p_i(t) = P[X_t = i]$
popisuje distribuci náhodné veličiny čase $t$.

\eye $p(t+1) = p(t) \cdot P$.

\begin{proof}
Podívejme se na $p_j(t+1)$. To jest $P[X_{t+1} = j] = \sum_{i} P[X_{t+1} = j
\mid X_t = i] P[X_t = i] = \sum_{i} P_{i,j} p_i(t) = p(t) \cdot P$.
\end{proof}

Uvažme $P_{i,j}^m = P[X_{t+m} = j \mid X_t = i]$. Pokud časy se nemění, pak
$P_{i,j}^m = (P^m)_{i,j}$ (lze dokázat iterací předchozího pozorování).

\paragraph{2-SAT.}

Mějme $\varphi = C_1 \wedge C_2 \wedge \dots$ formuli v CNF takovou, že každá
klauzule $C_i$ má nejvýše dva literály. Dále $n$ je počet proměnných.

Obecný SAT je NP-úplný, na druhou stranu 2-SAT je polynomiální. Ukážeme si algoritmus založený na Markovovských řetězcech:

\begin{enumerate}
\item Zvol nějaké ohodnocení $A_0$
\item Opakuj nejvýše $2mn^2$ krát:
\begin{enumerate}
\item Pokud $\varphi$ je splněná, skonči kladně
\item Zvol $C_i$ nesplněnou ohodnocením a změň ohodnocení náhodné proměnné
literálu.
\end{enumerate}
\item Skonči záporně
\end{enumerate}

\begin{veta}
Pokud $\varphi$ není splnitelná, pak algoritmus vždy funguje, jinak funguje s
pravděpodobností alespoň $1-2^{-m}$.
\end{veta}

\begin{proof}
Pokud $\varphi$ není splnitelná, pak vždy algoritmus projde smyčkou a odpoví
správně. Jinak si zafixujeme jedno splňující ohodnocení $A^*$.

Označme $A_t$ jako ohodnocení a $X_t$ jako počet proměnných shodujících se s
$A^*$ v čase $t$.

Pokud $X_t = n$, pak jistě končíme. 
Pokud $X_t = 0$, pak jistě $X_{t+1} = 1$.
Pokud $1 \leq X_t < n$, uvažme nesplněnou $C_i = x_1 \vee x_2$. Tudíž v $A_t$
$x_1 = x_2 = 0$. Naopak v $A^8$ platí $x_1 = 1$ nebo $x_2 = 1$ nebo obojí.

Pokud v $A^*$ platí $x_1 = x_2 = 1$, pak $X_{t+1} = X_t + 1$. Když pro $A^*$
platí $x_1 = 0, x_2 = 1$, pak $X_{t+1} = \pm 1$ s pravděpodobností $1/2$.
Tudíž $P[X_{t+1} = j+1 \mid X_t = j] \geq 1/2$ a $P[X_{t+1} = j-1 \mid X_t = j]
\leq 1/2$.

Definujme $Y_0,Y_1,\dots$ pesimistický odhad $X_t$ tak, že $Y_0 = X_0$,
$P[Y_{t+1} = 1 \mid Y_t = 0] = 1$ a $P_[Y_{t+1} = j \pm 1 \mid Y_t = j] = 1/2$.
To je již Markovovský řetězec s popisující náhodnou procházku na přímce z bodu
0 do bodu $n$. Zajímá nás $\E[\min t: Y_t = n]$.

Označme $h_j = \E[\text{počet kroků k dosáhnutí $Y_t = n$} \mid Y_0 = j]$.
Potom $h_0 = 1 + h_1, h_n = 0$ a $h_j = 1 + (h_{j-1} + h_{j+1})/2$.
Dostáváme $h_j = n^2 - j^2$.

\eye $\E[\min t: X_t = n] \leq \E[\min t: Y_t = n] \leq h_0 = n^2$. Tudíž
$P[\min(t: X_t = n) \geq 2n^2] \leq 1/2$.

Nyní si rozdělíme proces na $m$ bloků velikosti $2n^2$. Každý blok si můžeme
představit jako nezávislý výpočet. Pravděpodobnost, že první blok selže je
nejvýše $1/2$. Stejná pravděpodobnost selhání je i pro ostatní bloky. To nám
dává pravděpodobnost selhání $2^{-m}$.
\end{proof}



\end{document}