Given a bounded number of die rolls following unif{1,6}, produce unif{1,7}

This is a twist on the traditional problem of transforming between uniform discrete distributions of different sizes.

For this example, we can roll the die twice and get one of 36 possibilities. The usual solution says that the first 35 can be evenly distributed among the outputs 1..7, and the last one can be rejected, resulting in a reroll. This, however, is not bounded in the number of die rolls, since you can keep getting rejections indefinitely. My question is, does a bounded algorithm exist?

A slightly sketchy argument says no, as follows. The amount of information from each die roll is $\log_2 6$ bits, and we need a multiple of $\log_2 7$ bits. $\frac{\log_2 7}{\log_2 6}$ is unfortunately irrational, so we can't perfectly use up the information - we will always be losing information. This lost information implies that you're rejecting some numbers. And so you'll never be able to bound the number of die rolls that the algorithm requires.

This argument is super sketchy for a lot of reasons, and probably wrong, but the general thrust of the argument feels kind of correct. Am I correct, and if so how can I improve this "proof"?

The argument is fine. I think you can distill it to something simpler, though.

A sequence of rolls determines a branching probability tree with six branches at each node. Because the rolls are independent and each outcome has probability $6^{-1}$, the chance of reaching a given node at level $n$ (that is, a particular sequence of $n$ rolls) is $6^{-n}$. Let $N$ be any bound for the number of rolls. Then the chance of any event whatsoever is a sum of numbers of the form $6^{-n}$ where $0 \le n \le N$. Such a sum obviously is a multiple of $6^{-N}$. Since $1/7$ is not such a multiple, it cannot be realized as the probability of any such event, no matter how large $N$ may be.

Here's an alternative exposition of the same idea. The chance of any event after $N$ rolls, when written in base $6$, can be written using at most $N$ digits after the "seximal" point in base $6$. Since $1/7 = 0.050505\ldots_{[6]}$ requires an infinite expansion, it cannot arise as the chance of any such event.

If you're uncomfortable using base $6$, then (by analogy) contemplate a (hypothetical) ten-sided die, each outcome with a chance of $1/10$. After $N$ rolls, all probabilities can be expressed as decimals with exactly $N$ digits. Numbers like $1/3 = 0.333\ldots$, $1/7=0.142857\,142857\ldots$, etc., cannot arise as any such probability.

• I love the base 6 explanation - it makes so much sense :) Thank you! – oink Nov 6 '17 at 18:39

If I follow your line, we can note that $\frac{log_2{7}}{log_2{6}}=log_6{7}$ which is bound to be irrational, so we'll always lose some information (which is true, as 5 different results are represented by one number and the 36th result is discarded).

I do think, however, that by defining the event of a re-roll and its probability, you can get a bound on the number of re-rolls using Markov's inequality. The probability of having k re-rolls decays quickly to 0 so for some large k to your liking, you can start using zero-probability theorems.

• Thanks for your answer! The thing is, I want to have a deterministic upper bound on how many dice rolls I will have. Even though the probability is only 1/36 for one reroll, decaying exponentially downward for more rerolls, it's still nonzero for any arbitrarily large number of rerolls. – oink Nov 6 '17 at 9:49
• There will be no deterministic upper bound but rather a statistical one. You can, however, use convergence theorems to get this as rigorous as desired. – Spätzle Nov 6 '17 at 10:00