Math Problems Vault

Problem 7.1

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

Consider an M/M/1 queue as represented in Figure 7.4. Assume throughout that $X_{0} = i$ , where $i > 0$ . The purpose of this exercise is to understand the relationship between the holding interval until the next state transition and the interval until the next arrival to the M/M/1 queue. Your explanations in the following parts can and should be very brief.

?

(a)

Explain why the expected holding interval $\mathbb {E}\left[U_{1} \mid X_{0} = i\right]$ until the next state transition is $1/(\lambda +\mu )$ .

(b)

Explain why the expected holding interval $U_{1}$ , conditional on $X_{0} = i$ and $X_{1} = i+1$ , is

\mathbb {E}\left[U_{1} \mid X_{0} = i, X_{1} = i+1\right] = 1/(\lambda +\mu ).

Show that $\mathbb {E}\left[U_{1} \mid X_{0} = i, X_{1} = i-1\right]$ is the same.

(c)

Let $V$ be the time of the first arrival after time $0$ (this may occur either before or after the time $W$ of the first departure). Show that

\mathbb {E}\left[V \mid X_{0} = i, X_{1} = i+1\right] = \frac{1}{\lambda +\mu },

\mathbb {E}\left[V \mid X_{0} = i, X_{1} = i-1\right] = \frac{1}{\lambda +\mu }+\frac{1}{\lambda }.

(d)

Use your solution to (c) plus the probability of moving up or down in the Markov chain to show that $\mathbb {E}\left[V\right] = 1/\lambda$ . Note: You already know that $\mathbb {E}\left[V\right] = 1/\lambda$ . The purpose here is to show that your solution to (c) is consistent with that fact.

Remark.

?

In part (c), use the memorylessness of the exponential rv and the fact that $V$ under the condition $X_{1} = i-1$ is the time to the first departure plus the remaining time to an arrival.

Problem 7.2

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

Consider a Markov process for which the embedded Markov chain is a birth--death chain with transition probabilities $P_{i,i+1} = 2/5$ for all $i \geq 0$ , $P_{i,i-1} = 3/5$ for all $i \geq 1$ , $P_{01} = 1$ , and $P_{ij} = 0$ otherwise.

?

(a)

Find the steady-state probabilities $\left\{ \pi_{i}; i \geq 0\right\}$ for the embedded chain.

(b)

Assume that the transition rate $\nu_{i}$ out of state $i$ , for $i \geq 0$ , is given by $\nu_{i} = 2^{i}$ . Find the transition rates $\left\{ q_{ij}\right\}$ between states and find the steady-state probabilities $\left\{ p_{i}\right\}$ for the Markov process. Explain heuristically why $\pi_{i} \neq p_{i}$ .

(c)

Explain why there is no sampled-time approximation for this process. Then truncate the embedded chain to states $0$ to $m$ and find the steady-state probabilities for the sampled-time approximation to the truncated process.

(d)

Show that as $m \rightarrow \infty$ , the steady-state probabilities for the sequence of sampled-time approximations approach the probabilities $p_{i}$ in (b).

Problem 7.3

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

Consider a Markov process for which the embedded Markov chain is a birth--death chain with transition probabilities $P_{i,i+1} = 2/5$ for all $i \geq 1$ , $P_{i,i-1} = 3/5$ for all $i \geq 1$ , $P_{01} = 1$ , and $P_{ij} = 0$ otherwise.

?

(a)

Find the steady-state probabilities $\left\{ \pi_{i}; i \geq 0\right\}$ for the embedded chain.

(b)

Assume that the transition rate out of state $i$ , for $i \geq 0$ , is given by $\nu_{i} = 2^{-i}$ . Find the transition rates $\left\{ q_{ij}\right\}$ between states and show that there is no probability vector solution $\left\{ p_{i}; i \geq 0\right\}$ to the steady-state process equations $p_{j}\nu_{j} = \sum_{i}p_{i}q_{ij}$ for all $j \geq 0$ with $\sum_{i}p_{i} = 1$ .

(c)

Argue that the expected time between visits to any given state $i$ is infinite. Find the expected number of transitions between visits to any given state $i$ . Argue that, starting from any state $i$ , an eventual return to state $i$ occurs with probability $1$ .

(d)

Consider the sampled-time approximation of this process with $\delta = 1$ . Draw the graph of the resulting Markov chain and argue why it must be null recurrent.

Problem 7.4

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

Consider the Markov process for the M/M/1 queue, as given in Figure 7.4.

?

(a)

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.

(b)

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}$ .

(c)

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

(d)

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

Problem 7.5

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

Consider the Markov process illustrated below. The transitions are labeled by the rate $q_{ij}$ at which those transitions occur. The process can be viewed as a single-server queue where arrivals become increasingly discouraged as the queue lengthens. The word time average below refers to the limiting time average over each sample path of the process, except for a set of sample paths of probability $0$ . {#fig-1 width="70%"}

?

(a)

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}$ .

(b)

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.

(c)

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$ .

(d)

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

Remark.

?

Hint for (a): First find an equation relating $p_{i}$ to $p_{i+1}$ for each $i$ . It also may help to recall the power series expansion of $e^{x}$ .

Problem 7.6

?

(a)

Let $U_{n}$ be the $n$ th holding interval for a Markov process starting in steady state, with $\mathbb {P}\left\{ X_{0} = i\right\} = \pi_{i}$ . Show that $\mathbb {E}\left[U_{n}\right] = \sum_{k}\pi_{k}/\nu_{k}$ for each integer $n$ .

(b)

Let $S_{n}$ be the epoch of the $n$ th transition. Show that $\mathbb {P}\left\{ S_{n} \geq n\beta \right\} \leq (\sum_{k}\pi_{k}/\nu_{k})/\beta$ for all $\beta > 0$ .

(c)

Let $M(t)$ be the number of transitions of the Markov process up to time $t$ , given that $X_{0}$ is in steady state. Show that $\mathbb {P}\left\{ M(n\beta ) \geq n\right\} \geq 1-(\sum_{k}\pi_{k}/\nu_{k})/\beta$ .

(d)

Show that if $\sum_{k}\pi_{k}/\nu_{k}$ is finite, then $\lim_{t \rightarrow \infty }M(t)/t = 0$ WP1 is impossible. (Note that this is equivalent to showing that $\lim_{t \rightarrow \infty }M(t)/t = 0$ WP1 implies $\sum_{k}\pi_{k}/\nu_{k} = \infty$ .)

(e)

Let $M_{i}(t)$ be the number of transitions by time $t$ starting in state $i$ . Show that if $\sum_{k}\pi_{k}/\nu_{k}$ is finite, then $\lim_{t \rightarrow \infty }M_{i}(t)/t = 0$ WP1 is impossible.

Problem 7.7

(a)(b)

?

(a)

Consider the process in the figure below. The process starts at $X(0) = 1$ , and for all $i \geq 1$ , $P_{i,i+1} = 1$ and $\nu_{i} = i^{2}$ for all $i$ . Let $S_{n}$ be the epoch when the $n$ th transition occurs. Show that

\mathbb {E}\left[S_{n}\right] = \sum _{i=1}^{n}i^{-2} < 2 \qquad \text{for all } n.

{#fig-1 width="60%"}

(b)

Use the Markov inequality to show that $\mathbb {P}\left\{ S_{n} > 4\right\} \leq 1/2$ for all $n$ . Show that the probability of an infinite number of transitions by time $4$ is at least $1/2$ .

Remark.

?

Hint for (a): Upper bound the sum from $i = 2$ by integrating $x^{-2}$ from $x = 1$ .

Problem 7.8

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

?

(a)

Consider a Markov process with the set of states $\left\{ 0, 1, \ldots \right\}$ in which the transition rates $\left\{ q_{ij}\right\}$ between states are given by $q_{i,i+1} = (3/5)2^{i}$ for $i \geq 0$ , $q_{i,i-1} = (2/5)2^{i}$ for $i \geq 1$ , and $q_{ij} = 0$ otherwise. Find the transition rate $\nu_{i}$ out of state $i$ for each $i \geq 0$ and find the transition probabilities $\left\{ P_{ij}\right\}$ for the embedded Markov chain.

(b)

Find a solution $\left\{ p_{i}; i \geq 0\right\}$ with $\sum_{i}p_{i} = 1$ to the steady-state process equations (7.23).

(c)

Show that all states of the embedded Markov chain are transient.

(d)

Explain in your own words why your solution to (b) is not in any sense a set of steady-state probabilities.

Problem 7.9

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

Let $q_{i,i+1} = 2^{i-1}$ for all $i \geq 0$ and let $q_{i,i-1} = 2^{i-1}$ for all $i \geq 1$ . All other transition rates are $0$ .

?

(a)

Solve the steady-state equations and show that $p_{i} = 2^{-i-1}$ for all $i \geq 0$ .

(b)

Find the transition probabilities for the embedded Markov chain and show that the chain is null recurrent.

(c)

For any state $i$ , consider the renewal process for which the Markov process starts in state $i$ and renewals occur on each transition to state $i$ . Show that, for each $i \geq 1$ , the expected inter-renewal interval is equal to $2$ .

(d)

Show that the expected number of transitions between each entry into state $i$ is infinite. Explain why this does not mean that an infinite number of transitions can occur in a finite time.

Remark.

?

Hint for (c): Use renewal-reward theory.

Problem 7.10

(a)(b)

?

(a)

Consider the two-state Markov process of Example 7.3.1 with $q_{01} = \lambda$ and $q_{10} = \mu$ . Find the eigenvalues and eigenvectors of the transition rate matrix $\mathbf{Q}$ .

(b)

If $\mathbf{Q}$ has $\mathsf{M}$ distinct eigenvalues, the differential equation $d[P(t)]/dt = [Q][P(t)]$ can be solved by the equation

[P(t)] = \sum _{i=1}^{\mathsf{M}}\overrightarrow {\nu }_{i}e^{t\lambda _{i}}\overrightarrow {p}_{i}^{\mathsf{T}},

where $\overrightarrow {p}_{i}$ and $\overrightarrow {\nu }_{i}$ are the left and right eigenvectors of eigenvalue $\lambda_{i}$ . Show that this equation gives the same solution as that given for Example 7.3.1.

Problem 7.11

Consider the three-state Markov process below; the number given on edge $(i,j)$ is $q_{ij}$ , the transition rate from $i$ to $j$ . Assume that the process is in steady state. {#fig-1 width="45%"}

?

(a)

Is this process reversible?

(b)

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

(c)

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

(d)

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

(e)

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$ .

(f)

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

(g)

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.

Problem 7.12

(a)(b)(c)

?

(a)

Consider an M/M/1 queueing system with arrival rate $\lambda$ , service rate $\mu$ , $\mu > \lambda$ . Assume that the queue is in steady state. Given that an arrival occurs at time $t$ , find the probability that the system is in state $i$ immediately after time $t$ .

(b)

Assuming FCFS service, and conditional on $i$ customers in the system immediately after the above arrival, characterize the time until the above customer departs as a sum of rv's.

(c)

Find the unconditional probability density of the time until the above customer departs.

Remark.

?

Hint for (c): You know (from splitting a Poisson process) that the sum of a geometrically distributed number of IID exponentially distributed rv's is exponentially distributed. Use the same idea here.

Problem 7.13

(a)(b)(c)

?

(a)

Consider an M/M/1 queue in steady state. Assume $\rho = \lambda /\mu < 1$ . Find the probability $Q(i,j)$ for $i \geq j > 0$ that the system is in state $i$ at time $t$ and that $i-j$ departures occur before the next arrival.

(b)

Find the PMF of the state immediately before the first arrival after time $t$ .

(c)

There is a well-known queueing principle called PASTA, standing for `Poisson arrivals see time averages'. Given your results above, give a more precise statement of what that principle means in the case of the M/M/1 queue.

Problem 7.14

(a)(b)(c)

A small bookie shop has room for at most two customers. Potential customers arrive at a Poisson rate of ten customers per hour; they enter if there is room and are turned away, never to return, otherwise. The bookie serves the admitted customers in order, requiring an exponentially distributed time of mean $4$ minutes per customer.

?

(a)

Find the steady-state distribution of the number of customers in the shop.

(b)

Find the rate at which potential customers are turned away.

(c)

Suppose the bookie hires an assistant; the bookie and assistant, working together, now serve each customer in an exponentially distributed time of mean $2$ minutes, but there is only room for one customer (i.e., the customer being served) in the shop. Find the new rate at which customers are turned away.

Problem 7.15

This exercise explores a continuous time version of a simple branching process.

Consider a population of primitive organisms which do nothing but procreate and die. In particular, the population starts at time $0$ with one organism. This organism has an exponentially distributed lifespan $T_{0}$ with rate $\mu$ (i.e., $\mathbb {P}\left\{ T_{0} \geq \tau \right\} = e^{-\mu \tau }$ ). While this organism is alive, it gives birth to new organisms according to a Poisson process of rate $\lambda$ . Each of these new organisms, while alive, gives birth to yet other organisms. The lifespan and birthrate for each of these new organisms are IID to those of the first organism. All these and subsequent organisms give birth and die in the same way, again independently of all other organisms.

?

(a)

Let $X(t)$ be the number of (live) organisms in the population at time $t$ . Show that $\left\{ X(t); t \geq 0\right\}$ is a Markov process and specify the transition rates between the states.

(b)

Find the embedded Markov chain $\left\{ X_{n}; n \geq 0\right\}$ corresponding to the Markov process in (a). Find the transition probabilities for this Markov chain.

(c)

Explain why the Markov process and Markov chain above are not irreducible.

(d)

For purposes of analysis, add an additional transition of rate $\lambda$ from state $0$ to state $1$ . Show that the Markov process and the embedded chain are irreducible. Find the values of $\lambda$ and $\mu$ for which the modified chain is positive recurrent, null recurrent, and transient.

(e)

Assume that $\lambda < \mu$ . Find the steady-state process probabilities for the modified Markov process.

(f)

Find the mean recurrence time between visits to state $0$ for the modified Markov process.

(g)

Find the mean time $\overline{T}$ for the population in the original Markov process to die out.

Remark.

?

Note for (c): The majority of results you have seen for Markov processes assume the process is irreducible, so be careful not to use those results in this exercise.

Note for (g): We have seen before that removing transitions from a Markov chain or process to create a trapping state can make it easier to find mean recurrence times. This is an example of the opposite, where adding an exit from a trapping state makes it easy to find the recurrence time.

Problem 7.16

Consider the job sharing computer system illustrated below. Incoming jobs arrive from the left in a Poisson stream. Each job, independently of other jobs, requires preprocessing in system 1 with probability $Q$ . Jobs in system 1 are served FCFS and the service times for successive jobs entering system 1 are IID with an exponential distribution of mean $1/\mu_{1}$ . The jobs entering system 2 are also served FCFS and successive service times are IID with an exponential distribution of mean $1/\mu_{2}$ . The service times in the two systems are independent of each other and of the arrival times. Assume that $\mu_{1} > \lambda Q$ and that $\mu_{2} > \lambda$ . Assume that the combined system is in steady state. {#fig-1 width="65%"}

?

(a)

Is the input to system 1 Poisson? Explain.

(b)

Are each of the two input processes coming into system 2 Poisson? Explain.

(c)

Give the joint steady-state PMF of the number of jobs in the two systems. Explain briefly.

(d)

What is the probability that the first job to leave system 1 after time $t$ is the same as the first job that entered the entire system after time $t$ ?

(e)

What is the probability that the first job to leave system 2 after time $t$ both passed through system 1 and arrived at system 1 after time $t$ ?

Problem 7.17

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

Consider the following combined queueing system. The first queue system is M/M/1 with service rate $\mu_{1}$ . The second queue system has IID exponentially distributed service times with rate $\mu_{2}$ . Each departure from system 1 leaves the entire system with probability $1-Q_{1}$ and enters system 2 with the remaining probability $Q_{1}$ . System 2 has an additional Poisson input of rate $\lambda_{2}$ , independent of inputs and outputs from the first system. Each departure from the second system independently leaves the combined system with probability $Q_{2}$ and reenters system 2 with probability $1-Q_{2}$ . For (a), (b), (c) assume that $Q_{2} = 1$ (i.e., there is no feedback). {#fig-1 width="65%"}

?

(a)

Characterize the process of departures from system 1 that enter system 2 and characterize the overall process of arrivals to system 2.

(b)

Assuming FCFS service in each system, find the steady-state distribution of time that a customer spends in each system.

(c)

For a customer that goes through both systems, show why the time in each system is independent of that in the other; find the distribution of the combined system time for such a customer.

(d)

Now assume that $Q_{2} < 1$ . Is the departure process from the combined system Poisson? Which of the three input processes to system 2 are Poisson? Which of the input processes are independent? Explain your reasoning, but do not attempt formal proofs.

Problem 7.18

Suppose a Markov chain with transition probabilities $\left\{ P_{ij}\right\}$ is reversible. Suppose we change the transition probabilities out of state $0$ from $\left\{ P_{0j}; j \geq 0\right\}$ to $\left\{ P_{0j}'; j \geq 0\right\}$ . Assuming that all $P_{ij}$ for $i \neq 0$ are unchanged, what is the most general way in which we can choose $\left\{ P_{0j}'; j \geq 0\right\}$ so as to maintain reversibility? Your answer should be explicit about how the steady-state probabilities $\left\{ \pi_{i}; i \geq 0\right\}$ are changed. Your answer should also indicate what this problem has to do with uniformization of reversible Markov processes, if anything.

?

Remark.

?

Hint: Given $P_{ij}$ for all $i, j$ , a single additional parameter will suffice to specify $P_{0j}'$ for all $j$ .

Problem 7.19

Consider the closed queueing network in the figure below. There are three customers who are doomed forever to cycle between node $1$ and node $2$ . Both nodes use FCFS service and have exponential IID service times. The service times at one node are also independent of those at the other node and are independent of the customer being served. The server at node $i$ has mean service time $1/\mu_{i}$ , $i = 1, 2$ . Assume to be specific that $\mu_{2} < \mu_{1}$ . {#fig-1 width="40%"}

?

(a)

The system can be represented by a four-state Markov process. Draw its graphical representation and label it with the individual states and the transition rates between them.

(b)

Find the steady-state probability of each state.

(c)

Find the time-average rate at which customers leave node $1$ .

(d)

Find the time-average rate at which a given customer cycles through the system.

(e)

Is the Markov process reversible? Suppose that the backward Markov process is interpreted as a closed queueing network. What does a departure from node $1$ in the forward process correspond to in the backward process? Can the transitions of a single customer in the forward process be associated with transitions of a single customer in the backward process?

Problem 7.20

Consider an M/G/1 queueing system with last come, first served (LCFS) preemptive resume service. That is, customers arrive according to a Poisson process of rate $\lambda$ . A newly arriving customer interrupts the customer in service and enters service itself. When a customer is finished, it leaves the system and the customer that had been interrupted by the departing customer resumes service from where it had left off. For example, if customer $1$ arrives at time $0$ and requires $2$ units of service, and customer $2$ arrives at time $1$ and requires $1$ unit of service, then customer $1$ is served from time $0$ to $1$ ; customer $2$ is served from time $1$ to $2$ and leaves the system, and then customer $1$ completes service from time $2$ to $3$ . Let $X_{i}$ be the service time required by the $i$ th customer; the $X_{i}$ are IID rv's with expected value $\mathbb {E}\left[X\right]$ ; they are independent of customer arrival times. Assume $\lambda \mathbb {E}\left[X\right] < 1$ .

?

(a)

Find the mean time between busy periods (i.e., the time until a new arrival occurs after the system becomes empty).

(b)

Find the time-average fraction of time that the system is busy.

(c)

Find the mean duration, $\mathbb {E}\left[B\right]$ , of a busy period.

(d)

Explain briefly why the customer that starts a busy period remains in the system for the entire busy period; use this to find the expected system time of a customer given that that customer arrives when the system is empty.

(e)

Is there any statistical dependence between the system time of a given customer (i.e., the time from the customer's arrival until departure) and the number of customers in the system when the given customer arrives?

(f)

Show that a customer's expected system time is equal to $\mathbb {E}\left[B\right]$ .

(g)

Let $C$ be the expected system time of a customer conditional on the service time $X$ of that customer being $1$ . Find (in terms of $C$ ) the expected system time of a customer conditional on $X = 2$ . Repeat for arbitrary $X = x$ .

(h)

Find the constant $C$ .

Remark.

?

Hint for (c): Use (a) and (b).

Hint for (g): Compare a customer with $X = 2$ to two customers with $X = 1$ each.

Hint for (h): Use (f) and (g); do not do any tedious calculations.

Problem 7.21

Consider a queueing system with two classes of customers, type $A$ and type $B$ . Type $A$ customers arrive according to a Poisson process of rate $\lambda_{A}$ and customers of type $B$ arrive according to an independent Poisson process of rate $\lambda_{B}$ . The queue has a FCFS server with exponential IID service times of rate $\mu > \lambda_{A}+\lambda_{B}$ . Characterize the departure process of class $A$ customers; explain carefully.

?

Remark.

?

Hint: Consider the combined arrival process and be judicious about how to select between $A$ and $B$ types of customers.

Problem 7.22

Consider a preemptive resume LCFS queueing system with two classes of customers. Type $A$ customer arrivals are Poisson with rate $\lambda_{A}$ and Type $B$ customer arrivals are Poisson with rate $\lambda_{B}$ . The service time for type $A$ customers is exponential with rate $\mu_{A}$ and that for type $B$ is exponential with rate $\mu_{B}$ . Each service time is independent of all other service times and of all arrival epochs.

Define the `state' of the system at time $t$ by the string of customer types in the system at $t$ , in order of arrival. Thus state $AB$ means that the system contains two customers, one of type $A$ and the other of type $B$ ; the type $B$ customer arrived later, so is in service. The set of possible states arising from transitions out of $AB$ is as follows:

$ABA$ if another type $A$ arrives.

$ABB$ if another type $B$ arrives.

$A$ if the customer in service ( $B$ ) departs.

Note that whenever a customer completes service, the next most recently arrived resumes service, so the state changes by eliminating the final element in the string.

?

(a)

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.

(b)

Is this process reversible? Explain. Assume positive recurrence.

(c)

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

(d)

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}$ .

(e)

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}$ .

Remark.

?

Hint for (b): If there is a transition from one state $S$ to another state $S'$ , how is the number of transitions from $S$ to $S'$ related to the number from $S'$ to $S$ ?

Problem 7.23

(a)(b)

?

(a)

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$ .

(b)

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.

Problem 7.24

Consider a $k$ -node Jackson type network with the modification that each node $i$ has $s$ servers rather than one server. Each server at $i$ has an exponentially distributed service time with rate $\mu_{i}$ . The exogenous input rate to node $i$ is $\rho_{i} = \lambda_{0}Q_{0i}$ and each output from $i$ is switched to $j$ with probability $Q_{ij}$ and switched out of the system with probability $Q_{i0}$ (as in the text). Let $\lambda_{i}$ , $1 \leq i \leq k$ , be the solution, for given $\lambda_{0}$ , to

\lambda _{j} = \sum _{i=0}^{k}\lambda _{i}Q_{ij}, \qquad 1 \leq j \leq k,

and assume that $\lambda_{i} < s\mu_{i}$ ; $1 \leq i \leq k$ . Show that the steady-state probability of state $\overrightarrow {m}$ is

\mathbb {P}\left\{ \overrightarrow {m}\right\} = \prod _{i=1}^{k}p_{i}(m_{i}),

where $p_{i}(m_{i})$ is the probability of state $m_{i}$ in an $(M,M,s)$ queue.

?

Remark.

?

Hint: Simply extend the argument in the text to the multiple server case.

Problem 7.25

Suppose a Markov process with the set of states $A$ is reversible and has steady-state probabilities $p_{i}$ , $i \in A$ . Let $B$ be a subset of $A$ and assume that the process is changed by setting $q_{ij} = 0$ for all $i \in B, j \notin B$ . Assuming that the new process (starting in $B$ and remaining in $B$ ) is irreducible, show that the new process is reversible and find its steady-state probabilities.

?

Problem 7.26

(a)(b)(c)

Consider a queueing system with two classes of customers. Type $A$ customer arrivals are Poisson with rate $\lambda_{A}$ and type $B$ customer arrivals are Poisson with rate $\lambda_{B}$ . The service time for type $A$ customers is exponential with rate $\mu_{A}$ and that for type $B$ is exponential with rate $\mu_{B}$ . Each service time is independent of all other service times and of all arrival epochs.

?

(a)

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.

(b)

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.

(c)

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

Remark.

?

Hint for (a): Note that the type $A$ and type $B$ customers do not interact.

Hint for (b): Combine (a) with the result of Exercise 7.25.

Problem 7.27

(a)(b)

?

(a)

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$ .

(b)

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.

Problem 7.28

Consider a sampled-time M/D/m/m queueing system. The arrival process is Bernoulli with probability $\lambda \ll 1$ of arrival in each time unit. There are $m$ servers; each arrival enters a server if a server is not busy and otherwise the arrival is discarded. If an arrival enters a server, it keeps the server busy for $d$ units of time and then departs; $d$ is some integer constant and is the same for each server.

Let $n$ , $0 \leq n \leq m$ be the number of customers in service at a given time and let $x_{i}$ be the number of time units that the $i$ th of those $n$ customers (in order of arrival) has been in service. Thus the state of the system can be taken as $(n, \overrightarrow {x}) = (n, x_{1}, x_{2}, \ldots , x_{n})$ , where $0 \leq n \leq m$ and $1 \leq x_{1} < x_{2} < \cdots < x_{n} \leq d$ .

Let $A(n, \overrightarrow {x})$ denote the next state if the present state is $(n, \overrightarrow {x})$ and a new arrival enters service. That is,

A(n, \overrightarrow {x}) = (n+1, 1, x_{1}+1, x_{2}+1, \ldots , x_{n}+1) \qquad \text{for } n < m \text{ and } x_{n} < d,

A(n, \overrightarrow {x}) = (n, 1, x_{1}+1, x_{2}+1, \ldots , x_{n-1}+1) \qquad \text{for } n \leq m \text{ and } x_{n} = d.

That is, the new customer receives one unit of service by the next state time, and all the old customers receive one additional unit of service. If the oldest customer has received $d$ units of service, then it leaves the system by the next state time. Note that it is possible for a customer with $d$ units of service at the present time to leave the system and be replaced by an arrival at the present time (i.e., the second equation above with $n = m$ , $x_{n} = d$ ). Let $B(n, \overrightarrow {x})$ denote the next state if either no arrival occurs or if a new arrival is discarded:

B(n, \overrightarrow {x}) = (n, x_{1}+1, x_{2}+1, \ldots , x_{n}+1) \qquad \text{for } x_{n} < d,

B(n, \overrightarrow {x}) = (n-1, x_{1}+1, x_{2}+1, \ldots , x_{n-1}+1) \qquad \text{for } x_{n} = d.

?

(a)

Hypothesize that the backward chain for this system is also a sampled-time M/D/m/m queueing system, but that the state $(n, x_{1}, \ldots , x_{n})$ ( $0 \leq n \leq m$ , $1 \leq x_{1} < x_{2} < \cdots < x_{n} \leq d$ ) has a different interpretation: $n$ is the number of customers as before, but $x_{i}$ is now the remaining service required by customer $i$ . Explain how this hypothesis leads to the following steady-state equations:

\lambda \pi _{n,\overrightarrow {x}} = (1-\lambda )\pi _{A(n,\overrightarrow {x})}, \qquad n < m, x_{n} < d,

\lambda \pi _{n,\overrightarrow {x}} = \lambda \pi _{A(n,\overrightarrow {x})}, \qquad n \leq m, x_{n} = d,

(1-\lambda )\pi _{n,\overrightarrow {x}} = \lambda \pi _{B(n,\overrightarrow {x})}, \qquad n \leq m, x_{n} = d,

(1-\lambda )\pi _{n,\overrightarrow {x}} = (1-\lambda )\pi _{B(n,\overrightarrow {x})}, \qquad n \leq m, x_{n} < d.

(b)

Using this hypothesis, find $\pi_{n,\overrightarrow {x}}$ in terms of $\pi_{0}$ , where $\pi_{0}$ is the probability of an empty system.

(c)

Verify that the above hypothesis is correct.

(d)

Find an expression for $\pi_{0}$ .

(e)

Find an expression for the steady-state probability that an arriving customer is discarded.

Remark.

?

Hint for (b): Use the third and fourth steady-state equations above; your answer should depend on $n$ , but not $\overrightarrow {x}$ .

Problem 7.29

(a)(b)(c)

A taxi alternates between three locations. When it reaches location $1$ it is equally likely to go next to either location $2$ or $3$ . When it reaches location $2$ it will next go to $1$ with probability $1/3$ and to $3$ with probability $2/3$ . From location $3$ it always goes to $1$ . The mean time between locations $i$ and $j$ are $t_{12} = 20$ , $t_{13} = 30$ , $t_{23} = 30$ . Assume exponential service and assume $t_{ij} = t_{ji}$ .

?

(a)

Find the (limiting) probability that the taxi's most recent stop was at location $i$ , $i = 1, 2, 3$ .

(b)

What is the (limiting) probability that the taxi is heading for location $2$ ?

(c)

What fraction of time is the taxi traveling from location $2$ to location $3$ ?

Remark.

?

Note for (c): Upon arrival at a location the taxi immediately departs.

Problem 7.30

(a)(b)(c)

?

(a)

Assume that the Markov process in Exercise 7.5 is changed in the following way: whenever the process enters state $0$ , the time spent before leaving state $0$ is now a uniformly distributed rv, taking values from $0$ to $2/\lambda$ . All other transitions remain the same. For this new process, determine whether the successive epochs of entry to state $0$ form renewal epochs, whether the successive epochs of exit from state $0$ form renewal epochs, and whether the successive entries to any other given state $i$ form renewal epochs.

(b)

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

(c)

Is this modified process a Markov process in the sense that $\mathbb {P}\left\{ X(t) = i \mid X(\tau ) = j, X(s) = k\right\} = \mathbb {P}\left\{ X(t) = i \mid X(\tau ) = j\right\}$ for all $0 < s < \tau < t$ and all $i, j, k$ ? Explain.

Problem 7.31

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

Consider an M/G/1 queueing system with Poisson arrivals of rate $\lambda$ and expected service time $\mathbb {E}\left[X\right]$ . Let $\rho = \lambda \mathbb {E}\left[X\right]$ and assume $\rho < 1$ . Consider a semi-Markov process model of the M/G/1 queueing system in which transitions occur on departures from the queueing system and the state is the number of customers immediately following a departure.

?

(a)

Suppose a colleague has calculated the steady-state probabilities $\left\{ p_{i}\right\}$ of being in state $i$ for each $i \geq 0$ . For each $i \geq 0$ , find the steady-state probability $\pi$ of state $i$ in the embedded Markov chain. Give your solution as a function of $\rho$ , $\pi_{i}$ , and $p_{0}$ .

(b)

Calculate $p_{0}$ as a function of $\rho$ .

(c)

Find $\pi_{i}$ as a function of $\rho$ and $p_{i}$ .

(d)

Is $p_{i}$ the same as the steady-state probability that the queueing system contains $i$ customers at a given time? Explain carefully.

Problem 7.32

(a)(b)

Consider an M/G/1 queue in which the arrival rate is $\lambda$ and the service time distribution is uniform $(0, 2W)$ with $\lambda W < 1$ . Define a semi-Markov chain following the framework for the M/G/1 queue in Section 7.8.1.

?

(a)

Find $P_{0j}$ for $j \geq 0$ .

(b)

Find $P_{ij}$ for $i > 0$ ; $j \geq i-1$ .

Problem 7.33

Consider a semi-Markov process for which the embedded Markov chain is irreducible and positive recurrent. Assume that the distribution of inter-renewal intervals for one state $j$ is arithmetic with span $d$ . Show that the distribution of inter-renewal intervals for all states is arithmetic with the same span.

?