rand7 from rand5 without wasting the rejects
rand5() returns a uniform integer in . To produce one uniform value in , a generator keeps a pair with uniform on , starting from , and repeats:
- call
rand5()to get ; set and ; - let ; if , output and stop;
- otherwise set , (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)+
- After a rejection, how large is the range of the leftover uniform value? Does it depend on ?
- Track the range: ; each step keeps values.
- Use ; the states repeat every 6 calls.
Answer
Reveal answer →Final 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