Conditional expectation for maximum function

Question

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}.$$

Answer 1

Great that you have the formula written explicitly

$$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}.$$

Here $K=4$, since we have $4$ slots.

Let's compute the conditional expected value of $Y_{n+1}$ given $X_n$.

If $X_n=0$, then $E[Y_{n+1}|X_n=0]=E[\max\{0, A_n-4\}|X_n=0]=0$ since $A_n \le 3$.

This is expected since the buffer was empty, we can't possibly reject any packet.

We should also obtain similar outcome for $X_n \in \{1,2\}$ as we have sufficient slots to accept those packets.

If $X_n =m$ where $m \in \{1,2\}$,

$$E[Y_{n+1}|X_n=m]=E[\max\{0, X_n-1+A_{n+1}-4\}|X_n=m]=E[\max\{0, m+A_{n+1}-5\}]=0$$

since $m+A_{n+1}-5\le 2+3-5 =0.$

Now, let's consider the case when $X_n=3$.

\begin{align}E[Y_{n+1}|X_n=3]&=E[\max\{0, 3-1+A_{n+1}-4\}]\\&=E[\max\{0, A_{n+1}-2\}]\\&=Pr(A_{n+1}=3) \\ &= \frac14 \end{align}

In english, if $X_n=3$, then after dispatching, you have two slots available, hence you will only reject at most one packet when $3$ packets arrive and that happens with probability $\frac14$.

Now, let's consider the case when $X_n=4$.

\begin{align}E[Y_{n+1}|X_n=4]&=E[\max\{0, 4-1+A_{n+1}-4\}]\\&=E[\max\{0, A_{n+1}-1\}]\\&=2Pr(A_{n+1}=3) + Pr(A_{n+1}=2) \\ &= \frac34 \end{align}

In english, if $X_n=4$, then after dispatching, you have $1$ slots available, hence you will can either reject $1$ packet when $2$ packets arrive or reject $2$ packets when $3$ packets arrive.

Now, to address the quantity that you are interested from the beginning, we will use the law of total expectation:

\begin{align} &E[Y_{n+1}|X_0=0]\\ &= E[Y_{n+1}|X_n \le 2] \cdot Pr(X_n \le 2|X_0=0] +E[Y_{n+1}|X_n =3] \cdot Pr(X_n =3|X_0=0] + E[Y_{n+1}|X_n =4] \cdot Pr(X_n =4|X_0=0]\\ &= 0 \cdot Pr(X_n \le 2|X_0=0] +\frac14 \cdot Pr(X_n =3|X_0=0] + \frac34 \cdot Pr(X_n =4|X_0=0]\\ &=\frac14 \cdot Pr(X_n =3|X_0=0] + \frac34 \cdot Pr(X_n =4|X_0=0]\\ &=\frac14 \cdot p_{0,3}^{(n)}+ \frac34 \cdot p_{0,4}^{(n)}\\ \end{align}