Randomized algorithms — Las Vegas, Monte Carlo: Worked examples

This page is the drill floor for the parent topic. The parent taught you two machines: Las Vegas (always right, random time) and Monte Carlo (fixed time, maybe wrong). Here we don't teach new theory — we throw every kind of input at those two machines and watch what happens, so no exam case can surprise you.

Before we compute anything, one promise: every symbol you see below was already earned in the parent note. If you feel a gap, the linked prerequisite fills it:

$p$ = success probability of one trial → Probability and Expectation
$E [\cdot]$ = expected value (long-run average) → Probability and Expectation
$q^{k}$ boosting and $1 - x \leq e^{- x}$ → used in Chernoff Bounds and Markov's Inequality

The scenario matrix

Every randomized-algorithm question lives in one of these cells. Think of the two axes as: which machine (Las Vegas / Monte Carlo) and what weird thing the input does (extreme probability, zero, one-sided vs two-sided, real-world, exam twist). We will hit all ten cells.

Cell	Machine	Scenario class	Covered by
C1	Las Vegas	Ordinary $0 < p < 1$ retry loop	Ex 1
C2	Las Vegas	Limiting: $p \to 1$ (almost never retry) and $p \to 0$ (blows up)	Ex 2
C3	Las Vegas	Degenerate $p = 0$ — never succeeds	Ex 2
C4	Monte Carlo	One-sided error, choose $k$ for a target $ε$	Ex 3
C5	Monte Carlo	Extreme tiny success $p ≪ 1$ (Karger-style)	Ex 4 (figure)
C6	Monte Carlo	Two-sided error — majority vote, why last-run fails	Ex 5
C7	Conversion	LV → MC via a time budget + Markov	Ex 6
C8	Conversion	MC → LV via cheap verification	Ex 7
C9	Real-world	Word problem (server / dice framing)	Ex 8
C10	Exam twist	"Which class is it?" mis-labelled algorithm	Ex 9

Worked examples

Worked example Example 1 — Ordinary Las Vegas retry (Cell C1)

A randomized routine draws a random point in a square and keeps the point only if it lands inside an inscribed circle; otherwise it redraws. The circle covers $p = \frac{π}{4} \approx 0.785$ of the square. Each draw costs $c = 3$ units of work. What is the expected total work to get one point?

Forecast: guess before computing — will it be near $3$ , near $4$ , or huge? (The circle fills most of the square, so retries should be rare.)

Model each draw as one Bernoulli trial, success prob $p = π /4$ . Why this step? Each draw is independent and identical → the count of draws until first success is geometric, exactly the machine analysed in the parent note.
Apply $E [N] = \frac{1}{p}$ . $E [N] = \frac{1}{π /4} = \frac{4}{π} \approx 1.273 draws.$ Why this step? The memoryless retry loop's expected trial count is $1/ p$ — derived in the parent.
Multiply by per-trial cost $c = 3$ : $E [work] = \frac{c}{p} = \frac{3}{π /4} = \frac{12}{π} \approx 3.82.$ Why this step? Work $=$ (trials) $\times$ (cost per trial); by linearity $E [work] = c \cdot E [N]$ .

Verify: $p \approx 0.785$ is close to $1$ , so we expected barely more than one draw — and $1.27$ draws, $3.82$ work, matches. Units: draws are dimensionless, work is in "units", consistent.

Worked example Example 2 — Limiting and degenerate

$p$ (Cells C2, C3) Using the same $E [N] = 1/ p$ machine, evaluate the boundary behaviour: (a) $p = 0.999$ , (b) $p = 0.01$ , (c) $p \to 0^{+}$ , (d) $p = 0$ exactly.

Forecast: which of these makes the algorithm unusable?

(a) $p = 0.999$ : $E [N] = \frac{1}{0.999} \approx 1.001$ . Why this step? As $p \to 1$ the loop almost never retries, so $E [N] \to 1$ — the best case.
(b) $p = 0.01$ : $E [N] = \frac{1}{0.01} = 100$ . Why this step? Rare success means many retries; $E [N]$ grows like $1/ p$ , so a $100 \times$ drop in $p$ is a $100 \times$ blow-up in trials.
(c) $p \to 0^{+}$ : $E [N] = 1/ p \to + \infty$ . Why this step? The limit tells us the loop's expected time diverges — the algorithm still always eventually succeeds, but the average wait is unbounded.
(d) $p = 0$ exactly (degenerate): the loop never succeeds; $E [N]$ is undefined/ $\infty$ . Why this step? Division by zero is the mathematics screaming "this event never happens" — a Las Vegas algorithm with $p = 0$ is not an algorithm at all, it never halts.

Verify: monotonicity check — as $p$ shrinks $0.999 \to 0.01 \to 0$ , $E [N]$ grows $1.001 \to 100 \to \infty$ . Correct direction. Sanity: $E [N] \geq 1$ always (you always draw at least once), and indeed all values are $\geq 1$ .

Worked example Example 3 — One-sided Monte Carlo, pick

$k$ for a target (Cell C4) A primality tester (à la Primality Testing) is wrong on a composite with prob $q \leq \frac{1}{4}$ per round, and never wrong on a prime. You need the error below $ε = 1 0^{- 9}$ . How many rounds $k$ ?

Forecast: more rounds → smaller error. Will $k$ be around $5$ , $15$ , or $100$ ?

Error after $k$ independent rounds is $\leq q^{k}$ . Why this step? One-sided error: we only accept "composite" if a witness ever appears; a composite fools all $k$ rounds only if all $k$ independently fail — product $= q^{k}$ .
Solve $q^{k} \leq ε$ . Take logs (they turn products into sums, monotone so inequality survives): $k \geq \frac{l n ( 1/ ε )}{l n ( 1/ q )} = \frac{l n ( 1 0 ^{9} )}{l n 4} = \frac{20.723}{1.386} \approx 14.94.$ Why logs? $q^{k}$ is an exponential in $k$ ; the logarithm is the exact tool that "asks which exponent gives this value", i.e. it inverts exponentiation — see Chernoff Bounds for the same trick.
Round up: $k = ⌈ 14.94 ⌉ = 15$ rounds. Why ceil? $k$ must be a whole number of rounds and must exceed the threshold, so we round up.

Verify: $(1/4)^{15} = 4^{- 15} = 2^{- 30} \approx 9.3 \times 1 0^{- 10} < 1 0^{- 9}$ ✓, while $(1/4)^{14} \approx 3.7 \times 1 0^{- 9} > 1 0^{- 9}$ , so $14$ is too few — $15$ is exactly the minimum. Related to Primality Testing.

Worked example Example 4 — Extreme tiny success (Karger-style), with picture (Cell C5)

Karger's min-cut contraction succeeds on one run with tiny prob $s = \frac{1}{( 2 n )} = \frac{2}{n ( n - 1 )}$ . For $n = 10$ , $s = \frac{2}{90} = \frac{1}{45} \approx 0.0222$ . How many runs $T$ push the "all runs miss" probability below $1/ n = 0.1$ ?

Forecast: with a $2$ success chance, do you think you need dozens or thousands of runs?

Probability all $T$ runs miss $= (1 - s)^{T}$ . Why this step? Independent runs → the joint "every one fails" is the product of single-run failure probs $(1 - s)$ . Look at the figure: the curve $(1 - s)^{T}$ decays as $T$ grows.
Bound with $1 - s \leq e^{- s}$ so $(1 - s)^{T} \leq e^{- s T}$ . Why this step? The clean exponential is easier to solve; the red dashed curve in the figure sits above the true product, so bounding it below $0.1$ is safe (conservative).
Set $e^{- s T} \leq 0.1$ : $s T \geq ln 10$ , so $T \geq \frac{l n 10}{s} = 45 \times 2.3026 \approx 103.6 \Rightarrow T = 104.$ Why this step? Solving the exponential for $T$ gives the run count where the shaded "failure" region drops below the $0.1$ line in the figure.

Verify: exact check $(1 - \frac{1}{45})^{104} = (44/45)^{104} \approx 0.0977 < 0.1$ ✓, and $(44/45)^{103} \approx 0.0999 < 0.1$ too — the bound is slightly loose but safe. Matches the $T = O (n^{2} lo g n)$ scaling from the parent note.

Worked example Example 5 — Two-sided error, majority vote (Cell C6)

A Monte Carlo estimator returns the correct bit with prob $\frac{2}{3}$ per run, but can err either way. You run it $5$ times and take the majority. What's the chance the majority is wrong?

Forecast: each run is $2/3$ right — should a best-of-5 be safer than $2/3$ ? By how much?

Majority of $5$ is wrong iff $\geq 3$ runs are wrong. Wrong prob per run $= \frac{1}{3}$ . Why this step? With one-sided error you'd trust the "certain" answer; here neither answer is certain, so we let the crowd vote and only lose if a majority errs.
Count via the binomial (independent runs, each wrong w.p. $\frac{1}{3}$ ): $Pr [\geq 3 wrong] = \sum_{j = 3}^{5} (j 5) (\frac{1}{3})^{j} (\frac{2}{3})^{5 - j} .$ Why binomial? Independent yes/no trials with fixed prob is exactly the setting the binomial coefficient counts — see Probability and Expectation.
Compute: $=\frac{40+10+1}{243}=\frac{51}{243}\approx 0.2099.$$ *Why this step?* $\binom53=10,\binom54=5,\binom55=1$; the numerators are $10\cdot4,5\cdot2,1\cdot1$.$

Verify: $0.21 < 0.33$ — majority-of-5 beats a single run ✓. Contrast: if you'd just taken the last run, your error would stay $\frac{1}{3} \approx 0.333$ , worse. That's why two-sided error needs voting, not the last answer (Chernoff formalises the exponential improvement in Chernoff Bounds).

Worked example Example 6 — LV → MC via a time budget + Markov (Cell C7)

A Las Vegas algorithm has expected running time $E [T] = 50$ ms. You must return an answer within a fixed budget and are willing to give a wrong guess if it overruns. You set the cutoff at $a \cdot E [T]$ with $a = 10$ . Bound the probability the run overruns (and hence errs).

Forecast: a $10 \times$ generous budget — is the overrun risk under $50$ , under $20$ , or under $10$ ?

Apply Markov's Inequality: for a non-negative random time $T$ , $Pr [T \geq a E [T]] \leq \frac{E [ T ]}{a E [ T ]} = \frac{1}{a} .$ Why Markov? We know only the mean running time, nothing about its shape. Markov is the one tool that bounds a tail using only the mean — perfect when that's all we have.
Plug $a = 10$ : $Pr [overrun] \leq \frac{1}{10} = 0.1$ , at a cutoff of $10 \times 50 = 500$ ms. Why this step? The larger the budget multiple $a$ , the smaller the overrun risk — tune $a$ to the error you can tolerate.
Now the algorithm has fixed time (500 ms) and error $\leq 0.1$ — that is precisely a Monte Carlo algorithm. Conversion complete. Why this step? Trading a random-time/always-right machine into a fixed-time/maybe-wrong one is the definition of the LV→MC direction.

Verify: dimensional check — $a E [T] = 10 \times 50 ms = 500$ ms, a time ✓; the bound $1/ a = 0.1$ is dimensionless ✓. If instead $a = 2$ , bound $= 0.5$ — looser, as expected for a tighter budget.

Worked example Example 7 — MC → LV via cheap verification (Cell C8)

A Monte Carlo solver returns a candidate answer, correct with prob $p = 0.3$ per run, and you can verify any candidate in $O (1)$ . You loop: run, verify, stop when verification passes. What is the expected number of runs, and why is the result always correct?

Forecast: with $30$ success, expected runs near $2$ , near $3$ , or near $10$ ?

Verification filters out wrong answers, so you only ever output a verified-correct one. Why this step? Because a wrong candidate fails verification and is discarded, the final output is guaranteed correct — that's what upgrades the machine to Las Vegas (always right).
Runs until first pass are geometric with success prob $p = 0.3$ , so $E [runs] = \frac{1}{p} = \frac{1}{0.3} = \frac{10}{3} \approx 3.33.$ Why this step? Each run passes independently w.p. $p$ ; the wait to first pass is the same geometric machine as Ex 1 — but now the randomness lives in time, not correctness.
The running time is random (geometric), the answer is certain — the signature of Las Vegas. Why this step? We've swapped the error into the runtime: the exact mirror of Ex 6.

Verify: $E [runs] = 3.33 \geq 1$ ✓ and matches $1/ p$ . Sanity: cheap verification is the only ingredient that makes MC→LV possible — without it you cannot know which run to trust. See Amortized vs Expected Analysis for how this expected count differs from a worst-case bound.

Worked example Example 8 — Real-world word problem (Cell C9)

A load-balancer routes each request to a random one of $m = 4$ healthy servers, but on any given attempt a server is busy (rejects) with prob $0.25$ independently. It retries until accepted. Each attempt costs $2$ ms. Expected time to place one request? And with a 20 ms budget, overrun prob?

Forecast: with $75$ acceptance, is the average near $2$ ms or near $10$ ms?

Acceptance prob per attempt $p = 1 - 0.25 = 0.75$ ; attempts are geometric. Why this step? "Retry until accepted" is exactly the Las Vegas retry loop; acceptance is success.
Expected attempts $= \frac{1}{0.75} = \frac{4}{3} \approx 1.333$ ; expected time $= 2 \times \frac{4}{3} = \frac{8}{3} \approx 2.67$ ms. Why this step? $E [work] = c / p$ from the parent formula, with $c = 2$ ms.
Overrun of a 20 ms budget: here $a = 20/ E [T] = 20/ (8/3) = 7.5$ , so by Markov $Pr [\geq 20 ms] \leq \frac{1}{7.5} \approx 0.133$ . Why this step? Same LV→MC budgeting as Ex 6; Markov bounds the tail from the mean alone.

Verify: $2.67$ ms sits just above one attempt's $2$ ms — matches "usually accepted first try" ✓. Budget bound $0.133 < 1$ and looser than Ex 6's $0.1$ because $a = 7.5 < 10$ ✓. Units: ms throughout.

Worked example Example 9 — Exam twist: "Which class is it?" (Cell C10)

An algorithm sorts by random-pivot QuickSort but, to save time, stops early after exactly $2 n lo g_{2} n$ comparisons and returns whatever partial order it has. Las Vegas or Monte Carlo? Then: a Quickselect that runs to completion with random pivots — which class?

Forecast: does "always sorted output" or "fixed comparison budget" decide the label?

The capped sorter has a fixed comparison budget ( $2 n lo g_{2} n$ ) and may return an unsorted (wrong) array if unlucky → Monte Carlo. Why this step? Fixed/bounded time + possibly-wrong answer is the Monte Carlo signature; the cap converted a Las Vegas algorithm into Monte Carlo (an LV→MC move, like Ex 6).
Plain random-pivot Quickselect runs to the end, always returning the true $k$ -th element, with random running time → Las Vegas. Why this step? Always-correct + random time is the Las Vegas signature; the randomness is in when it finishes, never in what it outputs.
Rule of thumb: ask "can the OUTPUT be wrong?" If yes → Monte Carlo. If only the TIME varies → Las Vegas. Why this step? This single question resolves every mislabelling trap on an exam.

Verify: consistency with the parent's mnemonic — Las Vegas "always leaves with the right money but not knowing when" = Quickselect ✓; Monte Carlo "leaves on time, maybe wrong money" = the capped sorter ✓.

Recall Quick self-test

A retry loop succeeds with $p = 0.2$ . Expected trials? ::: $1/ p = 5$ . One-sided MC wrong w.p. $q = 1/4$ ; error after $k = 15$ rounds is below? ::: $(1/4)^{15} = 2^{- 30} \approx 9.3 \times 1 0^{- 10}$ . Two-sided error $1/3$ per run, best-of-5 wrong prob? ::: $51/243 \approx 0.21$ . Budget $= 10 E [T]$ , overrun bound by Markov? ::: $\leq 1/10$ . "Output can be wrong" → which class? ::: Monte Carlo.