QUESTION
1. Consider the following Markov Chain P, with states ordered f1; 2; 3; 4; 5g:
P =
0
B
B
B
B
B
B
@
0:0 0:8 0:2 0:0 0:0
0:7 0:0 0:2 0:0 0:1
0:4 0:6 0:0 0:0 0:0
0:8 0:1 0:0 0:1 0:0
0:0 0:0 0:0 1:0 0:0
0:0 0:0 0:0 0:0 1:0
(a)
Classify each state (recurrent, transient, absorbing).
(b) For each transient state k (if any), compute f
k
1
C
C
C
C
C
C
A
Due October 21, 2011
. (Refer to the notes for the de¯nition
of f
.)
(c) Find lim
k
= ¼. (You may use MATLAB to check your answer, but not to
justify your answer.)
n!1
P
n
(d)
For each transient state j and absorbing state k (if any), ¯nd ®
, the probability
that, starting from j the process will eventually be absorbed by k.
jk
(e) For each transient state k, compute the average number of steps taken by the process
to reach either an absorbing state or a recurrent state, if the process starts at k.
2. A Markov Chain on states f1; 2; 3; 4g is such that at any step the process is equally likely
to move to any of the other states. For example, if the process is at state 3, it is equally
likely to move to states 1, 2, or 4. Let S
be the state of the chain at step n. We are told
that S
0
n
= 1. We de¯ne the following random variable N: the number of times the process
visits state 4 after the ¯rst step, but strictly before returning to its starting state.
(a)
Write down the matrix P for this Markov chain.
(b)
Classify the states.
(c) What is the value of N(!) for each of the following paths of the process:
! = 12132434343221 ! = 12323434213432 ! = 141231213431
(d)
Find E[NjS
0
= 1].
3. N white marbles and N black marbles are divided equally between two urns, so that each
urn contains N marbles. Let S
be the number of white marbles in the ¯rst urn at step n.
At each step, a marble is randomly (equally likely) selected from the ¯rst urn, and another
marble is randomly selected from the second urn, and they are interchanged. Show that
S
n
n
is a Markov chain, and compute its transition matrix. What can you say about its
stationary distribution?
1
4. An M/M/1 queue has arrival rate ¸ = 2 and service rate ¹ = 3. Find the steady state
probabilities for this queue, the proportion of the time when the server is idle, the expected
length of the queue, and the expected waiting time in the queue (that includes the service
time).
5. An M/M/1 queue has arrival rate ¸ and service rate ¹. The queue is empty at time t = 0.
Find the probability that exactly two customers have been served by time T > 0 (¯xed).
Bonus questions
6.
Write a MATLAB program to compute the value E[NjS
= 1] in question 2d using
simulation. Help is available from me.
0
7. Generalize the set up in question 2 to allow for s states.
Notes.
Question 1. The theory for this question is all in the Markov Chain notes I distributed to
the class.
Question 2. Use the ¯rst-step analysis technique.
Question 3. Look at the solution to the tutorial problem about °eas on dogs.
Question 4. This is a straightforward application of the formulas we saw in class. You do
not need to derive the formulas again. Just make sure you can apply them.
Question 5. Remember that you need to have at least two customers, before they can be
served.
Question 6. I have written 19 lines of MATLAB code for this. If you have never done
anything like it, then this problem is hard. I am available for help, and I will post a sample
code (for a di®erent problem) on the course webpage.
Question 7. Self-explanatory.
Feel free to consult me if any of these questions is not clear.
SOLUTION
| Solution 4 | ||||||||
| ρ | 0.666667 | |||||||
| (a) | steady state | |||||||
| probabilities for this queue | 0.666667 | |||||||
| (b) | proportion of the time when the server is idle | 0.333333 | ||||||
| ( c ) | the expected | |||||||
| length of the queue | 2 | |||||||
| ( d ) | the expected waiting time in the queue | 1.333333 | ||||||
| Solution 5 | ||||||||
| Arrival rate | λ | |||||||
| Service rate | µ | |||||||
| probability that exactly two customers have been served by time T = p^2*(1-p) | ||||||||
| Where p= | Arrival rate/ service rate | |||||||
| Answer 3 | |||||||||||
| The index set T= { 0,1,2,3,—-,N} | |||||||||||
| For any of the state io, i1, i2,—,j belongs to S and any n belongs to T | |||||||||||
| we have , | |||||||||||
| P[Xn+1=jlXn=I,Xn-1=in-1,——,X0=i0] | |||||||||||
| So the Discrete state space S= { 1,2,3,—-,s} is nothing but Markov chain | |||||||||||
| transition matrix. | |||||||||||
| W | B | ||||||||||
| W | 0.5 | 0.5 | |||||||||
| B | 0.5 | 0.5 | |||||||||
| since is the case of recurrence so it has the propertyof stationary distribution. | |||||||||||
| Answer 2 | |||||||||||
| 0 | 1 | 2 | 3 | 4 | |||||||
| 0 | 1 | 0 | 0 | 0 | 0 | ||||||
| 1 | 0.5 | 0 | 0.5 | 0 | 0 | ||||||
| matrix P = | 2 | 0 | 0.5 | 0 | 0.5 | 0 | |||||
| 3 | 0 | 0 | 0.5 | 0 | 0.5 | ||||||
| 4 | 0 | 0 | 0 | 0 | 1 | ||||||
| Description of the state | |||||||||||
| State o and 4 in absorbing state | |||||||||||
| State 1,2 and 3 are transient states | |||||||||||
| Answer 1 | |||||||||||
| 0 | 0.8 | 0.2 | 0 | 0 | |||||||
| 0.7 | 0 | 0.2 | 0 | 0.1 | |||||||
| P = | 0.4 | 0.6 | 0 | 0 | 0 | ||||||
| 0.8 | 0.1 | 0 | 0.1 | 0 | |||||||
| 0 | 0 | 0 | 1 | 0 | |||||||
| 0 | 0 | 0 | 0 | 1 | |||||||
| Description of the states | |||||||||||
| State 4 and 5 are absorbing state | |||||||||||
| and states 0,1,2 and 3 are trasient state. | |||||||||||
| Directly P^n is not possible because number of rows and number of columns are different. | |||||||||||
GI31
But you can order it from our service and receive complete high-quality custom paper. Our service offers “Maths” sample that was written by professional writer. If you like one, you have an opportunity to buy a similar paper. Any of the academic papers will be written from scratch, according to all customers’ specifications, expectations and highest standards.”
