Say we want to simulate an N sided die.

^{M}/K < N for some K. Then, flip a coin with a 1/N bias for tails once.

This splits the probability space into:

- 2^{M} "large" outcomes of probability (1/2^{M})(1-1/N) and

- 2^{M} "small" oucomes of probability (1/2^{M})(1/N)

We have to assign these outcomes to the faces of the die such that the probability of each face sums to 1/N. Notice that all of the above outcomes have a common denominator of N*2^{M}.

To simplify the problem, let's pretend that we're actually assigning balls to bins, where each of N bins can hold 2^{M} units of space, each of 2^{M} large balls take up N-1 units of space, and each of 2^{M} small balls take up 1 unit of space.

Since K*(N-1) < 2^{M} for some K, we can first assign K large balls into each of the first N-1 bins without running out of large balls or overflowing the bins. Since 2^{M} - K*(N-1) < K, we can throw the remaining 2^{M} - K*(N-1) large balls into the last bin without overflowing it. Finally, we can fill out the remaining space in the bins with the 1-unit balls.

- 2