Randomized Algorithms

We are taught that computers are precise machines: same input, same output, every time. So it feels almost like cheating to learn that some of the fastest and simplest algorithms ever written deliberately flip coins.

A randomized algorithm makes random choices as it runs. Two runs on the very same input can take different paths — and sometimes even give different answers. That sounds like a bug, but used carefully it is a superpower: randomness can dodge the worst case, shrink the code, or solve a problem far faster than any known deterministic recipe.

The art is in what you trade. Some randomized algorithms are always correct but their running time varies. Others are blazing fast but carry a tiny, controllable chance of being wrong. Understanding that trade-off is the whole game.

Here is the most famous randomized trick of all. Throw darts at random into a square, and check how many land inside the circle that just fits in it. The fraction inside is the ratio of the circle's area to the square's — which works out to π/4. Multiply by four and you have estimated π with nothing but a random number generator.

<p class="hint">{{hint}}</p>
<canvas id="board" width="260" height="260"></canvas>
<div class="readout">
  <div><span class="lbl">{{lbl_darts}}</span><span id="total">0</span></div>
  <div><span class="lbl">{{lbl_inside}}</span><span id="inside">0</span></div>
  <div><span class="lbl">{{lbl_pi}}</span><span id="pi">—</span></div>
  <div><span class="lbl">{{lbl_error}}</span><span id="err">—</span></div>
</div>
<div class="btns">
  <button id="throw10" type="button">{{btn_throw10}}</button>
  <button id="throw1k" type="button">{{btn_throw1k}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#board { border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fb; display: block; }
.readout { display: grid; grid-template-columns: repeat(2, minmax(120px, 1fr)); gap: .35rem .9rem;
           margin: .7rem 0; font: 600 15px ui-monospace, monospace; }
.readout div { display: flex; justify-content: space-between; border-bottom: 1px solid #eef2f6; padding: .2rem 0; }
.lbl { color: #5a7088; font-weight: 600; }
#pi { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Throw a handful of darts and the estimate is rough and jittery. Throw thousands and it settles near 3.14159. This is a Monte Carlo algorithm in its purest form: each answer is probably close, and the more random samples you take, the tighter it gets. The error shrinks with the square root of the number of darts — never exact, but as accurate as you are patient.

Randomized algorithms fall into two great families, named after two cities famous for gambling:

• Monte Carlo algorithms run in a fixed, fast time but may be wrong with some small probability. The pi demo is Monte Carlo: it always finishes quickly, but its answer is only approximate. The fix is cheap — run it more and the error melts away.
• Las Vegas algorithms are always correct, but their running time is random. Randomized quicksort is the classic example: it never returns a wrong order, yet a bad streak of pivot choices can make a single run slow. On average it is fast, and a catastrophic case is astronomically unlikely.

You can always convert between them. Run a Las Vegas algorithm and cut it off early, and you get a Monte Carlo one. Re-run a Monte Carlo algorithm until a quick check confirms the answer, and you get Las Vegas.

Complexity theory bottles this up in the class BPP — problems solvable in polynomial time with a bounded error probability (say, wrong at most 1/3 of the time, which repetition crushes to nothing). A deep open question lurks here: is BPP = P? That is, can every fast randomized algorithm be derandomized into an equally fast one with no coins at all? Most researchers now believe the answer is yes, but it is still unproven — a quiet cousin of P vs NP.

Deliberate randomness is everywhere in the software you rely on:

• Primality and cryptography: the Miller–Rabin test decides whether a giant number is prime by flipping coins — it is how your browser finds the primes behind RSA keys. See Is N Prime?.
• Monte Carlo simulation: physicists, banks and weather services estimate impossible integrals by sampling — the same dart-throwing idea, scaled to millions of dimensions.
• Hashing and data structures: randomized hashing spreads keys evenly and defeats adversaries who would otherwise force the worst case.
• Machine learning: stochastic gradient descent, random forests and dropout all lean on randomness to train models and avoid overfitting.
• Load balancing: the "power of two random choices" keeps servers evenly loaded with almost no coordination.

The lesson echoes the way randomized methods sit beside exact ones in computing π: when the exact approach is too slow or too fragile, a few well-aimed coin flips often win.

Randomness turns out to be one of the most elegant resources in computing. A few coin flips can let an algorithm sidestep its worst case, replace pages of careful logic with a short loop, or estimate a quantity that no exact method could reach in time. The price is a touch of uncertainty — but it is uncertainty you control, shrinking it as small as you like by simply trying again.

So the next time you watch those darts settle near 3.14159, remember the bigger picture: whether all that randomness is truly necessary — whether BPP = P — is still an open question, and one of the quietly beautiful mysteries that lives next door to P vs NP.