Randomized algorithms — Las Vegas, Monte Carlo

WHAT exactly are these two classes?

HOW we analyse a Las Vegas algorithm — derive expected time

Take the simplest Las Vegas idea: keep retrying a random attempt until it succeeds. Suppose each independent attempt succeeds with probability $p$ and costs $c$ work.

WHY a geometric distribution? Each trial is an independent coin flip — "success" with prob $p$ . The number of trials $N$ until first success is geometric.

Derivation of $E[N]$ from scratch. Let $E = E[N]$ .

With prob $p$ : we succeed on trial 1, cost = $1$ trial.
With prob $1-p$ : we fail (cost 1 trial) and are back to the start, so an extra $E$ trials expected.

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

Why this step? The process is memoryless: after a failure the situation is identical to the start, so the remaining expectation is again $E$ . This self-reference lets us solve algebraically.

Expand: $E = p + (1-p) + (1-p)E = 1 + (1-p)E$ $E - (1-p)E = 1 \implies E\cdot p = 1 \implies \boxed{E[N] = \tfrac{1}{p}}$

So expected total work $= \dfrac{c}{p}$ .

HOW we analyse a Monte Carlo algorithm — boosting confidence

Suppose ONE run is wrong with probability $\le q$ (and runs are independent). Run it $k$ times.

One-sided error (e.g. test that says "yes" might be wrong, but "no" is always certain): take "yes" only if all $k$ runs say "yes". The chance all $k$ are wrongly "yes": $\Pr[\text{still wrong}] \le q^{k}$

Why this multiplies? Independent runs ⇒ joint probability is the product. Each wrong run has prob $\le q$ , so $k$ simultaneous wrong runs has prob $\le q^k$ , which shrinks exponentially.

To force error below a target $\varepsilon$ : $q^{k}\le\varepsilon \implies k \ge \frac{\ln\varepsilon}{\ln q} = \frac{\ln(1/\varepsilon)}{\ln(1/q)}$

Converting between the two

Worked examples

Worked example Example 1 — Randomized QuickSort (Las Vegas)

Pick the pivot uniformly at random. Output is the sorted array — always correct, so it's Las Vegas. Expected comparisons: let $X_{ij}=1$ if elements of rank $i<j$ are ever compared. Two ranks are compared iff one of them is the first pivot chosen among the $j-i+1$ elements between them — probability $\frac{2}{j-i+1}$ . $E[\#cmp]=\sum_{i<j}\frac{2}{j-i+1}=\sum_{i<j}\frac{2}{j-i+1}\le 2nH_n=O(n\log n)$ Why this step? Linearity of expectation lets us add up tiny per-pair probabilities without worrying about dependence. The harmonic sum $H_n\approx\ln n$ gives the $\log n$ factor. Worst case is still $O(n^2)$ , but that needs a specific unlucky sequence of coin flips, not a bad input — that's the win over deterministic QuickSort.

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

Randomly contract edges until 2 nodes remain; report the crossing edges as the cut. A single run returns the true min-cut with prob $\ge \frac{1}{\binom n2}=\frac{2}{n(n-1)}$ . Why one-sided? Whatever cut it reports is a real cut of the graph, so the algorithm can never undershoot the minimum — it can only return a cut that is too large, never too small. The "error" is therefore one-directional. We exploit this by keeping the smallest cut over many runs: any single lucky run that hits the true minimum is correct forever after. That single-run success prob is tiny, so run it $T=\binom n2\ln n$ times: $\Pr[\text{all }T\text{ runs miss}]\le\Big(1-\tfrac{1}{\binom n2}\Big)^{T}\le e^{-\ln n}=\tfrac1n$ Why $\;1-x\le e^{-x}$ ? This standard bound converts the product into a clean exponential, showing $T=O(n^2\log n)$ repetitions push failure below $1/n$ .

Common mistakes (Steel-man + fix)

Flashcards

Las Vegas algorithm — what is random?

The running time (a random variable); the output is always correct.

Monte Carlo algorithm — what is random?

The correctness of the answer (may be wrong with prob ≤ q); the running time is bounded/fixed.

Expected number of trials until first success when each succeeds w.p. p

1/p

(geometric distribution).

Derive E[N] for a retry loop

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

(memorylessness).

Error after k independent Monte Carlo runs (one-sided, each wrong ≤ q)

\le q^{k}

How many runs k to get error ≤ ε

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

Expected comparisons of randomized QuickSort

O(n\log n)

, from

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

Probability two ranks i<j are compared in randomized QuickSort

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

Single-run success prob of Karger's min-cut

\ge 1/\binom{n}{2}

Is Karger's min-cut one-sided or two-sided error?

One-sided — it reports a real cut, so it never returns smaller than the true minimum, only possibly larger.

How to convert Las Vegas → Monte Carlo

Cut off after a time budget; output a guess if not finished (Markov's inequality bounds error).

How to convert Monte Carlo → Las Vegas

Only if answers are cheaply verifiable: repeat until verification passes.

Inequality used to bound repeated Karger failure

1-x \le e^{-x}

Recall Feynman: explain to a 12-year-old

Imagine a maze. A Las Vegas robot ALWAYS finds the exit — but sometimes it wanders and takes longer, sometimes it's fast. A Monte Carlo robot ALWAYS stops after exactly 5 minutes — but if it didn't reach the exit yet, it just guesses where the door is, and might be wrong. Why use coins at all? Because a bully who hates your robot can build a maze that traps a predictable robot every time. If your robot turns randomly, the bully can't trap it — bad luck becomes rare instead of certain. And if you're worried Monte Carlo guessed wrong, just run it many times and vote — the chance ALL of them are wrong shrinks super fast (halve, halve, halve...).

Connections

Probability and Expectation — linearity of expectation, geometric distribution.
Markov's Inequality and Chernoff Bounds — tail bounds for cut-off and majority voting.
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 — expectation over coins, not over inputs.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, randomized algorithm matlab algorithm ke andar hum coin flip (random number) use karte hain. Iski wajah se same input par bhi algorithm har baar thoda alag chal sakta hai. Do flavour hote hain. Las Vegas wala hamesha sahi answer deta hai, bas time random hota hai — kabhi jaldi, kabhi der, par answer galat kabhi nahi. Monte Carlo wala fixed time mein khatam ho jata hai, par answer kabhi galat ho sakta hai (chhoti si probability se). Yaad rakhne ka trick: Las Vegas = aLways correct, Monte Carlo = Maybe wrong par time pe.

Randomness kyun? Kyunki agar tumhara algorithm predictable (deterministic) hai, to ek dushman aisa worst-case input bana sakta hai jo har baar tumhe phasa de — jaise sorted array par normal QuickSort $O(n^2)$ ho jata hai. Lekin agar tum pivot random choose karo, to dushman ko pata hi nahi ki tum kya chunoge, isliye bura case rare ho jata hai, guaranteed nahi. Expected time nikalne ka formula simple hai: agar har try success hone ka chance $p$ hai, to expected tries $=1/p$ (geometric distribution, memoryless property se derive hota hai).

Monte Carlo mein agar ek run galat hone ka chance $q$ hai, to $k$ baar chala kar error $q^k$ tak gir jata hai — yeh exponentially fast girta hai. Jaise $q=1/2$ par sirf 20 runs se error $10^{-6}$ se kam! Isiliye Miller-Rabin primality test bahut reliable hai. Ek important baat: Karger ka min-cut algorithm one-sided error wala hai — wo jo bhi cut deta hai woh ek asli cut hota hai, isliye kabhi true minimum se chhota nahi ho sakta, sirf bada ho sakta hai. Isiliye hum bahut runs ka sabse chhota cut rakhte hain. Dhyan rahe: one-sided error mein "certain" wala answer lo, two-sided error mein majority vote lo, last run ka answer mat uthao.

Randomized algorithms — Las Vegas, Monte Carlo

WHAT exactly are these two classes?

HOW we analyse a Las Vegas algorithm — derive expected time

HOW we analyse a Monte Carlo algorithm — boosting confidence

Converting between the two

Worked examples

Common mistakes (Steel-man + fix)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections