4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is "$A_n$"? Is it a process independent of $(X_n)$? $\endgroup$ – whuber Apr 3 '20 at 11:40
  • $\begingroup$ @whuber I have edited the post. $X_n$ is the amount of packets in a buffer with capacity $K = 4$. Is that clarifying? $\endgroup$ – The Pointer Apr 3 '20 at 11:45
  • $\begingroup$ Almost: exactly how is the process $X_n$ related to $A_n$? $\endgroup$ – whuber Apr 3 '20 at 11:52
  • 1
    $\begingroup$ @whuber Oh, I see. It is not a typographical error. My apologies; I am a novice to this. $\endgroup$ – The Pointer Apr 3 '20 at 14:33
  • 1
    $\begingroup$ @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. $\endgroup$ – The Pointer Apr 4 '20 at 4:01
3
+100
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – The Pointer Apr 6 '20 at 22:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – Siong Thye Goh Apr 7 '20 at 2:15
  • $\begingroup$ 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). $\endgroup$ – The Pointer Apr 7 '20 at 19:20
  • 1
    $\begingroup$ 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$. $\endgroup$ – Siong Thye Goh Apr 8 '20 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.