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?

• user21820: I edited your question to add the generalization. Hope it's okay with you!

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$.

• d_e: so simple...thanks.
• d_e: right ..deleted this part of the comment ...so I guess I am wrong with $\frac{36}{7}$ in the post...is should be $\frac{72}{7}$ ?
• MT_: I wonder if this generalizes nicely.
• user21820: @d_e: Ah yes I didn't notice that in your post itself.
• David C. Ullrich: Of course the question was to do it in as few rolls as possible. Since 7ドル$ does not divide 6ドル^N$ there's no way to do it in $N$ rolls for any fixed $ N$. So the meaingful version of the question is to minimize the expected value of the number of rolls. I wonder what does that...