Engineering / Mathematics — Discrete Probability
Infinite Discrete Probability Distributions
Countably infinite sample spaces, convergence conditions, and the geometric distribution arising from unbounded loops.
Executive summary
An algorithm that repeats until success has no bound on its running time, so its analysis needs a countably infinite sample space. The extension is routine but two conditions must be checked: that the probabilities sum to one, and that expectations converge.
The geometric distribution is the recurring instance.
Learning objectives
- Extend the probability framework to countable spaces.
- State the convergence conditions.
- Analyse a repeat-until-success loop.
01The extension
Discrete probability distribution
A countable set Ω with P : Ω → [0,1] satisfying Σ_{ω} P(ω) = 1, the sum being an absolutely convergent series.
Absolute convergence means the order of summation is irrelevant, which is what allows the finite-case manipulations to carry over unchanged. Markov's and Chebyshev's inequalities hold verbatim, given that the relevant expectations exist.
02The geometric distribution
Geometric distribution
Independent trials each succeeding with probability p. The number of trials X until the first success satisfies P(X = k) = (1−p)^{k−1}p.
- Expectation
E[X] = 1/pExpected trials until success - Variance
Var[X] = (1−p)/p²Spread grows as p shrinks - Tail
P(X > k) = (1−p)^kExponential decay; gives a clean cutoff bound - Memorylessness
P(X > j+k | X > j) = P(X > k)Past failures give no information
The tail bound is what justifies imposing an iteration cap. Setting the cap at k trials leaves failure probability (1−p)^k, which for modest k is negligible.
03Analysing a repeat-until-success loop
Random prime generation is the standard instance: draw a candidate, test it, repeat until one passes.
Establish per-trial success probability
For k-bit candidates the prime density gives p ≈ 2/(k ln 2).
Expected trials
1/p ≈ (k ln 2)/2, so about 355 for 1024-bit primes.
Expected total cost
Trials times per-trial cost, valid by Wald's identity since the trial count is independent of individual costs.
Impose a cap
Choose an iteration limit leaving failure probability below the system's error budget.
04Frequently asked questions
Can a distribution over a countable set be uniform?
No. Equal positive weights on infinitely many outcomes sum to infinity, and zero weights sum to zero. This is why uniform sampling from an unbounded set requires a different formalism.
Does memorylessness mean a long run of failures is not overdue?
Exactly. Each trial is independent, so past failures carry no information about the next. The gambler's fallacy is the intuitive denial of this property.
Is expected running time enough for a guarantee?
No. It says nothing about variability, and Markov's inequality alone gives only a weak tail bound. For the geometric distribution the exact exponential tail is available and should be used instead.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 141-147.
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.