Visual walkthrough — Randomized algorithms — Las Vegas, Monte Carlo

We build up ideas from Probability and Expectation, and at the end connect to how this powers QuickSort and Quickselect.

Step 1 — What is one "attempt"?

WHAT. Our Las Vegas retry loop does the same thing over and over: make one random attempt. Each attempt either succeeds or fails. Nothing in between.

WHY. Before we can count attempts, we must agree on the atom we are counting. The atom is a single attempt, and it has exactly two outcomes. We will draw an attempt as a coin flip: a coin that lands "success" some fraction of the time and "fail" the rest.

PICTURE. The coin below is biased: the green "SUCCESS" slice covers a fraction $p$ of the coin, the red "FAIL" slice covers the leftover $1-p$.

Step 2 — What does the loop actually look like over time?

WHAT. The algorithm keeps flipping this coin. On the first "success" it STOPS and returns the (always correct) answer. We call $N$ the number of flips until — and including — that first success.

WHY. $N$ is the thing the parent note calls "running time in trials". It is random: on a lucky day $N=1$; on an unlucky day the coin keeps landing red and $N$ grows. We want the average value of $N$ over many imaginary runs.

PICTURE. Three example runs. Run A got success immediately ($N=1$). Run B failed once then succeeded ($N=2$). Run C failed three times then succeeded ($N=4$). Notice: every run eventually ends in one green flip, and the reds pile up before it.

Step 3 — The probability of each possible run

WHAT. Let us list how likely each value of $N$ is. To get $N=1$, the very first flip is green: probability $p$. To get $N=2$, flip 1 is red then flip 2 is green: probability $(1-p)\cdot p$. To get $N=3$: red, red, green $=(1-p{)}^{2}p$. And so on.

WHY. Flips are independent — one flip's result never changes the next flip's odds (the coin has no memory). For independent events we multiply their probabilities. Each extra failure tacks on another factor of $(1-p)$.

PICTURE. The tree branches red (fail) on the left, green (success) on the right. Each leaf is a value of $N$; the probability written under it is the product of the branch fractions you walked through to reach it.

Step 4 — The memoryless trick (the key idea)

WHAT. Instead of summing an infinite series, we use a shortcut. Look at what happens on the very first flip and split into two worlds:

• Green world (probability $p$): we won on flip 1. Total flips used $=1$. Done.
• Red world (probability $1-p$): we wasted flip 1. But now — and this is the magic — we are standing at exactly the same starting line as before. The coin has no memory, so the expected number of additional flips from here is the very same $E[N]$ we are trying to find.

WHY. This is called memorylessness: after a failure the future looks identical to the beginning. That lets $E[N]$ refer to itself, turning an infinite process into one small equation.

PICTURE. The green branch ends the game at cost $1$. The red branch pays cost $1$ and then loops back into a fresh copy of the whole problem — drawn as an arrow curling back to "start".

Step 5 — Solving the equation

WHAT. Now it is pure algebra. Let $E=E[N]$ to keep it short.

WHY. We isolate $E$ to get a closed formula — a plain number we can plug $p$ into.

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

Multiply out the right side. The $(1-p)(1+E)$ becomes $(1-p)+(1-p)E$:

$E=p+(1-p)+(1-p)E$

The two lonely fractions add to $1$ (Step 1's identity, $p+(1-p)=1$):

$E=1+(1-p)E$

Now gather every $E$ on the left. Subtract $(1-p)E$ from both sides:

$E-(1-p)E=1$

Factor $E$ out of the left. Since $1-(1-p)=p$:

$E\cdot p=1$

Divide both sides by $p$:

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

PICTURE. The curve $E[N]=1/p$: as the green slice $p$ shrinks toward $0$, the expected number of tries rockets to infinity; as $p\to 1$ (an almost-always-winning coin), it flattens toward $1$ try.

Step 6 — Sanity checks and the edge cases

WHAT. A formula you cannot test is a formula you cannot trust. Let us hit every corner.

WHY. The contract: the reader must never meet a case we did not show. So we walk $p=\frac{1}{2}$, $p=0.01$, the extreme $p\to 1$, and the degenerate $p=0$.

PICTURE. A little table-plot: for each $p$ we mark $1/p$ as a dot, and shade the danger zone where $p$ approaches $0$.

The one-picture summary

Everything on one canvas: the biased coin (Step 1) feeds the branch (Step 4); the green branch stops at cost $1$, the red branch loops back; that loop is the equation $E=p\cdot 1+(1-p)(1+E)$, which collapses to the curve $E=1/p$.

Flashcards