Exercises — Randomized algorithms — Las Vegas, Monte Carlo

Las Vegas. Answer (sorted array) har run mein guaranteed correct hai; running time (comparison count) random quantity hai. Rule: Las Vegas = hamesha correct, time random.

Monte Carlo, one-sided error. Time fixed hai (40 rounds); answer galat ho sakta hai. Ek true prime ko kabhi galat composite nahi kaha jaata, isliye "composite" outputs hamesha safe hain — sirf "prime" hi error ho sakta hai. Monte Carlo = fixed time, answer risky.

Pehli success tak trials ka count geometric hota hai, isliye $E[N]=\frac{1}{p}$ (parent note mein memoryless self-reference $E=1+(1-p)E$ se derive kiya gaya hai). $E[N]=\frac{1}{0.2}=5.$ Tum 5 attempts expect karte ho.

Hum tabhi fail karte hain jab saare $k$ runs simultaneously galat hon. YEH KYUN multiply hoti hai "sab galat" ki probability? Kyunki runs independent hain — ek run ke coins doosre run ke baare mein kuch nahi batate. Independent events ke liye product rule (dekho Probability and Expectation) kehta hai $\mathrm{Pr}[A\text{ and }B]=\mathrm{Pr}[A]\cdot \mathrm{Pr}[B]$ jab $A,B$ independent hon; isse saare $k$ runs mein chain karke milta hai $\mathrm{Pr}[\text{all wrong}]\le q\cdot q\cdots q=q^k$. Isliye $\mathrm{Pr}[\text{error}]\le {\left(\frac{1}{4}\right)}^{10}=\frac{1}{4^{10}}=\frac{1}{1048576}\approx 9.54\times 10^{-7}.$

Hume chahiye $q^k\le \epsilon$. Log lete hain (log exponent $k$ ko multiplier mein badal deta hai taaki hum iske liye solve kar sakein): $k\ge \frac{\ln (1/\epsilon )}{\ln (1/q)}=\frac{\ln (10^6)}{\ln 2}=\frac{13.8155}{0.6931}=19.93\dots$ Upar round karo: $k=20$. Check: $2^{-20}=9.5\times 10^{-7}\le 10^{-6}$. ✓

Markov's Inequality: kisi non-negative quantity $T$ aur kisi bhi $a>0$ ke liye, $\mathrm{Pr}[T\ge aE[T]]\le \frac{1}{a}$. YEH TOOL KYUN? Yeh ek aisa bound hai jo sirf mean ke baare mein jaanta ho tab bhi kaam karta hai — perfect jab hum sirf $E[T]$ jaante hain. Yahan budget $500=5\times 100=5E[T]$ hai, isliye $a=5$: $\mathrm{Pr}[T\ge 500]\le \frac{1}{5}=\mathrm{0.2.}$ Cut-off zyaada se zyaada 20% time fire karta hai, isliye resulting Monte Carlo algorithm itni hi baar galat hota hai (yeh maanke ki guess hamesha galat hai — ek worst case).

Do ranks $i<j$ compare hote hain iff unme se ek rank $i$ aur $j$ ke beech waale poore $j-i+1$ elements ke block mein pehla pivot choose kiya jaata hai. KYUN? Agar koi beech wala element pehle pivot banta hai, toh woh $i$ aur $j$ ko alag partitions mein split kar deta hai aur woh phir kabhi nahi milte; sirf agar $i$ ya $j$ lead kare tab hi compare hote hain. $j-i+1$ elements mein se har ek equally likely hai pehla hone ka, aur unme se $2$ ($i$ aur $j$) favourable hain: $\mathrm{Pr}=\frac{2}{j-i+1}=\frac{2}{9-3+1}=\frac{2}{7}\approx \mathrm{0.2857.}$

Ranks $\mathrm{1..4}$ tak jaate hain. Har pair $(i,j)$ jahan $i<j$ ho aur uska gap $d=j-i+1$ list karo:

Sum: $3\cdot 1+2\cdot \frac{2}{3}+\frac{1}{2}=3+\frac{4}{3}+\frac{1}{2}=\frac{29}{6}\approx \mathrm{4.8333.}$ Expected comparisons $=\frac{29}{6}\approx 4.83$.

Single-run success $\ge \frac{1}{\left(\genfrac{}{}{0ex}{}{10}{2}\right)}=\frac{1}{45}$. Independent runs multiply hote hain, isliye $\mathrm{Pr}[\text{all }T\text{ miss}]\le (1-\frac{1}{45}{)}^T.$ $1-x\le e^{-x}$ use karte hain (KYUN: yeh ek ugly product ko ek clean exponential mein badal deta hai jise hum invert kar sakein): $(1-\frac{1}{45}{)}^T\le e^{-T/45}$. Force $e^{-T/45}\le \frac{1}{10}$: $-\frac{T}{45}\le \ln \frac{1}{10}=-\ln 10⟹T\ge 45\ln 10=45\times 2.302585=\mathrm{103.6.}$ Upar round karo: clean-bound requirement $T=104$ hai. Lekin humne actual product $(1-1/45{)}^T\le 0.1$ banana tha; integers test karne par, $(1-1/45{)}^{103}=0.0997\le 0.1$ pehle se kaam karta hai jabki $(1-1/45{)}^{102}=0.1020>0.1$ nahi karta. Isliye exact threshold $T=103$ hai, aur clean exponential bound ka $T=104$ ek safe (thoda conservative) over-estimate hai — dono failure ko $1/n$ se neeche laate hain.

Pehle precondition: majority voting tabhi help karta hai jab per-run success probability $p>\frac{1}{2}$ ho. KYUN? Har run ek biased coin hai jo "correct" land karta hai prob $p$ ke saath; majority in coins ki democracy hai. Agar $p>\frac{1}{2}$ toh correct answer typical outcome hai, isliye zyaada runs uske liye evidence pile up karte hain aur reliability $1$ ki taraf badhti hai. Agar $p<\frac{1}{2}$ toh galat answer typical hai, aur zyaada runs tumhe zyaada confidently galat bana denge — voting ulta pad jaata hai. Yahan $p=0.75>\frac{1}{2}$ hai, isliye hum safe hain.

Majority correct hai iff $5$ mein se kam se kam $3$ runs correct hain. Maano $C$ = correct ki sankhya; $C$ binomial hai $n=5,p=0.75$ ke saath (KYUN binomial: independent yes/no trials, har "yes" same probability ke saath). Hume chahiye $\mathrm{Pr}[C\ge 3]$: $\mathrm{Pr}[C\ge 3]={\sum }_{c=3}^5\left(\genfrac{}{}{0ex}{}{5}{c}\right)(0.75{)}^c(0.25{)}^{5-c}.$ Term by term compute karo:

• $c=3:\left(\genfrac{}{}{0ex}{}{5}{3}\right)(0.75{)}^3(0.25{)}^2=10\cdot 0.421875\cdot 0.0625=0.263672$
• $c=4:\left(\genfrac{}{}{0ex}{}{5}{4}\right)(0.75{)}^4(0.25{)}^1=5\cdot 0.316406\cdot 0.25=0.395508$
• $c=5:\left(\genfrac{}{}{0ex}{}{5}{5}\right)(0.75{)}^5=0.237305$

Sum $=0.896484\approx 0.8965$. Majority voting ne reliability $0.75$ se badhaakar lagbhag 89.6% kar di. Kyunki yeh Chernoff Bounds regime hai, zyaada runs isse exponentially $1$ ki taraf le jaate hain.

Construction. Loop: $M$ run karo (cost $t$), phir uske output par $V$ run karo (cost $v$). Agar $V$ "correct" kahe, woh answer output karo aur roko; warna repeat karo.

Hamesha correct? Hum sirf woh answer output karte hain jise $V$ ne certify kiya ho, aur $V$ kabhi jhooth nahi bolta. Isliye output guaranteed correct hai — yeh Las Vegas ki defining property hai. Randomness ab poori tarah kitne loops run karte hain, usme hai. ✓

Expected time. Har loop $t+v$ cost karta hai aur prob $p$ se succeed karta hai (verifier pass karta hai). Pehli success tak loops ki sankhya geometric hai mean $1/p$ ke saath (parent-note derivation). Linearity se, $E[\text{time}]=\frac{t+v}{p}.$ $p=\frac{1}{3}$ ke saath: $E[\text{time}]=3(t+v)$ — average mein teen loops.

Rule. $k$ independent rounds run karo. Agar KISI round ka output "composite" ho, toh answer composite do (certain, kyunki ek true prime kabhi witness trigger nahi karta). Agar saare $k$ "prime" kahein, toh answer prime do.

Error bound. Sirf ek hi possible mistake hai — composite ko "prime" kehna — jiske liye saare $k$ rounds witness miss karen — probability $\le q^k$ independence se. Force karo $q^k\le \epsilon$: $k\ge \frac{\ln (1/\epsilon )}{\ln (1/q)}=\frac{\ln (10^9)}{\ln 4}=\frac{20.7233}{1.3863}=\mathrm{14.95.}$ Upar round karo: $k=15$ rounds. Check karo $(1/4{)}^{15}=2^{-30}=9.31\times 10^{-10}\le 10^{-9}$. ✓

"Composite short-circuit" kyun valid hai. One-sidedness ka matlab hai witness proof hai: ek baar bhi compositeness dekhna irrefutable hai, isliye ek bhi "composite" hamesha correct hota hai — koi vote nahi chahiye. Sirf all-"prime" verdict mein residual doubt hota hai, aur woh exactly $q^k$ term hai jise humne bound kiya.

Las Vegas answer guarantee karta hai aur running time randomize karta hai. Monte Carlo running time guarantee karta hai aur answer randomize karta hai. Geometric mean trials to first success ::: $1/p$ Boosting one-sided error after $k$ runs ::: $\le q^k$ Run-count $k$ ke liye rounding direction ::: hamesha upar (ceiling) Two-sided error aggregation ::: majority vote (Chernoff); one-sided ::: jaise hi certain answer aaye le lo