Stationary distributions and reversibility of jump processes

Find the steady-state process probabilities (as a function of $\rho = \lambda /\mu$) from (7.15) and also as the solution to (7.23). Verify that the two solutions are the same.

For the remaining parts of the exercise, assume that $\rho = 0.01$, thus ensuring (for aiding intuition) that states $0$ and $1$ are much more probable than the other states. Assume that the process has been running for a very long time and is in steady state. Explain in your own words the difference between $\pi_{1}$ (the steady-state probability of state $1$ in the embedded chain) and $p_{1}$ (the steady-state probability that the process is in state $1$). More explicitly, what experiments could you perform (repeatedly) on the process to measure $\pi_{1}$ and $p_{1}$.

Now suppose you want to start the process in steady state. Show that it is impossible to choose initial probabilities so that both the process and the embedded chain start in steady state. Which version of steady state is closest to your intuitive view? (There is no correct answer here, but it is important to realize that the notion of steady state is not quite as simple as you might imagine.)

Let $M(t)$ be the number of transitions (counting both arrivals and departures) that take place by time $t$ in this Markov process and assume that the embedded Markov chain starts in steady state at time $0$. Let $U_{1}, U_{2}, \ldots$ be the sequence of holding intervals between transitions (with $U_{1}$ being the time to the first transition). Show that these rv's are identically distributed. Show by example that they are not independent (i.e., $M(t)$ is not a renewal process).

Find the time-average fraction of time $p_{i}$ spent in each state $i > 0$ in terms of $p_{0}$ and then solve for $p_{0}$.

Find a closed form solution to $\sum_{i}p_{i}\nu_{i}$, where $\nu_{i}$ is the rate at which transitions out of state $i$ occur. Show that the embedded chain is positive recurrent for all choices of $\lambda > 0$ and $\mu > 0$ and explain intuitively why this must be so.

For the embedded Markov chain corresponding to this process, find the steady-state probabilities $\pi_{i}$ for each $i \geq 0$ and the transition probabilities $P_{ij}$ for each $i, j$.

For each $i$, find both the time-average interval and the time-average number of overall state transitions between successive visits to $i$.

Is this process reversible?

Find $p_{i}$, the time-average fraction of time spent in state $i$ for each $i$.

Given that the process is in state $i$ at time $t$, find the mean delay from $t$ until the process leaves state $i$.

Find $\pi_{i}$, the time-average fraction of all transitions that go into state $i$ for each $i$.

Suppose the process is in steady state at time $t$. Find the steady-state probability that the next state to be entered is state $1$.

Given that the process is in state $1$ at time $t$, find the mean delay until the process first returns to state $1$.

Consider an arbitrary irreducible finite-state Markov process in which $q_{ij} = q_{ji}$ for all $i, j$. Either show that such a process is reversible or find a counter example.

Draw a graph for the states of the process, showing all states with two or fewer customers and a couple of states with three customers (label the empty state as $E$). Draw an arrow, labeled by the rate, for each state transition. Explain why these are states in a Markov process.

Is this process reversible? Explain. Assume positive recurrence.

Characterize the process of type $A$ departures from the system (i.e., are they Poisson, do they form a renewal process, at what rate do they depart, etc.?)

Express the steady-state probability $\mathbb {P}\left\{ A\right\}$ of state $A$ in terms of the probability of the empty state $\mathbb {P}\left\{ E\right\}$. Find the probability $\mathbb {P}\left\{ AB\right\}$ and the probability $\mathbb {P}\left\{ ABBA\right\}$ in terms of $\mathbb {P}\left\{ E\right\}$. Use the notation $\rho_{A} = \lambda_{A}/\mu_{A}$ and $\rho_{B} = \lambda_{B}/\mu_{B}$.

Let $Q_{n}$ be the probability of $n$ customers in the system, as a function of $Q_{0} = \mathbb {P}\left\{ E\right\}$. Show that $Q_{n} = (1-\rho )\rho^{n}$ where $\rho = \rho_{A}+\rho_{B}$.

Generalize Exercise 7.22 to the case in which there are $m$ types of customers, each with independent Poisson arrivals and each with independent exponential service times. Let $\lambda_{i}$ and $\mu_{i}$ be the arrival rate and service rate respectively of the $i$th user. Let $\rho_{i} = \lambda_{i}/\mu_{i}$ and assume that $\rho = \rho_{1}+\rho_{2}+\cdots +\rho_{m} < 1$. In particular, show, as before that the probability of $n$ customers in the system is $Q_{n} = (1-\rho )\rho^{n}$ for $0 \leq n < \infty$.

View the customers in (a) as a single type of customer with Poisson arrivals of rate $\lambda = \sum_{i}\lambda_{i}$ and with a service density $\sum_{i}(\lambda_{i}/\lambda )\mu_{i}\exp (-\mu_{i}x)$. Show that the expected service time is $\rho /\lambda$. Note that you have shown that, if a service distribution can be represented as a weighted sum of exponentials, then the distribution of customers in the system for LCFS service is the same as for the M/M/1 queue with equal mean service time.

First assume there are infinitely many identical servers, and each new arrival immediately enters an idle server and begins service. Let the state of the system be $(i,j)$, where $i$ and $j$ are the numbers of type $A$ and type $B$ customers respectively in service. Draw a graph of the state transitions for $i \leq 2, j \leq 2$. Find the steady-state PMF, $\left\{ p(i,j); i,j \geq 0\right\}$, for the Markov process.

Assume for the rest of the exercise that there is some finite number $m$ of servers. Customers who arrive when all servers are occupied are turned away. Find the steady-state PMF, $\left\{ p(i,j); i,j \geq 0, i+j \leq m\right\}$, in terms of $p(0,0)$ for this Markov process.

Let $Q_{n}$ be the probability that there are $n$ customers in service at some given time in steady state. Show that $Q_{n} = p(0,0)\rho_{n}/n!$ for $0 \leq n \leq m$, where $\rho = \rho_{A}+\rho_{B}$, $\rho_{A} = \lambda_{A}/\mu_{A}$, and $\rho_{B} = \lambda_{B}/\mu_{B}$. Solve for $p(0,0)$.

Generalize Exercise 7.26 to the case in which there are $K$ types of customers, each with independent Poisson arrivals and each with independent exponential service times. Let $\lambda_{k}$ and $\mu_{k}$ be the arrival rate and service rate respectively for the $k$th user type, $1 \leq k \leq K$. Let $\rho_{k} = \lambda_{k}/\mu_{k}$ and $\rho = \rho_{1}+\rho_{2}+\cdots +\rho_{K}$. In particular, show, as before, that the probability of $n$ customers in the system is $Q_{n} = p(0,\ldots ,0)\rho^{n}/n!$ for $0 \leq n \leq m$.

View the customers in (a) as a single type of customer with Poisson arrivals of rate $\lambda = \sum_{k}\lambda_{k}$ and with a service density $\sum_{k}(\lambda_{k}/\lambda )\mu_{k}\exp (-\mu_{k}x)$. Show that the expected service time is $\rho /\lambda$. Note that what you have shown is that, if a service distribution can be represented as a weighted sum of exponentials, then the distribution of customers in the system is the same as for the M/M/m/m queue with equal mean service time.

Let $T > 0$ and let $X = \left\{ X(t): 0 \leq t \leq T\right\}$ be an irreducible, non-explosive Markov chain with stationary distribution $\pi$, and suppose that $X(0)$ has distribution $\pi$. Let $Y(t) = X(T-t)$ for $0 \leq t \leq T$. We call $X$ reversible (in equilibrium) if $X$ and $Y$ have the same joint distributions.

(i) Show that $Y$ is a (left-continuous) Markov chain with transition probabilities $\widehat{p}_{i j}(t) = \left(\pi_{j} / \pi_{i}\right) p_{j i}(t)$ and generator $\widehat{\mathbf{G}}$ satisfying $\pi_{j} \hat{g}_{j i} = \pi_{i} g_{i j}$, where the $p_{j i}(t)$ and $\mathbf{G} = \left(g_{i j}\right)$ are those of $X$. Show that $Y$ is irreducible and non-explosive with stationary distribution $\pi$.

(ii) Show that $X$ is reversible in equilibrium if and only if the detailed balance equations $\pi_{i} g_{i j} = \pi_{j} g_{j i}$ (for all $i$ and $j$) hold.

(iii) Show that a measure $\mathbf{\nu }$ satisfies $\mathbf{\nu } \mathbf{G} = \mathbf{0}$ if it satisfies the detailed balance equations.

Let $X$ be irreducible and non-explosive with stationary distribution $\pi$, and assume $X(0)$ has distribution $\pi$.

(i) Kolmogorov’s criterion. Show that $X$ is reversible if and only if, for all $n$ and all finite sequences $k_{1}, k_{2}, \ldots , k_{n}$ of states,

(ii) Kelly’s criterion. Show that $X$ is reversible if, for all distinct triples $i, j, k \in S$, we have $g_{i j} g_{j k} g_{k i} = g_{i k} g_{k j} g_{j i}$, and in addition there exists $c \in S$ such that $g_{i c} > 0$ for all $i \neq c$.

Show that every irreducible chain $X$ with exactly two states is reversible in equilibrium.

Show that every non-explosive birth-death process $X$ having a stationary distribution is reversible in equilibrium.

for any $A \subseteq \mathbb {R},\left|\mathbb {P}\left(X_{t} \in A\right)-\mathbb {P}\left(Y_{t} \in A\right)\right| \rightarrow 0$ as $t \rightarrow \infty$,

if $\mathbb {P}\left(X_{0} \leq Y_{0}\right) = 1$, then $\mathbb {E}\left[g\left(X_{t}\right)\right] \leq \mathbb {E}\left[g\left(Y_{t}\right)\right]$ for any increasing function $g$.

Show that $\frac{1}{t} \int_{0}^{t} I_{\left\{ X(s) = j\right\} } d s \xrightarrow {\text{ a.s. }} \frac{1}{m_{j} g_{j}}$ as $t \rightarrow \infty$;

deduce that the stationary distribution $\pi$ satisfies $\pi_{j} = 1 /\left(m_{j} g_{j}\right)$;

show that, if $f$ is a bounded function on $S$,

Find the transition probability matrix of the embedded Markov chain $\xi_{n}^{*}$. Use it to classify the states and find the absorption probabilities for each of the essential classes.

Find all stationary distributions of the process $\xi (t)$ and of the embedded Markov chain $\xi_{n}^{*}$. Do they coincide? Why?

Find the limiting distributions for the Markov process and for the Markov chain, if $\xi (0) = 2$.

Find the limiting distributions for the Markov process and for the Markov chain, if $\xi (0) = 3$.