QWorld Bronze: Coin Flip Game

Published by strangeworks (01/06/2021)

A Game with two biased coins

Our friend Asja has one euro and one cent.

Both coins are biased, and the probabilities of getting heads and tails are as follows:

  • one euro: heads with probability 0.6 and tails with probability 0.4.
  • one cent: heads with probability 0.3 and tails with probability 0.7.

Asja flips her coins based on the following protocol:

  1. she starts with flipping one euro[*].
  2. whenever she gets heads, she flips one euro in the next step;
  3. whenever she gets tails, she flips one cent in the next step; and

By using a single bit, we summarize all possible transitions of this game as follows:

GameCoins=HeadTailHead0.60.3Tail0.40.7=0100.60.310.40.7GameCoins = \begin{array}{c|cc} & \mathbf{Head} & \mathbf{Tail} \\ \hline \mathbf{Head} & 0.6 & 0.3\\ \mathbf{Tail} & 0.4 & 0.7 \end{array} = \begin{array}{c|cc} & \mathbf{0} & \mathbf{1} \\ \hline \mathbf{0} & 0.6 & 0.3 \\ \mathbf{1} & 0.4 & 0.7 \end{array}​​

[*] We should fix an initial condition. Otherwise, Asja cannot pick any of the coins at the beginning of game.

Task 1: Convince yourself

Convince yourself about the correctness of transitions given in the table.

Remark that there is no difference between getting heads from one euro or getting heads from one cent.

Therefore, one bit is enough to represent all transitions.

Tracing Asja's three coin tosses

Suppose that Asja secretly tosses her coins based on the defined protocol.

By using python, we can calculate the probabilities of Asja seeing heads and tails after three coin tosses.

Remark: In the previous tasks of Coin Flipping, we know the ideal ratios, and we experiment many coin tosses and then expect to observe the results close to the ideal ratios.

Here we calculate the exact probabilities (the ideal ratio) by using python. (We will not do the experiments as in the previous tasks.)

We present our solution step by step.

#
# OUR SOLUTION
#

# initial condition:
# Asja will start with one euro,
#    and so, we assume that the probability of having head is 1 at the beginning.
prob_head =1
prob_tail =0

#
# first coin-flip
#

# the new probability of head is calculated by using the first row of table
new_prob_head = prob_head *0.6+ prob_tail *0.3

# the new probability of tail is calculated by using the second row of the table
new_prob_tail = prob_head *0.4+ prob_tail *0.7

# update the probabilities for the second round
prob_head = new_prob_head
prob_tail = new_prob_tail

# second coin-flip
#
# we do the same calculations
new_prob_head = prob_head *0.6+ prob_tail *0.3
new_prob_tail = prob_head *0.4+ prob_tail *0.7

prob_head = new_prob_head
prob_tail = new_prob_tail


# third coin-flip
#
# we do the same calculations

new_prob_head = prob_head *0.6+ prob_tail *0.3
new_prob_tail = prob_head *0.4+ prob_tail *0.7

prob_head = new_prob_head
prob_tail = new_prob_tail

# print prob_head and prob_tail
print("the probability of getting head after 3 coin tosses is",prob_head)
print("the probability of getting tail after 3 coin tosses is",prob_tail)

Task 2: Tracing ten biased coin tosses

By using python, calculate the probabilities of Asja seeing heads and tails after 10 coin tosses.

GameCoins=HeadTailHead0.60.3Tail0.40.7=0100.60.310.40.7GameCoins = \begin{array}{c|cc} & \mathbf{Head} & \mathbf{Tail} \\ \hline \mathbf{Head} & 0.6 & 0.3\\ \mathbf{Tail} & 0.4 & 0.7 \end{array} = \begin{array}{c|cc} & \mathbf{0} & \mathbf{1} \\ \hline \mathbf{0} & 0.6 & 0.3 \\ \mathbf{1} & 0.4 & 0.7 \end{array}​​

Use a loop in your solution.

Task 3

Repeat Task 2 for 20, 30, and 50 coin tosses.

Task 4

Repeat Task 2 for 10, 20, and 50 coin tosses by picking different initial conditions, e.g.,

prob_head = prob_tail = 1/2

or

prob_head = 0 
prob_tail = 1

Arbitrary transitions for GameCoins [extra]

By changing the bias of each Asja's coin, we can define arbitrary GameCoins.

If a is the probability of getting heads for one euro and b is the probability of getting heads for one cent, then we have the following transitions:

GameCoins(a,b)=HeadTailHeadabTail1a1b=010ab11a1bGameCoins(a,b) = \begin{array}{c|cc} & \mathbf{Head} & \mathbf{Tail} \\ \hline \mathbf{Head} & a & b\\ \mathbf{Tail} & 1-a & 1-b \end{array} = \begin{array}{c|cc} & \mathbf{0} & \mathbf{1} \\ \hline \mathbf{0} & a & b \\ \mathbf{1} & 1-a & 1-b \end{array}

Observe that if a=1 and b=0, then it is Identity operator, i.e., the initial condition will stay as it is.

If a=0 and b=1, then it is NOT operator. NOT operator swaps the probabilities of heads and tails in each step. If the initial probabilities are not 0.5 and 0.5, then the system never converges to a fixed probabilities.

Task 6

Randomly pick the values of a and b, and then implement Tasks 3 and 4 for GameCoins(a,b).

Task 7

10 times repeat Task 6 and observe whether the probabilities converge in each time.

Task 8

We can rewrite arbitrary GameCoins as

HeadTailHead1yxTaily1x=0101yx1y1x. \begin{array}{c|cc} & \mathbf{Head} & \mathbf{Tail} \\ \hline \mathbf{Head} & 1-y & x\\ \mathbf{Tail} & y & 1-x \end{array} = \begin{array}{c|cc} & \mathbf{0} & \mathbf{1} \\ \hline \mathbf{0} & 1-y & x \\ \mathbf{1} & y & 1-x \end{array}.​​

We assume that it is neither Identity nor NOT operator. Then, independent of the initial state, the system always converges to

Pr["heads"]=xx+y Pr[{"heads"}] = \dfrac{x}{x+y}and Pr["tails"]=yx+yPr[{"tails"}]=\dfrac{y}{x+y} ​,

which are the probabilities of getting heads and tails, respectively.

Observe this fact by checking the results of Task 7.