```{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)