Q&A

# A discrete-time queue Markov Chain problem

+0
−0

Hello everyone, I hope somebody can help me with this question, only for parts c and d, because I have already figured out parts a and b. Here is the question:

Items arrive in a queue during time intervals (0, 1), (1, 2), . . . . Let An denote the number of arrivals in the interval (n − 1, n), and assume that (An : n ≥ 1) are mutually independent and identically distributed with pmf aj = P(An = j) = 1 4 , j = 0, 1, 2, 3. The arriving items queue in a buffer with capacity 4: if arrivals exceed the buffer capacity, then the excess is lost. A single server dispatches one item per unit time (if any are waiting), with these dispatches occurring at times n = 1, 2, . . . (by which is meant that the dispatch at time n occurs after the arrivals An, and prior to the next arrivals An+1). Let Xn denote the buffer level at time n, immediately before any dispatch. We know that (Xn) is a Markov chain, with state space S = {0, 1, . . . , 4}. Denote by P = [pij ]i,j the transition probability matrix for (Xn). Suppose that the queue is empty initially, i.e. X0 = 0.

(a) Give the one-step transition probability matrix for (Xn).

(b) Find the mean occupation times (m0j (10) : j ∈ S) for (Xn).

(c) Find the expected time until the buffer reaches its capacity for the first time.

(d) Let Yn denote the number of items that go to waste from arrivals during the interval (n − 1, n). Show that E(Yn+1 | X0 = 0) = (1/4)*P^(n)(subscript 0,3 for P) + (3/4) * P^(n) (subscript 0,4 for P). [Hint: First evaluate E(Yn+1 | Xn = j), for each j ∈ S, and then apply the Law of Total Expectation: E(Yn+1 | X0 = 0) = P j∈S E(Yn+1 | Xn = j, X0 = 0)P(Xn = j | X0 = 0).]

For part a: I got the following matrix (which is correct because it has already been confirmed by my professor):

P =

1/4  1/4  1/4   1/4    0

0    1/4  1/4   1/4    1/4

0    0    1/4   1/4    1/2

0    0    0     1/4    3/4

0    0    0     0      1


For part b: I did the calculations using a statistical package and got the answer by adding up all the entries of the first row of the matrix.

For parts c and d: Well, that's where I need some serious help because I have no idea how to do them, so I would appreciate it any help.

Thanks

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

#### 2 comment threads

"No idea" (1 comment)
MathJax (1 comment) 