# generating random numbers using an unbiased coin

I have a question in which I need to generate random numbers in the range 0-9 by means of an unbiased coin such that it is equally likely to get any number. Since there is no limit on the number of coin tosses I first tried to do it like this:

1. Do 10 coin tosses.
2. If a head appears in the nth coin toss, then generate that number. I.e if the sequence is 0000000001, then generate 0, if 0000000010 then generate 1 and so on. I defined this as my random variable

This method does give an equal probability of (1/2) ^ 10 but the sum of all 10 events does (while calculating the probability mass function) not sum up to one.

Then afterwards I tried to do it by defining the random variable as the appearance of consecutive heads. So if, consecutive heads = 1, then generate 0, if consecutive heads = 2, then generate the number 2 and so on. This maps to a binomial distribution, and even though it sums up to 1, the probability of getting each number is different.

Is there any way I could do this, or could anyone please give me a hint on how to approach this problem?

Thank you.

• It' impossible to accomplish the task without discarding events, in my opinion, because $2^n$ is never a multiple of $10$. Anyway you discard too much: you can do with only 4 tosses, considering the outcome as a binary number. – Aretino Sep 20 '15 at 16:49
• As a (minor) variant to the suggestion in the prior comment, you could do $5$ tosses...the advantage being that you only need to discard $2$ cases, whereas with $4$ tosses you must discard $6$. – lulu Sep 20 '15 at 16:59
• @Aretino If I discard the 10, 11, 12, 13, 14, and 15 binary won't these events be no longer a part of the sample space? – QPTR Sep 20 '15 at 17:00
• @lulu 2 cases because I could something like map 00000 and 00001 to 0, 00010 and 00011 to 1 and so on? So, 30 binary numbers could be mapped on 10 decimal ones, leaving the two? edit: sorry, meant three binary numbers to each decimal one, so 00000, 00001 and 00010 to 0 and so on. – QPTR Sep 20 '15 at 17:04
• Exactly. This way you get a result $\frac {30}{32}=93.75\%$ of the time, whereas with $4$ tosses you only get a result $\frac {10}{16}=62.5\%$ of the time. – lulu Sep 20 '15 at 17:06