Suppose a coin is tossed repeatedly and independently, and the probability of observing a heads on any toss is 0.6. Now suppose that a one-dimensional simple random walk $\{\sigma_1,\sigma_2,\cdots\}$ is designed based on the coin tossing. For $i=1,2,\cdots,$ a coin is tossed and

$$ \sigma_i = \left\{ \begin{array}{ll} 1, & \text{if a head is observed} \\ -1, & \text{if a tails is observed} \\ \end{array} \right. $$

The random walk starts at the origin. Compute the expected position of the random walk when a string of 2 consecutive heads is observed for the first time. That is compute

$$ E\left(\sum_{i=1}^T \sigma_i\right) $$

where $\{T=i \in \mathbb{N}: \text{A string of 2 consecutive heads is observed for the first time after toss i}\} $.

So I figured I should first compute T, the expected number of flips to get two consecutive heads.

Basically, I did this by conditioning as shown below:

$$E(T) = (1+E(T))\frac{2}{5}+(2+E(T)\frac{3}{5}\frac{2}{5}+2\frac{3}{5}\frac{3}{5}$$

Solving for E(T) I then get E(T) = $\frac{40}{9}$.

Thus, I'm assuming when I calculate $ E\left(\sum_{i=1}^T \sigma_i\right) $, have T=5 since it is the next natural number.

Now even with this assumption I am stuck on what to do next. I guess I could just brute force it by writing out the terms of the sum from the standard expectation formula, but I think there might be an easier way. Any insight would be appreciated.

  • $\begingroup$ Have you tried calculating $E\left(\sum_{i=1}^T \sigma_i|T \right)$ and then using the Towering theorem? $\endgroup$ – alonso s Aug 9 '16 at 5:24
  • $\begingroup$ I have not used the Towering theorem/ total law of expectation due to the fact I'm not sure how to set it up for this problem. $\endgroup$ – kdrozd Aug 9 '16 at 6:17
  • $\begingroup$ Your starting point here was probably not a good idea: while it is true that under an independence-type assumption, $E[\sum_{i=1}^N X_i]=E[N] E[X_i]$, it is not obvious that such an independence assumption is true in this case. Indeed I don't think it is, I would expect that if your $T$ is large then the fraction of heads in your string should be smaller than 0.6. $\endgroup$ – Ian Aug 9 '16 at 21:25

Let $E_{\text{prev}=H}$ be the expected number of total flips to get two consecutive heads, given that the previous flip was a head. Let $E_{\text{prev}\neq H}$ be the expected number of total flips to get two consecutive heads, given that the previous flip was not a head.

$E_{\text{prev}=H} = \frac{6}{10}(1 + 0) + \frac{4}{10}(1 + E_{\text{prev}\neq H})$

$E_{\text{prev}\neq H} = \frac{6}{10}(1 + E_{\text{prev}=H}) + \frac{4}{10}(1 + E_{\text{prev}\neq H})$

We use $E_{\text{prev}\neq H}$ to get the total number of flips. Labeling $E_{\text{total}} = E_{\text{prev}\neq H}$ and combining equations, we have:

$E_{\text{total}} = \frac{6}{10}(1 + \frac{6}{10}(1 + 0) + \frac{4}{10}(1 + E_{\text{total}})) + \frac{4}{10}(1 + E_{\text{total}})$

Solving for $E_{\text{total}}$ we get $\frac{40}{9}$.

However, what we really need is the expected number of heads and the expected number of tails during this time, as this will tell us the expected value of the walk. Since the equation above counts both heads and tails, we can modify the equation to exclude what we don't want to count.

The expected number of heads:

$E_{\text{heads}} = \frac{6}{10}(\color{blue}1 + \frac{6}{10}(\color{blue}1 + 0) + \frac{4}{10}(\color{red}0 + E_{\text{heads}})) + \frac{4}{10}(\color{red}0 + E_{\text{heads}})$

The expected number of tails:

$E_{\text{tails}} = \frac{6}{10}(\color{red}0 + \frac{6}{10}(\color{red}0 + 0) + \frac{4}{10}(\color{blue}1 + E_{\text{tails}})) + \frac{4}{10}(\color{blue}1 + E_{\text{tails}})$

The red designates coin flips that have been removed from the equations, and blue designates the flips we want to count. We get $\frac{8}{3}$ heads and $\frac{16}{9}$ tails on average.

Then the expected value of the walk is $\frac{8}{3}- \frac{16}{9} = \frac{8}{9}$.

Another way to look at it: Since the probability distribution of a single flip also extends to the whole (due to the flips being independent and identically distributed), then if we know that the total number of flips is $\frac{40}{9}$ on average, then $\frac{6}{10}$ of these flips will be heads, with the rest tails. Therefore we get $\frac{40}{9}(\frac{6}{10} - \frac{4}{10}) = \frac{8}{9}$ again for the expected value of the walk.

  • $\begingroup$ Can you explain how you modified the equations slightly in your second to last sentance? $\endgroup$ – kdrozd Aug 9 '16 at 6:12
  • $\begingroup$ For example, if you want to count the number of heads, then you remove the $1$'s that correspond to counting tail flips. $\endgroup$ – Marcus Andrews Aug 9 '16 at 6:16
  • $\begingroup$ I must be interpreting what you did wrong because when I try to replicate I get 19/9 for expected tails and 13/9 for expected heads, which is obviously wrong. Can you show me your derivation real quick or at least your set up and I can handle the algebra. $\endgroup$ – kdrozd Aug 9 '16 at 6:35
  • $\begingroup$ @MarcusStuhr You might want to write down explicitely the recursive identity which yields E(T). $\endgroup$ – Did Aug 9 '16 at 8:09
  • $\begingroup$ Added some more detail. $\endgroup$ – Marcus Andrews Aug 9 '16 at 14:02

I actually think I just came up with the answer another way using Wald's equation:

$$E\left(\sum_{i=1}^T \sigma_i \right) = E(T) E(\sigma_1)= \frac{40}{9}*\left(1*.6-1*.4\right)=\frac{8}{9}$$

This is exactly what Marcus Andrews got above. Thanks for the help


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.