You're given a fair coin. The goal is to use it to generate a random decimal digit.
I didn't find any solutions on the internet, so I came up with one myself. It goes as follows:
Assign $0$ to heads and $1$ to tails. To the first ten binary numbers (starting with zero), assign the decimal digits from $0$ to $9$. Do the same to the binary versions of 10 through 19 and 20 through 29. The binary numbers corresponding to 30 and 31 must be discarded, and the procedure outlined below must be carried out again.
Toss the coin five times, this will generate a 5-tuple of ones and zeros. This 5-tuple can be viewed as a binary number (with the obvious condition to ignore the leading zero or zeros). By the assignment scheme outlined above, every 5-tuple corresponds to a decimal digit (except the binary 30 and 31 that should be ignored).
Note: I chose 5-tuples over 4-tuples because with 4-tuples, the whole procedure is less effective (a much larger portion of the possible outcomes must be discarded).
My question: Is there a simpler way to generate a random decimal digit using a fair coin than the one I've described?
This is a nice simple approach. If you just reroll entirely when you get $30$ or $31$ you use on average $\frac {32}{30}\cdot 5=\frac {16}3$ flips per digit.
You can do better at the cost of some complexity. You need at least an average of $\log_2 (10)\approx 3.322$ flips per digit. If you flip $10$ times you generate a number from $0$ to $1023$. If it is less than $1000$ you have three digits. If it is $1000-1019$ you have one digit. Ten flips then give you on average $\frac {1000\cdot 3 + 20\cdot 1}{1024}\approx 2.949$ bits or we use about $3.391$ flips per digit, which is not far from the optimum.
To do better yet, throw $332193$ flips and generate a huge binary number. Most of the time you will get $100\ 000$ decimal digits.