Coin flip experiment

Posted on November 13, 2012 by Sergio Verdu

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”

Sergio Verdu on November 18, 2012 at 3:02 pm said:

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

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

Reply ↓
- Sai on November 19, 2012 at 5:35 pm said:
  
  I think he’s referring to the sequence given here ( $2\sum_{k=1}^\infty2^{-2^k}$ ): http://oeis.org/A076214 .
  
  Perhaps this interpretation can be added to OEIS.
Sai on November 16, 2012 at 10:09 pm said:

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$ .

Reply ↓
Sai on November 16, 2012 at 2:18 am said:

2 bits

Reply ↓

Leave a Reply Cancel reply