Hence, the conjectured reversed time equations imply that

Pn,m=(λ/μ1)n(λ/μ2)mP0,0

Using that ∑n∑mPn,m=1, gives

Pn,m=(λ/μ1)n(1-λ/μ1)(λ/μ2)m(1-λ/μ2)

As it is easy to check that all the conjectured reverse time Equations (6.33), (6.34), and (6.35) are satisfied for the preceding choice of Pn,m, it follows that they are the limiting probabilities. Hence, we have shown that in steady state the numbers of customers at the two servers are independent, with the number at server i distributed as the number in the system of an M/M/1 queue with Poisson arrival rate λ and exponential service rate μi,i=1,2. (See Example 6.14.)

Figure 6.2 Forward and Reverse Transitions

6.8 Uniformization

Consider a continuous-time Markov chain in which the mean time spent in a state is the same for all states. That is, suppose that vi=v, for all states i. In this case since the amount of time spent in each state during a visit is exponentially distributed with rate v, it follows that if we let N(t) denote the number of state transitions by time t, then {N(t),t⩾0} will be a Poisson process with rate v.

To compute the transition probabilities Pij(t), we can condition on N(t):

Pij(t)=P{X(t)=j∣X(0)=i}=∑n=0∞P{X(t)=j∣X(0)=i,N(t)=n}P{N(t)=n∣X(0)=i}=∑n=0∞P{X(t)=j∣X(0)=i,N(t)=n}e-vt(vt)nn!

Now, the fact that there have been n transitions by time t tells us something about the amount of time spent in each of the first n states visited, but since the distribution of time spent in each state is the same for all states, it follows that knowing that N(t)=n gives us no information about which states were visited. Hence,

P{X(t)=j∣X(0)=i,N(t)=n}=Pijn

where Pijn is just the n-stage transition probability associated with the discrete-time Markov chain with transition probabilities Pij; and so when vi≡v

Pij(t)=∑n=0∞Pijne-vt(vt)nn! (6.36)

(6.36)

Equation (6.36) is often useful from a computational point of view since it enables us to approximate Pij(t) by taking a partial sum and then computing (by matrix multiplication of the transition probability matrix) the relevant n stage probabilities Pijn.

Whereas the applicability of Equation (6.36) would appear to be quite limited since it supposes that vi≡v, it turns out that most Markov chains can be put in that form by the trick of allowing fictitious transitions from a state to itself. To see how this works, consider any Markov chain for which the vi are bounded, and let v be any number such that

vi⩽v,for alli (6.37)

(6.37)

When in state i, the process actually leaves at rate vi; but this is equivalent to supposing that transitions occur at rate v, but only the fraction vi/v of transitions are real ones (and thus real transitions occur at rate vi) and the remaining fraction 1-vi/v are fictitious transitions that leave the process in state i. In other words, any Markov chain satisfying Condition (6.37) can be thought of as being a process that spends an exponential amount of time with rate v in state i and then makes a transition to j with probability Pij∗, where

Pij∗=1-viv,j=ivivPij,j≠i (6.38)

(6.38)

Hence, from Equation (6.36) we have that the transition probabilities can be computed by

Pij(t)=∑n=0∞Pij∗ne-vt(vt)nn!

where Pij∗ are the n-stage transition probabilities corresponding to Equation (6.38). This technique of uniformizing the rate in which a transition occurs from each state by introducing transitions from a state to itself is known as uniformization.

Example 6.23

Let us reconsider Example 6.11, which models the workings of a machine—either on or off—as a two-state continuous-time Markov chain with

P01=P10=1,v0=λ,v1=μ

Letting v=λ+μ, the uniformized version of the preceding is to consider it a continuous-time Markov chain with

P00=μλ+μ=1-P01,P10=μλ+μ=1-P11,vi=λ+μ,i=1,2

As P00=P10, it follows that the probability of a transition into state 0 is equal to μ/(λ+μ) no matter what the present state. Because a similar result is true for state 1, it follows that the n-stage transition probabilities are given by

Pi0n=μλ+μ,n⩾1,i=0,1Pi1n=λλ+μ,n⩾1,i=0,1

Hence,

P00(t)=∑n=0∞P00ne-(λ+μ)t[(λ+μ)t]nn!=e-(λ+μ)t+∑n=1∞μλ+μe-(λ+μ)t[(λ+μ)t]nn!=e-(λ+μ)t+[1-e-(λ+μ)t]μλ+μ=μλ+μ+λλ+μe-(λ+μ)t

Similarly,

P11(t)=∑n=0∞P11ne-(λ+μ)t[(λ+μ)t]nn!=e-(λ+μ)t+[1-e-(λ+μ)t]λλ+μ=λλ+μ+μλ+μe-(λ+μ)t

The remaining probabilities are

P01(t)=1-P00(t)=λλ+μ[1-e-(λ+μ)t],P10(t)=1-P11(t)=μλ+μ[1-e-(λ+μ)t]■

Example 6.24

Consider the two-state chain of Example 6.23 and suppose that the initial state is state 0. Let O(t) denote the total amount of time that the process is in state 0 during the interval (0,t). The random variable O(t) is often called the occupation time. We will now compute its mean.

If we let

I(s)=1,ifX(s)=00,ifX(s)=1

then we can represent the occupation time by

O(t)=∫0tI(s)ds

Taking expectations and using the fact that we can take the expectation inside the integral sign (since an integral is basically a sum), we obtain

E[O(t)]=∫0tE[I(s)]ds=∫0tP{X(s)=0}ds=∫0tP00(s)ds=μλ+μt+λ(λ+μ)2{1-e-(λ+μ)t}

where the final equality follows by integrating

P00(s)=μλ+μ+λλ+μe-(λ+μ)s

(For another derivation of E[O(t)], see Exercise 45.) ■

6.9 Computing the Transition Probabilities

For any pair of states i and j, let

rij=qij,ifi≠j-vi,ifi=j

Using this notation, we can rewrite the Kolmogorov backward equations

Pij′(t)=∑k≠iqikPkj(t)-viPij(t)

and the forward equations

Pij′(t)=∑k≠jqkjPik(t)-vjPij(t)

as follows:

Pij′(t)=∑krikPkj(t)(backward)Pij′(t)=∑krkjPik(t)(forward)

This representation is especially revealing when we introduce matrix notation. Define the matrices R and P(t), P′(t) by letting the element in row i, column j of these matrices be, respectively, rij,Pij(t), and Pij′(t). Since the backward equations say that the element in row i, column j of the matrix P′(t) can be obtained by multiplying the ith row of the matrix R by the jth column of the matrix P(t), it is equivalent to the matrix equation

P′(t)=RP(t) (6.39)

(6.39)

Similarly, the forward equations can be written as

P′(t)=P(t)R (6.40)

(6.40)

Now, just as the solution of the scalar differential equation

f′(t)=cf(t)

(or, equivalent, f′(t)=f(t)c) is

f(t)=f(0)ect

it can be shown that the solution of the matrix differential Equations (6.39) and (6.40) is given by

P(t)=P(0)eRt

Since P(0)=I (the identity matrix), this yields that

P(t)=eRt (6.41)

(6.41)

where the matrix eRt is defined by

eRt=∑n=0∞Rntnn! (6.42)

(6.42)

with Rn being the (matrix) multiplication of R by itself n times.

The direct use of Equation (6.42) to compute P(t) turns out to be very inefficient for two reasons. First, since the matrix R contains both positive and negative elements (remember the off-diagonal elements are the qij while the ith diagonal element is -vi), there is the problem of computer round-off error when we compute the powers of R. Second, we often have to compute many of the terms in the infinite sum (6.42) to arrive at a good approximation. However, there are certain indirect ways that we can utilize the relation in (6.41) to efficiently approximate the matrix P(t). We now present two of these methods.

Approximation Method 1 Rather than using Equation (6.42) to compute eRt, we can use the matrix equivalent of the identity

ex=limn→∞1+xnn

which states that

eRt=limn→∞I+Rtnn

Thus, if we let n be a power of 2, say, n=2k, then we can approximate P(t) by raising the matrix M=I+Rt/n to the nth power, which can be accomplished by k matrix multiplications (by first multiplying M by itself to obtain M2 and then multiplying that by itself to obtain M4 and so on). In addition, since only the diagonal elements of R are negative (and the diagonal elements of the identity matrix I are equal to 1), by choosing n large enough we can guarantee that the matrix I+Rt/n has all nonnegative elements.

Approximation Method 2 A second approach to approximating eRt uses the identity

e-Rt=limn→∞I-Rtnn≈I-Rtnnfornlarge

and thus

P(t)=eRt≈I-Rtn-n=I-Rtn-1n

Hence, if we again choose n to be a large power of 2, say, n=2k, we can approximate P(t) by first computing the inverse of the matrix I-Rt/n and then raising that matrix to the nth power (by utilizing k matrix multiplications). It can be shown that the matrix (I-Rt/n)-1 will have only nonnegative elements.

Remark

Both of the preceding computational approaches for approximating P(t) have probabilistic interpretations (see Exercises 41 and 42).

Exercises

1. A population of organisms consists of both male and female members. In a small colony any particular male is likely to mate with any particular female in any time interval of length h, with probability λh+o(h). Each mating immediately produces one offspring, equally likely to be male or female. Let N1(t) and N2(t) denote the number of males and females in the population at t. Derive the parameters of the continuous-time Markov chain {N1(t),N2(t)}, i.e., the vi,Pij of Section 6.2.

*2. Suppose that a one-celled organism can be in one of two states—either A or B. An individual in state A will change to state B at an exponential rate α; an individual in state B divides into two new individuals of type A at an exponential rate β. Define an appropriate continuous-time Markov chain for a population of such organisms and determine the appropriate parameters for this model.

3. Consider two machines that are maintained by a single repairman. Machine i functions for an exponential time with rate μi before breaking down, i=1,2. The repair times (for either machine) are exponential with rate μ. Can we analyze this as a birth and death process? If so, what are the parameters? If not, how can we analyze it?

*4. Potential customers arrive at a single-server station in accordance with a Poisson process with rate λ. However, if the arrival finds n customers already in the station, then he will enter the system with probability αn. Assuming an exponential service rate μ, set this up as a birth and death process and determine the birth and death rates.

5. There are N individuals in a population, some of whom have a certain infection that spreads as follows. Contacts between two members of this population occur in accordance with a Poisson process having rate λ. When a contact occurs, it is equally likely to involve any of the N2 pairs of individuals in the population. If a contact involves an infected and a noninfected individual, then with probability p the noninfected individual becomes infected. Once infected, an individual remains infected throughout. Let X(t) denote the number of infected members of the population at time t.

(a) Is {X(t),t⩾0} a continuous-time Markov chain?

(b) Specify its type.

(c) Starting with a single infected individual, what is the expected time until all members are infected?

6. Consider a birth and death process with birth rates λi=(i+1)λ,i⩾0, and death rates μi=iμ,i⩾0.

(a) Determine the expected time to go from state 0 to state 4.

(b) Determine the expected time to go from state 2 to state 5.

(c) Determine the variances in parts (a) and (b).

*7. Individuals join a club in accordance with a Poisson process with rate λ. Each new member must pass through k consecutive stages to become a full member of the club. The time it takes to pass through each stage is exponentially distributed with rate μ. Let Ni(t) denote the number of club members at time t who have passed through exactly i stages, i=1,…,k-1. Also, let N(t)=(N1(t),N2(t),…,Nk-1(t)).

(a) Is {N(t),t⩾0} a continuous-time Markov chain?

(b) If so, give the infinitesimal transition rates. That is, for any state n=(n1,…,nk-1) give the possible next states along with their infinitesimal rates.

8. Consider two machines, both of which have an exponential lifetime with mean 1/λ. There is a single repairman that can service machines at an exponential rate μ. Set up the Kolmogorov backward equations; you need not solve them.

9. The birth and death process with parameters λn=0 and μn=μ,n>0 is called a pure death process. Find Pij(t).

10. Consider two machines. Machine i operates for an exponential time with rate λi and then fails; its repair time is exponential with rate μi,i=1,2. The machines act independently of each other. Define a four-state continuous-time Markov chain that jointly describes the condition of the two machines. Use the assumed independence to compute the transition probabilities for this chain and then verify that these transition probabilities satisfy the forward and backward equations.

*11. Consider a Yule process starting with a single individual—that is, suppose X(0)=1. Let Ti denote the time it takes the process to go from a population of size i to one of size i+1.

(a) Argue that Ti,i=1,…,j, are independent exponentials with respective rates iλ.

(b) Let X1,…,Xj denote independent exponential random variables each having rate λ, and interpret Xi as the lifetime of component i. Argue that max(X1,…,Xj) can be expressed as

max(X1,…,Xj)=ε1+ε2+⋯+εj

where ε1,ε2,…,εj are independent exponentials with respective rates jλ, (j-1)λ,…,λ.

Hint: Interpret εi as the time between the i-1 and the ith failure.

(c) Using (a) and (b) argue that

P{T1+⋯+Tj⩽t}=(1-e-λt)j

(d) Use (c) to obtain

P1j(t)=(1-e-λt)j-1-(1-e-λt)j=e-λt(1-e-λt)j-1

and hence, given X(0)=1,X(t) has a geometric distribution with parameter p=e-λt.

(e) Now conclude that

Pij(t)=j-1i-1e-λti(1-e-λt)j-i

12. Each individual in a biological population is assumed to give birth at an exponential rate λ, and to die at an exponential rate μ. In addition, there is an exponential rate of increase θ due to immigration. However, immigration is not allowed when the population size is N or larger.

(a) Set this up as a birth and death model.

(b) If N=3,1=θ=λ,μ=2, determine the proportion of time that immigration is restricted.

13. A small barbershop, operated by a single barber, has room for at most two customers. Potential customers arrive at a Poisson rate of three per hour, and the successive service times are independent exponential random variables with mean 14 hour.

(a) What is the average number of customers in the shop?

(b) What is the proportion of potential customers that enter the shop?

(c) If the barber could work twice as fast, how much more business would he do?

14. Potential customers arrive at a full-service, one-pump gas station at a Poisson rate of 20 cars per hour. However, customers will only enter the station for gas if there are no more than two cars (including the one currently being attended to) at the pump. Suppose the amount of time required to service a car is exponentially distributed with a mean of five minutes.

(a) What fraction of the attendant’s time will be spent servicing cars?

(b) What fraction of potential customers are lost?

15. A service center consists of two servers, each working at an exponential rate of two services per hour. If customers arrive at a Poisson rate of three per hour, then, assuming a system capacity of at most three customers,

(a) what fraction of potential customers enter the system?

(b) what would the value of part (a) be if there was only a single server, and his rate was twice as fast (that is, μ=4)?

*16. The following problem arises in molecular biology. The surface of a bacterium consists of several sites at which foreign molecules—some acceptable and some not—become attached. We consider a particular site and assume that molecules arrive at the site according to a Poisson process with parameter λ. Among these molecules a proportion α is acceptable. Unacceptable molecules stay at the site for a length of time that is exponentially distributed with parameter μ1, whereas an acceptable molecule remains at the site for an exponential time with rate μ2. An arriving molecule will become attached only if the site is free of other molecules. What percentage of time is the site occupied with an acceptable (unacceptable) molecule?

17. Each time a machine is repaired it remains up for an exponentially distributed time with rate λ. It then fails, and its failure is either of two types. If it is a type 1 failure, then the time to repair the machine is exponential with rate μ1; if it is a type 2 failure, then the repair time is exponential with rate μ2. Each failure is, independently of the time it took the machine to fail, a type 1 failure with probability p and a type 2 failure with probability 1-p. What proportion of time is the machine down due to a type 1 failure? What proportion of time is it down due to a type 2 failure? What proportion of time is it up?

18. After being repaired, a machine functions for an exponential time with rate λ and then fails. Upon failure, a repair process begins. The repair process proceeds sequentially through k distinct phases. First a phase 1 repair must be performed, then a phase 2, and so on. The times to complete these phases are independent, with phase i taking an exponential time with rate μi,i=1,…,k.

(a) What proportion of time is the machine undergoing a phase i repair?

(b) What proportion of time is the machine working?

*19. A single repairperson looks after both machines 1 and 2. Each time it is repaired, machine i stays up for an exponential time with rate λi,i=1, 2. When machine i fails, it requires an exponentially distributed amount of work with rate μi to complete its repair. The repairperson will always service machine 1 when it is down. For instance, if machine 1 fails while 2 is being repaired, then the repairperson will immediately stop work on machine 2 and start on 1. What proportion of time is machine 2 down?

20. There are two machines, one of which is used as a spare. A working machine will function for an exponential time with rate λ and will then fail. Upon failure, it is immediately replaced by the other machine if that one is in working order, and it goes to the repair facility. The repair facility consists of a single person who takes an exponential time with rate μ to repair a failed machine. At the repair facility, the newly failed machine enters service if the repairperson is free. If the repairperson is busy, it waits until the other machine is fixed; at that time, the newly repaired machine is put in service and repair begins on the other one. Starting with both machines in working condition, find

(a) the expected value and

(b) the variance of the time until both are in the repair facility.

(c) In the long run, what proportion of time is there a working machine?

21. Suppose that when both machines are down in Exercise 20 a second repairperson is called in to work on the newly failed one. Suppose all repair times remain exponential with rate μ. Now find the proportion of time at least one machine is working, and compare your answer with the one obtained in Exercise 20.

22. Customers arrive at a single-server queue in accordance with a Poisson process having rate λ. However, an arrival that finds n customers already in the system will only join the system with probability 1/(n+1). That is, with probability n/(n+1) such an arrival will not join the system. Show that the limiting distribution of the number of customers in the system is Poisson with mean λ/μ.

23. A job shop consists of three machines and two repairmen. The amount of time a machine works before breaking down is exponentially distributed with mean 10. If the amount of time it takes a single repairman to fix a machine is exponentially distributed with mean 8, then

(a) what is the average number of machines not in use?

(b) what proportion of time are both repairmen busy?

*24. Consider a taxi station where taxis and customers arrive in accordance with Poisson processes with respective rates of one and two per minute. A taxi will wait no matter how many other taxis are present. However, an arriving customer that does not find a taxi waiting leaves. Find

(a) the average number of taxis waiting, and

(b) the proportion of arriving customers that get taxis.

25. Customers arrive at a service station, manned by a single server who serves at an exponential rate μ1, at a Poisson rate λ. After completion of service the customer then joins a second system where the server serves at an exponential rate μ2. Such a system is called a tandem or sequential queueing system. Assuming that λ<μi, i=1, 2, determine the limiting probabilities.
Hint: Try a solution of the form Pn,m=Cαnβm, and determine C,α,β.

26. Consider an ergodic M/M/s queue in steady state (that is, after a long time) and argue that the number presently in the system is independent of the sequence of past departure times. That is, for instance, knowing that there have been departures 2, 3, 5, and 10 time units ago does not affect the distribution of the number presently in the system.

27. In the M/M/s queue if you allow the service rate to depend on the number in the system (but in such a way so that it is ergodic), what can you say about the output process? What can you say when the service rate μ remains unchanged but λ>sμ?

*28. If {X(t)} and {Y(t)} are independent continuous-time Markov chains, both of which are time reversible, show that the process {X(t),Y(t)} is also a time reversible Markov chain.

29. Consider a set of n machines and a single repair facility to service these machines. Suppose that when machine i,i=1,…,n, fails it requires an exponentially distributed amount of work with rate μi to repair it. The repair facility divides its efforts equally among all failed machines in the sense that whenever there are k failed machines each one receives work at a rate of 1/k per unit time. If there are a total of r working machines, including machine i, then i fails at an instantaneous rate λi/r.

(a) Define an appropriate state space so as to be able to analyze the preceding system as a continuous-time Markov chain.

(b) Give the instantaneous transition rates (that is, give the qij).

(c) Write the time reversibility equations.

(d) Find the limiting probabilities and show that the process is time reversible.

30. Consider a graph with nodes 1,2,…,n and the n2 arcs (i,j),i≠j,i,j,=1,…,n. (See Section 3.6.2 for appropriate definitions.) Suppose that a particle moves along this graph as follows: Events occur along the arcs (i,j) according to independent Poisson processes with rates λij. An event along arc (i,j) causes that arc to become excited. If the particle is at node i at the moment that (i,j) becomes excited, it instantaneously moves to node j,i,j=1,…,n. Let Pj denote the proportion of time that the particle is at node j. Show that

Pj=1n

Hint: Use time reversibility.

31. A total of N customers move about among r servers in the following manner. When a customer is served by server i, he then goes over to server j, j≠i, with probability 1/(r-1). If the server he goes to is free, then the customer enters service; otherwise he joins the queue. The service times are all independent, with the service times at server i being exponential with rate μ,i=1,…,r. Let the state at any time be the vector (n1,…,nr), where ni is the number of customers presently at server i,i=1,…,r,∑ini=N.

(a) Argue that if X(t) is the state at time t, then {X(t),t⩾0} is a continuous-time Markov chain.

(b) Give the infinitesimal rates of this chain.

(c) Show that this chain is time reversible, and find the limiting probabilities.

32. Customers arrive at a two-server station in accordance with a Poisson process having rate λ. Upon arriving, they join a single queue. Whenever a server completes a service, the person first in line enters service. The service times of server i are exponential with rate μi,i=1,2, where μ1+μ2>λ. An arrival finding both servers free is equally likely to go to either one. Define an appropriate continuous-time Markov chain for this model, show it is time reversible, and find the limiting probabilities.

*33. Consider two M/M/1 queues with respective parameters λi,μi,i=1,2. Suppose they share a common waiting room that can hold at most three customers. That is, whenever an arrival finds her server busy and three customers in the waiting room, she goes away. Find the limiting probability that there will be n queue 1 customers and m queue 2 customers in the system.
Hint: Use the results of Exercise 28 together with the concept of truncation.

34. Four workers share an office that contains four telephones. At any time, each worker is either “working” or “on the phone.” Each “working” period of worker i lasts for an exponentially distributed time with rate λi, and each “on the phone” period lasts for an exponentially distributed time with rate μi,i=1, 2, 3, 4.

(a) What proportion of time are all workers “working”?
Let Xi(t) equal 1 if worker i is working at time t, and let it be 0 otherwise.
Let X(t)=(X1(t),X2(t),X3(t),X4(t)).

(b) Argue that {X(t),t⩾0} is a continuous-time Markov chain and give its infinitesimal rates.

(c) Is {X(t)} time reversible? Why or why not?

Suppose now that one of the phones has broken down. Suppose that a worker who is about to use a phone but finds them all being used begins a new “working” period.

(d) What proportion of time are all workers “working”?

35. Consider a time reversible continuous-time Markov chain having infinitesimal transition rates qij and limiting probabilities {Pi}. Let A denote a set of states for this chain, and consider a new continuous-time Markov chain with transition rates qij∗ given by

qij∗=cqij,ifi∈A,j∉Aqij,otherwise

where c is an arbitrary positive number. Show that this chain remains time reversible, and find its limiting probabilities.

36. Consider a system of n components such that the working times of component i,i=1,…,n, are exponentially distributed with rate λi. When a component fails, however, the repair rate of component i depends on how many other components are down. Specifically, suppose that the instantaneous repair rate of component i,i=1,…,n, when there are a total of k failed components, is αkμi.

(a) Explain how we can analyze the preceding as a continuous-time Markov chain. Define the states and give the parameters of the chain.

(b) Show that, in steady state, the chain is time reversible and compute the limiting probabilities.

37. A hospital accepts k different types of patients, where type i patients arrive according to a Poisson proccess with rate λi, with these k Poisson processes being independent. Type i patients spend an exponentially distributed length of time with rate μi in the hospital, i=1,…,k. Suppose that each type i patient in the hospital requires wi units of resources, and that the hospital will not accept a new patient if it would result in the total of all patient’s resource needs exceeding the amount C. Consequently, it is possible to have n1 type 1 patients, n2 type 2 patients,…, and nk type k patients in the hospital at the same time if and only if

∑i=1kniwi⩽C

(a) Define a continuous-time Markov chain to analyze the preceding. For parts (b), (c), and (d) suppose that C=∞.

(b) If Ni(t) is the number of type i customers in the system at time t, what type of process is {Ni(t),t⩾0}? Is it time reversible?

(c) What can be said about the vector process {(N1(t),…,Nk(t))t⩾0}?

(d) What are the limiting probabilities of the process of part (c). For the remaining parts assume that C<∞.

(e) Find the limiting probabilities for the Markov chain of part (a).

(f) At what rate are type i patients admitted?

(g) What fraction of patients are admitted?

38. Consider an n server system where the service times of server i are exponentially distributed with rate μi,i=1,…,n. Suppose customers arrive in accordance with a Poisson process with rate λ, and that an arrival who finds all servers busy does not enter but goes elsewhere. Suppose that an arriving customer who finds at least one idle server is served by a randomly chosen one of that group; that is, an arrival finding k idle servers is equally likely to be served by any of these k.

(a) Define states so as to analyze the preceding as a continuous-time Markov chain.

(b) Show that this chain is time reversible.

(c) Find the limiting probabilities.

39. Suppose in Exercise 38 that an entering customer is served by the server who has been idle the shortest amount of time.

(a) Define states so as to analyze this model as a continuous-time Markov chain.

(b) Show that this chain is time reversible.

(c) Find the limiting probabilities.

40. Consider a continuous-time Markov chain with states 1,…,n, which spends an exponential time with rate vi in state i during each visit to that state and is then equally likely to go to any of the other n-1 states.

(a) Is this chain time reversible?

(b) Find the long-run proportions of time it spends in each state.

41. Show in Example 6.22 that the limiting probabilities satisfy Equations (6.33), (6.34), and (6.35).

42. In Example 6.22 explain why we would have known before analyzing Example 6.22 that the limiting probability there are j customers with server i is (λ/μi)j(1-λ/μi),i=1,2,j⩾0. (What we would not have known was that the number of customers at the two servers would, in steady state, be independent.)

43. Consider a sequential queueing model with three servers, where customers arrive at server 1 in accordance with a Poisson process with rate λ. After completion at server 1 the customer then moves to server 2; after a service completion at server 2 the customer moves to server 3; after a service completion at server 3 the customer departs the system. Assuming that the service times at server i are exponential with rate μi,i=1,2,3, find the limiting probabilities of this system by guessing at the reverse chain and then verifying that your guess is correct.

44. For the continuous-time Markov chain of Exercise 3 present a uniformized version.

45. In Example 6.20, we computed m(t)=E[O(t)], the expected occupation time in state 0 by time t for the two-state continuous-time Markov chain starting in state 0. Another way of obtaining this quantity is by deriving a differential equation for it.

(a) Show that

m(t+h)=m(t)+P00(t)h+o(h)

(b) Show that

m′(t)=μλ+μ+λλ+μe-(λ+μ)t

(c) Solve for m(t).

46. Let O(t) be the occupation time for state 0 in the two-state continuous-time Markov chain. Find E[O(t)∣X(0)=1].

47. Consider the two-state continuous-time Markov chain. Starting in state 0, find Cov[X(s),X(t)].

48. Let Y denote an exponential random variable with rate λ that is independent of the continuous-time Markov chain {X(t)} and let

P¯ij=P{X(Y)=j∣X(0)=i}

(a) Show that

P¯ij=1vi+λ∑kqikP¯kj+λvi+λδij

where δij is 1 when i=j and 0 when i≠j.

(b) Show that the solution of the preceding set of equations is given by

P¯=(I-R/λ)-1

where P¯ is the matrix of elements P¯ij, I is the identity matrix, and R the matrix specified in Section 6.9.

(c) Suppose now that Y1,…,Yn are independent exponentials with rate λ that are independent of {X(t)}. Show that

P{X(Y1+⋯+Yn)=j∣X(0)=i}

is equal to the element in row i, column j of the matrix P¯n.

(d) Explain the relationship of the preceding to Approximation 2 of Section 6.9.

*49. 

(a) Show that Approximation 1 of Section 6.9 is equivalent to uniformizing the continuous-time Markov chain with a value v such that vt=n and then approximating Pij(t) by Pij*n.

(b) Explain why the preceding should make a good approximation.

Hint: What is the standard deviation of a Poisson random variable with mean n?

References

1. Cox DR, Miller HD. The Theory of Stochastic Processes. London: Methuen; 1965.

2. Drake AW. Fundamentals of Applied Probability Theory. New York: McGraw-Hill; 1967.

3. Karlin S, Taylor H. A First Course in Stochastic Processes. Second Edition New York: Academic Press; 1975.

4. Parzen E. Stochastic Processes. San Francisco, California: Holden-Day; 1962.

5. Ross S. Stochastic Processes. Second Edition New York: John Wiley; 1996.