Renewal processes and stationarity

You will get more from the exercises by trying them before looking at the solutions!

Suppose that $X$ is a simple symmetric random walk on $\mathbb{Z}$, started from 0. Show that \[T = \inf \{n \ge 0: X_n \in \{-10, 10\} \}\] is a stopping time (i.e. show that the event $\{T \le n\}$ is determined by $X_0, X_1, \ldots, X_n$). What is the value of $\operatorname{\mathbb{P}}\left(T < \infty\right)$? What is the distribution of $X_{T}$?

Hint: It may be easier to describe $\{T>n\}$ (why is this enough?). Will $X$ eventually make 20 consecutive jumps to the right? For $X_T$, think symmetry.

Solution: The event $\{T >n \} = \{ X_1 \not\in \{-10,10\}, X_2 \not\in \{-10,10\},\dots, X_n \not\in \{-10,10\} \}$ is clearly determined by $X_1, X_2, \dots, X_n$, and therefore so is the complementary event $\{ T \leq n\} = \{T>n\}^\mathsf{c}$. Since a simple symmetric random walk must eventually leave any bounded interval containing its starting point, the stopping time is almost surely finite: $\operatorname{\mathbb{P}}\left(T<\infty\right) = 1$. To prove rigorously, consider $X$ walking on the whole of $\mathbb{Z}$, and define events $A_k = \{ \text{jumps } 20k+1, 20k+2, \dots, 20k+20 \text{ are all to the right} \}$, for $k= 0,1,\dots$. Observe that: (i) the $A_k$ are independent, (ii) if $A_k$ occurs then $T < 20k+20$ (either $X$ already left $(-10,10)$ by time $20k$, or $X_{20k} \in (-10,10)$ and the next 20 steps are to the right, meaning $X_{20k+20} > 10$), (iii) $\operatorname{\mathbb{P}}\left(A_k\right) = 2^{-20}>0$. Hence the smallest $k$ for which $A_k$ occurs is a Geometric random variable with positive success probability, which is almost surely finite, and hence $T$ is too. The distribution of $X_T$ follows from symmetry of the random walk; since the walk starts at the mid point of the interval $[-10,10]$ is it equally likely to hit either end first: $\operatorname{\mathbb{P}}\left(X_T = 10\right) = \operatorname{\mathbb{P}}\left(X_T=-10\right) = 1/2$.

For an irreducible recurrent Markov chain $(X_n)_{n \ge 0}$ on a discrete state-space $S$, fix $i \in S$ and let $H_0^{(i)} = \inf\{n \ge 0: X_n=i\}$. For $m \ge 0$, let \[H_{m+1}^{(i)} = \inf \{n > H_m^{(i)}: X_n = i\}.\] Show that $H_0^{(i)}, H_1^{(i)}, \ldots$ is a sequence of stopping times.

Hint: You might find it helpful to view $H_m^{(i)}$ as the $(m+1)$-th visit to state $i$.

Solution: Guided by the hint, observe that $H_{m+1}^{(i)}$ is the first time after $H_m^{(i)}$ that $X$ visits state $i$. Hence an induction argument shows that $H_{m}^{(i)}$ is the time of the $(m+1)$-th visit to $i$. Then, $\{ H_m^{(i)} \leq n\}$ is just the event that at least $m+1$ of the random variables $X_0, X_1, \dots, X_n$ are equal to $i$, which is clearly determined by $X_0, \dots, X_n$.

Check that it follows from the strong Markov property that $(H_{m+1}^{(i)} - H_m^{(i)} , m \ge 0)$ is a sequence of i.i.d. random variables, independent of $H_0^{(i)}$.

Hint: Use the strong Markov property at the times $H_0^{(i)}, H_1^{(i)}, \dots$. Use the fact that $X_{H_m^{(i)}}$ is (almost surely) constant.

Solution: We apply the strong Markov property sequentially to the stopping times $H_0^{(i)}, H_1^{(i)}, \dots$. First, we remark that $H_0^{(i)}$ is finite almost surely, since $X$ is irreducible and recurrent. Moreover $X_{H_0^{(i)}} \equiv i$ almost surely, by definition. Hence the strong Markov property implies that $(X_{H_0^{(i)}+n})_{n\geq 0}$ has the same distribution as $(X_n)_{n\geq 0}$ started from $X_0=i$, whatever the value of $H_0^{(i)}$. This implies that $H_1^{(i)}-H_0^{(i)}$ is finite and has the same distribution as the first return time to state $i$ of the walk when started in state $i$, i.e., the distribution of $R_i = \inf\{n > 0: X_n = i\}$ given $X_0 = i$, and $H_1^{(i)}-H_0^{(i)}$ is independent of $H_0^{(i)}$. Now, suppose that $H_m^{(i)}$ is finite; applying the Strong Markov property to $H_m^{(i)}$ implies that $(X_{H_m^{(i)}+n})_{n\geq 0}$ has the same distribution as $(X_n)_{n\geq 0}$ started from $X_0=i$, whatever the value of $H_m^{(i)}$. So, as before, $H_{m+1}^{(i)}-H_m^{(i)}$ is finite, has the same distribution as $R_i$ given $X_0=i$, and $H_{m+1}^{(i)}-H_m^{(i)}$ is independent of $H_m^{(i)}$. Moreover, the strong Markov property also shows that $(X_{H_m^{(i)}+n})_{n\geq 0}$ and $(X_n)_{0\leq n< H_m^{(i)}}$ are independent, so $H_{m+1}^{(i)}-H_m^{(i)}$ is independent of $H_k^{(i)}$ for all $k=0,1,\dots, m-1$. Hence, by induction the random variables $H_{m+1}^{(i)}-H_m^{(i)}$, $m=0,1,\dots$ are independent and identically distributed and also independent of $H_0^{(i)}$.

Suppose that $(N(n))_{n \ge 0}$ is a delayed renewal process with inter-arrival times $Z_0, Z_1, \ldots$ where $Z_0$ is a non-negative random variable, independent of $Z_1, Z_2, \ldots$ which are i.i.d. strictly positive random variables with common mean $\mu$. Use the Strong Law of Large Numbers for $T_k = \sum_{i=0}^k Z_i$ to show that \[\frac{N(n)}{n} \to \frac{1}{\mu} \quad \text{ a.s. as $n \to \infty$}.\] Hint: note that $T_{N(n)-1} \le n < T_{N(n)}$ so that $N(n)/n$ can be sandwiched between $N(n)/T_{N(n)}$ and $N(n)/T_{N(n)-1}$. Use this and the fact that $N(n) \to \infty$ as $n \to \infty$.

Solution: Since $N(n) = \#\{k\geq 0: T_k \leq n\}$, the random variable $N(n)$ takes values in $\{1,2,\dots\}$ and $N(n) = \ell$ if and only if $T_{\ell-1} \leq n < T_{\ell}$, for all $\ell \geq 1$. In other words, $T_{N(n)-1} \leq n < T_{N(n)}$. This implies that $N(n)/T_{N(n)} < N(n)/n \leq N(n)/T_{N(n)-1}$. Since $Z_1$ is finite almost surely (since it has a finite mean), we have $N(n) \to\infty$ almost surely as $n\to\infty$. Thus $\liminf_{n\to\infty}(N(n)/n) \geq \liminf_{n\to\infty}(N(n)/T_{N(n)}) = \liminf_{n\to\infty}{n/T_n} = 1/\mu$, and $\limsup_{n\to\infty}(N(n)/n) \leq \limsup_{n\to\infty}\left(\frac{N(n)}{N(n)-1}\frac{N(n)-1}{T_{N(n)-1}}\right) \leq \limsup_{n\to\infty}(n/(n-1)) \cdot \limsup_{n\to\infty}{n/T_n} = 1/\mu$.

Let $(Y(n))_{n \ge 0}$ be the auxiliary Markov chain associated to a delayed renewal process $(N(n))_{n \ge 0}$ i.e. $Y(n) = T_{N(n-1)} - n$. Check that you agree with the transition probabilities given in the lecture notes.

Hint: Note that $T_{N(n-1)}$ agrees with the smallest sum $T_j = \sum_{i=0}^j Z_i$ that is greater than or equal to $n$, because $T_{N(n-1)-1} \leq n-1 < T_{N(n-1)}$. (This interpretation also holds for $n=0$, where $N(-1) \equiv 0$.)

Solution: Suppose $Y(n) = k \geq 1$, so that $T_{N(n-1)} = n + k \geq n+1$. In other words, $T_{N(n-1)}$ is greater than or equal to $n+1$, and it must be the smallest such $T_j$, since $T_{N(n-1)-1} \leq n-1 < n+1$. Hence $T_{N(n)} = T_{N(n-1)}$, and therefore $Y(n+1) = T_{N(n)} - (n+1) = T_{N(n-1)} - n - 1 = Y(n) - 1$, with probability 1. Otherwise, if $Y(n) = 0$, then $T_{N(n-1)} = n$, so $T_{N(n-1)}$ is strictly less than $n+1$, and $T_{N(n-1)+1} = T_{N(n-1)} + Z_{N(n-1)+1}$ is greater than or equal $n+1$ (since $Z_{N(n-1)+1}$ is strictly positive). Hence $T_{N(n)} = T_{N(n-1)} + Z_{N(n-1)+1}$, and therefore $Y(n+1) = T_{N(n)} - (n+1) = T_{N(n-1)} + Z_{N(n-1)+1} - n - 1 = Z_{N(n-1)+1}-1$. This means that the probability $\operatorname{\mathbb{P}}\left(Y(n+1) = i \mid Y(n)=0\right)$ is equal to $\operatorname{\mathbb{P}}\left(Z_{N(n-1)+1} = i+1\right) = \operatorname{\mathbb{P}}\left(Z_1 = i+1\right)$.

Let \[\nu_i = \frac{1}{\mu} \operatorname{\mathbb{P}}\left(Z_1 \ge i+1\right), \quad i \ge 0.\] Check that $\nu = (\nu_i)_{i \ge 0}$ defines a probability mass function.

Hint: Recall the “tail sum formula”” for expectation of a non-negative integer-valued random variable.

Solution: Since $Z_1$ is non-negative and integer valued, $\mu = \operatorname{\mathbb{E}}\left[Z_1\right] = \sum_{i\geq 0} \operatorname{\mathbb{P}}\left(Z_1 > i\right) = \sum_{i\geq 0} \mu \nu_i$ implying $\sum_{i\geq 0}\nu_i = 1$.

Suppose that $Z^*$ has the size-biased distribution associated with the distribution of $Z_1$, defined by \[\operatorname{\mathbb{P}}\left(Z^* = i\right) = \frac{i \operatorname{\mathbb{P}}\left(Z_1 = i\right)}{\mu}, \quad i \ge 1.\]
1. Verify that this is a probability mass function.
2. Let $L \sim \text{U}\{0,1,\ldots, Z^*-1\}$. Show that $L \sim \nu$.
  Note that you can generate $L$ starting from $Z^*$ by letting $U \sim \text{U}[0,1]$ and then setting $L = \lfloor U Z^* \rfloor$.
3. What is the size-biased distribution associated with $\text{Po}(\lambda)$?

Hint:

Use the usual definition of expectation of a non-negative integer-valued random variable.
Find $\operatorname{\mathbb{P}}\left(L=j\right)$ using the partition theorem/law of total probability (partitioning on the possible values of $Z^*$).
if $Z\sim \text{Po}(\lambda)$ then $\operatorname{\mathbb{P}}\left(Z=i\right) = \exp(-\lambda)\lambda^i/i!$.

Solution:

We have $\sum_{i\geq 1} \operatorname{\mathbb{P}}\left(Z^* = i\right) = \frac{1}{\mu} \sum_{i\geq 1} i \operatorname{\mathbb{P}}\left(Z_1 = i\right) = \frac{1}{\mu} \sum_{i\geq 0} i \operatorname{\mathbb{P}}\left(Z_1 = i\right) = \operatorname{\mathbb{E}}\left[Z_1\right]/\mu = 1$.
By the law of total probability $\operatorname{\mathbb{P}}\left(L=j\right) = \sum_{i\geq 1} \operatorname{\mathbb{P}}\left(L=j\mid Z^*=i\right)\operatorname{\mathbb{P}}\left(Z^*=i\right) = \sum_{i\geq j+1} \frac{1}{i} \frac{i \operatorname{\mathbb{P}}\left(Z_1 = i\right)}{\mu} = \frac{1}{\mu}\operatorname{\mathbb{P}}\left(Z_1 \geq j+1\right) = \nu_j$.
If $Z\sim \text{Po}(\lambda)$ then $\mu =\operatorname{\mathbb{E}}\left[Z\right] = \lambda$, and $\operatorname{\mathbb{P}}\left(Z^*=i\right) = \frac{i \exp(-\lambda)\lambda^i/i!}{\lambda} = \exp(-\lambda)\lambda^{i-1}/(i-1)! = \operatorname{\mathbb{P}}\left(Z = i-1\right)$. In other words, the size biased distribution $Z^*$ has the same distribution as $Z+1$.

Show that $\nu$ is stationary for $Y$.
Hint: $Y$ is clearly not reversible, so there’s no point trying detailed balance!

Additional hint: Show that $\nu P = \nu$ for the transition matrix $P$ for the chain $Y$.

Solution: Recall (from the lectures, or Exercise 5 above) that the non-zero entries of $P$ are $P_{k,k-1} = 1$ for $k\geq 1$ and $P_{0,i} = \operatorname{\mathbb{P}}\left(Z_1 = i+1\right)$ for $i\geq 0$. Thus for all $j\geq 0$, we have $\sum_i \nu_i P_{i,j} = \nu_{j+1} + \nu_0 \operatorname{\mathbb{P}}\left(Z_1 = j+1\right) = \frac{1}{\mu}\left(\operatorname{\mathbb{P}}\left(Z_1 \geq j+2\right) + \operatorname{\mathbb{P}}\left(Z_1 = j+1\right)\right) = \nu_j$.

(In fact, it is not difficult to show uniqueness here: if $\pi$ is a measure satisfying $\pi_j = \sum_i \pi_i P_{i,j} = \pi_{j+1} + \pi_0 \operatorname{\mathbb{P}}\left(Z_1=j+1\right)$ then $\pi$ is proportional to $\nu$.)

Check that if $\operatorname{\mathbb{P}}\left(Z_1 = k\right) = (1-p)^{k-1} p$, for $k \ge 1$, the stationary distribution $\nu$ for the time until the next renewal is $\nu_i = (1-p)^i p$, for $i \ge 0$. (In other words, if we flip a biased coin with probability $p$ of heads at times $n=0,1,2,\ldots$ and let $N(n) = \#\{0 \le k \le n: \text{we see a head at time $k$}\}$ then $(N(n), n \ge 0)$ is a stationary delayed renewal process.)

Hint: Calculate $\operatorname{\mathbb{P}}\left(Z_1\geq i+1\right) = \operatorname{\mathbb{P}}\left(Z_1 > i\right)$ using a geometric series (or knowledge about Geometric random variables).

Solution: For all $i\geq 0$, $\operatorname{\mathbb{P}}\left(Z_1 \geq i+1\right) = \sum_{k\geq i+1} (1-p)^{k-1}p = (1-p)^i \sum_{k\geq 1}(1-p)^{k-1}p = (1-p)^i$. But $\mu = 1/p$ since $Z_1$ is a Geometric random variable with success probability $p$. Hence $\nu_i = \frac{1}{\mu}\operatorname{\mathbb{P}}\left(Z_1 \geq i+1\right) = (1-p)^i p$.