# QWorld Bronze: Coin Flip Game

## 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**:

- she starts with flipping one euro[*].
- whenever she gets heads, she flips one euro in the next step;
- 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 = \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 = \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) = \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

$\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"}] = \dfrac{x}{x+y}$ $and$$Pr[{"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.