Generate a number with a die that has three 0s and three 1s

Question

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.

Answer 1

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.

Answer 2

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.