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.

  • $\begingroup$ 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. $\endgroup$ – Aretino Sep 20 '15 at 16:49
  • $\begingroup$ 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$. $\endgroup$ – lulu Sep 20 '15 at 16:59
  • $\begingroup$ @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? $\endgroup$ – QPTR Sep 20 '15 at 17:00
  • $\begingroup$ @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. $\endgroup$ – QPTR Sep 20 '15 at 17:04
  • $\begingroup$ 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. $\endgroup$ – lulu Sep 20 '15 at 17:06

Your Answer

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

Browse other questions tagged or ask your own question.