Take the 2-minute tour ×

can anyone help me with this: We are considering a symmetric random walk that ends if level 3 is reached or level -1 is reached. Start=0

What is the expected number of walks? So I am looking for: $E[{\tau}]$ with $\tau$=the stopping time.

share|improve this question
What are your thoughts on this question? –  Did Jan 27 '13 at 20:18
I find it difficult to have 2 bounds... –  user59871 Jan 27 '13 at 20:21
(Actually the question is easier with what you call two bounds than with only one.) What did you try? Which similar problems can you solve? –  Did Jan 27 '13 at 20:35
I can solve the one with 1 bound, which would yield: $E[\tau]=infinity$. I tried a similar technique but do not know how to incorporate the 2 bounds... (optional sampling?) –  user59871 Jan 27 '13 at 20:39
Show how you solve the one with 1 bound. –  Did Jan 27 '13 at 20:47

1 Answer 1

Basic argument: One asks for $t_0=\mathbb E_0(\tau)$ where $t_x=\mathbb E_x(\tau)$ for every $-1\leqslant x\leqslant3$. By the (simple) Markov property after one step, $u_x=1+\frac12(u_{x-1}+u_{x+1})$ for every $0\leqslant x\leqslant2$. By definition, $u_{-1}=u_3=0$. This is an affine system of $5$ equations with $5$ unknowns. Solve it. This yields $t_x=(3-x)(x+1)$ for every $-1\leqslant x\leqslant3$. In particular $t_0=3$.

Less basic argument: For every $n\geqslant0$, let $x_n$ denote the position after $n$ steps, $\mathfrak X_n$ the sigma-algebra generated by $(x_k)_{0\leqslant k\leqslant n}$, and $z_n=(x_n+1)(3-x_n)+n$. Then $z_0=3$, $z_\tau=\tau$, and $(z_n)_{n\geqslant0}$ is a martingale with respect to the filtration $(\mathfrak X_n)_{n\geqslant0}$, hence $\mathbb E(z_0)=\mathbb E(z_\tau)$, that is, $\mathbb E(\tau)=3$.

In full generality, the same argument shows that, for every $(a,b)$, the first hitting time of $\{a,b\}$ starting from $a\leqslant x\leqslant b$ has mean $(b-x)(x-a)$.

share|improve this answer

Your Answer


