Exercise 1 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 2 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 3 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 4 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\).