I am working on the following problem
Suppose that a certain queue may contain 0, 1, or 2 items. It is not possible for it to contain 3 or more items. At each time step, one of two things can happen:
(i) with probability 1/3, one item is removed from the queue, if there is an item to remove (and otherwise nothing happens), or
(ii) with probability 2/3, one item is added to the queue, if there is enough space (i.e. if there are not already 2 items in the queue) (and otherwise nothing happens).
(a) Formulate a finite Markov chain that describes this system.
(b) If the queue starts o empty, aer 4 time steps what is the probability that it is again empty?
(c) In the long term, what is the average rate at which items are removed from the queue?
For part a) i have represented it with the matrix
|1/3 2/3 0|
|1/3 0 2/3|
|1/3 2/3 2/3|
Although i am unsure if the last line is correct (should be 2/3 2/3 2/3)?
For part b) i am assuming i just multiply the matrix by itself 4 times, but i am not sure how to interpret this as a probability.
And for c) i think to use (P-I)x = 0 to find a steady state vector.
If anyone could tell me if im going in the right direction / give any help or advice it would be greatly appreciated.
Thanks
Let $X_n$ be the number of items in the system at time $n$, then $\{X_n:n=0,1,2\ldots\}$ is a Markov chain on $\{0,1,2\}$ with transition matrix $$ P = \begin{pmatrix}\frac13&\frac23&0\\\frac13&0&\frac23\\0&\frac13&\frac23 \end{pmatrix}. $$ For (b) we compute $$P^4 = \begin{pmatrix} \frac{5}{27} & \frac{22}{81} & \frac{44}{81} \\ \frac{11}{81} & \frac{26}{81} & \frac{44}{81} \\ \frac{11}{81} & \frac{22}{81} & \frac{16}{27} \end{pmatrix}. $$ From the Chapman-Kolmogorov equations we see that $$\mathbb P(X_4=0\mid X_0=0) = (P^4)_{00} = \frac5{27}. $$ This Markov chain is irreducible and aperiodic on a finite state space, so there exists a unique stationary distribution $\pi$ such that $\pi=\pi P$. These equations along with $\sum_i \pi_i=1$ yield \begin{align} \frac23\pi_0 -\frac13\pi_1 &= 0\\ \frac23\pi_1-\frac13\pi_2A &= 0\\ \pi_0 + \pi_1 + \pi_2 &= 1, \end{align} with solution $\pi = \left(\frac17,\frac27,\frac47\right)$.
For (c) we compute
$$\pi_1P_{10} + \pi_2P_{21} = \frac27\cdot\frac13 + \frac47\cdot\frac13 = \frac27. $$