Randomized algorithms — Las Vegas, Monte Carlo: Worked examples

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

Yeh page parent topic ka drill floor hai. Hum har tarah ki situation cover karenge jo do algorithm classes throw kar sakti hain: perfect success, tiny success, ek repetition, kaafi repetitions, degenerate "impossible" cases ( $p = 0$ , $p = 1$ ), error ki do directions, ek class ko doosri mein convert karna, aur ek real word problem. Har answer se pehle guess karo — forecast karna hi aadhi learning hai.

Yahan sab kuch parent note ke teen tools pe tikaa hai, jinhe hum neeche use karte waqt phir se earn karte hain: geometric expectation $E [N] = \frac{1}{p}$ , exponential boosting $Pr [error] \leq q^{k}$ , aur Markov's inequality. Agar koi symbol aisa aaye jo tumne pehle na dekha ho, ruko aur phir se padho — I promise to have built it first.

Scenario matrix

Kuch bhi solve karne se pehle, yeh poora map hai cases ka. Har worked example neeche tagged hai us cell se jise woh cover karta hai, taaki tum dekh sako ki kuch bhi skip nahi hua.

Cell	Class	Kya random hai	Jo tricky part test ho raha hai
A	Las Vegas	running time	typical success prob $0 < p < 1$ : expected trials
B	Las Vegas	running time	degenerate $p \to 0$ (almost never works) aur $p = 1$ (always works)
C	Las Vegas	running time	expected work jab har trial ka cost $c$ ho, $1$ nahi
D	Monte Carlo	the answer	one-sided error, single run
E	Monte Carlo	the answer	one-sided boosting: kitne runs $k$ chahiye target $ε$ ke liye
F	Monte Carlo	the answer	two-sided error — kyun majority vote, last run nahi
G	Conversion	—	LV → MC via a time budget + Markov's inequality
H	Conversion	—	MC → LV via cheap verification
I	Real-world	mixed	ek word problem jo tumhe class choose karne par majboor karta hai
J	Exam twist	—	" $p = 0.5$ , $k = 20$ " magic number, aur ek limiting sanity check

Har cell ko jo tool chahiye — is flow chart ko aise padho ki "har family of examples ek tool pull down karti hai":

Chart ko node by node kaise padhen.

T1 ("E of N equals 1 over p") geometric expectation hai. Examples 1, 2, 3 (cells A, B, C) aur Example 8 (cell H) sab yahi lever kheenchte hain — trials count karo, $1$ ko success chance se divide karo.
T2 ("error at most q to the k") exponential boosting hai. Examples 4 aur 5 (cells D, E) aur Example 10 (cell J) iska use karte hain — per-run error ko khud se $k$ baar multiply karo.
T3 ("Chernoff majority") voting tool hai. Example 6 (cell F) iska use karta hai — jab koi single answer trustworthy nahi hoti, ballots count karo aur Chernoff Bounds guarantee pe lean karo.
T4 ("Markov inequality") tail bound hai. Example 7 (cell G) iska use karta hai — sirf mean use karke time budget overrun hone ka chance bound karo. Example 9 (cell I, real-world) tools mix karta hai taaki class choice force ho.

Deeper machinery hum link karte hain jahan woh rehti hai: Probability and Expectation, Markov's Inequality, Chernoff Bounds.

Building block figures

Do pictures hain jo har Las Vegas / Monte Carlo calculation carry karti hain. Inhe open rakhna.

Figure — Randomized algorithms — Las Vegas, Monte Carlo

Figure s01 — Do random worlds. Left panel: magenta curve hai

E [N] = 1/ p

; horizontal axis success probability

p

hai

0.05

1

tak, vertical axis expected trials hai. Jaise

p

left ki taraf shrink hota hai, curve upar rocket karta hai (cell B ka blow-up). Violet dot mark karta hai

p = 0.5 \to 2

trials. Right panel: curves hain

q^{k}

(error after

k

runs) log vertical axis par; magenta hai

q = 0.5

, violet hai

q = 0.25

, aur orange dashed line hai target

ε = 1 0^{- 6}

. Dono curves dive karti hain kyunki hum

1

se chhota number khud se multiply karte hain (cells D–E). Left = Las Vegas (time random), right = Monte Carlo (answer random).

Worked examples

Cell A — Las Vegas, typical success probability

Worked example Example 1 — Retry-until-success (

$0 < p < 1$ ) Ek randomized layout routine ek component place karti hai; har independent attempt probability $p = 0.3$ se succeed karta hai. Hum tab tak retry karte hain jab tak ek succeed na kare. Expected number of attempts kya hai?

Forecast: Padhne se pehle guess karo — kya yeh $3$ ke kareeb hai ya $10$ ke?

Setup. == $N$ == ko pehli success tak ke attempts ki count maano (success include karte hue). Har attempt ek independent coin hai success chance $p$ ke saath, isliye $N$ woh geometric random variable hai jo upar define ki gayi hai, $Pr [N = n] = (1 - p)^{n - 1} p$ ke saath.

Self-referential equation likho. $E [N] = win now p \cdot 1 + fail, restart (1 - p) (1 + E [N])$ Yeh step kyun? Failure ke baad process sab kuch bhool jaata hai — situation exactly shuru jaisi hi hoti hai (memorylessness), isliye remaining expectation phir $E [N]$ hai.
Solve karo. $E [N] = 1 + (1 - p) E [N] \Rightarrow E [N] \cdot p = 1 \Rightarrow E [N] = \frac{1}{p} .$ Yeh step kyun? $E [N]$ terms collect karne se recursion plain algebra ban jaata hai.
$p = 0.3$ plug karo: $E [N] = 1/0.3 = 3. \overline{3} .$

Verify: Extremes ka sanity check. Agar $p = 1$ toh formula $1$ attempt deta hai — correct, tum instantly jeet jaate ho. Agar $p = 0.5$ toh $2$ deta hai — "fair coin flip until heads" se match karta hai. Hamara answer $3.33$ sensibly "always" aur "rare" ke beech baithta hai. ✓

Cell B — Las Vegas, degenerate $p \to 0$ aur $p = 1$

Worked example Example 2 — Do boundary cases

$E [N] = 1/ p$ use karke, describe karo kya hota hai (a) jab $p = 1$ ho, aur (b) jab $p \to 0^{+}$ ho.

Forecast: Inme se ek finite number deta hai; doosra explode karta hai. Kaunsa kaunsa hai?

$p = 1$ : $E [N] = 1/1 = 1$ . Har attempt succeed karta hai, isliye tum exactly ek trial mein hamesha finish karte ho. Yeh Las Vegas frame ke andar chhupa ek deterministic algorithm hai — zero variance. Yeh step kyun? $p = 1$ check karna confirm karta hai ki formula gracefully "no randomness" limit mein degrade karta hai.
$p \to 0^{+}$ : $E [N] = 1/ p \to + \infty$ . Agar success essentially impossible hai, tum expect karte ho forever wait karna. Figure mein left curve ka left edge dekho — woh sky ko shoot karta hai. Yeh step kyun? Yeh dikhata hai model honest hai: ek hopeless retry loop ka unbounded expected time hota hai, yahi reason hai ki pure Las Vegas ko $p$ bounded away from $0$ chahiye.
Exactly $p = 0$ : ab do statements carefully distinguish karo.
- Limit ke taur par, $lim_{p \to 0^{+}} E [N] = + \infty$ : expected wait grows without bound. Yeh ek meaningful, well-defined statement hai — expectation infinite hai.
- Plug-in ke taur par, $1/0$ koi number nahi hai, aur event "first success" kabhi occur nahi hoti (loop kabhi terminate nahi hota), isliye literally koi trial-count average karne ko nahi. Us exact sense mein $E [N]$ ek finite value ki jagah undefined hai. Yeh step kyun? "Infinite expectation" (ek limit jo diverge karta hai) aur "undefined reciprocal" (koi success kabhi nahi) do alag cheezein hain; ek careful reader inhe alag rakhna chahiye.

Verify: Monotonic sanity — jaise $p$ $1$ se $0$ ki taraf decrease hota hai, $1/ p$ $1$ se $\infty$ ki taraf increase karta hai bina kisi dip ke. $p = 0.5$ par yeh $2$ hai, $p = 0.1$ par $10$ hai, $p = 0.01$ par $100$ hai. Har chhota $p$ larger wait deta hai. ✓

Cell C — Las Vegas, cost per trial

Worked example Example 3 — Expected

work, sirf trials nahi Ek Las Vegas subroutine ka har attempt $c = 50$ operations cost karta hai aur $p = 0.25$ se succeed karta hai. Expected total work kya hai?

Forecast: Kya yeh $200$ ke kareeb hoga ya $50$ operations ke?

Expected trials: $E [N] = 1/ p = 1/0.25 = 4$ . Yeh step kyun? Cell A ka result — attempts ki count independent hai is baat se ki har ek cost kitna hai.
Per-trial cost se multiply karo. Kyunki har trial (success ya failure) same $c$ cost karta hai, total work $= c \cdot N$ , aur expectation linear hai: $E [work] = c \cdot E [N] = \frac{c}{p} = \frac{50}{0.25} = 200.$ Yeh step kyun? Linearity of expectation (Probability and Expectation) constant $c$ ko expectation se seedha bahar nikalne deta hai, koi independence gymnastics nahi chahiye.

Verify: Units check — $c$ hai operations/trial, $E [N]$ hai trials, product hai operations. ✓ Cross-check: $4$ trials $\times 50$ ops $= 200$ ops. ✓

Cell D — Monte Carlo, one-sided error, single run

Worked example Example 4 — Miller–Rabin ka ek round

Ek composite number $n$ test karte hue, ek random base "witness" hai (correctly expose karta hai $n$ ko composite ke roop mein) probability $\geq 3/4$ se. Toh ek round wrongly declare karta hai $n$ ko "prime" probability $q \leq 1/4$ se. Single round ki worst-case error kya hai, aur yeh kis direction mein fail ho sakta hai?

Forecast: Kya yeh test kabhi ek prime ko "composite" bol sakta hai? Haan ya nahi?

Ek run ki error: $q \leq 1/4 = 0.25$ . Yeh step kyun? Ek run fixed time mein finish hota hai; answer risky part hai — Monte Carlo ki hallmark (dekho Primality Testing).
Error ki direction. Ek genuine prime ka koi witness hota hi nahi, isliye test kabhi wrongly "composite" nahi bol sakta. Woh sirf wrongly "probably prime" bol sakta hai kisi aise composite ke liye jo witness se bach gaya. Yeh step kyun? Yahi one-sided ka matlab hai: do answers mein se ek ("composite") hamesha trustworthy hota hai; sirf doosra ("prime") risk carry karta hai.

Verify: Bound sanity — error probability $[0, 1]$ mein honi chahiye; $0.25$ qualify karta hai. Aur "certain" side (composite) ka error $0$ hai, one-sidedness ke saath consistent. ✓

Cell E — Monte Carlo, one-sided boosting

Worked example Example 5 — One-in-a-million ke liye kitne rounds?

Per-run error $q = 1/4$ ke saath, hum "prime" tabhi accept karte hain jab sab $k$ rounds "prime" kahein. Kitne rounds $k$ error ko $\leq ε = 1 0^{- 6}$ banate hain?

Forecast: Guess karo: $k$ around $5$ , $10$ , ya $20$ hai?

Sab $k$ independent runs ko saath mein fail karna hoga humein fool karne ke liye: $Pr [still wrong] \leq q^{k} = (1/4)^{k} .$ Yeh step kyun? Independent events multiply hote hain — yahi exponential collapse hai jo figure mein right curve ke roop mein draw hai.
Require karo $q^{k} \leq ε$ . Logs lo (log "kitni baar multiply hua" ko "axis par kitna aage" mein badal deta hai): $k \geq \frac{l n ( 1/ ε )}{l n ( 1/ q )} .$ Yeh ek clean positive number kyun hai? Log rule use karo $ln (1/ x) = - ln (x)$ . Kyunki $q = 1/4 < 1$ , hame $ln q < 0$ milta hai, isliye $ln (1/ q) = - ln q > 0$ . Similarly $ε < 1$ se $ln (1/ ε) > 0$ milta hai. Positive top over positive bottom ek positive $k$ hai — koi sign confusion nahi.
Evaluate karo: $k \geq \frac{l n ( 1 0 ^{6} )}{l n 4} = \frac{13.8155}{1.3863} = 9.966 \dots$
Round up (tum fractional round nahi run kar sakte): $k = ⌈ 9.966 ⌉ = 10$ .

Verify: Plug back karo — $(1/4)^{10} = 1/1048576 \approx 9.54 \times 1 0^{- 7} \leq 1 0^{- 6}$ . ✓ Aur $(1/4)^{9} \approx 3.8 \times 1 0^{- 6} > 1 0^{- 6}$ , isliye $9$ rounds enough nahi — $10$ tight hai. ✓

Figure s02 — One-sided boosting bars. Horizontal axis rounds $k$ ka number hai ( $1$ se $12$ tak); vertical axis error bound $(1/4)^{k}$ hai log scale par. Har bar apne left wale bar ki height ka one-quarter hai — error har round mein $4$ ka factor drop karta hai. Orange dashed line target $ε = 1 0^{- 6}$ hai. Magenta bars ( $k \leq 9$ ) abhi bhi line se upar hain; violet bars ( $k \geq 10$ ) neeche hain. Round $9$ aur round $10$ ke beech crossover exact reason hai ki $k = 10$ tight minimum kyun hai.

Cell F — Monte Carlo, two-sided error (voting kyun)

Worked example Example 6 — Two-sided test ke liye majority vote

Ek two-sided Monte Carlo test har run par probability $p = 0.6$ se correct hota hai (toh yeh kisi bhi direction mein err kar sakta hai). Hum ise $k = 5$ baar run karte hain aur majority answer lete hain. Majority ke correct hone ka chance kya hai?

Forecast: Single run ke $0.6$ se better ya worse?

$5$ mein se majority correct hai tab aur sirf tab jab $5$ mein se kam se kam $3$ runs correct hon. Har run ek independent correct/wrong coin hai correct-prob $p = 0.6$ ke saath. Correct runs $= M$ count karo, jo binomial variable hai. Yeh step kyun? One-sided error ke unlike, hum kisi bhi single answer pe trust nahi kar sakte, isliye hum ballots decide karne dete hain.
$M \geq 3$ ke liye binomial probabilities sum karo: $Pr [M \geq 3] = \sum_{m = 3}^{5} (m 5) (0.6)^{m} (0.4)^{5 - m} .$ Term by term compute karo:
- $m = 3 : (3 5) (0.6)^{3} (0.4)^{2} = 10 \cdot 0.216 \cdot 0.16 = 0.3456$
- $m = 4 : (4 5) (0.6)^{4} (0.4)^{1} = 5 \cdot 0.1296 \cdot 0.4 = 0.2592$
- $m = 5 : (5 5) (0.6)^{5} = 0.07776$ Sum $= 0.68256$ . Yeh step kyun? "3, 4, ya 5 correct" cases add karne se har tarika cover hota hai jis se majority sahi land kare.
Compare karo: $0.6826 > 0.6$ . Voting ne single run ko beat kiya.
Chernoff kahan aata hai. Exact binomial sum upar is $k = 5$ ka answer deta hai. Lekin general $k$ ke liye hum har baar re-sum nahi karna chahte — Chernoff bound ek clean closed form deta hai. Advantage $δ = p - \frac{1}{2}$ define karo (har run coin flip se kitna lean karta hai); yahan $δ = 0.6 - 0.5 = 0.1$ . Per-run correctness $p > \frac{1}{2}$ ke saath, $k$ runs par majority voting fail karta hai probability $Pr [majority wrong] \leq e^{- 2 δ^{2} k}$ se. $δ = 0.1$ plug karne se bound milta hai $e^{- 2 (0.1)^{2} k} = e^{- 0.02 k}$ , jo $k$ mein exponentially shrink karta hai. Yahi promised tool hai: ek single number ke liye exact sum, trend ke liye Chernoff exponential. Yeh step kyun? Yeh concrete computation ko general guarantee se tie karta hai — bina closed form ke hum kabhi nahi dekh sakte ki voting error ko $0$ ki taraf drive karta hai jaise $k$ badhta hai; Chernoff bound us decay ko ek line mein visible karta hai, kisi bhi $p > \frac{1}{2}$ ke liye.

Verify: Teeno terms $[0, 1]$ mein probabilities hain aur unka sum $0.6826 \in [0, 1]$ . ✓ Yeh single-run $0.6$ se zyada hai, amplification confirm karta hai. ✓ Chernoff sanity: $e^{- 2 (0.1)^{2} \cdot 5} = e^{- 0.1} \approx 0.905$ , matlab failure $\leq 0.905$ — exact failure $1 - 0.6826 = 0.3174$ se looser, jaise upper bound hona chahiye. ✓ (Last run lena tumhe exactly $0.6$ par chhod deta — woh galti jo parent note warn karta hai.)

Cell G — Conversion: Las Vegas → Monte Carlo

Worked example Example 7 — Time budget ke saath cutoff (Markov)

Ek Las Vegas algorithm ka expected running time $E [T] = 100$ ms hai. Hum ise budget $a \cdot E [T]$ dete hain aur agar yeh finish nahi hua toh guess output karte hain. $a$ choose karo taaki "guess" (possibly wrong) at most $10%$ of the time ho.

Forecast: Kya humein expected time ka $2 \times$ ya $10 \times$ budget chahiye?

Markov's Inequality kehti hai: non-negative time $T$ ke liye, $Pr [T \geq a E [T]] \leq \frac{1}{a} .$ Yeh step kyun? Markov woh tool hai jo tail ko sirf mean use karke bound karta hai — perfect jab humein bas $E [T]$ pata ho.
Tail ko $10% = 0.1$ se below force karo: $1/ a \leq 0.1 \Rightarrow a \geq 10$ set karo. $a = 10$ lo. Yeh step kyun? $1/ a$ overrun ki worst-case probability hai; $a$ large banana overruns ko rare banata hai.
Budget $= a \cdot E [T] = 10 \times 100 = 1000$ ms. Ab runtime $1000$ ms par fixed hai aur answer wrong sirf tab hota hai jab hum overrun karte hain (prob $\leq 0.1$ ) — yeh ek Monte Carlo algorithm hai.

Intuition — cutoff do axes ko kya karta hai. Figure s03 run-time distribution ko ek curve ke roop mein draw karta hai. Ek pure Las Vegas run mein right ki taraf long tail hota hai (kabhi kabhi bahut slow) lekin woh hamesha correct hota hai. Vertical budget line $a E [T]$ par slice karna us tail ko chop kar deta hai: line ke left mein sab normally finish karta hai (correct); shaded sliver right ki taraf — Markov ke hisaab se at most $1/ a$ total area — wahan hum time out karte hain aur guess karna padta hai (possibly wrong). Humne literally random time (long tail) ko ek chhota random error (shaded area) se trade kiya hai. Woh swap hai hi LV → MC.

Figure s03 — Tail ko slice karna. Horizontal axis: running time $E [T]$ ke units mein; curve chance hai ki run abhi bhi chal raha hai. Violet vertical line budget $a E [T]$ hai $a = 10$ ke saath. Line ke left mein area = "finished, correct"; right mein orange shaded sliver = "overran, guess" — Markov us sliver ko $1/ a = 0.1$ par cap karta hai.

Verify: Bound value $1/ a = 1/10 = 0.1 \leq 0.1$ . ✓ Units: $10$ (dimensionless) $\times 100$ ms $= 1000$ ms. ✓ Larger $a$ → smaller error, intuition se match karta hai. ✓

Cell H — Conversion: Monte Carlo → Las Vegas

Worked example Example 8 — Verify-and-repeat

Ek Monte Carlo algorithm ek candidate answer return karta hai jo probability $p = 0.9$ se correct hai, aur hum kisi bhi answer ko $O (1)$ mein check kar sakte hain. Hum loop karte hain: run karo, check karo, ruko jab check pass ho jaye. Expected number of runs kya hai, aur kya result hamesha correct hota hai?

Forecast: Kya yeh kabhi wrong answer return karega?

Correctness: hum sirf tab rukenge jab verifier answer confirm kare, isliye output hamesha correct hai — randomness ab purely kitna time loop kare mein rehti hai. Yeh precisely ek Las Vegas algorithm hai. Yeh step kyun? Verification "maybe wrong" ko "definitely right, but random time" mein convert karta hai, wahi swap jo do classes define karta hai.
Expected runs. Har loop "succeed" karta hai (verifier pass) probability $p = 0.9$ se, isliye cell A ke geometric result se: $E [N] = \frac{1}{p} = \frac{1}{0.9} = 1.111 \dots$ Yeh step kyun? Verify-loop hai hi ek retry-until-success loop; hum $E [N] = 1/ p$ verbatim reuse karte hain.

Verify: $1/0.9 = 1.1 \overline{1}$ , just $1$ se above — sensible, kyunki usually pehla run already pass ho jaata hai. ✓ Output correctness deterministic hai (checker se guaranteed), isliye error $= 0$ . ✓

Cell I — Real-world word problem

Worked example Example 9 — Shipping firm kaunsa class chahti hai?

Ek firm $1 0^{6}$ parcels per hour sort karti hai. Option X hamesha perfectly sort karta hai lekin kabhi kabhi usual se $3 \times$ zyada time leta hai (yaani $2$ extra hours), aur yeh overrun $20%$ hours mein hota hai. Option Y hamesha exactly $1$ hour mein finish karta hai lekin $1000$ mein $1$ parcel misroute karta hai. Agar ek misrouted parcel $\$ 5 $cos t k a r t ahaia u r * e k g han t e k i d e l a y *$ $400$ cost karti hai, har option classify karo aur decide karo firm ko per hour kaunsa pick karna chahiye.

Forecast: Kya "always correct" option automatically win karta hai?

Classify karo. Option X = Las Vegas (hamesha correct, variable time). Option Y = Monte Carlo (fixed time, small error rate). Yeh step kyun? Class name karna batata hai ki risk kahan rehta hai numbers touch karne se pehle.
Y ki errors ka cost per hour: expected misroutes $= 1 0^{6} \times \frac{1}{1000} = 1000$ parcels, $\$ 5 $e a c h se$ = $5000 $. * Y e h s t e p k y u n ? * E x p ec t e d co u n t$ = $t r ia l s$ \times$ per-trial error prob (linearity phir se).
X ki delay ka cost. $2$ -extra-hour overrun probability $0.2$ se hota hai; expected delay cost $= 0.2 \times 2 \times \$ 400 = $160$ per hour. Yeh step kyun? Har outcome ko uski probability se weight karo — "expected cost" ka yahi matlab hai.
Compare karo: $\$ 160 $(L a s V e g a s X) v s$ $5000$ (Monte Carlo Y). X choose karo, Las Vegas option: yahan correctness punctuality se kahin zyada worth hai.

Verify: Units sab dollars/hour mein. ✓ $1 0^{6} /1000 = 1000$ misroutes, $\times 5 = 5000$ . ✓ $0.2 \cdot 2 \cdot 400 = 160$ . ✓ $160 < 5000$ , isliye X decisively jeet jaata hai. ✓

Cell J — Exam twist: " $k = 20$ " magic number & ek limiting check

Worked example Example 10 — "20 runs → one-in-a-million" kahan se aata hai?

Parent note claim karta hai: $q = 1/2$ ke saath, $k = 20$ baar run karne par error $\leq 2^{- 20} \approx 1 0^{- 6}$ hoti hai. Ise derive karo, phir check karo limiting behaviour $k \to \infty$ par.

Forecast: $2^{- 20}$ $1 0^{- 6}$ se above hai ya below?

$q = 1/2$ ke saath: $q^{k} = 2^{- k}$ . $k = 20$ par, error $\leq 2^{- 20}$ . Yeh step kyun? Har run error half karna fastest simple boosting hai — har round confidence double karta hai. Yeh flow chart se phir wही tool T2 hai.
Evaluate karo: $2^{- 20} = 1/1048576 \approx 9.537 \times 1 0^{- 7}$ . Kyunki $9.537 \times 1 0^{- 7} < 1 0^{- 6}$ , bees runs one-in-a-million bar clear kar dete hain. Yeh step kyun? Confirm karta hai ki headline number $1 0^{- 6}$ se just under hai, koi loose exaggeration nahi.
Limit $k \to \infty$ : $2^{- k} \to 0$ . Error ko arbitrarily close to $0$ push kiya ja sakta hai, lekin one-sided Monte Carlo ke liye kabhi exactly $0$ nahi — hamesha ek vanishing chance hoti hai ki har run fool ho gaya. Yeh step kyun? Yeh Monte Carlo (error $\to 0$ ) aur Las Vegas (error $= 0$ ) ke beech boundary mark karta hai: sirf verification, repetition nahi, true zero tak pahuncha sakta hai.

Verify: $2^{- 20} = 9.5367 \times 1 0^{- 7} \leq 1 0^{- 6}$ . ✓ Aur $2^{- 19} = 1.907 \times 1 0^{- 6} > 1 0^{- 6}$ , isliye $k = 19$ fail karta — $20$ $q = 1/2$ ke liye tight minimum hai. ✓

Recall Quick self-test

One-sided MC test errs with $q = 1/3$ per run; kitne runs ke liye error $\leq 1 0^{- 4}$ ho? ::: $k \geq \frac{l n ( 1 0 ^{4} )}{l n 3} = \frac{9.21}{1.0986} \approx 8.39 \Rightarrow k = 9$ . Las Vegas retry with $p = 0.2$ , cost $c = 10$ per trial — expected work? ::: $c / p = 10/0.2 = 50$ . Two-sided MC, $k = 3$ , correct-prob $0.7$ , majority — kya single run se beat karta hai? ::: $Pr [M \geq 2] = 3 (0.7)^{2} (0.3) + (0.7)^{3} = 0.441 + 0.343 = 0.784 > 0.7$ , haan. LV → MC via Markov: overrun $\leq 5%$ ke liye budget? ::: $1/ a \leq 0.05 \Rightarrow a \geq 20$ , budget $= 20 E [T]$ .

Related deep material: QuickSort, Quickselect, Min-Cut and Max-Flow, Amortized vs Expected Analysis, aur Hinglish companion 3.7.19 Randomized algorithms — Las Vegas, Monte Carlo (Hinglish).