# Markov chain discrete-time queue example

I have the following Markov chain example:

Items arrive for processing during intervals $$(0, 1), (1, 2), \dots$$

$$A_n$$ is the number of arrivals during $$(n - 1, n), n = 1, 2, \dots$$

Assume the $$A_n$$ are i.i.d. with pmf $$a_j = P(A_n = j), j = 0, 1, \dots$$

Let $$b_i = P(A_n \ge i) = \sum_{j \ge i} a_j .$$

Arriving items queue in order of arrival in a buffer with capacity $$K \ge 1$$, with arbitrary ordering for simultaneous arrivals.

Arrivals to a full buffer are lost.

A single server dispatches one item at a time $$n$$, if any are waiting.

Let $$X_n$$ denote the buffer level at time $$n$$, just before dispatch.

$$S = \{ 0, 1, \dots, K \}$$

Checking the Markov property

If $$X_n = 0$$, there is no dispatch at $$n$$, and the number in the buffer at time $$n + 1$$ is the number of arrivals during $$(n, n + 1)$$ that can fit into the buffer.

i.e., $$X_{n + 1} = \min(A_{n + 1}, K)$$

I don't understand how it makes sense to have $$X_{n + 1} = \min(A_{n + 1}, K)$$. I would greatly appreciate it if someone would please take the time to clarify this.

This property is a formula that says: "Arrivals to a full buffer are lost". However, there seems to be something missing here to make everything correct, it seems to me that this should read,

$$X_{n+1} = \text{min}\left(X_{n} + A_{n+1}, K\right)$$

That is, the number of items at time n+1 equals the previous number of items plus the number of arrivals, or the maximum capacity if that's smaller.

• Thanks for the answer, but I think your are incorrect. See my answer. Mar 13, 2020 at 3:38
• Right, I didnt' read correctly, but if you assume $X_n$ equals zero, but then the formulas are equivalent. Except for the minus one, which appears in the second example.
– Gijs
Mar 13, 2020 at 8:43
• Thanks for the answer anyway Mar 13, 2020 at 9:09

I found an analogous, less contrived, version of this example (in fact, based on the completeness and coherency of the example, it's probably the original version) from the textbook Introduction to Modeling and Analysis of Stochastic Systems, second edition, by Kulkarni:

Example 2.8. (Telecommunications). The Tel-All Switch Corporation manufactures switching equipment for communications networks. Communication networks move data from switch to switch at lightning-fast speed in the form of packets; i.e., strings of zeros and ones (called bits). The Tel-All switches handle data packets of constant length; i.e., the same number of bits in each packet. At a conceptual level, we can think of the switch as a storage device where packets arrive from network users according to a random process. They are stored in a buffer with the capacity to store $$K$$ packets and are removed from the buffer one-by-one according to a pre-specified protocol. Under one such protocol, time is slotted into intervals of fixed length, say a microsecond. If there is a packet in the buffer at the beginning of a slot, it is removed instantaneously. If there is no packet at the beginning of a slot, no packet is removed during the slot even if more packets arrive during the slot. If a packet arrives during a slot and there is no space for it, it is discarded. Model this as a DTMC.

Let $$A_n$$ be the number of packets that arrive at the switch during the $$n$$th slot. (Some of these may be discarded.) 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 slow, 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 pdf

$$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\{ A_{n + 1}, K \} = j \vert X_n = 0) \\ &= P(A_{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 - 1 + 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 and using the notation

$$b_j = \sum_{k = j}^\infty a_k,$$

we get the transition probability matrix

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