1

The usual method to generate a uniform random number 0..n using coin flips is to build a rng for the smallest power of two greater than n in the obvious way, then whenever this algorithm generates a number larger than n-1, throw that number away and try again.

Unfortunately this has worst case runtime of infinity.

Is there any way to solve this problem while guaranteeing termination?

owencm
  • 8,384
  • 6
  • 38
  • 54
  • Obviously, n can be written as sum 2^p1 + 2^p2 + ... (which has q terms, let's say). Then you can generate q random numbers for each term of the previous sum and add them to generate your searched random number. – wxyz Jan 27 '14 at 13:53
  • Have a look at http://stackoverflow.com/a/891304/916657 You can achieve what you want at the expense of lots of memory. I'd rather go with the constant memory method, which is practically bounded in runtime because it gets exponentially more unlikely to run long. – Niklas B. Jan 27 '14 at 13:55
  • @wxyz that's no uniform distribution though and you can't specify the range. – Niklas B. Jan 27 '14 at 13:57
  • can be improved by flipping a coin also to decide if the number generated for 2^pi term should be added or not to the final result. – wxyz Jan 27 '14 at 14:00
  • @wxyz still not uniform and the range is hardcoded to 0..2^ceil (log n) - 1 – Niklas B. Jan 27 '14 at 14:05
  • @Niklas B., suppose that n = 12, we generate 3 numbers: n1<=7, n2<=4, n3<=1. Could be that n1=7, n2=4, n3=1 and we add them all -> generated number is 12. So, I can conclude that there's no range limitation. – wxyz Jan 27 '14 at 14:09
  • @wxyz the range you want is given, you don't get to decide what it is... have you actually read the question? – Niklas B. Jan 27 '14 at 14:12
  • 1
    @wxyz AND the sum of uniformly distributet random variables is not uniformly distributed! – Niklas B. Jan 27 '14 at 14:14
  • 1
    "*Unfortunately this has worst case runtime of infinity.*" Yes, and the probability of getting the worst case is Zero(0). – RBarryYoung Jan 27 '14 at 14:25
  • @Niklas B. Of course the range is given, that's why I said 'suppose' (you can pick whatever value you like for n). And that's not really the sum of uniformly distributed variables, it's rather a pseudo sum, since for each term we flip the coin again to decide if we add it or not. – wxyz Jan 27 '14 at 14:35
  • @wxyz I now understand what you mean. It's no uniform distribution though. You cannot even produce all the numbers in the range, only those that have a subset of n bits set. Say n=32, then 0 and 32 are the only numbers you can produce, if I understand you correctly – Niklas B. Jan 27 '14 at 14:57
  • @NiklasB. is right that the sum of uniformly distributed random variables is not uniformly distributed. Consider rolling two 6-sided dice. The sum skews towards 7/8 and away from 2 and 12. – owencm Jan 28 '14 at 16:25

1 Answers1

2

Quote from this answer https://stackoverflow.com/a/137809/261217:

There is no (exactly correct) solution which will run in a constant amount of time, since 1/7 is an infinite decimal in base 5.

Now ask Adam Rosenfield why it is true :)

Community
  • 1
  • 1
Mikhail
  • 20,685
  • 7
  • 70
  • 146