Randomized algorithms — Las Vegas, Monte Carlo

3.7.19 · Coding › Algorithm Paradigms

Ye do classes actually hain kya?

Figure — Randomized algorithms — Las Vegas, Monte Carlo

Las Vegas algorithm ka analysis kaise karte hain — expected time nikalna

Sabse simple Las Vegas idea lo: tab tak random attempt retry karte raho jab tak succeed na ho. Maano har independent attempt probability $p$ se succeed karti hai aur $c$ kaam karta hai.

Geometric distribution kyun? Har trial ek independent coin flip hai — "success" prob $p$ se. Trials ki sankhya $N$ pehli success tak geometric hoti hai.

$E [N]$ ki derivation scratch se. Maano $E = E [N]$ .

Prob $p$ se: hum trial 1 par succeed karte hain, cost = $1$ trial.
Prob $1 - p$ se: hum fail karte hain (cost 1 trial) aur wapas start par hain, toh extra $E$ trials expected hain.

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

Ye step kyun? Process memoryless hai: failure ke baad situation bilkul start jaisi hai, isliye remaining expectation phir se $E$ hai. Ye self-reference algebraically solve karne deta hai.

Expand karo: $E = p + (1 - p) + (1 - p) E = 1 + (1 - p) E$ $E - (1 - p) E = 1 ⟹ E \cdot p = 1 ⟹ E [N] = \frac{1}{p}$

Toh expected total work $= \frac{c}{p}$ .

Monte Carlo algorithm ka analysis kaise karte hain — confidence boost karna

Maano EK run probability $\leq q$ se galat hoti hai (aur runs independent hain). Ise $k$ baar chalao.

One-sided error (e.g. test jo "yes" kahta hai galat ho sakta hai, lekin "no" hamesha pakka hai): "yes" tabhi lo jab saare $k$ runs "yes" kahein. Chance ki saare $k$ galat "yes" hain: $Pr [abhi bhi galat] \leq q^{k}$

Ye multiply kyun hota hai? Independent runs ⇒ joint probability product hoti hai. Har galat run ki prob $\leq q$ hai, toh $k$ simultaneous galat runs ki prob $\leq q^{k}$ hai, jo exponentially shrink hoti hai.

Error ko target $ε$ se neeche karne ke liye: $q^{k} \leq ε ⟹ k \geq \frac{l n ε}{l n q} = \frac{l n ( 1/ ε )}{l n ( 1/ q )}$

Dono ke beech convert karna

Worked examples

Worked example Example 3 — Karger's Min-Cut (Monte Carlo, one-sided)

Edges randomly contract karo jab tak 2 nodes na bachen; crossing edges ko cut report karo. Ek run sahi min-cut return karta hai prob $\geq \frac{1}{( 2 n )} = \frac{2}{n ( n - 1 )}$ se. One-sided kyun? Jo bhi cut ye report karta hai woh graph ka real cut hai, toh algorithm kabhi minimum se kam nahi de sakta — sirf ek cut jo zyada bada hai de sakta hai, chhota nahi. Isliye "error" ek direction mein hai. Hum iska fayda uthate hain kai runs mein sabse chhota cut rakh ke: koi bhi ek lucky run jo sahi minimum hit kare woh hamesha ke liye correct hai. Ek single run ki success prob chhoti hai, toh ise $T = (2 n) ln n$ baar chalao: $Pr [all T runs miss] \leq (1 - \frac{1}{( 2 n )})^{T} \leq e^{- l n n} = \frac{1}{n}$ $1 - x \leq e^{- x}$ kyun? Ye standard bound product ko ek clean exponential mein convert karta hai, dikhata hai ki $T = O (n^{2} lo g n)$ repetitions failure ko $1/ n$ se neeche le jaati hain.

Common mistakes (Steel-man + fix)

Flashcards

Las Vegas algorithm — kya random hai?

Running time (ek random variable); output hamesha correct hota hai.

Monte Carlo algorithm — kya random hai?

Answer ki correctness (prob ≤ q se galat ho sakta hai); running time bounded/fixed hota hai.

Pehli success tak expected trials jab har ek prob p se succeed kare

1/ p

(geometric distribution).

Retry loop ke liye E[N] derive karo

E = p \cdot 1 + (1 - p) (1 + E) \Rightarrow E = 1/ p

(memorylessness).

k independent Monte Carlo runs ke baad error (one-sided, har ek ≤ q galat)

\leq q^{k}

Error ≤ ε ke liye kitne runs k chahiye

k \geq ln (1/ ε) / ln (1/ q)

Randomized QuickSort ke expected comparisons

O (n lo g n)

\sum_{i < j} \frac{2}{j - i + 1}

se.

Randomized QuickSort mein do ranks i<j ke compare hone ki probability

\frac{2}{j - i + 1}

Karger's min-cut ki single-run success prob

\geq 1/ (2 n)

Karger's min-cut one-sided ya two-sided error hai?

One-sided — ye ek real cut report karta hai, toh sahi minimum se kabhi chhota return nahi karta, sirf shayad bada.

Las Vegas → Monte Carlo kaise convert karein

Time budget ke baad cut off karo; finish na hone par guess output karo (Markov's inequality error bound karta hai).

Monte Carlo → Las Vegas kaise convert karein

Sirf tab agar answers cheaply verifiable hain: verification pass hone tak repeat karo.

Repeated Karger failure bound karne ke liye inequality

1 - x \leq e^{- x}

Recall Feynman: 12-saal ke bachche ko samjhao

Ek maze imagine karo. Las Vegas robot HAMESHA exit dhundh leta hai — lekin kabhi-kabhi woh bhatakta hai aur zyada time leta hai, kabhi-kabhi fast hota hai. Monte Carlo robot HAMESHA exactly 5 minute mein ruk jaata hai — lekin agar abhi tak exit nahi mila, toh woh bas guess karta hai darwaza kahan hai, aur galat ho sakta hai. Coins kyun use karein? Kyun ki ek bully jo tumhare robot se nafrat karta hai ek aisa maze bana sakta hai jo ek predictable robot ko har baar trap kare. Agar tumhara robot randomly mude, toh bully use trap nahi kar sakta — buri kismat rare ho jaati hai pakki nahi. Aur agar tum darr rahe ho ki Monte Carlo ne galat guess kiya, toh ise kai baar chalao aur vote karo — chance ki SAARE galat hain bahut fast shrink hota hai (aadha, aadha, aadha...).

Connections

Probability and Expectation — linearity of expectation, geometric distribution.
Markov's Inequality aur Chernoff Bounds — cut-off aur majority voting ke liye tail bounds.
QuickSort / Quickselect — classic Las Vegas examples.
Primality Testing — Miller–Rabin as Monte Carlo.
Min-Cut and Max-Flow — Karger's contraction algorithm.
Amortized vs Expected Analysis — coins par expectation, inputs par nahi.