Random Walks

Abstract

In this chapter we consider our second important example of discrete-time stochastic process, which is a random walk allowed to evolve over the set ${\mathbb Z}$ of signed integers without any boundary restriction. Of particular importance are the probabilities of return to a given state in finite time, as well as the corresponding mean return time.

Exercises

Exercise 3.1

We consider the simple random walk $(S_n)_{n\in \mathbb N}$ of Sect. 3.1 with independent increments and started at $S_0=0$, in which the probability of advance is p and the probability of retreat is $1-p$.

• (a) Enumerate all possible sample paths that conduct to $S_4 = 2$ starting from $S_0=0$.

• (b) Show that

  $$ {\mathbb {P}}( S_4 = 2 \mid S_0 = 0 ) = \left( {\begin{array}{c}4\\ 3\end{array}}\right) p^3 (1-p) = \left( {\begin{array}{c}4\\ 1\end{array}}\right) p^3 (1-p) . $$

• (c) Show that we have

  $$\begin{aligned}&{ {\mathbb {P}}( S_n = k \mid S_0 = 0 ) }\nonumber \\&= \left\{ \begin{array}{ll} \displaystyle \left( {\begin{array}{c}n\\ (n+k)/2\end{array}}\right) p^{(n+k)/2} (1-p)^{(n-k)/2}, &{} n+k \ \text{ even } \text{ and } |k|\le n,\\ {\mathbb {P}}( S_n = k \mid S_0 = 0 ) = 0, &{} n+k \ \text{ odd } \text{ or } |k| > n. \end{array} \right. \end{aligned}$$

  (3.4.24)

• (d) Show, by a direct argument using a “last step” analysis at time $n+1$ on random walks, that $p_{n, k}: = {\mathbb {P}}( S_n = k \mid S_0 = 0 )$ satisfies the difference equation

  $$\begin{aligned} p_{n+1,k} = p p_{n, k-1} + q p_{n, k+1}, \end{aligned}$$

  (3.4.25)

  under the boundary conditions $p_{0,0}=1$ and $p_{0,k}=0$, $k\not =0$.

• (e) Confirm that $p_{n, k} = {\mathbb {P}}( S_n = k \mid S_0 = 0 )$ given by (3.4.24) satisfies the equation (3.4.25) and its boundary conditions.

Exercise 3.2

Consider a random walk $(S_n)_{n\in \mathbb N}$ on ${\mathbb Z}$ with independent increments and probabilities p, resp. $q=1-p$ of moving up by one step, resp. down by one step. Let

$$ T_0 = \inf \{ n \ge 0 \ : \ S_n = 0 \} $$

denote the hitting time of state .

• (a) Explain why for any $k\ge 1$ we have

  $$ {\mathrm{I}}\!{\mathrm{E}}[ T_0 \mid S_0 = k ] = k {\mathrm{I}}\!{\mathrm{E}}[ T_0 \mid S_0 = 1 ], $$

  and compute ${\mathrm{I}}\!{\mathrm{E}}[ T_0 \mid S_0 = 1 ]$ using first step analysis when $q>p$. What can we conclude when $p\ge q$?

• (b) Explain why, by the Markov property, we have

  $$\begin{aligned} {\mathbb {P}}( T_0< \infty \mid S_0 = k ) = \left( {\mathbb {P}}( T_0 < \infty \mid S_0 = 1 ) \right) ^k, \qquad k\ge 1. \end{aligned}$$

• (c) Using first step analysis for random walks, show that $\alpha : = {\mathbb {P}}( T_0 < \infty \mid S_0 = 1 )$ satisfies the quadratic equation

  $$ p \alpha ^2 - \alpha + q = p ( \alpha - q/p) ( \alpha - 1) = 0, $$

  and give the values of ${\mathbb {P}}( T_0 < \infty \mid S_0 = 1 )$ and ${\mathbb {P}}( T_0 = \infty \mid S_0 = 1 )$ in the cases $p < q$ and $p \ge q$ respectively.

Exercise 3.3

Consider the random walk

$$ S_n : = X_1+\cdots + X_n, \qquad n \ge 1, $$

with $S_0=0$, where $(X_k)_{k\ge 1}$ is a sequence of Bernoulli random variables with

$$ {\mathbb {P}}( X_k = 1 ) = p\in (0,1), \qquad {\mathbb {P}}( X_k = -1 ) = q \in (0,1), $$

and $p+q=1$. Recall that the probability generating function (PGF)

$$\begin{aligned} G_{T_0^r} (s) = \sum _{k=0}^\infty s^k {\mathbb {P}}( T_0^r = k ), \qquad s\in [-1,1], \end{aligned}$$

(3.4.26)

of the first return time $T_0^r : = \inf \{ S_n = 0 \ : \ n \ge 1\}$ to state is given by

$$\begin{aligned} G_{T_0^r} (s) = 1 - \sqrt{1-4pqs^2}, \qquad s\in [-1,1]. \end{aligned}$$

(3.4.27)

• (a) Compute ${\mathbb {P}}(T_0^r = 0)$ and ${\mathbb {P}}( T_0^r < \infty )$ from $G_{T_0^r}$.

• (b) By differentiation of (3.4.26) and (3.4.27), compute ${\mathbb {P}}(T_0^r = 1)$, ${\mathbb {P}}(T_0^r = 2)$, ${\mathbb {P}}(T_0^r = 3)$ and ${\mathbb {P}}(T_0^r = 4)$ using the PGF $G_{T_0^r}$.

• (c) Compute ${\mathrm{I}}\!{\mathrm{E}}[ T_0^r \mid T_0^r < \infty ]$ using the PGF $G_{T_0^r}$.

Exercise 3.4

Consider a simple random walk $(X_n)_{n\ge 0}$ on ${\mathbb Z}$ with respective probabilities p and q of increment and decrement. Let

$$ T_0 : = \inf \{ n \ge 0 \ : \ X_n = 0 \} $$

denote the first hitting time of state , and consider the probability generating function

$$ G_i(s) : = {\mathrm{I}}\!{\mathrm{E}}\big [ s^{T_0} \mid X_0 = i \big ] , \qquad - 1< s < 1, \quad i \in {\mathbb Z}. $$

• (a) By a first step analysis argument, find the finite difference equation satisfied by $G_i(s)$, and its boundary condition(s) at $i=0$ and $i=\pm \infty$.

• (b) Find the value of $G_i(s)$ for all $i\in {\mathbb Z}$ and $s\in (0,1)$, and recover the result of (3.4.23) on the probability generating function of the hitting time $T_0$ of starting from state .

• (c) Recover Relation (2.2.13)–(3.4.16) using $G_i (s)$.

• (d) Recover Relation (2.3.12)–(3.4.18) by differentiation of $s \mapsto G_i (s)$.

• (e) Recover the result of (3.4.9) on the probability generating function of the return time $T_0^r$ to .

Exercise 3.5

Using the probability distribution (3.4.21) of $T_0^r$, recover the fact that ${\mathrm{I}}\!{\mathrm{E}}[ T_0^r \mathbbm {1}_{\{ T_0^r < \infty \} } \mid S_0 = 0 ] =\infty$, when $p=q=1/2$.

Exercise 3.6

Consider a sequence $(X_k)_{k \ge 1}$ of independent Bernoulli random variables with

$$ {\mathbb {P}}( X_k = 1 ) = p, \quad \text{ and } \quad {\mathbb {P}}( X_k = -1 ) = q, \qquad k\ge 1, $$

where $p+q=1$, and let the process $(M_n)_{n\in \mathbb N}$ be defined by $M_0 := 0$ and

$$ M_n := \sum _{k=1}^n 2^{k-1} X_k, \qquad n \ge 1. $$

• (a) Compute ${\mathrm{I}}\!{\mathrm{E}}[M_n]$ for all $n\ge 0$.

• (b) Consider the hitting time $\tau : = \inf \{ n \ge 1 \ : \ M_n = 1 \}$ and the stopped process

  $$ M_{\min ( n , \tau ) } = M_n \mathbbm {1}_{ \{ n < \tau \} } + \mathbbm {1}_{ \{ \tau \le n\} }, \qquad n \in \mathbb N. $$

  Determine the possible values of $M_{\min ( n , \tau )}$, and the probability distribution of $M_{\min ( n , \tau )}$ at any time $n\ge 1$.

• (c) Give an interpretation of the stopped process $(M_{\min ( n , \tau ) })_{n\in \mathbb N}$ in terms of strategy in a game started at $M_0=0$.

• (d) Based on the result of part (b), compute ${\mathrm{I}}\!{\mathrm{E}}[ M_{\min ( n , \tau ) } ]$ for all $n \ge 1$.

Exercise 3.7

Winning streaks. Consider a sequence $(X_n)_{n\ge 1}$ of independent Bernoulli random variables with the distribution

$$ {\mathbb {P}}( X_n = 1 ) = p, \qquad {\mathbb {P}}( X_n = 0 ) = q, \qquad n \ge 1, $$

with $q:=1-p$. For some $m\ge 1$, let $T^{(m)}$ denote the time of the first appearance of m consecutive “1” in the sequence $(X_n)_{n\ge 1}$. For example, for $m=4$ the following sequence

$$ ( \overset{1 \atop \downarrow }{0},\overset{2 \atop \downarrow }{1},\overset{3 \atop \downarrow }{1},\overset{4 \atop \downarrow }{0}, \underset{ 4 \text{ times } }{\underbrace{ \overset{5 \atop \downarrow }{1} , \overset{6 \atop \downarrow }{1}, \overset{7 \atop \downarrow }{1}, \overset{8 \atop \downarrow }{1} }} , 0 , 1, 1, 0, \ldots ) $$

yields $T^{(4)} = 8$.

• (a) Compute ${\mathbb {P}}(T^{(m)} < m)$, ${\mathbb {P}}(T^{(m)} = m)$, ${\mathbb {P}}(T^{(m)} = m+1)$, and ${\mathbb {P}}(T^{(m)} = m+2)$.

• (b) Show that the probability generating function

  $$ G_{T^{(m)}}(s) : = {\mathrm{I}}\!{\mathrm{E}}\left[ s^{T^{(m)}} \mathbbm {1}_{\{ T^{(m)} < \infty \} } \right] , \qquad s\in (-1,1), $$

  satisfies

  $$\begin{aligned} G_{T^{(m)}} (s) = p^m s^m + \sum _{k=0}^{m-1} p^k q s^{k+1} G_{T^{(m)}} (s) , \qquad s\in (-1,1). \end{aligned}$$

  (3.4.28)

  Hint: Look successively at all possible starting patterns of the form

  $$ (1, \ldots , 1, \overset{ k \atop \downarrow }{1}, 0 , \ldots ), $$

  where $k=0,1,\ldots , m$, compute their respective probabilities, and apply a “k-step analysis” argument.

• (c) From (3.4.28), compute the probability generating function $G_{T^{(m)}}$ of $T^{(m)}$ for all $s\in (-1,1)$.

  Hint: We have

  $$ \sum _{k=0}^{m-1} x^k = \frac{1-x^m}{1-x}, \qquad x\in (-1,1). $$

• (d) From the probability generating function $G_{T^{(m)}}(s)$, compute ${\mathrm{I}}\!{\mathrm{E}}[ T^{(m)}]$ for all $m\ge 1$.

  Hint: It can be simpler to differentiate inside (3.4.28) and to use the relation

  $$ (1-x) \sum _{k=0}^{m-1} (k+1)x^k + m x^m = \frac{1-x^m}{1-x}, \qquad x\in (-1,1). $$

Exercise 3.8

Consider a random walk $(S_n)_{n\in \mathbb N}$ on ${\mathbb Z}$ with increments $\pm 1$, started at $S_0 = 0$. Recall that the number of paths joining states and over 2m time steps is

$$\begin{aligned} \left( {\begin{array}{c}2m\\ m+k\end{array}}\right) . \end{aligned}$$

(3.4.29)

• (a) Compute the total number of paths joining $S_1=1$ to $S_{2n-1}=1$.

  Hint: Apply the formula (3.4.29).

• (b) Compute the total number of paths joining $S_1=1$ to $S_{2n-1}=-1$.

  Hint: Apply the formula (3.4.29).

• (c) Show that to every one path joining $S_1=1$ to $S_{2n-1}=1$ by crossing or hitting we can associate one path joining $S_1=1$ to $S_{2n-1}=-1$, in a one-to-one correspondence. Hint: Draw a sample path joining $S_1=1$ to $S_{2n-1}=1$, and reflect it in such a way that the reflected path then joins $S_1=1$ to $S_{2n-1}=-1$.

• (d) Compute the total number of paths joining $S_1=1$ to $S_{2n-1}=1$ by crossing or hitting . Hint: Combine the answers to part (b) and part (c).

• (e) Compute the total number of paths joining $S_1=1$ to $S_{2n-1}=1$ without crossing or hitting . Hint: Combine the answers to part (a) and (d).

• (f) Give the total number of paths joining $S_0=0$ to $S_{2n}=0$ without crossing or hitting between time 1 and time $2n-1$. Hint: Apply two times the answer to part (e). A drawing is recommended.

Exercise 3.9

Range process. Consider the random walk $(S_n)_{n\ge 0}$ defined by $S_0=0$ and

$$ S_n: = X_1 + \cdots + X_n, \qquad n \ge 1, $$

where $(X_k)_{k\ge 1}$ is an i.i.d.⁷ family of $\{ - 1 , + 1 \}$-valued random variables with distribution

$$ \left\{ \begin{array}{l} {\mathbb {P}}( X_k = +1 ) = p,\\ {\mathbb {P}}( X_k = -1 ) = q, \end{array} \right. $$

$k \ge 1$, where $p+q=1$. We let $R_n$ denote the range of $(S_0,S_1,\ldots , S_n)$, i.e. the (random) number of distinct values appearing in the sequence $(S_0,S_1,\ldots , S_n)$.

• (a) Explain why

  $$ R_n = 1 + \left( \sup _{k=0,1,\ldots , n} S_k \right) - \left( \inf _{k=0,1,\ldots , n} S_k \right) , $$

  and give the value of $R_0$ and $R_1$.

• (b) Show that for all $k\ge 1$, $R_k-R_{k-1}$ is a Bernoulli random variable, and that

  $$ {\mathbb {P}}( R_k - R_{k-1} = 1 ) = {\mathbb {P}}( S_k - S_0 \not = 0, S_k - S_1 \not = 0, \ldots , S_k - S_{k-1} \not = 0 ) . $$

• (c) Show that for all $k\ge 1$ we have

  $$ {\mathbb {P}}( R_k - R_{k-1} = 1 ) = {\mathbb {P}}( X_1 \not = 0, X_1 + X_2 \not = 0, \ldots , X_1+\cdots +X_k \not = 0 ) . $$

• (d) Show why the telescoping identity $\displaystyle R_n = R_0 + \sum _{k=1}^n ( R_k - R_{k-1} )$ holds for all $n \in \mathbb N$.

• (e) Show that ${\mathbb {P}}( T_0^r = \infty ) = \lim _{k \rightarrow \infty } {\mathbb {P}}( T_0^r > k )$.

• (f) From the results of Questions (c) and (d), show that

  $$ {\mathrm{I}}\!{\mathrm{E}}[ R_n ] = \sum _{k=0}^n {\mathbb {P}}( T_0^r > k ) , \qquad n \in \mathbb N, $$

  where $T_0^r = \inf \{ n \ge 1 \ : \ S_n = 0 \}$ is the time of first return to of the random walk.

• (g) From the results of Questions (e) and (f), show that

  $$ {\mathbb {P}}( T_0^r = \infty ) = \lim _{n\rightarrow \infty } \frac{1}{n} {\mathrm{I}}\!{\mathrm{E}}[ R_n ] . $$

• (h) Show that

  $$ \lim _{n\rightarrow \infty } \frac{1}{n} {\mathrm{I}}\!{\mathrm{E}}[ R_n ] = 0. $$

  when $p=1/2$, and that ${\mathrm{I}}\!{\mathrm{E}}[ R_n ] \simeq _{_{n\rightarrow \infty }} n | p - q |$, when $p \not = 1/2$.⁸

Fig. 3.5

Illustration of the range process

In Fig. 3.5 the height at time n of the colored area coincides with $R_n-1$.