Write a computer program to simulate the queue in Exercise. Have your program keep track of the proportion of the time that the queue length is [math]j[/math] for [math]j = 0, 1, \ldots,n[/math] and the average queue length. Show that the behavior of the queue length is very different depending upon whether the traffic intensity [math]s[/math] has the property [math]s \lt 1[/math], [math]s =1[/math], or [math]s \gt 1[/math].

In the queueing problem of Exercise, let [math]S[/math] be the total service time required by a customer and [math]T[/math] the time between arrivals of the customers.

• Show that [math]P(S = j) = (1 - r)^{j - 1}r[/math] and [math]P(T = j) = (1 - p)^{j - 1}p[/math], for [math]j \gt 0[/math].
• Show that [math]E(S) = 1/r[/math] and [math]E(T) = 1/p[/math].
• Interpret the conditions [math]s \lt 1[/math], [math]s = 1[/math] and [math]s \gt 1[/math] in terms of these expected values.

In Exercise the service time [math]S[/math] has a geometric distribution with [math]E(S) = 1/r[/math]. Assume that the service time is, instead, a constant time of [math]t[/math] seconds. Modify your computer program of Exercise so that it simulates a constant time service distribution. Compare the average queue length for the two types of distributions when they have the same expected service time (i.e., take [math]t = 1/r[/math]). Which distribution leads to the longer queues on the average?

A certain experiment is believed to be described by a two-state Markov chain with the transition matrix [math]\mat{P}[/math], where

and the parameter [math]p[/math] is not known. When the experiment is performed many times, the chain ends in state one approximately 20 percent of the time and in state two approximately 80 percent of the time. Compute a sensible estimate for the unknown parameter [math]p[/math] and explain how you found it.

Prove that, in an [math]r[/math]-state ergodic chain, it is possible to go from any state to any other state in at most [math]r - 1[/math] steps.

Let [math]\mat{P}[/math] be the transition matrix of an [math]r[/math]-state ergodic chain. Prove that, if the diagonal entries [math]p_{ii}[/math] are positive, then the chain is regular.

Prove that if [math]\mat{P}[/math] is the transition matrix of an ergodic chain, then [math](1/2)(\mat {I} + \mat {P})[/math] is the transition matrix of a regular chain. Hint: Use Exercise.

Prove that [math]\mat{P}[/math] and [math](1/2)(\mat {I} + \mat {P})[/math] have the same fixed vectors.

In his book, Wahrscheinlichkeitsrechnung und Statistik,^{[Notes 1]} A. Engle proposes an algorithm for finding the fixed vector for an ergodic Markov chain when the transition probabilities are rational numbers. Here is his algorithm: For each state [math]i[/math], let [math]a_i[/math] be the least common multiple of the denominators of the non-zero entries in the [math]i[/math]th row. Engle describes his algorithm in terms of moving chips around on the states---indeed, for small examples, he recommends implementing the algorithm this way. Start by putting [math]a_i[/math] chips on state [math]i[/math] for all [math]i[/math]. Then, at each state, redistribute the [math]a_i[/math] chips, sending [math]a_ip_{ij}[/math] to state [math]j[/math]. The number of chips at state [math]i[/math] after this redistribution need not be a multiple of [math]a_i[/math]. For each state [math]i[/math], add just enough chips to bring the number of chips at state [math]i[/math] up to a multiple of [math]a_i[/math]. Then redistribute the chips in the same manner. This process will eventually reach a point where the number of chips at each state, after the redistribution, is the same as before redistribution. At this point, we have found a fixed vector. Here is an example:

We start with [math]\mat {a} = (4,2,4)[/math]. The chips after successive redistributions are shown in Table.

We find that [math]\mat {a} = (20,8,12)[/math] is a fixed vector.

• Write a computer program to implement this algorithm.
• Prove that the algorithm will stop. Hint: Let [math]\mat{b}[/math] be a vector with integer components that is a fixed vector for [math]\mat{P}[/math] and such that each coordinate of the starting vector [math]\mat{a}[/math] is less than or equal to the corresponding component of [math]\mat{b}[/math]. Show that, in the iteration, the components of the vectors are always increasing, and always less than or equal to the corresponding component of [math]\mat{b}[/math].

Notes

(Coffman, Kaduta, and Shepp^{[Notes 1]}) A computing center keeps information on a tape in positions of unit length. During each time unit there is one request to occupy a unit of tape. When this arrives the first free unit is used. Also, during each second, each of the units that are occupied is vacated with probability [math]p[/math]. Simulate this process, starting with an empty tape. Estimate the expected number of sites occupied for a given value of [math]p[/math]. If [math]p[/math] is small, can you choose the tape long enough so that there is a small probability that a new job will have to be turned away (i.e., that all the sites are occupied)? Form a Markov chain with states the number of sites occupied. Modify the program FixedVector to compute the fixed vector. Use this to check your conjecture by simulation.

Notes