Jan 30, 2019

I have seen a very interesting math problem recently. The problem is about using fair/unfair coin to construct a game between you and another people; you need to make sure you can win the game with arbitrary probability of p. Now let's consider an even harder version: Die rolling. After I solve the die rolling problem, you will quickly know how to solve the coin tossing problem as well.

Consider you have a balanced die (each side of 1,2,3,4,5,and 6 shows up with equal probability). Come up with a game for you to play with another people, such that the probability for you to win the game is exactly p. Note that p is a real number between 0 and 1.

The key lies in the fact that you have to find a map between the outcomes and the real numbers between 0 and 1. You also have to make sure that every outcome is perfectly covered by a number between 0 and 1. How do I build such a mapping?

Solution: Let us use 6-ary number. We will have p expressed in:

where

The game now looks like this:

As you continue to roll the die, the game will end at some point with probability 1 (since the probability of getting exactly the same sequence as p is 0). You can see the winning probability is p as well. The proof is very simple and I will skip that, but you can see the trick here.