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?