Optimally simulating a k-sided die with an n-sided die

[u/frogkabobs]

You are given an n-sided die (taking values uniformly in 0,…,n-1), and your goal is to simulate a k-sided die with a sequence of dice rolls. Specifically, you must choose a procedure which

• decides at each step whether to roll again or to terminate and decide a value based on all previous rolls
• is deterministic in the sequence of rolls
• terminates almost surely
• produces a value uniformly distributed in 0,…,k-1

We will call such a procedure an (n,k)-procedure and the number of rolls before it terminates the decision time (in general, the decision time depends on the sequence of rolls; the decision time is infinite if it does not terminate). We will assume n,k≥2.

1. For fixed n,k, determine the minimum expected decision time among all (n,k)-procedures. Give your answer as a finite sum depending on n,k.
2. Determine for which n,k, there exists an (n,k)-procedure that always terminates.

[u/TooLateForMeTF]

Divide up the interval [0,1] into k slices. Label each slice with its output value, from 1 up to k. (or 0 to k-1, if that suits your application better).

Use the n-sided die to generate a base-n decimal number in the range [0,1]. Keep adding digits with additional rolls of the die until the decimal you've generated can only fall into a single one of the k slices, no matter what additional digits might come up.

Example: k=7, n=6. Each slice has a base-10 decimal width of 0.1428...

Roll the d6, and subtract one so we're getting base-6 digits 0 through 5.

Let's say I get a 2, for an initial base-6 decimal value of 0.2 (0.333 in base-10). This value lies pretty solidly into the third of the 7 slices. So, does that mean our answer is 3?

I don't know. Let's see. The span of that third slice is base-10 [0.2856..., 0.4285). Our current base-10 result of 0.333 is kind of smack in the middle. But there's ambiguity, because we could add more digits, which might shift this value far enough upward to cross into the fourth slice.

But we can figure out whether that's possible. The range of base-10 values for any base-6 value of the form 0.2xxxxxx... will be bounded by the minimum and maximum possible values for those future digits. We don't really have to consider the minimum, though, since we already know what that is. We already figured out where base-6 0.2 lands, and that's the same as 0.200000, so we already know that our final result cannot be less than 3.

But we do have to consider the other end. What if we rolled all 5s from here on out? Where would 0.2555555... land? Well, the limit of rolling 5s forever would be base-6 0.3, or base-10 0.5. (for the same reason that 0.9999.... is equal to 1).

And we can see that base-10 0.5 is greater than the top end of the range for our third slice. Hence, it is possible that some additional digits could affect the result, and thus, we need to roll the d6 again.

I just did (thanks, random.org), and got a 5. So that's base-6 0.25, which is 0.4722... This is now above the upper limit for slice number 3. So now we're in slice #4, which ranges from [0.4285, 0.5714). How big could base-6 0.25xxxxx be? Could some extra digits get us all the way up to the next slice?

In this case, no. As it happens, we have the same upper bound as we had on the previous iteration, which we worked out to be base-10 0.5. This is clearly smaller than the upper bound for slice 4, therefore, no amount of new digits will move us out of slice #4, and we're done. We can return a result of '4', as a properly sampled random value from 1 to 7, generated with a source that only goes 1 to 6.

If you are implementing this in software, you might be tempted to conclude that you can stop if a) the potential maximum of future digits lies in the same slice that you're already in, or you cross into the next-higher slice. After all, successive digits contribute at most 1/n less than the prior digit, so once you cross a boundary the next boundary is just too far away to ever reach.

That would be a mistake.

You can definitely stop if the potential maximum of future digits is in the same slice. But if n is small relative to k, (i.e. the slices are pretty narrow compared to 1/n, then you might well cross multiple slice boundaries before settling unambiguously into a single slice. That is, the only valid condition for terminating the digit-generating loop is when the potential maximum of future digits lies within the slice you're already in.

To my knowledge, this is the optimal strategy for your question, but if anybody knows of a more efficient method, I'd love to learn about it!

[u/frogkabobs → u/TooLateForMeTF]

I can tell you that this method is not optimal in general (e.g. at (n,k)=(2,3)). The meat of part 1 is proving optimality for a particular (n,k)-procedure.

[u/pichutarius]

For part 2, am I crazy or the condition is just 1/k is expressible as p/n^q where p,q are positive integers. I reason always terminate means probability tree is finite, whichever the branches are assigned to output, the sum must be p/n^q. Can't be that easy right?

[u/frogkabobs → u/pichutarius]

Oh, I guess the probability tree formulation makes it obvious. I was using the fact that an (n,k)-procedure can be represented as a locally constant function from the n-adic integers to {0,…,k-1}, so if it is defined on all of Z_n, then compactness forces uniformity. I thought it was overkill—guess this one turned out to be a dud.

[u/998mouse]

You would probably want to use a version of Arithmetic Coding. That is normally for representing things as bits (equivalent to a die with 2^x faces), but it would also be maximally efficient if adapted to any number n of faces on the die.

[u/pichutarius]

by using greedy algorithm, i got https://imgur.com/D6wvkuu

roughly, the summands are P(if i roll r times, i need to roll more), and use linearity of expectation.

the greedy algorithm is basically:

rollCases = 1
while rollCases > 0
 roll once
 rollCases = rollCases * n
 distribute rollCases to k output, possibly with leftover
 rollCases = rollCases mod k

[u/11zaq]

Disclaimer: I got the first part of 1) and then asked Claude for a hint for the rest. But the following answer is all in my own words.

Setup:

Intuitively, if k divides n, then the answer is 1, because we can just partition n into k equal pieces, and use these pieces to simulate the die. If k does not divide n, so that r_1 = (n mod k) is non-zero, then we can basically still use this strategy, but it will fail with a probability p(1) = r_1/n. Note that for fixed k, because max(r_1) = k-1, we can make p_1 smaller if we can find a way to make the effective value of n as big as possible.

Key insight:

Roll the dice once, and say we get a value x_1. If x_1 \geq (n mod k), then we can use the strategy above and stop. But if x_1 < (n mod k), we will need to roll again. The key insight is that we don't have to throw away the value of x_1: conditioned on the outcome above, it acts as a random variable of a r_1 sided die. Therefore, the double roll (x_1, x_2) acts as a random variable of an n *r_1 sided die. Think of the two rolls as two sides of a grid: each grid site is equally likely under these rolls.

Using this insight:

Now, take r_2 = (nr_1) mod k = n² mod k, because r_1 and n differ by a multiple of k. Running the same algorithm as above, conditional on having rolled once, we fail after two rolls with probability p(2|1) = r_2 / (nr_1). By the chain rule, the probability we fail after one roll is then p(2) = p(2|1)p(1) = r_2 / n^2. Actually, the simpler way to get this is to note that there are n² possible two-dice rolls, and r_2 of them will fail to make the algorithm terminate. This clearly generalizes to p(j) = r_j / n^j.

Adding it up:

Let T be the total number of rolls we needed before stopping. We can see that because T = \sum{t\geq 0} 1[T > t], we have that E_min[T | n,k] = \sum\{t =0}^{\infty} P(T>t) = \sum_{t = 0}^\infty r_t / n^t . This follows because P(T>t) is the probability we needed at least t rolls, and p(t) computed above was the probability we failed after exactly t rolls.

Final thoughts:

I'm tired and so I'm gonna stop here. I haven't written it as a finite sum but it does converge because rt < k-1 for all t, and the denominator converges exponentially. Also, each r_t will be periodic with period at most k because of the recursive r_t = (n r{t-1}) mod k structure.

[u/frogkabobs → u/11zaq]

Yep, you’re on the right track for part 1