Homework 8

Exercise 1 (Borel-Cantelli)

• Let \(P\) be a transition matrix for a Markov chain. Show that if

\[ \sum_{n =1} ^{\infty} p_{ss}(n) < \infty\] then the state \(s\) is transient.

• Consider a sequence of coin-flips \((X_n)_{n\in \mathbb{Z}^+}\) where \(p_n = \frac{1}{n^2}\) and \(\mathbb{P}(X_n = 1) = p_n\). Show that there is a random time \(N\) such that \(\mathbb{P}(N < \infty) =1\) and for all \(n > N\), we have \(X_n =0\).
  

Exercise 2 Let \(X\) be an irreducible aperiodic Markov chain on a finite number of states, started at the state \(s\). Show without using any fancy limit theorems, that \(\mathbb{E} T < \infty\), where

\[T = \inf\{ n \geq 1: X_n =s\}.\]

Exercise 3 Let \(N\) be a Poisson process on \([0, \infty)\). Fix \(T >0\). Show that \(R(t) = N(T-t)\) is a Poisson process on \([0, T]\). Hint: appeal to appropriate construction of Poisson processes.

Exercise 4 By brute force, show that for a \(M(\lambda)/M(\mu)/1\) queue that is started with at stationarity, so that the number of items in the system at time any time \(t\) has distribution

\[\mathbb{P}(Q(t) = n) = \rho^n(1-\rho)\]

has the property that an arrival waits time \(W\) until being served, where \(W\) has law

\[ \mathbb{P}(W \leq x) = 1- \rho e^{-x(\mu - \lambda)}.\]

Exercise 5 We say that a continuous-time Markov chain with generator-(Q matrix) \(G\) is reversible with respect to the probability measure \(\pi\) if

\[ \pi_i g_{ij} = \pi_j g_{ji}\]

for all states \(i,j\).

• Show that \(\pi\) must be stationary.

• Show the the continuous-time Markov chain corresponding to a \(M(\lambda)/M(\mu)/1\) queue is reversible with respect to its stationary distribution.

---

---

• Version: 01 December 2020
• Rmd Source