## home

author: niplav, created: 2019-02-08, modified: 2019-11-19, language: english, status: maintenance, importance: 4, confidence: highly likely

Imagine getting up every morning and throwing a coin so often that heads and tails have come up an equal amount of times. How often would you throw the coin on average? Infinitely often, it turns out. Code in Klong.

# Equally Many Heads and Tails

This thought experiment can be modeled as a simple expected value calculation in a countably infinite case:

$$\mathbb{E}=\sum_{i=1}^{\infty} p_{i}*x_{i}$$

## Finding $x_{i}$

We know that flipping the coin definitely ends when for 2*n coin flips, we have gotten heads n times and tails n times as well. This gives us $x_{i}=2*i$.

## Finding $p_{i}$

Finding out $p_{i}$ is a bit harder. In order to find it, it is best to look at the first iterations of the process.

### Observing Coin Flips

After starting, we have flipped the coin 2 times, so the possible solutions are:

H;H
H;T
T;H
T;T


We are done in two cases, H;T and T;H. p₁ therefore is $\frac{2}{4}=0.5$. We then continue flipping the coin 2 more times, starting with either H;H or T;T, with the following possible results:

H;H;H;H
H;H;H;T
H;H;T;H
H;H;T;T
T;T;H;H
T;T;T;H
T;T;H;T
T;T;T;T


Of these, only two finish: H;H;T;T and T;T;H;H. So the chance of finishing given 4 coin flips is $\frac{2}{8}=0.25$.

We continue flipping the coin with the non-finishing sequences, and our possible results look like this:

H;H;H;H;H;H
H;H;H;H;H;T
H;H;H;H;T;H
H;H;H;H;T;T

H;H;H;T;H;H
H;H;H;T;H;T
H;H;H;T;T;H
H;H;H;T;T;T

H;H;T;H;H;H
H;H;T;H;H;T
H;H;T;H;T;H
H;H;T;H;T;T

T;T;T;H;H;H
T;T;T;H;T;H
T;T;T;H;H;T
T;T;T;H;T;T

T;T;H;T;H;H
T;T;H;T;T;H
T;T;H;T;H;T
T;T;H;T;T;T

T;T;T;T;H;H
T;T;T;T;H;T
T;T;T;T;T;H
T;T;T;T;T;T


Here, the sequences H;H;H;T;T;T, H;H;T;H;T;T, T;T;T;H;H;H,T;T;H;T;H;H finish, so given six coin flips, the chance of finishing is $\frac{4}{24}=0.1666666\dots$.

Writing down the next step gets messy, but we have already observed enough iterations to find a pattern in the sequences.

### Considerations on Coin Flips

First of all, the number of finishing sequences given 2*n coin flips is the Catalan number Cₙ. In this case, it describes the number of Dyck words of the length 2*n. To quote Wikipedia:

A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's.

Wikipedia, “Dyck word”, 2019

This applies exactly to the given problem. A finishing sequence has equally many heads and tails, but doesn't begin with a sequence of equally many heads and tails. Cₙ is defined as $\frac{1}{n+1}*{2*n \choose n}$.

Catalan numbers can be easily implemented using the binomial coefficient:

fact::{:[0=x;1;*/1+!x]}
bincoeff::{[n k];n::x;k::y;fact(n)%(fact(k)*fact(n-k))}
catalan::{bincoeff(2*x;x)%x+1}
f::{2*catalan(x)}


We call the number of finishing steps given 2*n coin flips fₙ.

One can also see that the total number of possible sequences of coin flips oₙ after 2*n coin flips is $4*(o_{n-1}-f_{n-1})$, because one appends H;H or H;T or T;H or T;T to the remaining number of sequences. So let oₙ be

$$o_{1}=4\\ o_{n}=4*(o_{n-1}-f_{n-1})$$

One can implement $o_{n}$ simply:

o::{:[x=1;4;4*o(x-1)-f(x-1)]}


When one executes o and f, one notices something peculiar: it seems that $o_{n}=2*n*f_{n}$.

#### Proof that $o_{n}=2*n*f_{n}$

Induction basis:

$$o_{1}=2*1*f_{1}\\ 4=2*1*2$$

Induction assumption:

$$o_{n}=2*n*f_{n}$$

Induction step:

$$o_{n+1}=2*(n+1)*f_{n+1}\\ 2*(o_{n}-f_{n})=(n+1)*f_{n+1}\\ 2*(2*n*f_{n}-f_{n})=(n+1)*f_{n+1}\\ 8*n*C_{n}-4*C_{n}=(n+1)*2*C_{n+1}\\ C_{n}*\frac{4*n-2}{n+1}=C_{n+1}$$

This is equivalent to a recursive definition of the Catalan numbers in the OEIS (sixth formula).

### Probability of Finishing at $2*n$ Steps

So, what's the probability of finishing given 2*n steps now? Simple: it's $\frac{f_{n}}{o_{n}}=\frac{f_n}{2*n*f_{n}}=\frac{1}{2*n}$.

pgn::{1%2*x}


Note that this probability is different from finishing at 2*n steps: pgn simply tells us how likely it is for us to finish in the next 2 flips if we have flipped the coin 2*(n-1) times steps already. But we are looking for the probability of finishing at 2*n steps.

For this, we can now define $r_{n}$ that tells us the probability of arriving at a sequence with 2*n coin flips. This can only have happened if we arrived at the last step and did not finish there. We define $r_{n}$ recursively:

$$r_{0}=1\\ r_{n}=r_{n-1}-\frac{1}{2*(n-1)}*r_{n-1}$$

Now, defining $p_{n}$ is simple: $p_{n}=\frac{1}{2*n}*r_{n}$.

## Final Formula and Final Code

Our final formula for the expected value is thus

$$\mathbb{E}=\sum_{i=1}^{\infty} \frac{1}{2*i}*r_{i}*2*i$$

We could implement $r_{n}$ very easily:

r::{r(x-1)-pgn(x-1)*r(x-1)}


But since we don't want to compute $r_{n}$ every time we execute a new iteration, we simply embed it into the final evaluation function: