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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – lulu Apr 16 at 9:52
  • $\begingroup$ @lulu will it be $E_n = 0.5(2E_{n-1}+1 )$ $\endgroup$ – jeea Apr 16 at 9:55
  • $\begingroup$ @jeea Compute $E_n$ directly for small $n$ and test that formula against your values. $\endgroup$ – lulu Apr 16 at 9:58
  • $\begingroup$ @lulu, I think I got the idea. I will post my solution after I finish. Thank you! $\endgroup$ – 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}\;. $$

| cite | improve this answer | |
  • $\begingroup$ That's amazingly clear! Thanks! $\endgroup$ – 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!

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.