Randomized algorithms — Las Vegas, Monte Carlo: Visual walkthrough

3.7.19 · D2 · Coding › Algorithm Paradigms › Randomized algorithms — Las Vegas, Monte Carlo

Koi bhi symbol aane se pehle, yeh raha plain-English cast of characters. Hum inse dobara milenge, dheerey dheerey, ek drawing ke saath.

Ek trial = ek attempt (dice ka ek roll, ek random pivot, ek random base).
Success = attempt kaam kar gaya. Yeh ek fixed chance se hota hai, jise hum $p$ kahenge, har baar.
$N$ = trials ki count jeet wali trial tak, including us jeet wali trial ko. Yeh count khud random hai.
$E [N]$ = $N$ ki average value agar tum poora process ek million baar replay karo. Yahi ek number hai jo poora page compute karta hai; end tak hum dikhayenge ki yeh $\frac{1}{p}$ ke barabar hai.

Step 1 — "Probability $p$ " actually kaisa dikhta hai?

KYA. Hum ek number $p$ fix karte hain, ek fraction jahan $0 < p \leq 1$ — ek single trial ke succeed hone ki chance. (Hum jaanbujhkar $p = 0$ ko exclude karte hain, ek aisi attempt jo kabhi nahi jeet sakti, aur Step 7 mein us forbidden case ko revisit karte hain; hum $p = 1$ ko allow karte hain, ek pakki jeet.) Baaki sab kuch is ek dial par build hota hai.

KYUN. Har retry-style randomized algorithm "attempt, maybe fail, repeat" mein simmer ho jaata hai. Time ke baare mein reason karne ke liye, hume pehle ek attempt ke baare mein saaf tarike se reason karna hoga. Agar hum ek single coin picture nahi kar sakte, toh hum hazaar coin picture nahi kar sakte.

PICTURE. Neeche, lambaai $1$ ki ek horizontal bar (certainty ka poora hissa) split ki gayi hai: blue part $p$ hai (success), gray part $1 - p$ hai (failure). Ek trial = bar par ek dart phenk do; blue mein land karo toh kaam ho gaya.

Figure — Randomized algorithms — Las Vegas, Monte Carlo

Step 2 — Trials stack karna: count $N$ geometric shape kyun follow karta hai

KYA. Ab hum trials ek ke baad ek run karte hain aur jaise hi ek succeed hoti hai ruk jaate hain. Humne jitni trials use ki hain woh $N$ hai. Hum poochhte hain: $N = 1$ ki kitni likely hai? $N = 2$ ? $N = 3$ ?

KYUN. $N$ ko average karne ke liye hume yeh jaanna hoga ki iski probability kaise spread out hai — har possible value kitni likely hai. Us spread ka ek naam hai, geometric distribution, aur iski shape poori derivation ka engine hai.

PICTURE. Neeche har bar ek scenario hai. $N = 1$ matlab "abhi jeet": chance $p$ . $N = 2$ matlab "fail, phir jeet": dart ko miss karna chahiye (gray, chance $1 - p$ ) aur phir hit karna chahiye (blue, chance $p$ ), toh $p (1 - p)$ . Har extra failure ek aur gray $(1 - p)$ se multiply ho jaati hai.

Step 3 — "Expected value" ka matlab, compute karne se pehle

KYA. $E [N]$ un saari bars ka balance point hai — woh value jahan $N$ endless replays par average ho jaata. Yeh ek weighted average hai: har possible $N = k$ (for $k = 1, 2, 3, \dots$ ) ko iski likelihood se weight kiya gaya hai.

KYUN. Hume formula se pehle meaning pin karni hogi, warna algebra sirf symbol-pushing hai. Poori backing ke liye Probability and Expectation dekho: $E [N] = \sum_{k = 1}^{\infty} k \cdot Pr [N = k]$ — "har outcome ko uski chance se multiply karke add karo."

PICTURE. Step 2 ki shrinking bars ko socho jaise $1, 2, 3, \dots$ positions par see-saw par rakhe weights. Neeche triangular pivot wahan baitha hai jahan see-saw balance karta hai. Us pivot ki position hi $E [N]$ hai.

Step 4 — Memoryless trick: kyun hum poore future ko ek $E$ mein fold kar sakte hain

KYA. Ek infinite series sum karne ki jagah, hum kuch almost magical notice karte hain: ek failure ke baad, process apne hi beginning ki perfect copy hai. Dice ko miss yaad nahi hai.

KYUN. Yeh self-similarity hume ek chhoti si equation likhne deti hai jo khud ko reference karti hai — ek infinite sum ki jagah ek line. Yeh derivation ka dil hai aur woh step hai jise zyaadatar log skip kar dete hain.

PICTURE. Ek flowchart: start → ek trial karo. Blue arrow (chance $p$ ): "done, cost $1$ ." Gray arrow (chance $1 - p$ ): ek identical start par wapas loop — aur wahan se expected extra work phir exactly $E$ (yani $E [N]$ ) hai, kyunki situation ke baare mein kuch nahi badla.

Step 5 — Self-referential equation likhna aur solve karna

KYA. Hum flowchart ko algebra mein badal kar $E$ ke liye solve karte hain (yaad karo $E$ sirf $E [N]$ hai).

KYUN. Flowchart ki har branch contribute karti hai (uski probability) $\times$ (trials mein uski cost). Dono branches ko sum karna ek unknown $E$ mein ek equation deta hai — saaf tarike se solvable.

PICTURE. Wohi do arrows, ab har ek average mein jo contribute karta hai usse tag kiya gaya.

Do branches:

$E = win now: prob p, cost 1 p \cdot 1 + fail: prob 1 - p, cost 1 now + E later (1 - p) (1 + E)$

Term by term: winning branch par hum sirf current trial ( $1$ ) pay karte hain; failing branch par hum current trial ( $1$ ) aur ek fresh expected wait $E$ (loop-back) face karte hain. Ab expand karo:

$E = p + (1 - p) + (1 - p) E$

$p + (1 - p)$ collapse hokar $1$ ho jaata hai (Step 1 ki poori bar ke do pieces):

$E = 1 + (1 - p) E$

$E$ terms ko saath laao — yeh unknown ko isolate karta hai:

$E - (1 - p) E = 1 ⟹ E [1 - (1 - p)] = 1 ⟹ E \cdot p = 1$

$E [N] = \frac{1}{p}$

Step 6 — Picture ke against sanity-check: kya $\frac{1}{p}$ see-saw balance karta hai?

KYA. Hum formula ko dial ke dono ends par test karte hain aur confirm karte hain ki yeh Step 3 ke pivot picture se match karta hai.

KYUN. Ek formula jise tum sanity-check nahi kar sakte woh formula hai jis par tum trust nahi karte. Extreme $p$ plug in karna hume instantly bata deta hai ki algebra sane hai ya nahi.

PICTURE. Ek saath do see-saws. Left: $p = \frac{1}{2}$ , bars gently decay karti hain, pivot $2$ par baitha hai. Right: $p = \frac{1}{4}$ , bars slowly decay karti hain, pivot $4$ tak right slide karta hai. Chhota $p$ ⇒ far bars zyada heavy ⇒ pivot aur bahar — exactly wahi jo $\frac{1}{p}$ predict karta hai.

$p = \frac{1}{2} \Rightarrow E = 2$ . Ek fair coin: average mein heads dekhne ke liye do flips. Gut feeling se match karta hai. ✅
$p = \frac{1}{4} \Rightarrow E = 4$ . Right-hand pivot se match karta hai. ✅

Step 7 — Woh edge cases jo formula quietly chhupaata hai

KYA. Hum boundaries $p \to 1$ aur $p \to 0$ probe karte hain, aur forbidden $p = 0$ .

KYUN. The Contract: reader ko kabhi aisa scenario nahi milna chahiye jise hum skip kar gaye. Ek denominator $\frac{1}{p}$ chillata hai "zero ke paas kya hota hai?" — hume jawab dena hai.

PICTURE. $E = \frac{1}{p}$ ka ek curve $p$ ke against plot kiya gaya: $p = 1$ ke paas yeh $1$ par flatten ho jaata hai; $p \to 0^{+}$ ke roop mein yeh infinity tak rocket karta hai (red mein vertical asymptote).

Case	$E = \frac{1}{p}$	Matlab
$p = 1$ (hamesha jeetna)	$1$	Ek trial, guaranteed. Sensible floor.
$p \to 0^{+}$ (almost kabhi nahi jeetna)	$\to \infty$	Wait without bound grow karti hai. Red asymptote.
$p = 0$ (kabhi nahi jeetna)	undefined	Loop kabhi halt nahi hota — expectation infinite hai. Formula sahi hi $0$ se divide karne se mana karta hai.

Ek-picture summary

Har idea, ek frame mein: split bar (Step 1) shrinking geometric bars ko feed karti hai (Step 2), jo ek pivot par balance karti hain (Step 3); memoryless loop (Step 4) ek one-line equation ban jaata hai (Step 5) jiska solution $\frac{1}{p}$ (Step 6) blow-up curve trace karta hai (Step 7).

Recall Feynman retelling — aise bolo jaise kisi dost ko explain karo

Tum kuch aisa try karte rehte ho jo $p$ mein se ek baar kaam karta hai. Poochho "average mein kitni tries?" Pehli try $p$ chance se jeetti hai; agar flop ho jaata hai — aur ek random trial apne flops kabhi yaad nahi rakhta — tum waapis wahan ho jahan se shuru kiya, dobara wahi average wait face karte hue. Toh average equal hai "ek try pakki, plus (chance tum fail hue) times (poora average phir se)." Woh sentence hi equation $E = 1 + (1 - p) E$ hai. Solve karo aur failure part peel away ho jaata hai, $E \cdot p = 1$ baar kar, toh average $\frac{1}{p}$ hai. Check karo: ek fair coin, $p = \frac{1}{2}$ , $2$ flips deta hai — obviously sach. $p$ ko zero ki taraf push karo aur wait infinity tak explode karta hai, jo exactly ek rare event ki danger hai. Woh single number $\frac{1}{p}$ hi reason hai ki Las Vegas retry loops fast kyun hain jab success common ho aur hopeless jab yeh vanishingly rare ho.

Recall Quick self-test

Sabse bada probability bar hamesha $N = 1$ kyun hota hai? ::: Kyunki har extra trial $(1 - p) < 1$ se multiply hoti hai, toh bars sirf shrink kar sakti hain — koi middle hump nahi. Equation $E = 1 + (1 - p) E$ kahan se aati hai? ::: Memoryless property: ek failure ke baad expected remaining trials phir $E$ hai, toh failing branch $1 + E$ cost karti hai. $E [N]$ kya hai jab $p = \frac{1}{4}$ ? ::: $\frac{1}{1/4} = 4$ trials. $p = 0$ formula kyun tod deta hai? ::: Loop kabhi succeed nahi hota, $E [N] = \infty$ , aur $\frac{1}{0}$ undefined hai.

Related tools jo is exact bound ko reuse karte hain: Primality Testing, Min-Cut and Max-Flow, aur tail-refinements Markov's Inequality aur Chernoff Bounds mein.