Generating a Uniform Distribution over {1, 2, 3} from an Arbitrary RNG

Probability · Medium · Free problem

You have access to a random number generator that produces integers uniformly over $\{1, 2, \ldots, n\}$ for some given $n$. You want to produce outputs that are uniformly distributed over $\{1, 2, 3\}$ -- each value appearing with probability exactly

/3$.

How would you design this procedure? Consider two cases: 1. The generator produces integers from $\{1, \ldots, 6\}$ (a fair die). 2. The generator produces integers from $\{1, \ldots, 5\}$.

For the general case, describe an algorithm that works for any $n$ and prove that it produces exact uniform probabilities.

Hints

  1. You cannot perfectly split $n$ equally-likely outcomes into exactly 3 groups unless $3 \mid n$. The standard fix is rejection sampling: throw away some outcomes to make the effective sample space divisible by 3.
  2. Find the largest multiple of 3 that is at most $n$ -- call it $m = 3\lfloor n/3 \rfloor$. Accept draws in $\{1, \ldots, m\}$ and reject the rest. Conditional on acceptance, the draw is uniform over a set of size $m$, which divides evenly by 3.
  3. Map an accepted draw $X$ to output $((X-1) \bmod 3) + 1$. Verify: for $n=6$, $m=6$, $P(\text{output}=k) = 2/6 = 1/3$ for each $k$. For $n=5$, $m=3$, $P(\text{output}=k) = 1/3$ conditional on acceptance, and acceptance probability is $3/5$.

Worked Solution

How to Think About It: The fundamental tension here is that

/3$ is irrational in binary (and in base-$n$ for $n$ not divisible by 3). So you can never map the output of a generator with $n$ outcomes directly onto $\{1,2,3\}$ with exact uniform probabilities unless $3 \mid n$. The fix is rejection sampling: use only the outcomes that divide evenly into three equal groups, and retry when you land outside that range. This is conceptually simple but the key insight is choosing the right threshold for rejection to guarantee uniformity without bias.

Key Insight: If $3 \mid n$, every integer in $\{1, \ldots, n\}$ can be mapped to $\{1,2,3\}$ via $((x-1) \bmod 3) + 1$ with no rejection needed. If $3 \nmid n$, restrict to the range $\{1, \ldots, 3\lfloor n/3 \rfloor\}$ and reject values above that threshold.

The Method:

  1. Let $m = 3\lfloor n/3 \rfloor$ (the largest multiple of 3 that is $\leq n$).
  2. Draw $X \sim \text{Uniform}\{1, \ldots, n\}$.
  3. If $X > m$, discard $X$ and return to step 2.
  4. If $X \leq m$, return $((X - 1) \bmod 3) + 1$.

Why it works: Conditional on acceptance ($X \leq m$), the variable $X$ is uniform on $\{1, \ldots, m\}$. Since $3 \mid m$, exactly $m/3$ values in $\{1, \ldots, m\}$ map to each of $\{1, 2, 3\}$. So each output value has conditional probability $\frac{m/3}{m} = 1/3$. Exact uniformity.

Case 1: Fair die ($n = 6$). $6 = 3 \times 2$, so $m = 6$ and there is no rejection. Map: $1, 2 \to 1, \quad 3, 4 \to 2, \quad 5, 6 \to 3$ All 6 outcomes are used; each of $\{1,2,3\}$ gets probability

/6 = 1/3$. Zero wasted draws.

Case 2: $n = 5$ (rand over $\{1,2,3,4,5\}$). $\lfloor 5/3 \rfloor = 1$, so $m = 3$. Accept $X \in \{1, 2, 3\}$, reject $X \in \{4, 5\}$. - Map:

\to 1$,
\to 2$, $3 \to 3$. - $P(\text{accept}) = 3/5$ per draw. - Expected number of draws: $5/3 \approx 1.67$.

Practical Considerations: - Efficiency: The rejection probability is at most /n$ (at most 2 values are discarded per draw). For large $n$, this is negligible. - No modular bias: A common mistake is to simply compute $X \bmod 3$ and map 0 to 3. This produces bias whenever $n$ is not divisible by 3, because the 'extra' values (above $m$) inflate probabilities for some outcomes. - Bits, not integers: If your source is a bit stream (fair coin), the same principle applies: draw $\lceil \log_2 3 \rceil = 2$ bits at a time, giving values $\{0,1,2,3\}$; accept $\{0,1,2\}$ and map to $\{1,2,3\}$, reject $3$ and retry. Expected bits consumed: \times \frac{4}{3} = 8/3 \approx 2.67$ bits per output.

Answer: Use rejection sampling. Discard draws above $3\lfloor n/3 \rfloor$; map accepted draws via $((X-1) \bmod 3) + 1$. Each of $\{1, 2, 3\}$ appears with exact probability

/3$. For a fair die ($n=6$): no rejection, direct mapping. For $n=5$: accept $\{1,2,3\}$, reject $\{4,5\}$, expected 1.67 draws per output.

Intuition

Rejection sampling is the go-to tool whenever you need to transform one probability distribution into another that is not a clean ratio of the source. The key principle is: instead of trying to stretch or compress an ill-fitting distribution, throw away the inconvenient part and condition on what remains. As long as the acceptance region is chosen symmetrically with respect to the target distribution, the conditional distribution of the accepted draws is exactly what you want.

This shows up in more sophisticated forms throughout quant work: inverse CDF sampling, the Box-Muller transform, and Metropolis-Hastings MCMC all use versions of this idea. The common mistake -- taking $X \bmod 3$ directly without rejection -- is called modular bias and is a notorious bug in random number generation for games, simulations, and cryptographic applications. Even a small bias (like $P(1) = 0.3334$ vs

/3$) compounds badly over many samples.

Open the full interactive solver →