0

I have a $6$-sided dice and I would like to sample integers uniformly from $0$ to $k$ with $k > 6$. I think that $k$ should be written in its binary representation. Let's say its binary representation has $n$ bits. I should then roll the dice and set rolls $1,2,3$ as corresponding to 0, and rolls $4,5,6$ as corresponding to 1. Then I should roll the dice $n$ times to get each binary bit.

If the resulting number is greater than $k$ (eg, it is 244 which has an 8-bit binary representation, but there exist 8-bit binary numbers which are greater than it), then the number should be rejected and the process should be repeated until we get an appropriate number.

Does this sample uniformly?

I think that it should. I think that this uniformly gives an 8-bit binary number because it's like we're sampling on $\{0,1\}^n$ which can be done by sampling $n$ i.i.d uniform variables for each coordinate.

However, how can it be guaranteed that the rejection part of this process makes sure that the sample will still be uniform?

Featherball
  • 216
  • 2
    There's a number of posts already on the topic of generating uniform random numbers using a fair die. It might be worth trying a few searches. – Glen_b Mar 13 '22 at 11:06
  • @Glen_b I couldn't find anything relating to an approach using binary – Featherball Mar 13 '22 at 11:47
  • 1
    Use the representation of integers in base 6, not 2? – Xi'an Mar 13 '22 at 17:30
  • 1
    @Featherball Oh, sorry I was distracted while typing that. When you're dichotomizing, search for using a coin instead, since that's the obvious model people will discuss. – Glen_b Mar 13 '22 at 22:24
  • For a generalization, see https://stats.stackexchange.com/questions/354678/brain-teaser-how-to-generate-7-integers-with-equal-probability-using-a-biased-c. – whuber Jul 21 '22 at 15:30

0 Answers0