Skip to content
Get started

rand7 from rand5 without wasting the rejects

rand5() returns a uniform integer in {0,1,2,3,4}\{0, 1, 2, 3, 4\}. To produce one uniform value in {0,…,6}\{0, \dots, 6\}, a generator keeps a pair (U,m)(U, m) with UU uniform on {0,…,m−1}\{0, \dots, m-1\}, starting from (0,1)(0, 1), and repeats:

  1. call rand5() to get bb; set U←5U+bU \leftarrow 5U + b and m←5mm \leftarrow 5m;
  2. let q=7⌊m/7⌋q = 7\lfloor m/7 \rfloor; if U<qU < q, output U mod 7U \bmod 7 and stop;
  3. otherwise set U←U−qU \leftarrow U - q, m←m−qm \leftarrow m - q (the rejected value is still uniform on the smaller range) and go back to step 1.

What is the expected number of rand5() calls per output? Give it to 3 decimal places.

Show hints (3)+
  1. After a rejection, how large is the range of the leftover uniform value? Does it depend on UU?
  2. Track the range: 1→5→4→…1 \to 5 \to 4 \to \dots; each step keeps 5m mod 75m \bmod 7 values.
  3. Use E[N]=∑kP(N≥k)E[N] = \sum_k P(N \ge k); the states repeat every 6 calls.

Answer

Reveal answer →

2.212 (± 0.002)

Create a free account to see the full worked solution and track your progress.

Interview format: Market Maker, Prop Trading

Related questions