Question. Let $X_1,X_2,…$ be an i.i.d sequence of random variable with $P(X_i=0)=P(X_i=1)=1/2$. Let $\tau$ be the waiting time until the appearance of the six consecutive $1's$. That is
$$
\tau = \inf\{k \geq 6 : X_{k-5}=1,X_{k-4}=1,..,X_{k}=1\}
$$
Find $E(\tau)$.
My attempt:
I am thinking to apply Optional Stopping theorem to find $E(\tau)$.
Firstly, I have shown that $P(\tau < \infty)=1$. Let
$$
Y_i = 2^61_{\{X_i=1,X_{i+1}=1,..X_{i+5}=1\}}
$$
Then I define a random variable $$
Z_n= \sum_{i =1}^n E[Y_i|F_n]-n
$$
I proved the $Z_n$ is a martingale w.r.t to $F_n$ where $F_n= \sigma(X_1,….X_n)$.
If I will show that $\tau$ is a stopping time, then
by Optional Stopping theorem ,
$$E(Z_{\tau})=E(Z_1)$$.
I got $E(Z_1)=0$, this implies $$ E(\tau)= \sum_{i=1}^\tau E(E(Y_i|F_{\tau})$$
I am not sure how to conclude the last part of this question, can anyone help me with this?
Can anyone also suggest how do I claim $\{\tau \leq n\}\in F_n$ to prove $\tau$ is a stopping time?
Best Answer
This is a supplement to @Snoop's answer, which uses the standard Markov chain formulation of this problem.
For us to apply OST, we introduce a casino as follows. At every time $t$, a new player arrives and bets $\$1$ on a fair coin-flip landing on heads (i.e. $X_t = 1$). If the coin lands heads, then the casino pays this player $\$2$ and the player stays at the casino; if the coin lands tails (i.e. $X_t = 0$), the player loses all their money and leaves the casino. At any time $t$, all other remaining players in the casino bet their entire fortune on heads; if the coin lands heads the player doubles their fortune, otherwise they lose it all and leave.
Let $V_t$ be the value process of this casino. By construction, $V_0 = 0$ and since the payoffs are fair, $V_t$ is a martingale. At the stopping time$^\dagger$ $\tau$, the casino will have received an inflow of $\tau$ dollars and will have paid off the wagers each of the players who entered the casino at times $\tau - 5, \tau - 4, \ldots , \tau - 1, \tau$. By the construction of the betting strategy, the outflow of this casino is $2+4+8+16+32+64$. Altogether, the value process of this casino at $\tau$ amounts to $$V_\tau = \tau - (2+4+8+16+32+64) = \tau - 126$$ By the OST$^{\dagger \dagger}$, we get: $$0 = E(V_0) = E(V_\tau ) = E(\tau) -126$$ So that $E(\tau) = 126 = 2(2^{6}-1)$, which agrees with @Snoop's answer.
A couple of technical remarks are remaining:
$(\dagger)$ Observe that for a discrete-time process, $\{\tau \leq k\}\in \mathcal{F}_k$ for all $k$ is equivalent to $\{\tau = k\} \in\mathcal{F}_k$ for all $k$. Note that $\{\tau_k = k\} = \{X_{k-5}=1,X_{k-4}=1, \ldots = X_k = 1\} \in \mathcal{F}_k = \sigma(X_1, \ldots , X_k)$, as the truthiness of $\{X_{k-5}=1,X_{k-4}=1, \ldots = X_k = 1\}$ can be determined by the states of $X_t$ up to time $k$.
$(\dagger \dagger)$ To apply the OST, we can show that $E(\tau) <\infty$ by using an argument analogous to the one used to show that gambler's ruin has a stopping time with bounded first moment. In particular, one sees that $\tau$ is stochastically dominated by $6Y$ where $Y \sim Geo(2^{-6})$, so that $E(\tau) \leq 6E(Y) <\infty$.