12
$\begingroup$

We want to make a close equivalent of a fair coin throw, by throwing an N-sided fair die T times. The catch: only one side is marked, by a colored disk on that side's center (like the traditional marking for one on a regular 6-sided die). We want something that always yields a decision after T throws.

Update: the position of observers must not matter. Say, the die is thrown on a slowly rotating platter.

Warmup: N=6, T=2.

More difficult: N=4 (a tetrahedron, with rounded edges and vertices). What's the lowest T allowing to reach a probability of 1/2 ± 1/1000?

Bonus: extend to other platonic solids N∈{8,12,20} and common dice N∈{10,14,16,18}.

$\endgroup$
5
  • 1
    $\begingroup$ I don't see how to always get a decision in the warmup question, though I can get an exact equivalent to a coin throw in 10 out of 36 cases and no decision in 26 out of 36 cases. $\endgroup$ Apr 19 at 8:44
  • $\begingroup$ @Jaap Scherphuis: likely you use an oversimplified model of the dice throw. $\endgroup$
    – fgrieu
    Apr 19 at 8:54
  • $\begingroup$ @JaapScherphuis the question wouldn't make much sense if rejection sampling were allowed. $\endgroup$
    – loopy walt
    Apr 19 at 9:13
  • $\begingroup$ @JaapScherphuis Fair enough. --- Oops, no pun intended. $\endgroup$
    – loopy walt
    Apr 19 at 9:19
  • 2
    $\begingroup$ This is actually a classic problem in computer science! It's known as "bit whitening" or "randomness extraction". In general, you have some random sequence of bits (0 or 1) that is biased (probabilities are not even), and you'd like to produce a shorter unbiased sequence. The most well-known solution is the Von Neumann extractor, but that does not work here because it's not guaranteed to work within T throws. $\endgroup$ Apr 19 at 18:17
9
$\begingroup$

Given the hint of the oversimplified model, here is another way to do the warm-up question N=6 T=2:

The dot can be on top, on a side, or hidden on the bottom. Take as one outcome that the two dice throws are the same (i.e. both on top, both on side, or both on bottom). The probability of that is $\frac{1}{36}+\frac{16}{36}+\frac{1}{36}=\frac{1}{2}$.

This does not work in the N=4 case, but can be generalised to other dice shapes.

For the other Platonic solids N={8,12,20}, T=1 is enough, as the dot is either in the upper or lower half. There are no face centres directly on the equator.

For the N=4 case the above trick does not work so we have to do it the hard way. Loopywalt came up with an answer for this first, but below is slightly simpler.

The smallest probability case is to land on the dot $T$ times, probability $1/4^T$. This is smaller than $1/1000$ when $T=5$, so let's try that first.
We have the following cases depending on how many times the dot is down (from 5 times face down to 0 times face down):
1* 1/1024
5* 3/1024
10* 9/1024
10* 27/1024
5* 81/1024
1* 243/1024
The first number is the number of different orders in which the throws can occur.
It just so happens that $243+10*27=513$, so a very simple way is to choose one outcome to be that it lands 0 or 2 times on the dot.
With smaller $T$ you would have to find cases with probabilities adding up to exactly $1/2$. You can see it as a knapsack problem in which the weights are multiples of one another. In such a problem the greedy algorithm is optimal, but the greedy algorithm does not give the sum $1/2$ in for each case of $T=2,3,4$, so those values of $T$ do not get us close enough to a fair coin.

$\endgroup$
10
  • $\begingroup$ Ah, that's clever. (+1) Thinking about it and not being a dice games buff, if you have a tetrahedron die how do you actually read a throw? I mean, there is no top face, is there? $\endgroup$
    – loopy walt
    Apr 19 at 9:34
  • 1
    $\begingroup$ @loopywalt Usually they essentially number the vertices, so the value of the top vertex is taken. $\endgroup$ Apr 19 at 9:35
  • $\begingroup$ Common dices for N∈{10,14,16,18} can be handled as suggested the larger platonics. This leaves the tetrahedron as the only unsolved case. $\endgroup$
    – fgrieu
    Apr 19 at 9:57
  • $\begingroup$ @fgrieu I don't see anything better than loopywalt's now deleted answer (or something equivalent) for that. $\endgroup$ Apr 19 at 10:07
  • 1
    $\begingroup$ I don't understand what the 1, 5, 10, 10, 5, 1 mean in your N=4 case. $\endgroup$ Apr 19 at 17:51
9
$\begingroup$

Warmup: N=6, T=2.

Actually, this can be done in T=1. Toss the die and see whether the dot is facing you. (Three faces face you, except in the extremely unlikely case that the die lands so that only two faces face you.)

$\endgroup$
3
  • $\begingroup$ Had not thought of that. Will tune up the question to exclude solutions where position of observer matters. $\endgroup$
    – fgrieu
    Apr 19 at 9:06
  • 1
    $\begingroup$ But +1 for the "thinking outside the box" ! And I promise I won't change the question again. $\endgroup$
    – fgrieu
    Apr 19 at 9:19
  • $\begingroup$ in the 'extremely unlikely case that only 2 face you', you can just agree before hand that if it's on the right side, it counts as 'facing you' $\endgroup$
    – TKoL
    Apr 20 at 16:22
4
$\begingroup$

With the clever bits having been handled by @Jaap and assuming nothing of the kind can be done for a 4-sided die, here is an answer to the main question.

Choose T=5.

Group 1: No dot or
exactly one dot but not in the first or last trial or
a dot in exactly the first or last three or four trials or
all dots
Group 2: everything else
p1 = (243 + 3 x 81 + 2 x (9 + 3) + 1) / 1024 = 511 / 1024

Proof that we cannot do better:

It suffices to show that events cannot be evenly split. In units of 1/N^T there is only one event (all dots) that is not divided by N-1. Therefore one group's probability is divided by N-1 the other's isn't.

$\endgroup$
6
  • $\begingroup$ Yes. I like the proof that we can't do better. Note: there's a simpler-stated solution with the same T. Hint: the order of the throws does not matter to this one. $\endgroup$
    – fgrieu
    Apr 19 at 10:37
  • $\begingroup$ The tidiest I can think of would be something like: At least 3 dots or no dot or a single dot in the first or last trial, @fgrieu. $\endgroup$
    – loopy walt
    Apr 19 at 10:53
  • $\begingroup$ What about: no or two (times the dot is not visible)? $\endgroup$
    – fgrieu
    Apr 19 at 10:55
  • $\begingroup$ Of course! My brain seems to be awol today... $\endgroup$
    – loopy walt
    Apr 19 at 10:58
  • $\begingroup$ By "not divided by" you mean "not divisible by"? $\endgroup$
    – justhalf
    Apr 19 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.