Practice Assignment (Markov Chains and Queuing Theory)

1. A computer system can operate in two different modes. Every hour, it remains in the
same mode or switches to a different mode according to the transition probability matrix

1. 0.4 2. 0.6
P= 3. 0.6 4. 0.4

a) Compute the 2-step transition probability matrix.

b) If the system is in Mode I at 5:30 pm, what is the probability that it will be in
Mode I at 8:30 pm on the same day?

2. A system has three possible states, 0, 1 and 2. Every hour it makes a transition to a
different state, which is determined by a coin flip. For example, from state 0, it makes a
transition to state 1 or state 2 with probabilities 0.5 and 0.5.

a) Find the transition probability matrix.

b) Find the three-step transition probability matrix.

3. We observe the state of a system at discrete points in time. The system is observed only
when it changes state. Define Xn as the state of the system after nth state change, so that
Xn = 0, if the system is running; Xn = 1 if the system is under repair; and Xn = 2 if the
system is idle. Assume that the matrix transition matrix is:

5. 0 6. 0.5 7. 0.5
8. 1 9. 0 10. 0
P= 11. 1 12. 0 13. 0

Compute the matrix Pn for all possible n.

4. Each time a certain horse runs in a three-horse race, he has probability 1/2 of winning,
1/4 of coming in second, and 1/4 of coming in third, independent of the outcome of any
previous race. We have an independent trials process, but it can also be considered from
the point of view of Markov chain theory. Find the TPM?

5. We have two urns that, between them, contain four balls. At each step, one of the four
balls is chosen at random and moved from the urn that it is in into the other urn. We
choose, as states, the number of balls in the first urn. Find the TPM?

6. Consider a machine that works as follows. If it is up at the beginning of a day, it stays up

at the beginning of the next day with probability p and fails with probability 1-p. It takes
exactly 2 days for the repairs, at the end of which the machine is as good as new. Let Xn
be the state of the machine at the beginning of day n, where the state is 0 if the machine

This study source was downloaded by 100000835991620 from CourseHero.com on 04-08-2023 02:15:28 GMT -05:00

https://www.coursehero.com/file/62691835/Practice-Assignment-MarkovnQueuing-pdf/
 has just failed, 1 if 1 days’ worth of repair work is done on it, and 2 if it is up. Show that
{Xn; n≥ 0} is a Markov chain, and deduce its transition probability matrix.

7. Items arrive at a machine shop in a deterministic fashion at a rate of one per minute. Each
item is tested before it is loaded onto the machine. An item is found to be nondefective
with probability p and defective with probability 1 - p. If an item is found defective, it is
discarded. Otherwise, it is loaded onto the machine. The machine takes exactly 1 minute
to process the item, after which it is ready to process the next one. Let Xn be 0 if the
machine is idle at the beginning of the nth minute and 1 if it is starting the processing of
an item. Show that {Xn; n≥ 0} is a Markov chain, and deduce its transition probability
matrix.
8. Consider the birth-and-death process with the following mean rates. The birth rates are
0  2, 1  3, 2  2, 3  1, and n  0 for n  0 . The death rates are
1  3, 2  4, 3  1, and n  2 for n  4 .
a) Construct the rate diagram for this birth-and-death process.
b) Develop the balance equations.
P , P ,L
c) Solve these equations to find the steady-state probability distribution 0 1 .
P , P ,L
d) Use the general formulas for the birth-and-death process to calculate 0 1 . Also
L, Lq ,W , and Wq
calculate .
9. Consider the birth-and-death process with all n
  2(n  0,1,L ), 1  2, and n  4, for
n  2, 3, ... .
e) Display the rate diagram.
P P P P
f) Calculate 0 and 1 . Then give a general expression for n in terms of 0 for
n  2,3,K .
g) Consider a queueing system with two servers that fits this process. What is the mean
arrival rate for this queueing system? What is the mean service rate for each server
when it is busy serving customers?
10. A service station has one gasoline pump. Cars wanting gasoline arrive according to a
Poisson process at a mean rate of 15 per hour. However, if the pump already is being used,
these potential customers may balk (drive on to another service station). In particular, if
there are n cars already at the service station, the probability that an arriving potential
customer will balk is n/3 for n = 1, 2, 3. The time required to service a car has an exponential
distribution with a mean of 4 minutes.
h) Construct the rate diagram for this queueing system.
i) Develop the balance equations.
j) Solve these equations to find the steady-state probability distribution of the number
of cars at the station. Verify that this solution is the same as that given by the general
solution for the birth-and-death process.
k) Find the expected waiting time (including service) for those cars that stay.

This study source was downloaded by 100000835991620 from CourseHero.com on 04-08-2023 02:15:28 GMT -05:00

https://www.coursehero.com/file/62691835/Practice-Assignment-MarkovnQueuing-pdf/
 11. A certain small grocery store has a single checkout stand with a full-time cashier.
Customers arrive at the stand “randomly” (i.e., a Poisson input process) at a mean rate of
30 per hour. When there is only one customer at the stand, she is processed by the
cashier alone, with an expected service time of 1.5 minutes. However, the stock boy has
been given standard instructions that whenever there is more than one customer at the
stand, he is to help the cashier by bagging the groceries. This help reduces the expected
time required to process a customer to 1 minute. In both cases, the service-time distribution
is exponential.
l) Construct the rate diagram for this queueing system.
m) What is the steady-state probability distribution of the number of customers at the
checkout stand?
n) Derive L for this system. Use this information to determine Lq ,W , and Wq .
12. A department has one word-processing operator. Documents produced in the department
are delivered for word processing according to a Poisson process with an expected inter-
arrival time of 20 minutes. When the operator has just one document to process, the
expected processing time is 15 minutes. When she has more than one document, then
editing assistance that is available reduces the expected processing time for each document
to 10 minutes. In both cases, the processing times have an exponential distribution.
o) Construct the rate diagram for this queueing system.
p) Find the steady-state distribution of the number of documents that the operator has
received but not yet completed.
q) Derive L for this system. Use this information to determine Lq ,W , and Wq .
13. The Security & Trust Bank employs 4 tellers to serve its customers. Customers arrive
according to a Poisson process at a mean rate of 2 per minute. However, business is
growing and management projects that the mean arrival rate will be 3 per minute
a year from now. The transaction time between the teller and customer has an exponential
distribution with a mean of 1 minute. Management has established the following guidelines
for a satisfactory level of service to customers. The average number of customers waiting
in line to begin service should not exceed 1. At least 95 percent of the time, the number of
customers waiting in line should not exceed 5. For at least 95 percent of the customers,
the time spent in line waiting to begin service should not exceed 5 minutes.
r) Use the M/M/s model to determine how well these guidelines are currently being
satisfied.
s) Evaluate how well the guidelines will be satisfied a year from now if no change is
made in the number of tellers.
t) Determine how many tellers will be needed a year from now to completely satisfy
these guidelines.
14. Jim McDonald, manager of the fast-food hamburger restaurant McBurger, realizes that
providing fast service is a key to the success of the restaurant. Customers who have to wait
very long are likely to go to one of the other fast-food restaurants in town next time. He
estimates that each minute a customer has to wait in line before completing service costs
him an average of 30 cents in lost future business. Therefore, he wants to be sure that

This study source was downloaded by 100000835991620 from CourseHero.com on 04-08-2023 02:15:28 GMT -05:00

https://www.coursehero.com/file/62691835/Practice-Assignment-MarkovnQueuing-pdf/
 enough cash registers always are open to keep waiting to a minimum. Each cash register is
operated by a part-time employee who obtains the food ordered by each customer and
collects the payment. The total cost for each such employee is $9 per hour.
u) During lunch time, customers arrive according to a Poisson process at a mean rate
of 66 per hour. The time needed to serve a customer is estimated to have an
exponential distribution with a mean of 2 minutes.
v) Determine how many cash registers Jim should have open during lunch time to
minimize his expected total cost per hour.

---xxx---

This study source was downloaded by 100000835991620 from CourseHero.com on 04-08-2023 02:15:28 GMT -05:00

https://www.coursehero.com/file/62691835/Practice-Assignment-MarkovnQueuing-pdf/
Powered by TCPDF (www.tcpdf.org)