Renewal processes and stationarity

1. 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}\)?
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.
3. 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)}\).
4. 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)} \le n < T_{N(n)+1}\) so that \(N(n)/n\) can be sandwiched between \(N(n)/T_{N(n)+1}\) and \(N(n)/T_{N(n)}\). Use this and the fact that \(N(n) \to \infty\) as \(n \to \infty\).
5. 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.
6. 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.
7. 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)\)?
8. Show that \(\nu\) is stationary for \(Y\).
   Hint: \(Y\) is clearly not reversible, so there’s no point trying detailed balance!
9. 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.)