# Symmetric random walk with bounds

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.

• 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

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, $t_x=1+\frac12(t_{x-1}+t_{x+1})$ for every $0\leqslant x\leqslant2$. By definition, $t_{-1}=t_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)$.

• I have a question regarding your basic argument. Why by definition does $u_{-1}=u_{3}=0$? If we are trying to calculated the expected first hitting time for either boundary why do we computer $t_{x}$ at $x=0$? Is this because we assume the process starts at $x=0$? – user75514 Apr 7 '17 at 18:13
• @user75514 Yes, $\mathbb E_x$ refers to the random walk starting at $x$. – Did Apr 7 '17 at 18:20
• So are $u_{-1}$ and $u_{3}$ the expected first arrival at -1 and 3? Why are these 0? – user75514 Apr 7 '17 at 18:23
• @user75514 Because $\tau=\inf\{n\geqslant 0\mid x_n\in\{-1,3\}\}$ is such that $P_{-1}(\tau=0)=P_3(\tau=0)=1$ hence $t_{-1}=E_{-1}(\tau)=0$ and $t_3=E_3(\tau)=0$. (Nota: $u_x$ is a typo for $t_x$.) – Did Apr 7 '17 at 18:27
• @Did In order to use the optimal stopping theorem (I guess this is what you've used here), we need to show that $\tau$ is a.s. bounded. However, here, we only have that $\mathrm{P}[\tau < \infty] = 1$. I think you need to modify this argument to guarantee that the stopping time is a.s. bounded. – Pantelis Sopasakis Jan 24 '19 at 12:41

$$\newcommand{\Z}{\mathbb{Z}}\newcommand{\N}{\mathbb{N}}\newcommand{\E}{\mathbb{E}}\newcommand{\F}{\mathcal{F}}\newcommand{\P}{\mathrm{P}}$$As @Did pointed out in a comment above, the optional stopping theorem (OST) holds under relaxed uniform integrability assumptions. I was unaware of this more general statement, so I used the more classical statement of OST which requires $$\tau$$ to be a.s. bounded to compute the expected stopping time. I found these lecture notes and this book where the OST is stated under UI conditions (and the proof is not too difficult).

In any case, I had already derived the result using the version of the OST I knew, so here it is:

The a.s. boundedness assumption often fails to hold in practice. However, for every fixed $$N\in\N$$, $$\tau \wedge N$$ is a bounded stopping time. The idea is to apply OST for $$\tau \wedge N$$ and take $$N\to\infty$$.

Problem. Let $$(X_n)_n$$ be the standard symmetric random walk with $$X_0=x$$ and let $$a < x < b$$ with $$a,b\in\Z$$. Define $$\tau = \inf\{n\in\N {}\mid{} X_n \in \{a,b\}\}$$. Find $$\E[\tau]$$.

Step 1. We will show that $$Y_n = X_n^2 - n$$ is a martingale with respect to the natural filtration of $$X_n$$, $$(\F_n)_n$$. Indeed,

1. $$Y_n$$ is $$\F_n$$-measurable
2. Since $$\E[|X_n|]\leq |x| + n$$, we have $$\E[Y_n] = \E[X_n^2 - n] \leq (|x|+n)^2 < \infty$$
3. We have $$Y_{n+1} = Y_n + W_n$$, and \begin{align} \E[Y_{n+1}\mid \F_n] {}={}& \E[X_{n+1}^2-n-1 {}\mid{} \F_n]\\ {}={}& \E[(X_{n}+W_{n+1})^2-n-1 {}\mid{} \F_n]\\ {}={}& \E[X_{n}^2+W_{n+1}^2+2X_nW_{n+1}-n-1 {}\mid{} \F_n]\\ {}={}& X_{n}^2+\E[W_{n+1}^2\mid \F_n] +2X_n\E[W_{n+1}\mid \F_n]-n-1\\ {}={}& X_{n}^2-n=Y_n\\ \end{align}

Step 2. Let $$N\in\N$$. Since $$Y_n$$ is an $$\F_n$$-martingale, $$\tau\wedge N$$ is a bounded $$\F_n$$-measurable stopping time (indeed, $$\tau\wedge N \leq N$$), we may employ OST: \begin{align} {}&{}\E[Y_{0}] = \E[Y_{\tau \wedge N}]\\ \Leftrightarrow{}&{} x^2 {}={} \E[X_{\tau \wedge N}^2 - \tau\wedge N]\\ \Leftrightarrow{}&{} x^2 {}={} \E[X_{\tau \wedge N}^2] - \E[\tau\wedge N] \tag{1} \end{align}

Step 3. Note that $$\tau\wedge N \leq \tau \wedge (N+1)$$, therefore, by virtue of Lebesgue's monotone convergence theorem, \begin{align} \lim_{N\to\infty}\E[\tau \wedge N] = \E[\lim_{N\to\infty} \tau \wedge N] = \E[\tau]\tag{2} \end{align}

Step 4. We need to compute $$\lim_n \E[X_{\tau \wedge N}^2]$$. We will use a known fact for random walks: for $$x,m\in \N$$ let $$\tau(m) = \inf\{n \in \N {}\mid{} X_n = m, \text{with }X_0 = x\}$$. Then, for $$a,

\begin{align} \P[\tau(b,x) < \tau(a, x)] = \frac{x-a}{b-a}.\tag{3} \end{align}

This is easy to prove. We also have that

\begin{align} \E[X_{\tau\wedge N}^2] = \E[X_{\tau}^2 1_{\tau < N}] + \E[X_{N}^2 1_{\tau \geq N}]\tag{4} \end{align}

For the second term in (4) we have that $$0 \leq \E[X_N^2 1_{\tau \geq N}] \leq \max\{a^2, b^2\} \E[1_{\tau \geq N}] \to 0$$ as $$N\to\infty$$.

For the first term, we have

\begin{align} \lim_n \E[X_{\tau}^2 1_{\tau < N}] {}={}& a^2 \P[\tau(a, x) < \tau(b,x )] + b^2 \P[\tau(b, x) < \tau(a,x )]\\ {}={}& a^2 \left(1 - \frac{x-a}{b-a}\right) + b^2 \frac{x-a}{b-a}\\ {}={}& x(a+b) - ab\tag{5} \end{align}

Therefore, from all the above we have

\begin{align} \E[\tau] = (b-x)(x-a)\tag{*} \end{align}

• For the record, using $\tau\wedge n$ and letting $n$ go to infinity is the classical way to prove the most classical version of the OST (which, sorry to say, is definitely not the version for almost surely bounded stopping times, since this restricted version is almost never usable). – Did Jan 25 '19 at 12:24

I asked a similar question to poster and was directed here, but found the level of complexity of the arguments very difficult to sift through for my level of math experience.

It turns out the answer is incredibly simple - I was shocked.

For anyone who just needs the solution for application purposes, the answer is A*B, where A is the upper bound and B is the lower bound.

Quote from wikipedia: If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab. The probability that this walk will hit b before −a is a/(a+b), which can be derived from the fact that simple random walk is a martingale.

• As explained explicitely for roughly three years in the other answer. Why the shock then? – Did Apr 7 '17 at 18:21