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.

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die?

For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, but it seems we cannot choose between 7 things with a finite algorithm.

share|improve this question
    
What do you call a finite algorithm exactly? –  Did Feb 13 '13 at 21:57
    
@Did Good question. One interpretation is an algorithm based on a predefined number of dice rolls. Another would allow a random number of dice rolls, but with the number of rolls having a finite expectation. With this definition, any $n$ is possible. –  Harald Hanche-Olsen Feb 13 '13 at 22:00
    
If you want pessimistic finite time, then (as Ross Millikan pointed out) $\frac{1}{n}$ has to be a fraction that terminates in base $6$ (i.e. $\frac{1}{n} = \frac{p}{6^q}$ for some $p,q\in\mathbb{N}$). If you want expected finite time, then any finite $n$ is good. –  dtldarek Feb 13 '13 at 22:12
    
by finite algorithm, I mean a finite number of throws. a finite series of actions (without loops used in programming) which lead to a choice. Another similar example is: There is not a finite process which divides any angle to three equal ones. –  user59671 Feb 13 '13 at 22:15
    
Your analogy with trisection is flawed: You can use dice to chose exactly uniformly between $n$ outcomes in a finite number of throws, but you can't determine that finite number before you start. There is no analogue for this statement in the trisection case: There, you never achieve an exact trisection. –  Harald Hanche-Olsen Feb 13 '13 at 23:02
show 7 more comments

2 Answers 2

up vote 10 down vote accepted

With a six sided die you can choose between any number of options of the form $2^p3^q$ with a finite process, but no others. The number of possible throws is always $6^k$ and so you need a fraction that terminates in base $6$, which means the denominator has to have factors only of $2$ and $3$.

share|improve this answer
    
Care to explain why you can't select between others? –  vonbrand Feb 14 '13 at 1:15
1  
@vonbrand: the same reason you can't select out of $5$. After $k$ rolls you will have $6^k$ possibilities, which you can't split evenly among the choices. You can use $1$ through $5$ to make choices and reroll the $6$ if you want, but that might go on forever. That is why the number of choices has to divide evenly into $6^k$ for some $k$. Primes other than $2$ and $3$ never do. –  Ross Millikan Feb 14 '13 at 1:32
add comment

Given $n$ events, throw $k = \lceil \log_6 n \rceil$ dice, to generate a number from $1$ to $6^k$ in base 6. If the number thrown is greater than $n$, keep throwing until you get a number that's less than $n$.

While this will never be guaranteed to terminate in a specified number of throws, the more you throw, the greater the probability that one of the events will be one you can use, and the probability that this process does go on forever vanishes to zero.

If you require exact probabilities on a single throw, then Ross' solution is the best you can get, as your sample space is always going to be a power of 6 and the only way to divide that sample space up among events equally is to use a number of events that is a factor of a power of 6.

share|improve this answer
    
>If the number thrown (ie k) is greater than n (ie n < k), keep throwing (ie add to k) until you get a number that's less than n (ie k<n). ...? –  user59671 Feb 14 '13 at 1:57
1  
I think you're misunderstanding what I'm saying. I mean something along the lines of: Given 28 events, throw two dice, one white and one black, using the white as the "sixes" digit. Suppose the white die came up 5 and the black die came up 5. This means you rolled 29, which is too high (greater than 28), so you roll again. –  Joe Z. Feb 14 '13 at 2:00
add comment

Your Answer

 
discard

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