Math Problems Vault

Problem 6.1

Let $\left(P_{ij}; i, j \geq 0\right)$ be the set of transition probabilities for a countable-state Markov chain. For each $i, j$ , let $\mathsf{F}_{ij}(n)$ be the probability that state $j$ occurs sometime between time 1 and $n$ inclusive, given $X_{0} = i$ . For some given $j$ , assume that $\left\{ x_{i}; i \geq 0\right\}$ is a set of non-negative numbers satisfying $x_{i} = P_{ij}+\sum_{k \neq j} P_{ik} x_{k}$ for all $i \geq 0$ . Show that $x_{i} \geq \mathsf{F}_{ij}(n)$ for all $n$ and $i$ , and hence that $x_{i} \geq \mathsf{F}_{ij}(\infty )$ for all $i$ .

?

Problem 6.2

(a)(b)

Consider the Markov chain shown below. {#fig-1 width="60%"}

?

(a)

For the Markov chain above, show that, for $p \geq 1/2$ , $\mathsf{F}_{00}(\infty ) = 2(1-p)$ and show that $\mathsf{F}_{i0}(\infty ) = [(1-p)/p]^{i}$ for $i \geq 1$ . Note that you have shown that the chain is transient for $p > 1/2$ and that it is recurrent for $p = 1/2$ .

(b)

Under the same conditions as (a), show that $\mathsf{F}_{ij}(\infty )$ equals $2(1-p)$ for $j = i$ , equals $[(1-p)/p]^{i-j}$ for $i > j$ , and equals 1 for $i < j$ .

Problem 6.3

(a)(b)(c)

?

(a)

Show that the $n$ th-order transition probabilities, starting in state 0, for the Markov chain in Exercise 6.2 satisfy

P_{0j}^{n} = p P_{0, j-1}^{n-1}+q P_{0, j+1}^{n-1} \quad j \neq 0; \qquad P_{00}^{n} = q P_{00}^{n-1}+q P_{01}^{n-1}.

(b)

For $p = 1/2$ , use this equation to calculate $P_{0j}^{n}$ iteratively for $n = 1, 2, 3, 4$ . Verify (6.3) for these values and then use induction to verify (6.3) in general. Note: This becomes an absolute mess for $p \neq 1/2$ , so do not attempt this in general.

(c)

As a more interesting approach, which brings out the relationship of the Markov chain in Exercise 6.2 and the Markov chain of Figure 6.1 (a Markov chain with a countable-state space modeling a Bernoulli process; state space the integers, with transition probability $p$ from state $i$ to $i+1$ and $q = 1-p$ from state $i$ to $i-1$ , for all $i$ ), note that (6.3), with $j+n$ even, is the probability that $S_{n} = j$ for the chain in Figure 6.1 and (6.3) with $j+n$ odd is the probability that $S_{n} = -j-1$ for the chain in Figure 6.1. By viewing each transition over the self loop at state 0 as a sign reversal for the chain in Figure 6.1, explain why this surprising result is true. (Again, this does not work for $p \neq 1/2$ , since the sign reversals also reverse the $+1, -1$ transitions.)

Problem 6.4

Let $j$ be a transient state in a Markov chain and let $j$ be accessible from $i$ . Show that $i$ is transient also. Interpret this as a form of Murphy's law (if something bad can happen, it will, where the bad thing is the lack of an eventual return).

?

Problem 6.5

This exercise treats a mathematical detail from the proof of Lemma 6.2.4. Assume that $j$ is recurrent, there is a path of probability $\alpha > 0$ from $j$ to $i$ , and $n \geq 1$ is an integer. Let $T_{ji}$ be the possibly defective rv giving the first-passage time from $j$ to $i$ . Verify the following equations for any integer $t > 0$ :

\begin{aligned} \mathbb {P}\left(T_{ji} > t\right) & = \mathbb {P}\left(T_{ji} > t, T_{jj}^{(n)} > t\right)+\mathbb {P}\left(T_{ji} > t, T_{jj}^{(n)} \leq t\right) \\ & \leq \mathbb {P}\left(T_{jj}^{(n)} > t\right)+\mathbb {P}\left(T_{ji} > T_{jj}^{(n)}\right) \\ & \leq \mathbb {P}\left(T_{jj}^{(n)} > t\right)+(1-\alpha )^{n}; \\ \mathbb {P}\left(T_{ji} > \infty \right) & \leq (1-\alpha )^{n}. \end{aligned}

?

Problem 6.6

(a)(b)(c)

Assume that state $j$ in a countable-state Markov chain is recurrent and $i$ communicates with $j$ . More specifically, assume that there is a path of length $m$ from $i$ to $j$ and one of length $k$ from $j$ to $i$ .

?

(a)

Show that for any $n > 0$ ,

P_{ii}^{m+n+k} \geq P_{ij}^{m} P_{jj}^{n} P_{ji}^{k}.

(b)

By summing over $n$ , show that state $i$ is also recurrent.

(c)

Explain why this shows that all states in a class are recurrent or all are transient.

Problem 6.7

(a)(b)(c)(d)

Consider an irreducible Markov chain that is positive recurrent. Recall the technique used to find the expected first-passage time from $j$ to $i$ , i.e., $\overline{T}_{ji}$ , in Section 4.5: state $i$ was turned into a trapping state by turning all the transitions out of $i$ into a single transition $P_{ii} = 1$ . Here, in order to preserve the positive recurrence, we instead move all transitions out of state $i$ into the single transition $P_{ij} = 1$ .

?

(a)

Use the Markov chain of Exercise 6.2 to illustrate that the above strategy can turn an irreducible chain into a reducible chain. Also explain why states $i$ and $j$ are still positive recurrent and still in the same class.

(b)

Let $\left\{ \pi_{k}'; k \geq 0\right\}$ be the steady-state probabilities for the positive-recurrent class in the modified Markov chain. Show that the expected first passage time $\overline{T}_{ji}'$ from $j$ to $i$ in the modified Markov chain is $(1/\pi_{i}')-1$ .

(c)

Show that the expected first passage time from $j$ to $i$ is the same in the modified and unmodified chains.

(d)

Show by example that after the modification above, two states $i$ and $j$ that were not positive recurrent before the modification can become positive recurrent and the above technique can again be used to find the expected first-passage time.

Problem 6.8

(a)(b)

Let $\left\{ X_{n}; n \geq 0\right\}$ be a branching process with $X_{0} = 1$ . Let $\overline{Y}$ and $\sigma^{2}$ be the mean and variance respectively of the number of offspring of an individual.

?

(a)

Argue that $\lim_{n \rightarrow \infty } X_{n}$ exists WP1 and either has the value 0 (with probability $\mathsf{F}_{10}(\infty )$ ) or the value $\infty$ (with probability $1-\mathsf{F}_{10}(\infty )$ ).

(b)

Show that $\operatorname {Var}\left[X_{n}\right] = \sigma^{2} \overline{Y}^{n-1}(\overline{Y}^{n}-1)/(\overline{Y}-1)$ for $\overline{Y} \neq 1$ and $\operatorname {Var}\left[X_{n}\right] = n \sigma^{2}$ for $\overline{Y} = 1$ .

Problem 6.9

There are $n$ states and for each pair of states $i$ and $j$ , a positive number $d_{ij} = d_{ji}$ is given. A particle moves from state to state in the following manner. Given that the particle is in any state $i$ , it will next move to any $j \neq i$ with probability $P_{ij}$ given by

P_{ij} = \frac{d_{ij}}{\sum _{j \neq i} d_{ij}}.

Assume that $P_{ii} = 0$ for all $i$ . Show that the sequence of positions is a reversible Markov chain and find the limiting probabilities.

?

Problem 6.10

Consider a reversible Markov chain with transition probabilities $P_{ij}$ and limiting probabilities $\pi_{i}$ . Also consider the same chain truncated to the states $0, 1, \ldots , M$ . That is, the transition probabilities $\left\{ P_{ij}'\right\}$ of the truncated chain are

P_{ij}' = \begin{cases} \dfrac {P_{ij}}{\sum _{k=0}^{m} P_{ik}}, & 0 \leq i, j \leq M, \\ ]1ex] 0, & \text{elsewhere.} \end{cases} \[ Show that the truncated chain is also reversible and has limiting probabilities given by \] \overline{\pi }_{i} = \frac{\pi _{i} \sum _{j=0}^{M} P_{ij}}{\sum _{k=0}^{M}\left(\pi _{k} \sum _{m=0}^{M} P_{km}\right)}. \[ \]

?

Problem 6.11

(a)(b)

A Markov chain (with states $\left\{ 0, 1, 2, \ldots , J-1\right\}$ , where $J$ is either finite or infinite) has transition probabilities $\left\{ P_{ij}; i, j \geq 0\right\}$ . Assume that $P_{0j} > 0$ for all $j > 0$ and $P_{j0} > 0$ for all $j > 0$ . Also assume that for all $i, j, k$ , we have $P_{ij} P_{jk} P_{ki} = P_{ik} P_{kj} P_{ji}$ .

?

(a)

Assuming also that all states are positive recurrent, show that the chain is reversible and find the steady-state probabilities $\left\{ \pi_{i}\right\}$ in simplest form.

(b)

Find a condition on $\left\{ P_{0j}; j \geq 0\right\}$ and $\left\{ P_{j0}; j \geq 0\right\}$ that is sufficient to ensure that all states are positive recurrent.

Problem 6.12

(a)(b)(c)

?

(a)

Use the birth and death model described in Figure 6.4 (a birth--death Markov chain: state space the non-negative integers, transition probability $p_{i}$ from state $i$ to $i+1$ , $q_{i}$ from state $i$ to $i-1$ , and $1-p_{i}-q_{i}$ a self-transition) to find the steady-state PMF for the number of customers in the system (queue plus service facility) for the following queues:

M/M/1 with arrival probability $\lambda \delta$ , service completion probability $\mu \delta$ ;
M/M/m with arrival probability $\lambda \delta$ , service completion probability $i \mu \delta$ for $i$ servers busy, $1 \leq i \leq m$ ;
M/M/ $\infty$ with arrival probability $\lambda \delta$ , service probability $i \mu \delta$ for $i$ servers. Assume $\delta$ so small that $i \mu \delta < 1$ for all $i$ of interest. Assume the system is positive recurrent.

(b)

For each of the queues above give necessary conditions (if any) for the states in the chain to be (i) transient, (ii) null recurrent, (iii) positive recurrent.

(c)

For each of the queues find:

$L =$ (steady-state) mean number of customers in the system;
$L^{q} =$ (steady-state) mean number of customers in the queue;
$W =$ (steady-state) mean waiting time in the system;
$W^{q} =$ (steady-state) mean waiting time in the queue.

Problem 6.13

(a)(b)(c)

?

(a)

Given that an arrival occurs in the interval $(n \delta , (n+1) \delta )$ for the sampled-time M/M/1 model in Figure 6.5, find the conditional PMF of the state of the system at time $n \delta$ (assume $n$ is arbitrarily large and assume positive recurrence).

(b)

For the same model, again in steady state but not conditioned on an arrival in $(n \delta , (n+1) \delta )$ , find the probability $Q(i, j)$ ( $i \geq j > 0$ ) that the system is in state $i$ at $n \delta$ and that $i-j$ departures occur before the next arrival.

(c)

Find the expected number of customers seen in the system by the first arrival after time $n \delta$ .

Problem 6.14

Find the backward transition probabilities for the Markov chain model of age in Figure 6.3. Draw the graph for the backward Markov chain, and interpret it as a model for residual life.

?

Problem 6.15

Consider the sampled-time approximation to the M/M/1 queue in Figure 6.5.

In (b)--(g) do not use reversibility and do not use Burke's theorem. Let $X_{n}$ be the state of the system at time $n \delta$ and let $D_{n}$ be a rv taking on the value 1 if a departure occurs between $n \delta$ and $(n+1) \delta$ , and the value 0 if no departure occurs. Assume that the system is in steady state at time $n \delta$ .

?

(a)

Give the steady-state probabilities for this chain (no explanations or calculations required -- just the answer).

(b)

Find $\mathbb {P}\left(X_{n} = i, D_{n} = j\right)$ for $i \geq 0, j = 0, 1$ .

(c)

Find $\mathbb {P}\left(D_{n} = 1\right)$ .

(d)

Find $\mathbb {P}\left(X_{n} = i \mid D_{n} = 1\right)$ for $i \geq 0$ .

(e)

Find $\mathbb {P}\left(X_{n+1} = i \mid D_{n} = 1\right)$ and show that $X_{n+1}$ is statistically independent of $D_{n}$ .

(f)

Find $\mathbb {P}\left(X_{n+1} = i, D_{n+1} = j \mid D_{n}\right)$ and show that the pair of variables $(X_{n+1}, D_{n+1})$ is statistically independent of $D_{n}$ .

(g)

For each $k > 1$ , find $\mathbb {P}\left(X_{n+k} = i, D_{n+k} = j \mid D_{n+k-1}, D_{n+k-2}, \ldots , D_{n}\right)$ and show that the pair $(X_{n+k}, D_{n+k})$ is statistically independent of $(D_{n+k-1}, D_{n+k-2}, \ldots , D_{n})$ .

(h)

What do your results mean relative to Burke's theorem.

Problem 6.16

(a)(b)(c)

Let $\left\{ X_{n}, n \geq 1\right\}$ denote a positive recurrent Markov chain having a countable-state space. Now consider a new stochastic process $\left\{ Y_{n}, n \geq 0\right\}$ that only accepts values of the Markov chain that are between 0 and some integer $m$ . For instance, if $m = 3$ and $X_{1} = 1, X_{2} = 3, X_{3} = 5, X_{4} = 6, X_{5} = 2$ , then $Y_{1} = 1, Y_{2} = 3, Y_{3} = 2$ .

?

(a)

Is $\left\{ Y_{n}, n \geq 0\right\}$ a Markov chain? Explain briefly.

(b)

Let $p_{j}$ denote the proportion of time that $\left\{ X_{n}, n \geq 1\right\}$ is in state $j$ . If $p_{j} > 0$ for all $j$ , what proportion of time is $\left\{ Y_{n}, n \geq 0\right\}$ in each of the states $0, 1, \ldots , m$ ?

(c)

Suppose $\left\{ X_{n}\right\}$ is null recurrent and let $p_{i}(m), i = 0, 1, \ldots , m$ denote the long-run proportions for $\left\{ Y_{n}, n \geq 0\right\}$ . Show that for $j \neq i$ , $p_{j}(m) = p_{i}(m) \mathbb {E}\left[\text{time the }X\text{ process spends in }j\text{ between returns to }i\right]$ .

Problem 6.17

This exercise concerns the round-robin queueing system of Section 6.8. There, a state is denoted $\mathbf{m} = (m, z_{1}, \ldots , z_{m})$ , where $m$ is the number of customers in the system and $z_{i}$ , $1 \leq i \leq m$ , is the amount of service already received by the customer in position $i$ of the queue (position 1 being served, the others waiting); $\phi$ denotes the empty state. Customers arrive as a Bernoulli process of rate $\lambda$ per increment, each requiring an integer number of service increments with PMF $f(w)$ and complementary CDF $\overline{F}(w)$ ; the customer being served receives one increment of service per unit time and, if not yet finished, rotates to the back of the queue (a round-robin service discipline). A backward Markov chain for this system is hypothesized, with backward transition probabilities guessed so as to satisfy the balance equations for: a rotation transition (labeled (6.56)), a departure transition (labeled (6.57)), an arrival transition (labeled (6.58)), and the transitions to/from the empty state $\phi$ (labeled (6.59)). Substituting the guessed backward probabilities into these equations and solving yields the hypothesized steady-state probability

\pi _{\mathbf{s}} = \left(\frac{\lambda }{1-\lambda }\right)^{m}\left(\prod _{j=1}^{m} \overline{F}(z_{j})\right) \pi _{\phi }, \tag {6.62}

where the state $\mathbf{s}$ is $\mathbf{s} = (m, z_{1}, \ldots , z_{m})$ and time has been normalized so that $\delta = 1$ is the unit service time. Verify that (6.58) is satisfied by the hypothesized solution to $\pi$ in (6.62). Also show that the equations involving the idle state $\phi$ are satisfied.

?

Problem 6.18

(a)(b)(c)(d)

Replace the state $\mathbf{m} = (m, z_{1}, \ldots , z_{m})$ in Section 6.8 with an expanded state $\mathbf{m} = (m, z_{1}, w_{1}, z_{2}, w_{2}, \ldots , z_{m}, w_{m})$ , where $m$ and $\left\{ z_{i}; 1 \leq i \leq m\right\}$ are as before and $w_{1}, w_{2}, \ldots , w_{m}$ are the original service requirements of the $m$ customers.

?

(a)

Hypothesizing the same backward round-robin system as hypothesized in Section 6.8, find the backward transition probabilities and give the corresponding equations to (6.56)--(6.59) for the expanded state description.

(b)

Solve the resulting equations to show that

\pi _{\mathbf{m}} = \pi _{\phi }\left(\frac{\lambda \delta }{1-\lambda \delta }\right)^{m} \prod _{j=1}^{m} f(w_{j}).

(c)

Show that the probability that there are $m$ customers in the system, and that those customers have original service requirements given by $w_{1}, \ldots , w_{m}$ , is

\mathbb {P}\left(m, w_{1}, \ldots , w_{m}\right) = \pi _{\phi }\left(\frac{\lambda \delta }{1-\lambda \delta }\right)^{m} \prod _{j=1}^{m}(w_{j}-1) f(w_{j}).

(d)

Given that a customer has original service requirement $w$ , find the expected time that the customer spends in the system.