Pravděpodobnostní prostor je trojice $(\Omega, \Sigma, P)$, kde $\Omega$ je množina, $\Sigma \subseteq 2^{\Omega}$ je $\sigma$-algebra na $\Omega$ (množina podmnožin $\Omega$ uzavřená na komplement, spočetná sjednocení a spočetné průniky) a $P$ je ‘countably additive’ míra na $\Sigma$ s $P[\Omega]=1$. Elementy $\Sigma$ jsou náhodné jevy a elementy $\Omega$ jsou elementární jevy. Pro event $A$ je $P[A]$ jeho pravděpodobnost.

Náhodná proměnná $A$ na pravděpodobnostním prostoru $(\Omega, \Sigma, P)$ je funkce $X: \Omega \rightarrow \mathbb{R}$ taková, že pro každé $a \in \mathbb{R}, \{\omega \in \Omega: X(\omega)\leq a\} \in \Sigma$.

Střední hodnota $\mathbb{E}[X]=\sum_{\omega \in \Omega} p(\omega)X(\omega)$ Platí linearita střední hodnoty $E[aX+bY]=aE[X]+bE[Y]$, a pro nezávislé náhodné proměnné platí $E[XY]=E[X]E[Y]$. Důkaz plyne přímo z definic.

Indikátor $I_A$ eventu $A$ je náhodná proměnná $I_A[\omega]=1$ pokud $\omega \in A$ a $0$ jinak. Platí pro ni $E[I_A]=\Pr[A]$.

Rozptyl je $Var(X)=E[(X-E[X])^2]=E[X^2]-E[X]^2$.

Odhady

Pro faktoriál triviálně platí $n! \leq n^n$. Máme ale i těsnější $\left(\frac{n}{e}\right)^n \leq n! \leq en\left(\frac{n}{e}\right)^n.$ Úplná Stirlingova formule je velice těsná mez na faktoriál.

Pro binomiální koeficient je $\binom{n}{m} \leq n^k$, také ale $\left(\frac{n}{k}\right)^k \leq \binom{n}{k} \leq \left(\frac{en}{k}\right)^k.$

Pro všechna $k$ platí $\binom{n}{k} \leq 2^n$ a speciálně pro $2k=n$ máme $\frac{2^{2k}}{2\sqrt{k}} \leq \binom{2k}{k} \leq \frac{2^{2k}}{\sqrt{2k}}.$

Pro reálná $x$ platí $1+x \leq e^x$. Zvláště pak $(1-p)^m \leq e^{-mp}$ a speciálně pro $0 \leq p \leq \frac{1}{2}$ také $1-p \geq e^{-2p}$.

Pravděpodobnostní rovnosti a nerovnosti

  • Boolova nerovnost (Union Bound): $\Pr[\bigcup_i A_i] \leq \sum_i \Pr[A_i]$
  • Markovova nerovnost: pro nezáporná $a$ platí $\Pr[X \geq a] \leq \frac{E[X]}{a}$
  • Bayesova věta: $\Pr[B_i | A]=\frac{\Pr[A | B_i]\Pr[B_i]}{\sum_j \Pr[B_j | A]\Pr[B_j]}$
  • Chebyshehova nerovnost: mějme náhodnou proměnnou $X$ s konečným rozptylem, pak $\Pr[|X-E[X]| \geq t] \leq \frac{Var[X]}{t^2}$

Pravděpodobnostní metoda

Ramseyova čísla

$R(k) > 2^{k/2}$

Uvažujme náhodný graf s pravděpodobností každé hrany $\frac{1}{2}$ na $n$ vrcholech. Pravděpodobnost kliky $K_k$ na vybraných $k$ vrcholech je $p=2^{-\binom{k}{2}}$. Stejná pravděpodobnost platí pro nezávislou množinu. V grafu máme $\binom{n}{k}$ množin vrcholů velikosti $k$. Použijeme union bound a získáváme $$\Pr[K_k \subseteq G \vee K_k \subseteq \bar{G}] \leq 2\binom{n}{k}2^{-\binom{k}{2}}.$$ Nyní zkontrolujeme kdy je tento výraz menší jak $1$. S použitím $\binom{n}{k} \leq n^k$ zjistíme, že stačí aby $2n^k < 2^{k(k-1)/2}$ což platí pro $n \leq 2^{k/2-1}$.

Z toho vyplívá, že existuje graf na $2^{k/2-1}$ vrcholech takový, že obsahuje kliku $K_k$ nebo nezávislou množinu velikosti $k$.

SAT

Formule SAT s méně jak $2^k$ klauzulema velikosti $k$ je splnitelná. Náhodné ohodnocení proměnných má šanci nesplnit formuli nejvýše $2^{-k}$. Přes union bound dostaneme, že šance nesplnit jednu formuli je nejvýše $\frac{t}{2^k}$ kde $t$ je počet klauzulí. Pokud je $t<2^t$ tak existuje splňující ohodnocení.

Erdős-Ko-Rado theorem

Mějme soubor množin $F \subseteq \binom{X}{k}$ je ‘intersecting’ pokud každá dvojice prvků má neprázdný průnik, jaká je maximální velikost $F$ pro různá $k$? Pokud $k > n/2$ tak mají dvě množiny vždy průnik a tak je $|F|=\binom{n}{k}$. Pokud $k \geq n/2$ pak lze zkonstruovat $F$ tak že zafixujeme jeden elment a vložíme ho do všech množin. Tato konstrukce tedy zaručuje horní mez $|F| \leq \binom{n-1}{k-1}$. Nyní stačí dokázat, že to není víc. Pro $k < n/2$ a množinu $X$ řad po sobě jdoucích čísel $\mod n$ je největší rodina $|F| \leq k$. [Erdős-Ko-Rado theorem] BÚNO $X=\{0,1,\dots,n-1\}$. Mějme $s \in [n]$, permutaci $\sigma \in S_n$ a $$A_{s,\sigma}=\{\sigma(s),\sigma(s+1),\dots,\sigma(s+k-1)\}$$ (tj. podsekvence $k$ prvků permutace $\sigma$). Jaká je pravděpodobnost, že $A_{s,\sigma}$ najdeme v $F$, když vybereme $s$ a $\sigma$ uniformě náhodně a nezávisle? Vybrání zcela náhodné permutace je $\Pr[A_{s,\sigma}]=\frac{|F|}{\binom{n}{k}}$. Pokud se ale na situaci podíváme tak, že nejdříve náhodně vybereme $\sigma$ a až potom $s$, tak víme, že z fixní permutace může být maximálně $k$ prvků v $F$, dostáváme $\Pr[A_{s,\sigma}] \leq \frac{k}{n}$. Dosazením dostáváme $\frac{|F|}{\binom{n}{k}} \leq \frac{k}{n}$ a tedy $|F| \leq \frac{k}{n}\binom{n}{k} = \binom{n-1}{k-1}$.

Počet fixních bodů permutace

Mějme permutaci $A$ a indikátor $I$ toho, že $A_i$ je fixní bod permutace. Pro $i \in [n]$ je šance toho, že $A_i$ je fixní bod rovna $P[A_i] = \frac{1}{n} = E[I_{A_i}]$. $$E[I]=E[\sum_i I_{A_i}]=\sum_i E[I_{A_i}]=\sum_i \frac{1}{n} = 1$$

Turnaj má hodně Hamiltonovských cest

Mějme orientovaný $K_n$ (tzv. turnaj) s náhodným orientováním hran. Vezměme permuci $\sigma \in S_n$ a mějme indikátor $I_{\sigma}$, že $\sigma$ tvoří Hamiltonovskou cestu v pořadí vrcholů podle permutace. Očividně $E[I_{\sigma}] = \frac{1}{2^{n-1}}$ a existuje $n!$ různých permutací, takže střední počet hamiltonovských cest v turnaji je $$E[I]=E[\sum_{\sigma} I_{\sigma}] = \sum_{\sigma} E[I_{\sigma}] = \frac{n!}{2^{n-1}}$$

MAX-cut

Mějme graf G a chceme najít rozdělení na dvě množiny s velkým počtem hran vedoucích mezi nima (největší řez). Přiřaďme vrcholy náhodně do množiny A či B. Pro každou hranu platí, že pravděpodobnost, že je v řezu, je $\frac{1}{2}$. Střední hodnota je $\frac{m}{2}$.

Derandomizace – výše zmíněný postup nevede na konstrukci řezu. Lze hladově dávat vrchol tam, kde s již rozdělenými vrcholy dá větší počet hran do řezu, to zaručí řez velikosti alespoň $\frac{m}{2}$.

MAX-SAT

Mějme SAT formuli s $m$ klauzulemi, každá s $k$ různými literály. Náhodně ohodnotíme proměnné. Jev $A_c$ značí, že klauzule $c$ je splněná, $E[I_{A_c}] = P[A_c] = \frac{2^k-1}{2^k}$. A proto je očekávaný počet splněných klauzulí $$E[I]=E[\sum_c I_{A_i}]=\sum_c E[I_{A_i}]=\sum_c \frac{2^k-1}{2^k} \geq m\frac{2^k-1}{2^k}$$

Derandomizace – dělá se podobně jako MAX-cut. Vybereme proměnnou a spočteme střední hodnotu zbytku pro obě její možná ohodnocení. Které vyjde lépe, tak zvolíme. Na zbytku spustíme tu samou procedůru.

Balancing vectors

Mějme $n$ vektorů velikosti $1$, každý s $n$ prvky. Vyberme náhodně $\epsilon_i \in \{-1,1\}$. Mějme náhodnou proměnnou $X = ||\epsilon_1 v_1 + \cdots + \epsilon_n v_n||^2$. Její střední hodnota $$ E[X] = E[\sum_{i,j=1}^n \epsilon_i \epsilon_j (v_i,v_j)] = \sum_{i,j=1}^n E[\epsilon_i \epsilon_j (v_i,v_j) ] =$$ $$ = \sum_{i,j=1}^n E[\epsilon_i \epsilon_j] (v_i,v_j) = \sum_{i=1}^n (v_i,v_i) = \sum_{i=1}^n ||v_i||^2 = n $$ Takže lze vybrat takové hodnoty $\epsilon$ aby výsledný vektor byl buď $\leq \sqrt{n}$ či $\geq \sqrt{n}$, dle toho, jak to potřebujeme.

Alterations – Weak Turán’s theorem

Mějme graf $G$, kde $d=\frac{2m}{n}$ je průměrný stupeň, pak nezávislost $\alpha(G) \geq \frac{n}{2d}$ (plná věta říká $\geq \frac{n}{d+1}$). Vezměme náhodný sbuset $S \subseteq V$ s $\Pr[v \in S] = p$. $X=|S|, Y=|E(G[S])|$, $E[X]=pn$, $E[Y]=p^2m$, $E[X-Y]=p(n-pm)=pn(1-p\frac{d}{2})$. Tato funkce nabývá maxima v $p=\frac{1}{d}$, a vychází $E[X-Y]=\frac{n}{2d}$. Intuice je, že z vybraného subsetu odebereme od každé hrany jeden incidentní vrchol. Ve výsledné množině zbudou už pouze isolovené vrcholy, a těch očekáváme $\frac{n}{2d}$.

Erdös theorem o obvodu a barevnosti

Pro všechna $k$ a $l$ existuje graf $G$ s $g(G) > l$ a $\chi(G) > k$ kde $g$ je obvod a $\chi$ je barevnost. Nastavme $\epsilon=\frac{1}{2l}$ a $p=n^{\epsilon-1}$, uvažujme graf s náhodnými hranami s pravděpodobností $p$. Počet různých cyklů velikosti $i$ uvnitř $K_n$ je roven $$\frac{(i-1)!}{2}\binom{n}{i} \leq \frac{i! n!}{i!(n-i)!} =\frac{n!}{(n-i)!} \leq n^i$$ Mějme náhodnou proměnnou $X$, počet cyklů velikosti maximálně $l$. $$E[X] \leq \sum_{i=3}^l n^i p^i=\sum_{i=3}^l n^{\epsilon i}\leq ln^{\frac{1}{2}}=o(n)$$ Tedy pro dostatečně velká $n$ je $E[X]<\frac{n}{4}$. Dle Markovovy nerovnosti $$P[X>\frac{n}{2}]<\frac{n/4}{n/2}=\frac{1}{2}.$$

Ohledně barevnosti lze pozorovat, že $\chi(G) \geq \frac{|V(G)|}{\alpha(G)}$. Nechť $a=\lceil\frac{3}{p}\ln n\rceil$ a pozorujme událost, že nezávislá množina je velikosti $a$. Díky union bound dostáváme $$\Pr[\alpha(G)\geq a] \leq \binom{n}{a}(1-p)^{\binom{a}{2}} \leq n^a e^{-p\binom{a}{2}} \leq n^a n^{-3(a-1)/2} \rightarrow 0.$$ Pro dost velká $n$ bude $\Pr <\frac{1}{2}$.

Spojením dvou vyšších výsledků dostáváme, že pro dost velká $n$ bude díky union bound šance malého cyklu nebo malé barevnosti menší než $1$.

Frievald’s algorithm – testování výsledku násobení matic

Mějme 3 matice A,B a C velikosti $n \times n$ a chceme zjistit jestli $A \times B = C$. Vygenerujeme vektor $r$ s $n$ náhodně vybranými 0/1 prvky a zkontrolujeme, že $A(Br)-Cr = 0$.

  • Pokud $A \times B=C \Rightarrow (AB)r=Cr \Rightarrow A(Br)=Cr \Rightarrow A(Br)-Cr=0$

Jinak $D=AB-C$ má někde nenulový záznam $d_{i,j}$. Nechť $Dr=v$ a $v_i=\sum_{k=1}^n d_{ik} r_k=d_{ij}r_j + y$ ($y$ je zbytek). Aby vyšla nula, tak musí být oba tyto členy nulové, nebo se odečtou na nulu. $$\Pr[v_i=0]=\Pr[v_i=0|y_i=0]\Pr[y_i=0]+\Pr[v_i=0|y_i\neq 0]\Pr[y_i\neq 0]\leq$$ $$\leq \frac{1}{2}\Pr[y_i=0]+\frac{1}{2}\Pr[y_i\neq 0]=\frac{1}{2}$$ Takže pravděpodobnost nahlášení false positiva je nejvýše $\frac{1}{2}$. Pokud provedeme $k$ pokusů, tak je šance špatného výsledku nejvýše $1-2^{-k}$.

Malý trojúhelník ve čtverci

Mějme čtvercovou plochy s body $T$, kde $S(T)$ je plocha nejmenšího trojúhelníku tvořený body $T$. Jaký je největší možný $S(T)$, kterého lze dosáhnout vhodným rozmístěním bodů? (lze $\Omega(\frac{\log(n)}{n^2})$)

Mějme $3$ náhodné body $P,Q,R$ ve čtverci. Určeme si krok $\Delta$ a zkoumejme jak vypadají trojůhelníky, které mají $d(PQ) \in [(i-1)\Delta,i\Delta]$. Prvně, jaká je šance, že $d(PQ)$ spadne do tohoto rozsahu? $B_i = P[d(PQ) \in [(i-1)\Delta,i\Delta]] \leq \Pi(i^2\Delta^2-(i-1)^2\Delta^2)=\Pi(2i-1)\Delta$

Šance, že je trojúhelník malý pak vychází $$\Pr[t(PQR) \leq \epsilon] = \sum_{i=1}^{\sqrt{2}/\Delta} \Pr[t(PQR)\leq \epsilon |B_i]\Pr[B_i]=$$ $$=T\Delta^2+\sum_{i=2}^{|\epsilon|+1}\frac{4\epsilon}{(i-1)\Delta}\sqrt{2}\Pi(2i-1)\Delta^2$$

… zbytek jsem nepochopil

Threshold funkce pro trojúhelník

Střední počet trojúhelníků v náhodném grafu $G(n,p)$ je $$E[X]=\binom{n}{3}p^3=\Theta(n^3 p^3).$$ Povšimněme si, že pro $p=o(\frac{1}{n})$ jde k nule a pro $p=\omega(\frac{1}{n})$ jde do nekonečna. Formálně je ale potřeba trochu zamakat.

Horní mez je ezy díky Markovovi $\Pr[\Delta \in G]\leq E[X] \rightarrow 0$.

Pro dolní mez mějme $X$ indikátory přítomnosti trojúhelníku. $$Var(X)=Var(\sum_i X_i)=\sum Var(X_i)+\sum Cov(X_i,X_j)$$ $$Var(X_i)=E[X_i^2]-E[X_i]^2 \leq E[X_i^2]=p^3$$ Pro kovarianci $Cov(X_i,X_j)$ víme, že pokud sdílí trojúhelníky $2$ a více hran, tak jsou totožné. Pokud sdílí jednu hranu, tak je kovariance $\leq E[X_iX_j]=p^5$ a pokud nesdílí nic, tak jsou nezávislé a kovariance je $0$.

Díky Chebyshevovi víme, že $P[|X_n-E[X_n]| \geq E[X_n]] \leq \frac{Var(X_n)}{E[X_n]^2}$, takže $$\lim_{n\rightarrow \infty}\frac{Var(X_n)}{E[X_n]^2}=0 \Rightarrow \lim_{n\rightarrow\infty} \Pr[X_n>0]=1,$$ protože $\Pr[X_n>0]=1-\Pr[X_n=0]\geq 1-\frac{Var(X_n)}{E[X_n]^2}$.

Nyní využijeme předchozích výpočtů a pro $p=\omega(\frac{1}{n})$ dostáváme $$\frac{Var(X_n)}{E[X_n]^2} \leq \frac{\binom{n}{3}p^3+\binom{n}{2}(n-2)(n-3)p^5}{(\binom{n}{3}p^3)^2}=O\left(\frac{1}{n^3p^3}+\frac{1}{n^2p}\right) \rightarrow 0$$

Threshold funkce pro vybalancované grafy

Mějme $G$, kde $\rho=\frac{e}{v}$ je hustota $G$. Říkáme, že $G$ je vybalancovaný, pokud pro všechny jeho podgrafy $H$ platí, že $\rho(H) \leq \rho(G)$. Ukážeme si, že threshold pro takové grafy je $n^{-\frac{1}{\rho}}$ velice podobným důkazem jako pro trojúhelník (nebudeme opakovat vše do detailu).

Střední hodnta jevu objevu podgrafu $H$ je $$E[X]=\sum_b E[X_b]=\sum_b p^e=\Theta(n^vp^e).$$

Horní mez opět vyplívá triviálně. Pro $p=o(n^{-\frac{1}{\rho}})$ je $$E[X]=o(n^v(n^{-\frac{1}{\rho}})^e)=o(n^v(n^{-\frac{v}{e}})^e)=o(1).$$ Takže dle Markova $\Pr[X\geq 1]\leq\frac{E[X]}{1}=o(1)\rightarrow 0$.

Pro horní mez mějme $p=\omega(\frac{1}{n})$ a $v$-tuple $b$ vrcholů $G$ a $X_b$ indikátor, že $b$ tuple obsahuje $H$ ve správném pořadí jako podgraf. Spočteme rozptyl $Var[X]=\sum_{i,j}Cov(X_i,X_j)$. Parametrizujeme počet vrcholů v průniku množin $i$ a $j$ parametrem $t$. $$Cov(X_i,X_j)\leq E[X_iX_j]\leq p^{2e-t\rho},$$ a proto $$\sum_{i,j}Cov(X_i,X_j)=O(n^{2v-t}p^{2e-t\rho})=O((n^v p^e)^{2-\frac{t}{v}})=o(1)\rightarrow 0.$$

Odhad prostředního binomiálního koeficientu

Mějme prostřední binomiální koeficient $\binom{2m}{m}$ a $2m$ náhodných nezávislých proměnných $X_i$ s hodnotami $\{0,1\}$. $$\Pr[|X-E[X]|\geq \sqrt{m}] \leq \frac{Var(X)}{\sqrt{m}^2} =\frac{1}{2}$$ Takže víme, že šance být daleko od odmocniny z m je menší než polovina. Tento závěr obrátíme a použijeme dále. $$\frac{1}{2} \leq \Pr[|X-E[X]| < \sqrt{m}] = \sum_{|k|<\sqrt{m}} \binom{2m}{m+k}2^{-2m}\leq (2m+1)\binom{2m}{m}2^{-2m}$$ A z toho lze úpravou dostat dolní mez $\binom{2m}{m}\geq \frac{4^m}{4\sqrt{m}+2}$.

Chernoffova nerovnost

Mějme nezávislé náhodné proměnné $X_i$ s hodnotami $\{-1,1\}$, potom $\Pr[X \geq t] \leq e^{-\frac{t^2}{2\sigma^2}}$ a $\Pr[X \leq -t] \leq e^{-\frac{t^2}{2\sigma^2}}$ kde $\sigma^2=Var(X)$.

Nastavíme $Y=e^{qt}$, pak $$E[Y]=E[e^{qX}]=E\left[\prod e^{qX_i}\right]=^{(ind.)}\prod E[e^{qX_i}]=\left(\frac{e^q+e^{-q}}{2}\right)^n \leq (e^\frac{q^2}{2})^n$$ Markov nám říká $\Pr[X \geq t]=\Pr[Y \geq e^{qt}] \leq \frac{E[Y]}{e^{qt}} \leq e^{\frac{q^2n}{2}-qt}$ Funkce $\frac{q^2n}{2}-qt$ nabývá minima ve $q=\frac{t}{n}$ a po substituci dostáváme $$\Pr[X \geq t] \leq e^{-\frac{t^2}{2n}}$$

A pro $Y_i \in \{0,1\}$ je $Y_i=\frac{X_i+1}{2}$, $Y=\frac{X}{2}+\frac{n}{2}$. $$\Pr[Y\geq \frac{n}{2}+t]=\Pr[X\geq 2t] < e^{-\frac{(2t)^2}{2n}} = e^{-\frac{2t^2}{n}}$$

Nicméně, pro tuto distribuci lze dosáhnout lepšího výsledku. Je známo, že $$\Pr[X \geq E[X]+t] < e^{-\frac{t^2}{2(\sigma^2 +t/3)}}.$$

Combinatorial discrepency

Let for a graph $G$ the $dis(G,c)=\max_{f\in F} |c(F)|$ be the maxial color class size for a given coloring $c$ of $G$. Let the discrepancy be the minimum of discrepancies over all colorings $dis(G)=\min_{c} dis(G,c)$.

Let us take a random coloring $c$, then $c(F)$ is random variable which is sum of random variables over all vertices (independent). $$\Pr[|c(F)| \geq t]<2e^{-\frac{t^2}{2|F|}}\leq 2e^{-\frac{t^2}{2S}}\leq \frac{1}{m}$$ when we substitute $t=\sqrt{2n \ln(2m)}$.

Randomizované zaokrouhlování pro k-matching

K-matching je problém, kde máme zadán $n$ prvkový set $V$ a rodinu $F$ subsetů $V$ o velikosti $m$. Výběr $M\subseteq F$ je k-matching pokud žádný bod $V$ není ve více jak $k$ setech $M$. Úkolem je maximalizovat počet vybraných setů v $M$ tak, že neporuší zadanou podmínku.

Definujme si $n \times m$ matici $A$, kde prvek $a_{ij}=1$ pokud $v_i \in S_j$ a $0$ jinak. Náš problém pak lze přeformulovat jako celočíselný program $$\max\{1^Tx:x\in\{0,1\}^m, Ax \leq k1\}.$$ Ovšem řešit celočíselný LP je NP-těžké, takže problém relaxujeme na neceločíselný LP, kde umíme optimum najít v polynomiálním čase. Nalezené optimum označme $x’$ a mějme počet setů $OPT’=1^T x’$. Zřejmě $OPT’ \geq OPT$. Abychom dostali aproximaci hledaného optima, tak náhodně zaokrouhlíme vektor $x’$ a získáme vektor $y$. Každou složku $x’$ zaokrouhlíme na $1$ s pravděpodobností $(1-\frac{\epsilon}{2})x’_i$, takže složka s hodnotou 0.8 bude na drobek méně než 80% zaohrouhlena na 1. Výsledný vektor negarantuje ani optimalitu, ani validní řešení, ale pravděpodobnosti rozumného výsledku nejsou špatné.

Díky linearitě očekávané hodnoty $E[1^Ty]=1^Tx’=OPT’$ a $E[(Ay)_i]=(Ax’)_i \leq k$ pro všechna $i$. Nyní odhadneme šanci $\Pr[X < (1-\epsilon)OPT’]$ Každé přiřazení s $k$ sety podmínku splňuje, takže $OPT’\geq k$. Dále $E[X]=(1-\frac{\epsilon}{2})OPT’$ a $Var[X]\leq E[X]$, což využijeme a použijeme Chernoffovu nerovnost pro 0/1 proměnné s $t=\frac{\epsilon}{2}OPT’$ a $\sigma^2\leq OPT’$. $$\Pr[X<(1-\epsilon)OPT’] \leq e^{-\frac{\epsilon^2}{10}OPT’} \leq e^{-\frac{\epsilon^2}{10}k}\leq\frac{1}{2n+2}$$

Předpokládejme, že $k \geq \frac{10}{k^2} \ln(2n+2)$, pak s pravděpodobností alespoň $\frac{1}{2}$ je vektor $x’$ validní k-matching s hodnotou $(1-\epsilon)OPT$.

Směrování v hyperkrychli

Mějme kyperkostku dimense $n$ a směrujeme z každého z $N$ vrcholů packet pomocí hran tak, aby se dostal do cílového vrcholu, který je daný permutací $\pi$. Naivní směrování opravováním bitů může zahltit hranu a trvat až $\sqrt{N}$. Lze pořešit tak, že provedeme dvě permutace místo jedné. První permutace bude zcela náhodná a druhá permutace nasměruje packety z náhodných pozic na cílové pozice.

Mějme hranu $e$ kde $X(e)$ je náhodná proměnná počtu packetů, které přes $e$ projdou. Doba zpoždění po celé cestě jednoho packetu je $T(P)=\sum_{i=1}^m X(e_i)$. Celková doba běhu algoritmu tak bude $n+\max_i T(P_i)$. Všiměme si, že existuje $2^{2n}$ různých cest.

Vezměme packet a nazvěme ho aktivní v kroku $i$, pokud musí změnit svůj $i$-tý bit. Nyní spočtěme počet aktivních kroků přes všechny packety. Protože destinace všech packetů je nezávislá, vychází nám suma nezávislých proměnných $H=\sum_{k=1}^NH_k$. Počet aktivních packetů na vrcholu $v_{i-1}$ je tolik, kolik je packetů, které z něho musí na $i$-tý krok přejít dimenzi. Tyto packety musí mít stejný suffix výchozí adresy, takže jich je nejvíce $2^{j-1}$. Podobně, aktivní kolizní packety ve vrcholu $v_{j-1}$ jsou pouze ty, které mají v cílové adrese stejný prefix. Takže šance, že je aktivní je $2^{-(j-1)}$. To nám dává střední hodnotu $1$. Díky linearitě střední hodnoty dostáváme $E[H] \leq m.1 \leq n$. Protože $H$ je 0/1 náhodná proměnná, můžeme použít Chernoffovu nerovnost $$\Pr[H \geq 6n \geq 6E[H]]\leq 2^{-6n}.$$

chybí dokončení DK…

Local Lovasz lemma

Je elegantní mez pro pravděpodobnost v následujícím znění: Mějme náhodné jevy $A_i$ které jsou nezávislé na všech kromě nejvýše $D$ jevech a zároveň $\Pr[A_i] \leq p$, potom pokud $ep(d+1)\leq 1$ pak $\Pr[\cap \bar{A_i}]>0$.

Obecná verze zní trošku hůř: Mějme náhodné jevy $A_i$ a graf závislostí $D=(V,E)$ a váhy $x_i \in [0,1)$, pokud $\Pr[A_i] \leq x_i \prod_{(i,j)\in E}(1-x_j)$, potom $\Pr[\cap \bar{A_i}] \geq \prod_{i=1}^n (1-x_j) > 0$.

Symetrická (ta první) verze lze z obecné dostat pouhým nastavením $x_i=\frac{1}{d+1}$.

Edge-disjoint path problem

Mějme graf s $n$ starty a cíly. Dále mějme kolekci $m$ různých cest mezi $s_i$ a $e_i$ takovou, že s jinou kolekcí vybraná cesta sdílí hranu s maximálně $k$ cestama z oné kolekce. Vyberme náhodnou cestu z každé kolekce a zaveďme event $A_{i,j}$, že cesta z $i$ a $j$ sdílí hranu. Všimněme si, že $A_{i,j}$ je závislá maximálně na nejvýše $2(n-2)$ dalších eventech a zároveň $\Pr[A_{i,j}]\leq p\leq \frac{k}{m}$. Pozorujeme, že aby platilo LLL, tak musí $ep(d+1)=\frac{ek}{m}(2n-3)<1$, tedy $k<\frac{m}{e(2n-3)}$. Pokud platí LLL, tak je jisté, že průnik doplňku je neprázný, a tedy existuje takový výběr cest, že se ani jedna z nich neprotíná.

Cyklus v orientovaném grafu

Mějme orientovaný graf s výstupním stupněm alespoň $\delta$ a vstupním stupněm nejvýše $\Delta$. Ořežme stupně tak, aby výstupní byly právě $\delta$. Obarvíme vrcholy $G$ náhodně $[k]$ barvami a vytvořme event $A_i$ tedy, že vrchol nemá hranu, která by vedla do barvy, která je o jedna vyšší (barvíme čísly) v modulu $k$. Pravděpodobnost vrcholu se špatnou barvou je $\Pr[A_i]=(1-\frac{1}{k})^\delta$.

Pozorujme, že $A_i$ je nezávislé na všech eventech, kromě barev vrcholů, do kterých z $i$ vede hrana. Takže stupeň závoslosti $A_i$ je $\delta\Delta$. Proto dosadíme do předpokladu LLL a získáváme $$ep(d+1)=e(1-\frac{1}{k})^\delta (\delta\Delta+1)=e e^{-\frac{\delta}{k}}(\delta\Delta+1) < 1$$ Což bude platit pro $k<\frac{\delta}{1+\ln(1+\delta\Delta)}$. Takže pro tyto hodnoty je šance, že žádný z těchto jevů nenastak $>0$, takže existuje takové dobré obarvení, kde každý vrchol má výstupní stupeň do další vrstvy alespoň jedna. Pak stačí po těchto vrstvách chodit dokud nenarazím na již projitý vrchol a tím se uzavře cyklus délky, která je dělitelná $k$.

Postup pro řešení 2-SAT

Začneme v náhodném stavu $a_0$. Budeme opakovat $2rn^2$ následující: Pokud $\Sigma(a_i)$ je splněno, výstupem je pravda, a pokud ne, tak najdeme nesplněnou klauzuli a náhodně změníme hodnotu jedné z proměnných. Pokud jsme během $2rn^2$ kroků neřekli, že je formule splnitelná, tak řekneme, že není splnitelná.

Mějme cílové ohodnocení $b$, které je splnitelné, pak $X_t$ označuje vzdálenost k $b$ v $t$-ém kroku. Algoritmus se od tohoto ohodnocení v každém kroku buď vzdaluje, nebo se k němu přiblíží. Protože v klauzuli jsou vždy jen dvě proměnné, šance pro pozitivní změnu je alespoň $\frac{1}{2}$. Očekávaná vzdálenost od začátku je pro MC v řádu $\sqrt{n}$ a proto je šance, že je potřeba nejvýše $2n^2$ kroků $\Pr[<2n^2]\geq\frac{1}{2}$. Zmíněný algoritmus bude fungovat správně s pravděpodobností $\Pr[\mbox{ok}] \geq 1-\frac{1}{2^r}$, pokud postup zopakujeme $r$-krát.

3-SAT

Opět začneme z náhodného ohodnocení a budeme opakovat stejné kroky $3n$-krát, pokud nevyjdou, vypíšeme, že není splnitelné. Šance, že spravíme ohodnocení správným způsobem je nyní alespoň $\frac{1}{3}$. Z teorie MC víme, že šance na to, dostat se po $j+2k$ krocích z $0$ do $j$ je $$P_{0,j}^{j+2k} \geq \binom{j+2k}{k}(\frac{1}{3})^{j+k}(\frac{2}{3})^k.$$

Stacionární rozdělení Markovova řetězce

Pokud je MC aperiodick a ireducibilní, potom má unikátní stracionární rozdělení $\pi$.

Zdroje