{r setup, include=FALSE} knitr::opts_chunk$set(echo = TRUE)  {exercise} 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} 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} **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} 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.  {solution} * We recall that the rows of a$Q$matrix are cooked up to sum to zero. Hence, $$(\pi G)_k = \sum_i \pi_i g_{ik} = \pi_k\sum_i g_{ki} = \pi_k \cdot 0 = 0$$ * We recall that $$\pi_i = \rho^i(1-\rho)$$ $$g(n, n+1) = \lambda \text{ and } g(n, n-1) = \mu \text{ for } n \geq 1$$ $$g(0, 1)= \lambda.$$ 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. 

* Version: r format(Sys.time(), '%d %B %Y') * [Rmd Source](https://tsoo-math.github.io/ucl/QHW8.1-sols.Rmd)