# Coin flip experiment

Experiment: A fair coin is flipped until a tail appears.

Find the minimal average number of bits required to encode the outcome of the experiment.

## 4 thoughts on “Coin flip experiment”

1. The answer is 0.632843 =
$2 \sum_{k=1}^\infty 2^{-2^{k}}$

If the first flip is tail, the compressor outputs nothing.

2. Ah, I don’t think that is the minimum for a single experiment.

The mapping {1,2}->{0,1},{3,4,5,6}->{00,01,10,11} and so on will give

$\sum _{j=1}^{\infty } \left(\sum _{i=\sum _{k=0}^{j-1} 2^k}^{\sum _{k=0}^j 2^k-1} \frac{j}{2^i}\right) \approx 1.26569$.