Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
show 1 more comment

1 Answer

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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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