4. Randomizált algoritmusok

Randomizalt algoritmusok

Soft error: Annak a valsege, hogy a kovetkezo mikroszekundumban hibazik az algoritmus.
Ennek a tipikus erteke $\frac{1}{2^{55}}$

A kovetkezo feladatot fogjuk nezni:
Legyen $f$ egy $n$ valtozos $\le d$-ed foku polinom, van egy orakulum megadva amivel barmikor lekerdezhetjuk az $f$ erteket $n$ helyen.

Feladat: Dontsuk el, hogy $f\stackrel{?}{\equiv }0$

Scwartz-Zippel-lemma: Valasszunk ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\in \{1,2,3,\dots ,N\}$ ertekeket egyenletesen fuggetlenul.
Ha $f\not\equiv 0$, akkor

$$\mathbb{P}(f({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)=0)\le \frac{d}{N}$$

Biz.: $n=1$-re az algebra alaptétele adja az indukció kezdetét. $n$-re tudjuk, $n+1$ ?

$h\left(x_1,..,x_n,x_{n+1}\right)$ polinom, írjuk fel $x_1$ hatványai szerint $h=\sum x_1^i{h}_i$, ahol a $h_i$-k n-változósak. Legyen $t$ a legnagyobb index, amire $h_t\not\equiv 0$, ha $t=0$, akkor az indukciós feltevés szerint készen vagyunk.

$$\mathbb{P}(h(\xi )=0)=\mathbb{P}\left(h(\xi )=0\mid h_t(\xi )\ne 0\right)\mathbb{P}\left(h_t(\xi )\ne 0\right)+\mathbb{P}\left(h(\xi )=0\mid h_t(\xi )=0\right)\mathbb{P}\left(h_t(\xi )=0\right)$$

a teljes valószínűség tételéből, becsüljük a két tagot. A másodikra alkalmazhatjuk az indukciós feltevést: $\le 1\cdot nd/N$. Nyilván $\mathbb{P}\left(h_t(\xi )\ne 0\right)\le 1$, a szorzótényezőjéhez $h_t(\xi )\ne 0$ miatt egy 1-változós $t$-edfokú polinom nullhelyét keressük, indukcióból így

$$\mathbb{P}\left(h(\xi )=0\mid h_t(\xi )\ne 0\right)\le t/N\le d/N$$

összeadva $(n+1)d/N$.

Indukcio $n$-re
Ha $n=1$ akkor $\le \frac{d}{N}$ az algebra alaptetele miatt, mert legfeljebb $d$ gyoke lehet egy legfeljebb $d$-ed foku polinomnak.

Indukcios lepes
$\underline{x}=(x_1,\dots ,x_n),\underline{y}=(x_2,\dots ,x_n)$

$$f(\underline{x})=h_0(\underline{y})+h_1(\underline{y})x_1+h_2(\underline{y})x_1^2+\cdots +h_k(\underline{y})x_1^k$$

ugy, hogy $h_k(\underline{y})\not\equiv 0$ akkor $\le d$
Ha $f(\underline{\alpha })=0$ akkor
$h_k({\alpha }_2,\dots ,{\alpha }_n)=0$ vagy $h_k({\alpha }_2,\dots ,{\alpha }_n)\ne 0$ de $f(\underline{\alpha })=0$

i) $\mathbb{P}(h_k({\alpha }_2,\dots ,{\alpha }_n)=0)\le \frac{d-k}{N}$

ii) Tetszolegesen lefixaljuk az ${\alpha }_2,\dots ,{\alpha }_n$ szamokat ugy, hogy $h_k({\alpha }_2,\dots ,{\alpha }_n)\ne 0$.
Az az eset amikor $h_k({\alpha }_2,\dots ,{\alpha }_n)=0$ azt neztuk az i) esetben.
$f$-be behelyettesitjuk ezeket
Minket az erdekel hogy $f({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)$ mikor lesz $0$.

$$f({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)=h_0+h_1\cdot x_1+h_2\cdot x_1^2+\cdots +h_k\cdot x_1^k$$

az $x_1={\alpha }_1$ helyen, ahol $h_i=h_i({\alpha }_2,{\alpha }_3,\dots ,{\alpha }_n)$
$x_1$ egyvaltozos $k$-ad foku polinomja, ebbol kovetkezik, hogy

$$\mathbb{P}(f({\alpha }_1,\dots ,{\alpha }_n)=0)\le \frac{k}{N}$$

Algoritmus

Legyen $N:=2d$
sorsolunk veletlen fuggetlen ${\alpha }_i$-ket es behelyettesitjuk $f$-be es ha $0$-at kapunk akkor a valasz az hogy $f\equiv 0$ kulonben $f\not\equiv 0$

All.:

• Ha $f\equiv 0$ akkor biztosan nem tevedunk.
• Ha $f\not\equiv 0$ akkor legfeljebb $\frac{1}{2}$ valoszinuseggel rossz valaszt fogunk adni.

Ötlet: Futtassuk le $t$-szer az algorimust es ha egyszer is $0$-tol kulonbozo erteket kaptunk akkor a valasz $\not\equiv 0$ kulonben $\equiv 0$

All.:

• Ha $f\equiv 0$ akkor bizotsan nem tevedunk.
• Ha $f\not\equiv 0$ akkor annak a valoszinusege, hogy hibazunk az legfeljebb $1/2^t$.

Alkalmazas:
$G=(L\cup U,E)$ paros graf ahol $|L|=|U|=n$ es el szeretnenk donteni, hogy van-e teljes parositas.

Legyen $M\in {\mathbb{R}}^{n\times n}$ aminek az elemei lehetnek akar valtozok is, ahol

$$M(i,j)=\{\begin{array}{ll}{x}_{ij}& \text{ha }{l}_i{u}_j\in E\\ 0& \text{kulonben}\end{array}$$

All.: $\det M$ egy $|E|=m$ valtozos $n$-ed foku polinom.

Tetel: Letezik $G$-ben teljes parositas $⟺$ $\det M\not\equiv 0$
${\alpha }_i\in \{1,\dots ,2n\}$
Vegyuk eszre, hogy ha van egy nem $0$ kifejtesi tag, akkor tudjuk hogy a grafban letezik teljes parositas.
Forditva is igaz, hogy ha letezik egy teljes parositas akkor letezik egy nem $0$ kifejtesi tag.

(megj.: a matrixban egy permutacio megad egy teljes parositast)

All.:

• Ha nem letezik teljes parositas, akkor $\det M\equiv 0$ tehat biztosan jo valaszt adunk.
• Ha letezik teljes parositas, akkor legfeljebb $\frac{1}{2}$ valseggel adunk rosz valaszt.

Min Vagas

$G=(V,E),|V|=n,|E|=m$ multigraf
Vagas: $V=A\cup B,A\ne \varnothing ,B\ne \varnothing$
Vagas erteke: azoknak az eleknek a szama amelyeknek az egyik vege $A$-ban a masik $B$-ben van.
Cel: minimalis vagas erteke.

Osszehuzas muvelet: $u$ es $v$ csucsokat osszehuzom ha van koztuk el, az osszehuzott csubol azok az elek mennek mint amik $u$ bol es $v$ bol mentek.
jeloles G/uv

Karger algoritmus

Karger(G, n):
	IF n > THEN
		uv in E veletlen
		KARGER (G/uv, n-1)
	RETURN (|E|)

Tetel: Tegyuk fel, hogy $(A,B)$ egy minimalis vagas $c$ ertekkel. Ekkor

$$\mathbb{P}(\text{Karger algoritmus ezt adja ki})\ge \frac{1}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$$

Def.: Azt mondjuk, hogy $(A,B)$ tulel egy $uv$ osszehuzast, ha $u,v\in A$ vagy $u,v\in B$

$$\mathbb{P}(\text{elso osszehuzasnal }(A,B)\text{ tulel})\ge \left(1-\frac{2}{n}\right)$$

A fentibel a valseg-ben $1-\frac{c}{m}$

All.: $m\ge \frac{cn}{2}$, mert minden csucsa foka $\ge c$.

$$\mathbb{P}(\text{i. osszehuzasnal }(A,B)\text{ tulel }|\text{ meg el})\ge \left(1-\frac{2}{n+1-i}\right)$$ $$\mathbb{P}(\text{vegig tulel})\ge \prod _{i=1}^{n-2}\left(1-\frac{2}{n+1-i}\right)=\frac{n-2}{n}\cdot \frac{n-3}{n-1}\cdot \dots \cdot \frac{3}{5}\cdot \frac{2}{4}\cdot \frac{1}{3}=\frac{2}{n(n-1)}=\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$$

Ismeteljuk meg $n^2\log n$ -szer az algorimust. Ekkor

$$\mathbb{P}(\text{a legjobb}>\min )\le {\left(1-\frac{1}{n^2}\right)}^{n^2\log n}\approx e^{\log n}=\frac{1}{n}$$