Engineering / Mathematics — Probabilistic Algorithms
Flipping a Coin Until a Head Appears
The geometric waiting time, its expectation and tail, and its role as the model for repeat-until-success algorithms.
Executive summary
The number of trials until the first success is the simplest non-trivial infinite-support distribution, and it models every repeat-until-success algorithm in this subject.
Its expectation is the reciprocal of the success probability and its tail decays geometrically, which together supply everything an analysis needs.
Learning objectives
- Derive the expectation of the geometric distribution.
- State the tail bound and use it to set an iteration cap.
- Apply the model to a concrete algorithm.
01Expectation
Expected waiting time
With independent trials each succeeding with probability p > 0, the expected number of trials until the first success is 1/p.
The cleanest derivation uses the tail-sum formula together with the tail probability.
E[X] = Σ_{k≥0} P(X > k) = Σ_{k≥0} (1−p)^k = 1/pAn alternative derivation conditions on the first trial: either it succeeds, or one trial is spent and the situation resets by memorylessness, giving E = 1 + (1−p)E.
02Tail behaviour
- Tail probability
P(X > k) = (1−p)^kExponential decay in k - Cap at c/p trials
failure ≤ e^{−c}Using (1−p)^{1/p} ≤ 1/e - Cap at 100/p
failure ≤ e^{−100}Below any practical threshold
The bound (1−p)^{1/p} ≤ 1/e is the exponential inequality again, and it converts an iteration cap expressed as a multiple of the expected count into a clean failure bound.
03Application
Finding a quadratic non-residue modulo a prime is the standard illustration. Exactly half the non-zero residues are non-residues, so a random guess succeeds with probability one half.
Find a quadratic non-residue mod p
odd prime pa quadratic non-residue modulo p- Draw a uniformly at random from {1, ..., p−1}.
- Compute the Legendre symbol of a modulo p.
- If the symbol is −1, return a.
- Otherwise repeat, up to a fixed cap.
expected 2 iterations, each O(len(p)²)04Frequently asked questions
Is the expected value ever attained?
Not generally — for p = 1/2 the expectation is 2, which is attainable, but for p = 1/3 the expectation is 3 while the distribution is supported on integers with no particular mass at 3. Expectation is an average, not a typical value.
Why does memorylessness hold?
Because trials are independent, so conditioning on past failures leaves the future distribution unchanged. The geometric distribution is the only discrete distribution with this property.
What if the success probability is unknown?
A lower bound on p suffices to bound the expected count and set a cap. This is the usual situation in prime generation, where the prime number theorem supplies the lower bound.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 158-159.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.