Flipping A Binary Coin

Probability Level 5

You have a fair coin with a "1" on one side and a "0" on another side. You decide to flip it until you get a string of "1"s and "0"s that is the binary representation of a number you are thinking of.

For example, if you pick the number 3, then its binary representation would be "11" and the expected number of flips to get this combination would be 6.

For what number is the expectation value for the number of flips needed to get its binary representation exactly 62?

Note: Leading zeros aren't allowed. i.e. The number 5 would be represented by 101, not 0101 nor 00101. Also, you keep flipping until you see the number anywhere in the string. i.e. You don't "start over" once you fail to see the string.

Other Expected Value Quizzes

Image credit : www.cointalk.com

The answer is 31.

1 solution

Geoff Pilling
Jul 8, 2016

$31$ in binary is $11111$ . And in general to get $n$ heads in a row, or in this case $1$ 's, it is well known that the expectation value is given by:

$E(n) = 2*(2^n - 1)$
$E(5) = 62$

This can be derived by solving the following set of linear equations, where $E_i$ represents the expectation value of getting $5$ $n$ 's once you have $i$ $n$ 's :

$E = 1 + (1/2)(E+E_1)$
$E_1 = 1 + (1/2)(E+E_2)$
$E_2 = 1 + (1/2)(E+E_3)$
$E_3 = 1 + (1/2)(E+E_4)$
$E_4 = 1 + (1/2)(E)$

Solving for $E$ , yields $E=\boxed{62}$

how did you know that the answer was going to solely have consecutive ones?

Willia Chang - 4 years, 11 months ago

I didn't know until I solved it... :-P

Then I solved lots other ones and saw that it was pretty much the only one whose expectation value is 62. And I convinced myself that all 6 digit ones will be 64 or greater.

Geoff Pilling - 4 years, 11 months ago

How do you know that 62 is the unique answer to the problem?

Calvin Lin Staff - 4 years, 11 months ago

Aaaargh.... thought someone might ask that... :-)

For me I solved for all the binary numbers through $111111_2$ , and noticed a pattern, that for $n$ digits, the answer was always in the range $2^n \leq E_n < 2^{n+1}$ . So, although not an exhaustive proof, since for $n=5$ , none of the expectation values were $62$ except for $11111_2$ , I convinced myself that $31$ is the unique answer.

Admittedly, though, although this is fairly convincing, it isn't a proof. Lemme try to see if I can come up with an elegant way to prove this...

Geoff Pilling - 4 years, 11 months ago

62 is 111110. Because when you got to 5 heads in a row, it doesn't matter if you get another head, game will end when you get a tail. The expected amount of flips is 2, so adding that to 62, we get 64. This is better off in linear algebra rather than discrete math, since solving this generally involve using a matrix, except for this special case of consecutive heads. Also, you solved E to be 62, the answer given (by you) is 31.

Lam Nguyen - 4 years, 11 months ago

Please read carefully.

The question asks you to find an $n$ (which the solution has not shown is unique) such that E[number of steps to obtain binary representation of $n$ ] is equal to 62.

The solution shows that E[number of steps to obtain $31=1111_2$ ] is equal to 62.

Calvin Lin Staff - 4 years, 10 months ago

Flipping A Binary Coin

Image credit : www.cointalk.com

The answer is 31.

1 solution

0 pending reports