# Conditional expectation for maximum function

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

• What is "$A_n$"? Is it a process independent of $(X_n)$?
– whuber
Apr 3, 2020 at 11:40
• @whuber I have edited the post. $X_n$ is the amount of packets in a buffer with capacity $K = 4$. Is that clarifying? Apr 3, 2020 at 11:45
• Almost: exactly how is the process $X_n$ related to $A_n$?
– whuber
Apr 3, 2020 at 11:52
• @whuber Oh, I see. It is not a typographical error. My apologies; I am a novice to this. Apr 3, 2020 at 14:33
• @whuber I also edited with the solution. So it's not so much that I'm interested in the solution itself -- it's the method and reasoning that led to the solution that I don't understand. Apr 4, 2020 at 4:01

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}

• Thanks for the answer, Siong! With regards to $n \in \{1,2\}$, do you mean $m \in \{1,2\}$? Also, in general, why does $E[\max\{ 0, X_n - 1 + A_{n+1} - 4 \} \vert X_n = m] = E[\max\{ 0, X_n - 1 + A_{n+1} - 4 \}]$? What happened to the conditional dependence in all of these equations in your answer? Apr 6, 2020 at 22:34
• You are right $m \in \{1,2\}$. In general we can write $E[Z|X]=E[Z]$ if $Z$ is independent of $X$. Hence $E[\max\{0, X_n-1+A_{n+1}-4|X_n=m]=E[\max\{0, m-1+A_{n+1}-4|X_n=m]=E[\max\{0, m-1+A_{n+1}-4]$ where in the last equality is due to we have $\max\{0, m-1+A_{n+1}-4$ is independent of $X_n$. Apr 7, 2020 at 2:15
• Thank you for the clarification. With regards to $=2Pr(A_{n+1}=3) + Pr(A_{n+1}=2)$, I understand that you said that, if 3 packets arrive, then we reject 2 packets, but I'm still finding it difficult to understand why it mathematically makes sense to have $2Pr(A_{n+1}=3)$ (the multiplication by $2$, that is). Apr 7, 2020 at 19:20
• when $A_{n+1}=3$, $\max\{0, A_{n+1}-1\}=\max\{0, 3-1\}=\max\{0,2\}=2$, hence we multiplied it by $2$. Apr 8, 2020 at 1:39