Randomized algorithms — Las Vegas, Monte Carlo: Question bank

Before we start, one word we lean on constantly:

True or false — justify

TF1. "A Las Vegas algorithm can occasionally return a wrong answer."

False. In Las Vegas the randomness lives entirely in the running time; the output is always correct. It may be slow, never wrong.

TF2. "A Monte Carlo algorithm's running time is a random variable."

False (in the standard sense). Its running time is fixed/bounded — that's the whole point. The answer is the risky part. It is the mirror image of Las Vegas.

TF3. "Randomized QuickSort has worst-case

O (n lo g n)

False. Its worst case is still

O (n^{2})

; it just requires an unlucky sequence of coin flips, not a bad input. The

O (n lo g n)

is the expected time on every input.

TF4. "For a Monte Carlo algorithm with success probability

p

, repeating

k

times and combining reduces error."

True, but only if you combine correctly — "all-agree" for one-sided, majority vote for two-sided. Just running more times without a combining rule does nothing.

TF5. "Miller–Rabin can wrongly declare a prime to be composite."

False. It is one-sided: a genuine prime has no witness, so "composite" verdicts are always right. Only "probably prime" can be an error.

TF6. "Karger's min-cut may report a cut smaller than the true minimum."

False. It contracts real edges and reports an actual cut, which can never be below the true minimum. Its error is one-sided: it can only overshoot.

TF7. "Because a single Karger run succeeds with tiny probability

\approx 2/ n^{2}

, the algorithm is useless."

False. Running it

O (n^{2} lo g n)

times and keeping the smallest result pushes failure below

1/ n

, since a single lucky correct run is never spoiled by later unlucky ones.

TF8. "If success probability per trial is

p

, a Las Vegas retry loop expects exactly

1/ p

trials."

True. The process is memoryless, so

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

solves to

E = 1/ p

(see Probability and Expectation).

TF9. "You can always convert a Monte Carlo algorithm into a Las Vegas one."

False. Only if you can verify an answer cheaply. Then you re-run until verification passes. Without a cheap checker there is no way to know when you're correct.

TF10. "Doubling

k

from 10 to 20 rounds halves the error of a one-sided Monte Carlo test."

False. Error is

q^{k}

, so error goes from

q^{10}

q^{20} = (q^{10})^{2}

— it is squared, an exponential improvement, not halved.

Spot the error

SE1. "Since QuickSort dies on sorted input, randomized QuickSort is slow on sorted input too."

Error: with random pivots the input's order is irrelevant. The adversary can't control the coin flips, so sorted input is expected

O (n lo g n)

like any other (see QuickSort).

SE2. "To boost a two-sided Monte Carlo algorithm, just take the answer from the final run."

Error: the last run is no more reliable than any other. Two-sided error needs a majority vote, whose failure decays via Chernoff Bounds.

SE3. "Cut a Las Vegas algorithm off at time

T = E [T]

and it rarely fails."

Error: at exactly

T = E [T]

, Markov's Inequality gives no useful bound (bound is

\leq 1

). You need a generous budget like

a \cdot E [T]

so that

Pr [T_{r u n} \geq a E [T]] \leq 1/ a

is small.

SE4. "One-sided boosting: output 'prime' if any round says prime."

Error: backwards. For Miller–Rabin you output "prime" only if all rounds fail to find a witness. A single witness in any round proves compositeness.

SE5. "Karger has two-sided error, so we should majority-vote its outputs over many runs."

Error: it is one-sided — it never undershoots the true min-cut. So you keep the minimum cut seen, never a majority vote.

SE6. "Expected running time and amortized running time are the same guarantee."

Error: expected time averages over the algorithm's coin flips; amortized averages over a sequence of operations with no randomness needed (see Amortized vs Expected Analysis).

SE7. "Monte Carlo error

q^{k}

assumes the

k

runs can share randomness."

Error: the multiplication

q^{k}

requires the runs to be independent. Shared randomness would correlate failures and break the product bound.

Why questions

WY1. Why does randomness defeat a worst-case adversary?

A deterministic algorithm's choices are predictable, so an adversary can hand-craft a bad input. Random choices are unknown in advance, so no fixed input is reliably bad — bad cases become unlikely, not guaranteed.

WY2. Why is the retry-loop trial count geometric?

Each attempt is an independent success/fail flip with fixed probability

p

; the number of flips until the first success is exactly the geometric distribution, giving

E [N] = 1/ p

WY3. Why does one-sided error boost as

q^{k}

rather than

q \cdot k

Independent runs multiply their probabilities. All

k

runs must simultaneously be wrong, and simultaneous independent events multiply:

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

— exponential shrink.

WY4. Why does the min-cut proof use

1 - x \leq e^{- x}

It converts the messy product

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

into a clean exponential

e^{- T / (2 n)}

, making the failure bound easy to read off as

1/ n

WY5. Why does randomized Quickselect beat deterministic median-of-medians in practice despite the same big-O?

Random pivots give expected linear time with tiny constants and no bookkeeping, whereas the deterministic version pays large constant factors for its guarantee.

WY6. Why can't we lower Las Vegas error by re-running?

There is no error to lower — it is already always correct. Re-running only affects the time distribution.

Edge cases

EC1. What happens to a retry loop's expected trials

E [N] = 1/ p

p \to 0

E [N] \to \infty

: if success is essentially impossible, you expect to wait forever. Randomization gives no free lunch when the success event is vanishingly rare.

EC2. What if

p = 1

in a Las Vegas retry loop?

E [N] = 1

: you always succeed on the first try — the algorithm is effectively deterministic, with no randomness benefit or cost.

EC3. In the boosting count

k = ⌈ ln (1/ ε) / ln (1/ q)⌉

, what if

q = 1

ln (1/ q) = 0

, division blows up: with per-run error

1

the algorithm is always wrong and no amount of repetition helps. Boosting needs

q < 1

EC4. What if a Monte Carlo run has error

q > 1/2

for a two-sided problem?

Majority vote can make things worse, since the runs vote wrong more than half the time. You need each run better than a coin flip (

q < 1/2

) before Chernoff-style boosting helps.

EC5. What is

Pr [error]

after

k

one-sided rounds when the true answer is on the "certain" side?

Exactly

0

. One-sided error can only occur on one type of answer; on the certain side every round is correct, so no error is possible regardless of

k

EC6. What does Markov's bound

Pr [T \geq a E [T]] \leq 1/ a

give at

a = 1

The trivially useless bound

\leq 1

. Markov only becomes informative for

a > 1

; that's why LV→MC cutoffs must use a budget several times the expected time.

EC7. A Monte Carlo algorithm reports the same wrong answer on all

k

independent runs — is boosting broken?

No — it is simply a low-probability event (

\leq q^{k}

). Boosting bounds the probability of this happening, not its impossibility; it can occur, just rarely.

Recall Quick self-check

One-sided vs two-sided boosting rule? ::: One-sided → take the "certain" answer if it ever appears (all-agree); two-sided → majority vote. Where does randomness live in Las Vegas vs Monte Carlo? ::: Las Vegas: in the running time (answer always correct). Monte Carlo: in the answer (time always bounded). Why keep the minimum over Karger runs, not a vote? ::: Error is one-sided (never undershoots the true cut), so the smallest observed cut is closest to truth and a lucky run is never spoiled.