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\}.\]

Solution. We go back to basics. If \(P\) is the transition matrix, then by the assumptions of irreducibility and aperiodicity, we know that \(P^M\) has all positive entries for some \(M>0\); let \(\delta >0\) be the smallest entry. Hence every \(M\) steps, we have a non-zero probability \(\delta >0\) of getting to the state \(s\). Thus \[ \mathbb{P}(T > kM) \leq (1- \delta)^k\] from which we easily deduce that \(T\) has finite expectation.

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.

Solution. We use the construction of Poisson processes are uniform random variables. Suppose we are dealing with a Poisson process of intensity \(\lambda\). Specifically, we divide \([0, \infty)\) into intervals of length \(T\), where we independently place a Poisson number, with mean \(T \lambda\), of independent random variables that are uniformly distributed in the interval of length \(T\). There is no real notation of direction in this construction; moreover if \(U\) is uniformly distributed in \([0, T]\), then \(T-U\) is still uniformly distributed in \([0,T]\). Thus the desired reversibility is obvious.

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)}.\]

Solution. An arrival arrives at time \(t\) to a queue with \(n\) items in front with probability \(\rho^n(1-\rho)\), will have to wait for these \(n\) items to clear, taking time which is a sum of exponentials, giving a gamma distribution; here we also note that the memoryless property of exponentials allows us to forget about the time spent serving an item before the arrival.

We have for \(x \geq 0\), that

\[\begin{eqnarray*} \mathbb{P}(W \leq x) &=& 1-\rho + \sum_{n=1} ^{\infty} \mathbb{P}(W \leq x | Q(t)= n) \mathbb{P}(Q(t) =n) \\ &=& 1-\rho + \sum_{n=1} ^{\infty} \int_0 ^x \Big( \frac{\mu^n t^{n-1} }{\Gamma(n)} e^{-\mu t} dt \Big) \rho^n(1-\rho) \\ &=& 1-\rho + (1- \rho)\int_0 ^x e^{-\mu t} \sum_{n=1} ^{\infty} \frac{\lambda^n t^{n-1} }{(n-1)!} dt \\ &=& 1-\rho + (1-\rho) \int_0 ^x \lambda e^{-\mu t} \sum_{n=0} ^{\infty} \frac{ (\lambda t)^n }{n!} dt \\ &=& 1-\rho + (1-\rho) \int_0 ^x \lambda e^{-\mu t} e^{\lambda t} dt \\ &=& 1-\rho + \rho (1- e^{-(\mu - \lambda)x} ) \\ &=& 1- \rho e^{-x(\mu - x)}. \end{eqnarray*}\]

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\).


Hence we easily verify that for \(n \geq 1\), we have

\[ \pi_n g(n,n+1) = \rho^n(1-\rho) \lambda\] and \[ \pi_{n+1} g(n+1,n ) = \rho^{n+1}(1-\rho) \mu.\] Thus recalling that \(\rho = \lambda/\mu\), we obtain the equality \[ \pi_n g(n, n+1 ) = \pi_{n+1} g(n+1, n).\] Similarly, \[ \pi_n g(n, n-1 ) = \pi_{n-1} g(n-1, n).\] For the case \(n=0\), we have

\[\pi_0g(0,1) = (1- \rho)\lambda\] and \[ \pi_1g(1,0) = (1- \rho)\rho \mu\] so that \[ \pi_0 g(0,1) = \pi_1 g(1,0).\]

Thus we have verified the reversibility conditions.