# Expected value of a coin tossing game

The game is like this:

I toss a coin and you guess whether it's a head or tail. We will play 10 rounds. If you correctly guess it, you get 1 point (wrong then 0), and, if you get the right guess consecutively, you will get 2,3,4, etc. That means if you get all 10 guesses correct, you will have 1+2+...+10 = 55 points.

For example, in the 10 rounds, your guesses are 'rrrwwrwrr' (r=right, w=wrong). then you will get 1+2+3+0+0+1+0+1+2 = 10points

I found it is quite difficult to compute the expected value of this game. Any idea?

• Work recursively. Let $E_n$ be the expected value of the game with $n$ tosses (so you want $E_{10}$. No problem computing it for small $n$. But it's easy to connect $E_n$ to $E_{i}$ for $i<n$. – lulu Apr 16 at 9:52
• @lulu will it be $E_n = 0.5(2E_{n-1}+1 )$ – jeea Apr 16 at 9:55
• @jeea Compute $E_n$ directly for small $n$ and test that formula against your values. – lulu Apr 16 at 9:58
• @lulu, I think I got the idea. I will post my solution after I finish. Thank you! – pok fung Chan Apr 16 at 9:59

You can think of it as getting one point for each substring of consecutive correct guesses. (For instance, $$3$$ consecutive correct guesses contain $$6$$ substrings of correct guesses and yield $$6$$ points.) Thus, by linearity of expectation the expected number of points is the sum over all substrings of the probability that the substring consists entirely of correct guesses. Since there are $$n-k+1$$ substrings of length $$k$$ (with $$n$$ the number of rounds, in your case $$n=10$$) and a substring of length $$k$$ has probability $$2^{-k}$$ of consisting entirely of correct guesses, the expected value of the game is

$$\sum_{k=1}^n(n-k+1)2^{-k}=n-1+2^{-n}\;.$$

• That's amazingly clear! Thanks! – pok fung Chan Apr 17 at 2:19

With @lulu suggestion, I worked out the answer recursively. @joriki solution is smart and concise.

Consider the expected value of an $$n$$ round game = $$E_n$$. Now let's look at n+1 th round: if the player guesses wrong, then he will get 0 additional point. If the player guesses right, he gets additional points which depends on how many consecutive wins before the n+1 th round.

The number of permutation of getting n+1, n, n-1, ..., 1 consecutive wins (including the n+1 th one) will be: $$1, 1, 2, 2^2,...,2^{n-1}$$, so the additional points will be $$1(n+1), 1(n), 2(n-1), 2^2(n-2),...,2^{n-1}$$. The total permutation of the first n guesses = $$2^n$$.Therefore the additional expected value contributed by the n+1 th correct guess is

$$\frac{1}{2^n}[(n+1) + n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}] = 2 - \frac{1}{2^n}$$

And because the probability of getting the n+1 th guess correct = $$\frac{1}{2}$$, so

$$E_{n+1} = E_n + \frac{1}{2}(2 - \frac{1}{2^n}) = E_n + 1 - \frac{1}{2^{n+1}}$$

With $$E_1 = \frac{1}{2}$$, we can arrive to

$$E_{n} = n-1-\frac{1}{2^n}$$

which agrees to @joriki solution. Thank you all for the help!