I have a discrete-time Markov chain queuing problem.
Packets (computer packets, that is) arrive in the intervals. $A_n$ denotes the number of arrivals in the interval $(n – 1, n)$, where $n \ge 1$, and the $A_n$ are independent and identically distributed. The probability mass function is $P(A_n = j) = \dfrac{1}{4}$ for $j = 0, 1, 2, 3$.
The packets first enter a buffer that can hold $K = 4$ packets. If the amount of packets arriving is greater than $K = 4$, then any surplus is terminated. One packet is dispatched per unit time (assuming there are packets waiting to be dispatched in the buffer), where unit time is, as I said, $n = 1, 2, \dots$. For time $n$, the packets are dispatched after the new entrance of packets $A_n$, but before the arrivals at the next time, $A_{n + 1}$.
$X_n$ is the amount of packets in the buffer at time $n$. This is before any packets have been dispatched. So we have that $X_n$ is a MC and has state space $\{ 0, 1, 2, 3, 4 \}$. We assume that the queue is empty at the beginning (that is, that $X_0 = 0$).
The $p_{i,j}$ are the elements of the transition matrix $P$.
Let $Y_n$ be the number of packets lost during the $n$th time slot.
So we have that
$$Y_{n + 1} = \begin{cases} \max\{ 0, A_n – K \}, & X_n = 0 \\ \max\{0, X_n – 1 + A_{n + 1} – K\}, & X_n > 0 \end{cases}.$$
I am trying to find $E[Y_{n + 1} \vert X_0 = 0]$.
I do not understand how to do this. Thinking about how conditional expectation is done, my understanding is that the expressions should look something like $E[ A_n – 4 > 0 \vert X_0 = 0 ] P(A_n – 4 > 0 \vert X_0 = 0)$, or something. But, honestly, I have no idea how to do this.
I would greatly appreciate it if people would please take the time to clarify this.
The solution is said to be $\dfrac{1}{4}p^{(n)}_{0, 3} + \dfrac{3}{4}p^{(n)}_{0, 4}$, where $p^{(n)}_{i, j}$ are the values of the $n$th-step transition matrix. It's not so much the solution itself that I'm interested in; rather, I'm interested in the calculations and reasoning that leads to the solution.
With regards to the transition matrix, the textbook presents the example as follows:
Let $A_n$ be the number of packets that arrive at the switch during the $n$th slot. Let $X_n$ be the number of packets in the buffer at the end of the $n$th slot. Now, if $X_n = 0$, then there are no packets available for transmission at the beginning of the $(n + 1)$st slot. Hence all the packets that arrive during that slot, namely $A_{n + 1}$, are in the buffer at the end of that slot unless $A_{n + 1} > K$, in which case the buffer is full at the end of the $(n + 1)$st slot. Hence $X_{n + 1} = \min\{ A_{n + 1}, K \}$. If $X_n > 0$, one packet is removed at the beginning of the $(n + 1)$st slot and $A_{n + 1}$ packets are added during that slot, subject to capacity limitations. Combining these cases, we get
$$X_{n + 1} = \begin{cases} \min\{ A_{n + 1} \}, K & \text{if} \ X_n = 0 \\ \min\{ X_n + A_{n + 1} – 1, K \} & \text{if} \ 0 < X_n \le K. \end{cases}$$
Assume that $\{ A_n, n \ge 1 \}$ is a sequence of iid random variables with common pmf
$$P(A_n = k) = a_k, k \ge 0.$$
Under this assumption, $\{ X_n, n \ge 0 \}$ is a DTMC on state space $\{ 0, 1, 2, \dots, K \}$. The transition probabilities can be computed as follows. For $0 \le j < K$,
$$\begin{align} P(X_{n + 1} = j \vert X_n = 0) &= P(\min\{ X_{n + 1}, K \} = j \vert X_n = 0) \\ &= P(X_{n + 1} = j) \\ &= a_j \end{align}$$
$$\begin{align} P(X_{n + 1} = K \vert X_n = 0) &= P(\min\{ A_{n + 1}, K \} = K \vert X_n = 0) \\ &= P(A_{n + 1} \ge K) \\ &= \sum_{k = K}^\infty a_k. \end{align}$$
Similarly, for $1 \le i \le K$ and $i – 1 \le j < K$,
$$\begin{align} P(X_{n + 1} = j \vert X_n = i) &= P(\min\{ X_n + A_{n + 1} – 1, K \} = j \vert X_n = i) \\ &= P(A_{n + 1} = j – i + 1) \\ &= a_{j – i + 1}. \end{align}$$
Finally, for $1 \le i \le K$,
$$\begin{align} P(X_{n + 1} = K \vert X_n = i) &= P(\min\{ X_n + A_{n + 1} – 1, K \} = K \vert X_n = i) \\ &= P(A_{n + 1} \ge K – i + 1) \\ &= \sum_{k = K – i + 1}^\infty a_k. \end{align}$$
Combining all these cases using the notation
$$b_j = \sum_{k = j}^\infty a_k,$$
we get the transition probability matrix
$$P = \begin{bmatrix} a_0 & a_1 & \dots & a_{K – 1} & b_K \\ a_0 & a_1 & \dots & a_{K – 1} & b_K \\ 0 & a_0 & \dots & a_{K – 2} & b_{K – 1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & a_0 & b_1 \end{bmatrix}.$$
Best Answer
So $X_n$ is a Markov chain with state space $\{0,1,2,3,4\}$ and $X_0=0$. Let us determine the transition matrix:
When $X_n \leq 1$, then $X_{n+1}=A_{n+1}$, because you dispatch the potential packet in the buffer before getting another one. When $X_n \geq 2$, then $X_{n+1} = \min(4,X_n-1+A_{n+1})$.
So, writing everything out, the transition matrix (I'm considering the probability distributions of the $X_k$ as column vectors) is:
$P=\begin{bmatrix} 0.25 & 0.25 & 0 & 0 & 0\\ 0.25 & 0.25 & 0.25 & 0 & 0\\ 0.25 & 0.25 & 0.25 & 0.25 & 0\\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25\\ 0 & 0 & 0.25 & 0.5 & 0.75\\ \end{bmatrix}$
Now, depending on the values of $X_n$ and $A_{n+1}$, we split into different cases:
$X_n \leq 2$: $Y_{n+1}=0$ (one packet is dispatched so there remains at most one, and at most three are added so none need to be dismissed)
$X_n = 3$: $Y_{n+1} = 1$ if $A_{n+1}=3$ and $0$ otherwise (explanation is similar to that below)
$X_n = 4$: then we dispatch one packet, (three remain) and add $A_{n+1}$ of them, and dismiss all the packet but four: thus the number of packets dismissed is $0$ if $A_{n+1} \leq 1$, $1$ if $A_{n+1} = 2$, and $2$ if $A_{n+1}=3$.
Having written this all out, we can write:
$\mathbb{E}[Y_{n+1}|X_0=0] = \mathbb{E}[Y_{n+1}1(X_n \geq 3)|X_0=0]$ (as $Y_{n+1}1(X_n \leq 2)=0$) and then split by linearity over the values of $A_{n+1}$ and $X_n$:
$\mathbb{E}[Y_{n+1}|X_0=0]=\mathbb{E}[1(X_n=3,A_n=3)+(A_{n+1}-1)^+1(X_n=4)|X_0=0]$.
Now, $\sigma(A_{n+1})$ and $\sigma(X_0,\ldots,X_n)$ are independent, so by the properties of conditional expectations, $\mathbb{E}[1(X_n=3,A_n=3)|X_0=0] = \mathbb{E}[1(A_n = 3)]\mathbb{E}[1(X_n=3|X_0=0)] = P(A_{n+1} = 3)P(X_n=3|X_0=0)=\frac{1}{4}p^{(n)}_{3,0}$ (I'm using column vectors to be applied to transition matrices, hence possibly the index reversal).
Similarly, $$\mathbb{E}[(A_{n+1}-1)^+1(X_n=4)|X_0=0] = \mathbb{E}[(A_{n+1}-1)^+]\mathbb{E}[1(X_n=4)|X_0=0] = \frac{1}{4}\left((0-1)^++(1-1)^++(2-1)^++(3-1)^+\right)p^{(n)}_{4,0} = \frac{3}{4}p^{(n)}_{4,0},$$ which shows the final formula:
$$\mathbb{E}[Y_{n+1}|X_0=0] = \frac{1}{4}p^{(n)}_{3,0}+\frac{3}{4}p^{(n)}_{4,0},$$ which we wanted to show.