Creating unusual probabilities with a single dice, using the minimal number of expected rolls

Question

Problem

I want to create an 'event' with probability of $\frac{1}{7}$ with a single dice as efficiently as possible (to roll the dice as little as possible).

To give you some better understanding of the question, if I would like an event with probability of $\frac{1}{9}$, I could easily do it in various ways. One way is to see whether the sum of two rolls is $5$. Another way is to roll the dice twice and see whether they are both not higher than $2$.

If I had to choose $\frac{1}{5}$, we can do this 'trick': success on drawing $1$, but if we draw $6$ just disregard it and roll again, until we draw a number which is not $6$. In that case the expected number of rolls is $\frac{6}{5}$.

So, one way to get probability of $\frac{1}{7}$ is basically the same, choosing $7$ predefined ordered pairs of 2 rolls to be the success set, and disregard any other combination (and to roll the dice twice again, if other combination occurs). In that case, the expected number of dice rolls needed is $\frac{72}{7}$ which seems pretty bad to me and makes we wonder... is there a better way?

Generalization

In general, if we have a $k$-sided dice what is the optimal way of obtaining an event with probability $\frac1m$ using the least expected dice rolls? And what if we want to simulate an $m$-side dice and not just one event?

Answer 1

Two rolls give $6 \times 6 = 5 \times 7 + 1$ possible outcomes. Just split them into $7$ equally likely groups except for one outcome and re-roll if you get that.

In general given a $k$-dice that you wish to use to simulate an $m$-dice, the algorithm is as follows: $\def\lfrac#1#2{{\large\frac{#1}{#2}}}$ $\def\floor#1{\lfloor #1 \rfloor}$

Set $n := 1$ and $x := 0$.   [$n$ is the number of branches; $x$ is the branch index (0-based).]

Repeat:

  Roll the $k$-dice once and let $p$ be the outcome.

  Set $n := kn$ and $x := kx+p$.   [Expand every branch and move down a random one.]

  If $n \ge m$ then:   [Enough to have $m$ equal parts.]

    Let $a,b$ be integers such that $n = am+b$ and $0 \le b < m$.   [$a$ is the size of each part.]

    If $x < am$ then: Return $x \bmod m$.   [Falls into one of the equal parts.]

    Otherwise: Set $n := b$ and $x := x-am$.   [Falls into the leftover branches.]

Clearly this algorithm $A$ halts with probability $1$. I also claim that it is optimal. Take any optimal algorithm using the $k$-dice. It will create a $k$-way outcome tree, with some branches ending in leaf nodes. Label each leaf with the output. Iteratively swap branches to make the leaves in decreasing order of weight. Within each level sort the leaves in order of label. Then [(1)] there are no $k$ leaves in a level with the same label otherwise they can be swapped to the front of that level and pushed up. I claim that this tree $T'$ is exactly the outcome tree $T$ for $A$. Suppose otherwise. Consider the first level where there is a difference. $T'$ must have less leaves than $T$ (because $A$ is greedy). But [by (1)] that extra leaf in $T$ has more weight than all smaller leaves with the same label in $T'$, and so it is impossible for $T'$ to make up the difference. Thus $T'$ is incorrect. Therefore the supposition is false and $T' = T$.