Skip to main content
1 of 2
The Pointer
  • 2.2k
  • 3
  • 29
  • 59

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

The Pointer
  • 2.2k
  • 3
  • 29
  • 59