2
$\begingroup$

Let's say I have a regular fair die, but instead of digits 1 through 6, there are three 0s and three 1s.

I can generate a random $n$-digit binary number as follows: if initially I roll a zero (or a series of them), I ignore them; then what is left to do is just roll the die $n$ times. [Thanks to user Alex Meiburg, I have learned that this strategy does generate random numbers, but not uniformly; as he pointed out, generating, e.g., '101' is 3 (!) times more likely than generating '111'. Given this, I would appreciate if someone proposed a strategy lacking this oddity.]

Question: What is the simplest algorithm to generate a random $n$-digit number in base-$b$, $b\neq2$ using this "binary" die?

I have been trying to come up with an answer for a few hours, but I feel that there is none.

$\endgroup$
3
  • 1
    $\begingroup$ The algorithm you describe for binary numbers is random, and has a nonzero chance of producing every n-bit number, but it's not uniform. For instance, you have 3 times the chance of generating "101" over "111". Is this what you want? $\endgroup$ – Alex Meiburg Nov 19 '16 at 20:34
  • $\begingroup$ @AlexMeiburg definitely not. I have made an edit pointing this out. $\endgroup$ – user376034 Nov 19 '16 at 20:39
  • 1
    $\begingroup$ I'm not sure I understand the question. Can you just roll your die $n-1$ times and stick a $1$ at the beginning to maoe an $n $-bit nunber? $\endgroup$ – Mark S. Nov 19 '16 at 20:50
2
$\begingroup$

This method is probably best explained by an illustrative example. Suppose you want a random four-digit number in base 6: anything from $1000_6$ to $5555_6$ inclusive (for a total of $1295-216+1=1080$ possibilities).

Since $10$ bits would only give you $1024$ possibilities, we need to use at least $11$ bits, so generate $11$ random bits (by rolling the "die" 11 times), and write them as a binary number (like $00000000110_2=6$). If that number is between $0$ and $1079$ inclusive, add $6^3$ to it to get to get a number between $1000_6$ and $5555_6$. If the binary number was between $1080$ and $2047$ inclusive: too bad, try again by generating 11 new random bits.

In a bad case like this where nearly half of the possibilities are too high to use, the expected number of tries is a little under 2, so this method with retries like this isn't so terrible.

Side note: This algorithm/question is very closely related to the one at Generate random integers from random bit sequence.

$\endgroup$
2
  • $\begingroup$ Thank you for this wonderful answer! Side question: does the strategy you described in the question's comments section generate random binary numbers uniformly? $\endgroup$ – user376034 Nov 25 '16 at 7:46
  • 1
    $\begingroup$ @user376034, If I understand your question correctly, the answer is "yes". Example: If you want a three "digit" binary number, there are $2^{3-1}=4$ possibilities between $100$ and $111$. If you flip a coin (i.e. roll your die) twice then each of "00", "01", "10", and "11" have an equal chance ($\frac14$) of occurring. "sticking a $1$ at the front" as in my comment and "adding $2^2$" as in my answer do the exact same thing: they map these four equally-likely possibilities to the four possibilities you're interested in. $\endgroup$ – Mark S. Nov 25 '16 at 18:25
-1
$\begingroup$

I'm not sure what your difficulty is.

To generate a $n$-digit binary number.

First roll produces $0$ or $1$: this is the first digit.

Second roll produces $0$ or $1$: this is the second digit.

Keep rolling until you have $n$ digits.

This will give you (in binary) the numbers from $0$ to $2^{n}-1$. Each will be equally likely to occur.

To generate a $n$-digit number for another base $b \ne2$, first find the smallest value $k$ such that $2^k >b$.

For the first digit, produce a $k$-digit binary number $n$. If $n \ge b$ then it is not suitable for use in base $b$, so generate another $k$-digit binary number $n$ until $n <b$. This is the first digit.

For the second digit, produce a $k$-digit binary number $n$. If $n \ge b$ then it is not suitable for use in base $b$, so generate another $k$-digit binary number $n$ until $n <b$. This is the second digit.

Continue until you have a list of $n$ digits.

$\endgroup$
2
  • $\begingroup$ The first digit of any nonzero binary number is 1. $\endgroup$ – user376034 Nov 20 '16 at 5:46
  • 1
    $\begingroup$ @user376034 Not necesarily. If I am using 4 bits to encode my binary numbers then the possible numbers are: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. These are the 16 different possible 4-digit binary numbers. My algorithm would give each an equal chance of being produced. $\endgroup$ – tomi Nov 20 '16 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.