Randomized algorithms — Las Vegas, Monte Carlo: Question bank

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

Definition Is page par use hone wale symbols

$p$ = ek randomized attempt ki per-trial success probability.
$q$ = ek single Monte Carlo run ki per-run error probability (ek run ke galat hone ka chance).
$k$ = hum confidence boost karne ke liye kitne independent runs karte hain.
$ε$ = target error bound jo hum chahte hain ki boosted error isse neeche aaye.
$N$ = random variable jo count karta hai ki Las Vegas retry loop ko apni pehli success tak kitne trials lagte hain (ek random number — har run par alag hota hai).
$E [\cdot]$ = expectation operator: $E [X]$ ka matlab hai "many runs ke upar random quantity $X$ ki average value." Yeh apne aap ek number nahi hai — iske andar ek random variable chahiye. Toh $E [N]$ average trial count hai, aur $E [T]$ average running time hai.
$T$ = ek execution ki running time, ek random variable ki tarah dekha jaata hai; $E [T]$ iska expected value hai. (Jahan hum Karger repetitions count karte hain, hum wahan explicitly bolte hain aur us count ko $T_{rep}$ kehte hain.)

True ya false — justify karo

Las Vegas algorithm kabhi kabhi galat answer de sakta hai.

False. Las Vegas mein randomness sirf running time mein hoti hai; output hamesha correct hota hai. Agar galat ho sakta hai, toh woh Monte Carlo hai.

Monte Carlo algorithm ki running time random aur unpredictable hoti hai.

False. Iski running time design se bounded/fixed hoti hai — yahi woh cheez hai jo tum possibly-wrong answer accept karke khareedto ho. Las Vegas ka mirror image.

Randomized QuickSort Las Vegas hai.

True. Output har run par fully sorted array hota hai; sirf comparisons ki sankhya random hoti hai. Hamesha correct, time variable ⇒ Las Vegas.

Miller–Rabin primality Las Vegas hai kyunki yeh randomized hai.

False. Yeh har round mein fixed time mein chalta hai lekin galti se ek composite ko "prime" bol sakta hai. Galat answer possible hai ⇒ Monte Carlo, Las Vegas nahi.

Las Vegas retry loop ke liye, jisme per-trial success probability

p

hai, expected number of trials

p

hi hota hai.

False. Yeh

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

hai, jahan

N

random trial count hai. Chhota

p

matlab zyada expected trials, toh expectation

p

ke ghatne par badhni chahiye —

\frac{1}{p}

badhta hai,

p

nahi badhta.

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

dekhne ke liye: probability

p

se hum trial

1

par succeed karte hain (cost

1

); probability

1 - p

se hum ek trial waste karte hain aur dobara shuru karte hain, toh

E [N] = p \cdot 1 + (1 - p) (1 + E [N])

, jo solve hoke

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

deta hai. Dekho Probability and Expectation.

Ek one-sided Monte Carlo test ko

k

baar repeat karne se error

q^{k}

ki tarah neeche aata hai, jahan

q

per-run error probability hai.

True, sirf "risky" answer ke liye. Independent runs multiply hote hain, toh

k

baar simultaneously galat hone ki probability

\leq q^{k}

hoti hai, jo

k

mein exponentially shrink karti hai.

Randomized QuickSort ka

O (n^{2})

worst case ek specific bad input (jaise sorted array) se trigger hota hai.

False. Random pivots ke saath, expectation mein koi bhi input bura nahi hota.

O (n^{2})

case ke liye ek unlucky coin sequence chahiye, jise adversary control nahi kar sakta. Dekho QuickSort.

Karger ke min-cut mein two-sided error hai, toh yeh true minimum se chhota cut return kar sakta hai.

False. Yeh graph ka ek actual cut report karta hai, jo true minimum se neeche kabhi nahi ja sakta. Error one-sided hai — yeh sirf aisa cut return karta hai jo bahut bada hota hai. Dekho Min-Cut and Max-Flow.

Tum hamesha ek Monte Carlo algorithm ko Las Vegas mein convert kar sakte ho.

False. Sirf tab jab tum ek answer ko cheaply verify kar sako. Saste check ke bina tum nahi jaante kab retry karna band karo, toh correctness guarantee nahi kar sakte.

Las Vegas algorithm ko ek time budget par cut off karne se ek Monte Carlo algorithm milta hai.

True. Maano

T

run ki (random) running time hai aur

E [T]

uska expected value. Time fixed ho jaati hai (budget) aur agar khatam nahi hua toh answer ab ek guess ho sakta hai. Markov's Inequality overrun ko bound karta hai:

Pr [T \geq a E [T]] \leq \frac{1}{a}

, toh

a E [T]

ka budget at most

\frac{1}{a}

probability se overrun karta hai.

Two-sided-error Monte Carlo run ke liye jo

k

baar repeat kiya gaya ho, last run ka answer lena ek valid boosting strategy hai.

False. Last run kisi bhi doosre run se zyada reliable nahi hai. Tumhe majority vote lena hoga, jiski error Chernoff Bounds se bounded hoti hai.

Karger ke algorithm ka ek lucky run ek unlucky baad ke run se "spoil" ho sakta hai.

False. Kyunki har reported cut genuine hota hai, sabhi runs mein sabse chhota cut rakhna safe hai: ek correct run minimum ko hamesha ke liye pin kar deta hai, aur baad ke runs sirf equal-ya-bade cuts propose kar sakte hain.

Error dhundho

"Miller–Rabin galti se ek prime number ko composite declare kar sakta hai."

Galat. Ek true prime ka koi compositeness witness nahi hota, toh "composite" outputs hamesha correct hote hain. Sirf "probably prime" galat ho sakta hai — error one-sided doosri taraf hai.

"Kyunki randomized QuickSort randomness use karta hai, iski expected time is par depend karti hai ki input kitna adversarial hai."

Galat. Random pivots expectation ko har input par

O (n lo g n)

banate hain. Adversary input control karta hai lekin coins nahi, toh koi bhi input expectation mein doosre se bura nahi hota.

"Las Vegas algorithm ki confidence boost karne ke liye, ise

k

baar run karo aur majority vote lo."

Galat. Las Vegas pehle se hamesha correct hota hai — boost karne ke liye kuch nahi hai. Boosting (voting / repeating) ek Monte Carlo technique hai.

E [N] = p \cdot 1 + (1 - p) (1 + E [N])

solve nahi ho sakti kyunki

E [N]

dono taraf appear karta hai."

Galat. Yahan

E [N]

pehli success tak trials ki expected number hai. Self-reference hi ise solvable banata hai: memorylessness ka matlab hai ki failure ke baad remaining expectation phir se

E [N]

hai, ek linear equation deta hai

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

"Confidence amplification ke liye humein

q^{k} \leq ε

chahiye (jahan

ε

target error bound hai), toh

k \geq ε / q

Galat.

q^{k} \leq ε

solve karne ke liye logarithms chahiye:

k \geq \frac{ln ( 1/ ε )}{ln ( 1/ q )}

. Dependence logarithmic hai, isliye itne kam runs error ko khatam kar dete hain.

"Karger per run approximately

1/2

probability se succeed karta hai, toh thode runs kaafi hain."

Galat. Ek single run ki success probability sirf

\geq \frac{2}{n ( n - 1 )}

hoti hai — bahut chhoti. Failure ko

1/ n

se neeche laane ke liye tumhe

Θ (n^{2} lo g n)

runs chahiye.

"Two-sided error ke saath,

k = 4

baar run karke majority lena safe hai."

Galat. Even

k

ke saath votes exactly aadhe-aadhe split ho sakte hain, koi strict majority nahi rehti. Odd

k

use karo, ya ek deterministic tie-break rule fix karo; tabhi majority vote well-defined hota hai.

Why questions

Randomness ek worst-case adversary ko defeat kyun karta hai?

Ek deterministic algorithm ka ek fixed response hota hai, toh adversary woh ek input design kar sakta hai jo uski cost maximize kare. Random choices unpredictable hoti hain, guaranteed bad cases ko sirf unlikely ones mein badal deti hain.

Las Vegas loop mein retries ki sankhya geometrically distributed kyun hoti hai?

Har trial success probability

p

ke saath ek independent success/failure coin flip hota hai. Pehli success tak trial count

N

by definition geometric hota hai, jo

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

deta hai.

Boosting karte waqt independent error probabilities multiply kyun hote hain?

Independence ka matlab hai

k

events ki joint probability unki probabilities ka product hoti hai. Har galat run ki probability

\leq q

hoti hai (per-run error), toh

k

baar simultaneously galat hone ki probability

\leq q^{k}

hoti hai.

Karger ke analysis mein bound

1 - x \leq e^{- x}

kyun aata hai?

Yeh awkward product

(1 - \frac{1}{( 2 n )})^{T_{rep}}

— jahan

T_{rep}

independent contraction runs ki sankhya hai — ko ek clean exponential

e^{- T_{rep} / (2 n)}

mein convert karta hai, jise

1/ n

jaise target se compare karna aasaan hai.

QuickSort mein linearity of expectation per-pair comparison probabilities kyun add kar sakti hai jabki comparisons dependent hain?

Linearity of expectation dependence ki parwah kiye bina hamesha hold karti hai:

E [\sum X_{ij}] = \sum E [X_{ij}]

hamesha. Toh hum har pair ki chhoti probability

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

unke correlations suljhaye bina sum karte hain. Dekho Probability and Expectation.

Ek two-sided Monte Carlo algorithm majority voting kyun use karta hai, na ki one-sided error ke liye use ki jaane wali "trust any certain answer" trick?

Two-sided error ke saath koi certain answer nahi hota — dono outputs galat ho sakte hain. Sirf statistical majority truth ki taraf concentrate hota hai, aur Chernoff Bounds batata hai kitni jaldi.

Even number of majority-vote runs ko special care kyun chahiye?

Even

k

ke saath votes exactly aadhe mein split ho sakte hain, koi strict majority nahi rehti. Clean

q^{k}

-style guarantees ek decisive majority assume karti hain, toh ya toh odd

k

use karo ya ek fixed tie-break rule add karo.

Edge cases

Jab

p \to 0

ho toh Las Vegas retry loop ka kya hota hai?

E [N] = \frac{1}{p} \to \infty

: expected running time blow up ho jaati hai. Algorithm correct rehta hai (yeh kabhi jhooth nahi bolta), lekin effectively kabhi khatam nahi ho sakta.

Jab

p = 1

ho (har trial succeed karta hai) toh Las Vegas retry loop ka kya hota hai?

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

: loop pehle hi trial par hamesha succeed karta hai. Yahan randomness degenerate hai — yeh ek ordinary one-shot deterministic step ki tarah behave karta hai.

Boosting ke baad error kya hoti hai jab

q = 0

(per-run error zero hai)?

q^{k} = 0

kisi bhi

k \geq 1

ke liye: ek single run pehle se errorless hai. Yeh degenerate "actually randomized nahi" case hai — koi boosting ki zaroorat nahi.

Agar

q = 1

ho (single run hamesha galat ho) toh kya?

q^{k} = 1

sabhi

k

ke liye: boosting kuch nahi karta. Repetition ek aisi test ko fix nahi kar sakta jo kabhi sahi nahi hoti — tumhe fundamentally better algorithm chahiye.

Amplification formula ke liye, agar target error

ε \geq 1

ho toh kya?

Tab

ln (1/ ε) \leq 0

deta hai

k \leq 0

, yaani zero runs kaafi hain — tumhe itni baar galat hone ki already permission thi. Formula sahi kehta hai "kuch mat karo."

Karger ki success probability

\frac{2}{n ( n - 1 )}

n = 2

par kya karti hai?

Yeh

1

ke barabar hoti hai: ek 2-node graph already contracted hai, toh single crossing set certainty ke saath min-cut hai. Formula sabse chhote case par gracefully degrade karta hai.

Agar ek Monte Carlo algorithm ki runtime inputs ke beech thodi vary karti hai, toh kya ab yeh Las Vegas hai?

Nahi. Monte Carlo ko define karta hai yeh ki answer galat ho sakta hai. Sirf input-dependent (lekin bounded, non-random) runtime correctness ko affect nahi karta, toh yeh Monte Carlo rehta hai.

Kya koi algorithm hamesha correct aur hamesha bounded-time dono ho sakta hai?

Haan — woh bas ek ordinary deterministic (ya zero-error, fixed-time) algorithm hai. Las Vegas time guarantee relax karta hai; Monte Carlo correctness guarantee relax karta hai. Dono ko relax na karna tumhe plain deterministic algorithm deta hai.

Recall Page band karne se pehle self-test karo

Mirror-image structure ::: Las Vegas = hamesha correct, random time (measure = $E [T]$ ). Monte Carlo = fixed time, shayad galat (measure = error prob). One-sided vs two-sided boosting ::: One-sided → certain answer par trust karo agar kabhi bhi aaye (error $\leq q^{k}$ ). Two-sided → majority vote (Chernoff), odd $k$ ke saath ya tie-break rule ke saath. Adversary ki asli limit ::: Woh input chunata hai, coins kabhi nahi — toh random pivots har input ko expectation mein equally good banate hain.