Randomized algorithms — Las Vegas, Monte Carlo: Foundations

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

Yeh page toolbox room hai. Pehle parent note Randomized algorithms — Las Vegas, Monte Carlo mein jaane se pehle, hum har ek symbol aur idea table par rakhte hain, ek aisi order mein jahan har cheez usse pehle wali cheez se banti hai. Kuch bhi assume nahi kiya gaya. Ek smart 12-saal-ka bachcha line one se start karke finish tak ready ho jayega.

0. Sabse pehla idea: code ke andar ek coin flip

Socho ek machine hai jo, jab bhi algorithm puche, ek coin spin karke result wapas de deti hai. Algorithm woh result padhta hai aur decide karta hai aage kya karna hai.

YEH TOPIC IS CHEEZ KI ZAROORAT KYU HAI: ek ordinary (deterministic) algorithm same input par hamesha exactly same steps karta hai. Isliye ek chalaak dushman usse woh ek input de sakta hai jo usse slow kar de. Jab algorithm asli coins flip karne lagta hai, toh dushman path predict nahi kar sakta — isliye "bad luck" "bad input" ki jagah le leti hai.

1. Probability $Pr [\cdot]$ — "kitni baar" measure karna

Picture yeh hai: socho 100 identical runs ek row mein lined up hain. Ek event ki probability un runs ka fraction hai jahan woh event hota hai. Jo "hua" wale runs hain unhe orange colour karo aur count karo.

"AND" ke liye multiply kyun? Agar A aadhe time hota hai, aur un aadhe cases ke andar B ek chauthai time hota hai, toh "dono" $\frac{1}{2} \times \frac{1}{4} = \frac{1}{8}$ time hota hai. Independence ka matlab sirf yeh hai ki "B ka chance A ki wajah se nahi badalta". Parent note exactly yahi use karta hai jab woh kehta hai ki $k$ galat runs ki probability $q^{k}$ hai — woh $q$ ko khud se $k$ baar multiply karna hai.

Poora toolkit dekhne ke liye Probability and Expectation dekho; yahan hume sirf yahi do rules chahiye.

2. Ek random variable aur letter $E [\cdot]$ — average outcome

Picture: algorithm 1000 baar chalao, har baar $T$ likh lo, sab add karo, 1000 se divide karo. Woh number (bahut close to) $E [T]$ hai. Yeh ek single fixed number hai chahe $T$ khud idhar-udhar jump karta rahe.

TOPIC KO $E [\cdot]$ KI ZAROORAT KYU HAI: ek Las Vegas algorithm ka time $T$ ek random variable hai — iska koi single value nahi hota. Ise describe karne ka sirf ek fair tarika hai iski average, $E [T]$ . Yahi poora "expected running time" ka idea hai.

3. Geometric picture — "tab tak try karo jab tak kaam na kare"

Picture: coin flips ki ek row hai; aap left se right chalte ho aur pehli success (star) par ruk jaate ho. Kabhi kabhi aap turant ruk jaate ho, kabhi bahut door tak chalte ho.

YEH KYUN MATTER KARTA HAI: sabse simple Las Vegas algorithm bilkul yahi hai "tab tak ek random attempt retry karo jab tak kaam kare". Iske attempts ki sankhya exactly yeh $N$ hai, aur parent note yeh beautiful result prove karta hai ki $E [N] = \frac{1}{p}$ — agar har try $\frac{1}{10}$ time kaam kare, toh aap $10$ tries expect karte ho.

Recall Quick check: agar

$p = \frac{1}{3}$ ho, toh $E [N]$ kya hai? $E [N] = \frac{1}{p} = \frac{1}{1/3} = 3$ tries on average.

4. Woh symbols jo confidence badhate hain: $q$ , $k$ , $ε$

Monte Carlo section teen letters juggle karta hai. Yahan woh clearly hain.

Kyunki runs independent hain, isliye chance ki saare $k$ runs ek saath galat hain woh $q$ ko khud se $k$ baar multiply karna hai: $Pr [still wrong after k runs] \leq q^{k} .$

Picture: har run ka galat hona width $q$ ka ek orange slice hai; $k$ slices stack karne se multiply hota hai, aur woh sliver jaldi chhota ho jaata hai.

YEH TEEN KYUN: yeh ek shaky one-run algorithm ko almost-certain bana dete hain, aur $k = ⌈ ln (1/ ε) / ln (1/ q)⌉$ batata hai ki kitne runs se woh certainty milti hai.

5. Do named tools jo parent borrow karta hai

6. Symbol dictionary (ek nazar mein)

Symbol	Plain meaning	Picture
$r an d o m ()$	code ke andar ek coin flip	spinning coin
$Pr [A]$	$A$ kitni baar hota hai ( $0$ se $1$ )	100 runs mein orange fraction
$N, T, X$	random variables (har run mein badle)	wobbling bar
$E [X]$	$X$ ka long-run average	wobble ke through flat dashed line
$p$	ek attempt ki success chance	"win" slice ki width
$q$	ek run ki error chance	"wrong" slice ki width
$k$	repeated runs ki sankhya	stacked slices
$ε$	tolerated final error	tiny target sliver
$\leq$	"at most / se bada nahi"	ek bar par ceiling
$H_{n}$	$1 + \frac{1}{2} + \dots + \frac{1}{n} \approx ln n$	dheere-dheere badhti staircase

Yeh sab topic mein kaise feed hote hain

Equipment checklist

Khud test karo — parent note kholne se pehle har ek ka answer dena chahiye.

r an d o m ()

ek algorithm ke andar kya karta hai?

Har call par ek naya unpredictable value (jaise heads/tails) return karta hai, isliye runs alag ho sakte hain.

Pr [A] = 0.25

ka plain words mein kya matlab hai?

Average par

A

har 4 runs mein se 1 mein hota hai.

Pr [A and B] = Pr [A] \cdot Pr [B]

kab valid hai?

Sirf tab jab

A

aur

B

independent hain.

Random variable kya hota hai?

Ek aisi quantity jiska value coin flips par depend karta hai, isliye woh run to run badalta hai.

E [T]

kya measure karta hai?

Bahut saare runs mein running time

T

ka long-run average.

Linearity of expectation state karo.

E [X + Y] = E [X] + E [Y]

, hamesha, chahe

X

aur

Y

dependent hon.

Success prob

p

wale geometric process mein

E [N]

kya hai?

E [N] = 1/ p

k

independent galat runs ki probability

\leq q^{k}

kyun hoti hai?

Independence se aap har run ki error

q

multiply kar sakte ho, jo

q \cdot q \dots = q^{k}

deta hai.

ε

ka kya matlab hai?

Maximum final error jo aap tolerate karne ko taiyaar hain.

Markov's inequality plain words mein state karo.

Average time se kam se kam

a

guna zyada time lene ka chance at most

1/ a

hai.

Karger's analysis mein use hone wala exponential shortcut kya hai?

1 - x \leq e^{- x}