Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A. Several years before, I was solving some problems, and one of problems was something like

Explain how you can get non-biased random natural numbers between 1~10, with a six-sided(normal) dice.

I found the solution easily, but I was quite unhappy, because my solution included re-throwing, like this: Throw dice until numbers between 1~5 appears. I thought about the solution that doesn't require re-throwing, but I couldn't find one.


B. I saw a programming puzzle about fixing broken random number in Programming Puzzles & Code Golf. The problem was:

Given a function that returns 2 (probability:80%) or 5(probability:20%) randomly, make a program that returns random natural numbers between 1~5 evenly.

Algorithms used in answers were quite interesting, but all answers required for or while loop which can be looped infinitely.


I found this post in SO saying that there's no correct solution to expend the range of random from 1~5 to 1~7 that doesn't require any loop, because 1/7 is an infinite decimal in base 5. Using same strategy, there's no solution to the problem in A that doesn't requires re-throwing. However, I don't get it - why the fact that 1/10 is an infinite decimal in base 6 results in that conclusion? It does seem that two things are related, but I have no idea how they're actually related. Maybe there's some clever algorithm, like adding many random numbers and divide into 10 cases, considering about discrete probability distribution.

And, I'm curious that whether the puzzle in B can be solved without using any loops, and whether this problem is related to the problem in A.

So, my questions are

  • Why there's no solution of the problem in A that doesn't require re-throwing?
  • Is there any answer of the puzzle in B that doesn't require any loops?
  • Are above two questions are related?
share|improve this question

1 Answer 1

up vote 5 down vote accepted

A. You have to (potentially) throw the dice infinitely many times. If you only throw at most $n$ times, then there are $6^n$ possibilities, so the probability of any particular event is $\frac{k}{6^n}$ for some $k$, and this is never equal to $\frac{1}{10}$ by unique factorization. (In other words, it's a terminating decimal in base $6$, whereas $\frac{1}{10}$ isn't.)

B. The reason you can't make random numbers from $1$ to $7$ without (potentially) looping infinitely many times is the same as above. The reason you can't make random numbers from $1$ to $5$ without (potentially) looping infinitely many times is somewhat different. Imagine that the function is a $5$-sided die with $4$ sides showing two and $1$ side showing five. If you only throw it $n$ times, then there are $5^n$ possibilities, and you want the probability of generating each of the numbers from $1$ to $5$ using your algorithm to be $\frac{1}{5}$, so each number needs to be assigned $5^{n-1}$ possibilities, which is odd. But all of the events except the event of getting five $n$ times occurs an even number of times because there are $4$ sides showing two, so this is impossible.

The two arguments above are related in that they are both number theoretic.

share|improve this answer
    
Thank you for the simple and nice answer!! –  JiminP May 26 '11 at 14:28
    
Fun puzzle: for every $m$ there is a $p$ such that a bounded number of flips of a $p$-coin can be used to generate a uniform distribution over $\{1, \ldots, m\}$. –  Alon Amit May 26 '11 at 15:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.