Generate Uniform 1-7 from Uniform 1-5
You are given a function rand5() that returns a uniformly random integer from 1 to 5. Using only rand5(), build rand7() returning a uniformly random integer from 1 to 7, then measure it empirically.
Implement the function
```python def rand7_mean(n, seed): ... ```
which must: - create a deterministic generator rng = random.Random(seed) and rand5 = lambda: rng.randint(1, 5), - build rand7() from rand5() by rejection sampling: take two rand5() calls as num = 5*(rand5()-1) + (rand5()-1) (uniform on $\{0,\dots,24\}$); if num < 21 accept and output num % 7 + 1, otherwise reject and retry, - draw n independent rand7() values and return their empirical mean sum(draws) / n (a float).
The result must be deterministic given (n, seed). As n grows the mean converges to the true mean of a uniform draw on $\{1,\dots,7\}$, namely $4.0$.
Constraints: - You may call rand5() as many times as needed; each call is independent and uniform on $\{1,2,3,4,5\}$. - Each of $\{1,\dots,7\}$ must be produced with probability exactly $\frac{1}{7}$.
Example
rand7_mean(20000, 1) -> 3.9981
With seed=1, the seeded RNG makes the 20000 draws fully reproducible; their average 3.9981 sits just below the true mean 4.0, and it tightens toward 4.0 as n increases.
Hints
- Two calls to
rand5()give you 25 equally likely outcomes -- how can you map a subset of those to 7 equal groups? - The largest multiple of 7 at most 25 is 21. Use outcomes 0-20 and reject 21-24.
- Compute
5 * (rand5() - 1) + (rand5() - 1)to get a uniform value in $\{0, \ldots, 24\}$, then use modulo 7 on the accepted range.
Worked Solution
How to Think About It: Two calls to rand5() give you $5 \times 5 = 25$ equally likely outcomes. You need to map these to 7 equally likely outcomes. Since 7 does not divide 25, you cannot use all 25 outcomes -- you must reject some. The largest multiple of 7 that fits in 25 is 21, so you use outcomes 0-20 (mapped to 1-7 via modulo) and reject outcomes 21-24. This is rejection sampling.
What this problem actually asks: the graded entry point is rand7_mean(n, seed), not rand7() by itself. You must (1) build a deterministic rand5() from random.Random(seed), (2) build rand7() on top of it via rejection sampling, then (3) return the empirical mean of n independent rand7() draws, sum(draws) / n. Because the RNG is seeded, the result is fully reproducible for a given (n, seed), and as n grows it converges to the true mean of a uniform draw on $\{1,\dots,7\}$, which is $4.0$.
Algorithm for rand7():
- Call
rand5()twice to generate a uniform random number in $\{0, 1, \ldots, 24\}$ using $5 \cdot (a - 1) + (b - 1)$. - If the result is less than 21, return
result % 7 + 1. - Otherwise, reject and repeat from step 1.
Each of the values 0-20 maps to exactly one of 1-7 (three values each), so the output is perfectly uniform.
Code:
```python import random
def rand7_mean(n, seed): rng = random.Random(seed) rand5 = lambda: rng.randint(1, 5) def rand7(): while True: num = 5 * (rand5() - 1) + (rand5() - 1) if num < 21: return num % 7 + 1 total = 0 for _ in range(n): total += rand7() return total / n ```
Complexity: - Each rand7() iteration uses 2 calls to rand5(); acceptance probability $\frac{21}{25} = 0.84$. - Expected rand5() calls per output: $2 \times \frac{25}{21} = \frac{50}{21} \approx 2.38$. - rand7_mean therefore makes $\approx 2.38 n$ calls to rand5() and returns a single float.
Why rejection is unavoidable: a single rand5() produces $\log_2 5 \approx 2.32$ bits of entropy while rand7() needs $\log_2 7 \approx 2.81$ bits, and since $\log_2 7 / \log_2 5$ is irrational no finite number of rand5() calls yields exactly the right entropy. Rejection sampling is the standard fix.
Answer: Build rand7() by rejection sampling on the 25-outcome space (accept 21, reject 4), then average n draws. rand7_mean returns that empirical mean, which tends to $4.0$.
Intuition
This is the canonical example of rejection sampling for discrete distributions. The fundamental issue is that 5 and 7 are coprime, so no finite number of base-5 "digits" can produce a range that is a multiple of 7. You deal with this by generating a range larger than you need, carving out the biggest chunk divisible by 7, and throwing away the rest.
This pattern is ubiquitous in practice. Random number generators in standard libraries use exactly this technique when converting from one range to another. The efficiency depends on how much you waste: here you reject $4/25 = 16\%$ of attempts. You could reduce waste by using more calls (e.g., three calls give $125$ outcomes, and $\lfloor 125/7 \rfloor = 17$, using $119/125 = 95.2\%$), but the marginal improvement shrinks quickly. In an interview, the two-call version is clean and sufficient.