0
$\begingroup$

Consider the follow game played with a fair coin:

  • You start at 0.
  • Each heads flip moves you forward one unit. (i.e. +1)
  • Each tails flip moves you backwards one unit. (i.e. -1)
  • The game ends when you reach either -32 or +63.

What is the expected value of the number of flips it takes before this game ends? Use probability theory to calculate the expected value of the number of flips required to end this game.


I need help to get started on this problem. Where do I begin?

$\endgroup$
  • 1
    $\begingroup$ $$32\cdot63{}$$ $\endgroup$ – Did Feb 27 '17 at 12:00
0
$\begingroup$

For $-32 \leq i \leq 63$, denote the expected number of flips required to end the game as $f_i$ if you starts at position $i$. We have: $$ f_i = \begin{cases} 1 + \frac{f_{i-1} + f_{i+1}}{2}, & \text{if } -32 < i < 63 \\ 0, &\text{if } i = -32 \text{ or } i = 63 \end{cases} \tag{$\spadesuit$} $$ By letting $\Delta_i = f_i - f_{i-1}$, from $(\spadesuit)$, we further have for $-32 < i < 63$, $$ \Delta_i = 2 + \Delta_{i+1} $$ Therefore, $\Delta_{-31} = \Delta_{63} + 188$. Moreover, by symmetry, we have $\Delta_{-31} = -\Delta_{63}$. We conclude $$ \Delta_{63} = -94 \quad\text{and}\quad \Delta_i = 32 - 2i $$ Therefore, \begin{align} f_0 &= f_{-1} + \Delta_0 = f_{-2} + \Delta_{-1} + \Delta_0 = \cdots = f_{-32} + \Delta_{-31} + \cdots + \Delta_0 \\ &= 0 + 94 + \cdots + 32 = 2016 \end{align}


Motivated by Did's comment, more generally, \begin{align} f_i~&=~ f_{-32} + \Delta_{-31} + \cdots + \Delta_i \\ &=~ 0 + 94 + \cdots + (32 - 2i) \\ &=~ (i - (-32))(63 - i) \end{align}

$\endgroup$

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.