In this section, we provide an elegant construction of a queueing process based on a random walk.¹¹ If you don't like math, then you can skip this section. This serves two aims. The first is to show that queueing theory is essentially based on fundamental probabilistic concepts—the random walk—and its close relation to applications in finance, inventory, and insurance. The second goal is to show that it is very hard to characterize the transient behavior of a queueing process analytically. Thus, we will henceforth study queueing systems only in steady state, i.e., their long-run average limits; see Section 4.1.

In the construction of discrete-time queueing processes as set out in Section 2.1, we consider two sequences of iid rvs: arrivals \(\{a_k\}\) and capacities \(\{c_k\}\) per period. The system size then satisfies \(L_k = [L_{k-1} +a_k- c_{k}]^+\). The \([\cdot]^{+}\) operator complicates computations. Removing it yields a related stochastic process \(\{Z_k, k=0,1,\ldots\}\) defined by

\begin{equation*} Z_k = Z_{k-1} + a_k - c_k. \tag{2.4.1} \end{equation*}

In fact, \(\{Z_k\}\) is a random walk, since \(Z_{k}\) makes a jump of size \(a_k-c_k\), where \(\{a_k-c_k\}\) forms a sequence of iid rvs. Observe that \(\{Z_k\}\) is `free'—it can take positive and negative values—while \(\{L_{k}\}\) is restricted to non-negative integers.

It is useful to express \(\{\L_k\}\) in terms of \(\{Z_k\}\). From Eq. (2.4.1), we have \(a_k - c_k = Z_k - Z_{k-1}\), hence

\begin{equation*} L_k = [L_{k-1} +a_k- c_{k}]^+ = [L_{k-1} +Z_k- Z_{k-1}]^+. \end{equation*}

It follows that \(L_k - Z_{k} = \max\{\L_{k-1} - Z_{k-1}, -Z_k\}\), and by iterating the recursion,²² Opt 2.4.1.

\begin{equation*} L_k = Z_k - \left(\min_{1\leq i \leq k} Z_i\right)\wedge 0, \tag{2.4.2} \end{equation*}

where \(a\wedge b := \min\{a,b\}\).

This recursion for \(L_k\) yields instructive plots. In Fig. 1, let \(a_k \sim \Bern{0.3}\) and \(c_k \sim \Bern{0.4}\). We clearly see that \(L_k = Z_k - \min_{i\leq k} \{Z_{i}\}\). In Fig. 2, \(a_k\sim \Bern{0.49}\) so that the random walk satisfies

\begin{equation*} Z_k = Z_{k-1} + 2 a_k -1. \tag{2.4.3} \end{equation*}

Thus, if \(a_k=1\), the random walk increases by one, while if \(a_k=0\), the random walk decreases by one, so \(Z_k \neq Z_{k-1}\) always. This differs slightly from Eq. (2.4.1), where \(Z_{k}=Z_{k-1}\), if \(a_k=c_k\).

What can we say about the transient (time-dependent) behavior of \(\{\L_k\}\)? To gain insight, suppose \(a_k\sim \Pois{\lambda}\) and \(c_k \sim \Pois{\mu}\).

\begin{equation*} Z_k = Z_0+N_{\lambda, k} - N_{\mu, k}. \end{equation*}

Writing \(Z_0=m\), one can show³³ Opt 2.4.2. that⁴⁴ Unlike their sum, the difference of two Poisson rvs is not Poisson.

\begin{equation*} \PP{m}{Z_k=n} = e^{-(\lambda+\mu)k} (\lambda k)^{n-m} \sum_{j=0}^\infty \frac{(\lambda\mu k^2)^j} {j!(n-m+j)!}. \tag{2.4.4} \end{equation*}

Formally, one could derive the distribution of \(L_{k}\) from this and Eq. (2.4.2), but no simple expression results. Consequently, no tractable expressions exist for \(\P{L_k=n}\) as a function of \(n\).

Interestingly, \(\{L_k\}\) is among the simplest transient queueing system to analyze; most others are far more complex. For this reason, we henceforth focus on the steady-state regime, i.e., the limit as \(t\to\infty\).