## Pages

### A tail probability estimate for the busy time in a discrete time queue

In this previous post, I wrote down some analysis of a discrete time queue where one customer is serviced per time unit (i.e., "minute"). If at the beginning of a minute, the queue is empty, a random number of customers arrives during the minute, and the distribution of this number is that of a random variable $A$. If at least one customer is already waiting, the number of new customers is distributed like a random variable $B$. All arrivals are assumed to be independent. In other words, if the length of the queue at the beginning of minute $t$ (a nonnegative integer), is denoted by $Q(t)$, we have the following

$Q(t+1) = \left\{\begin{array}{lll} Q(t) -1 + &B(t)&\text{ if } Q(t) > 0\\&A(t)&\text{ if } Q(t)=0,\end{array}\right.$

where the $A(t)$ are iid random variables distributed as $A$ and the $B(t)$ are iid random variables distributed as $B$. Moreover, $Q(0) = 0$.

As in the other post, we are interested in the busy time $X$ after the start, in other words, the time between 0 and the first return of $Q(t)$ to the state 0. I already argued that, if $h(z)$ is the probability generating function of this time, and $g_A(z)$ and $g_B(z)$, are the probability generating functions of $A$ and $B$, respectively, then the following is true

\begin{aligned} h(z) &= g_A( f(z) )\\ f(z) &= z\, g_B( f(z) )\end{aligned}

where $f(z)$ is the probability generating function of some other random variable, which is no longer of particular interest here.

In this post, I'd like to make some statements about properties of $X$, based on the system of equations for the probability generating function.

#### The mean

In the other post, we obtained the formula for the mean of $X$ as a consequence of the fact that $Q(t)$ is a stationary Markov chain, for which we could write down the probability that it is in state 0. Here, I'll use the probability generating function. We have to compute $h'(1)$. By the chain rule, we obtain

\begin{aligned}f'(z) &= g_B(f(z)) + z g_B'(f(z)) f'(z)\\h'(z) &= g_A'(f(z)) f'(z),\end{aligned}

and, assuming everything converges, we obtain

\begin{aligned}f'(1) &= 1 + g_B'(1) f'(z)\\h'(z) &= g_A'(1) \frac{1}{1-g_B'(1)}, \end{aligned}

where, to obtain the second equation, we solved the first one for $f'(1)$. With $\lambda := \mathbb E A$ and $\nu := \mathbb E B$, this is just what we obtained from the Markov chain. At this point, note that the desired convergence of the power series $f$ and $h$ is equivalent to them having finite means, plus Abel's theorem, possibly.

#### Tail inequality

Now I'd like to bound the probability that the server is busy for a very long time. For this, I will focus on specific distributions of $A$ and $B$, namely, I'll assume that both are Poisson distributions. Thus, the probability generating functions of $A$ and $B$ are the following:

\begin{aligned} g_A(z) &= e^{\lambda(z-1)} \\ g_B(z) &= e^{\nu(z-1)}. \end{aligned}

Hence, we obtain

\begin{aligned} h(z) &= e^{\lambda(f(z)-1)} \\ f(z) &= z\, e^{\nu(f(z)-1)}. \end{aligned}

The second equation can be rewritten as

$z = f(z) e^{\nu(1-f(z))}, \ \ \ \ \ (*)$

of course, so we have a nice expression for the inverse $f^{-1}$ of $f$. Given that we already have'' the probability generating functions, we will use the exponential moment method (= exponentiate + Markov + optimize) to bound the probability:

$\Pr[ X \ge \alpha ] = \Pr[ t^X \ge t^\alpha ] \le h(t)t^{-\alpha},$

which is valid for every $t \ge 1$, and $t$ is optimized at some point. The expression on the right is equal to

$h(t) t^{-\alpha} = e^{\lambda(f(t)-1) -\alpha\log t}.$

We now write $s := f(t)$ and use (*). Noting that $t > 0$ is equivalent to $s > 0$, we compute

\begin{aligned}\log \Pr[ X \ge \alpha ] &\le \lambda(s-1) -\alpha\log(s e^{\nu(1-s)}) = \lambda(s-1) - \alpha\log s - \alpha\nu(1-s) \\&= (s-1)(\lambda + \alpha \nu) - \alpha\log s.&(**)\end{aligned}

Now we optimize $s$ (later we'll have to make sure that for our choice of $s$, there really exists a $t \ge 1$). Noting that since for $s\to 0$ and $s\to\infty$ the expression (**) goes to infinity, we just have to take for $s$ the unique point where the derivative in (**) vanishes, which is

$\displaystyle s = \frac{\alpha}{\alpha\nu + \lambda}$.

Summarizing, we obtain the following estimate.
Proposition (Tail estimate for our discrete queue).

$\displaystyle \Pr[ X \ge \alpha ] \le \exp\left( \left( 1-\nu - \log \frac{\alpha}{\alpha\nu + \lambda} \right)\alpha - \lambda\right).$

Now, with $\alpha\to\infty$, the term under the logarithm tends to $1/\nu$, and $\log(1/\nu) < \nu-1$ because of $\nu < 1$, so that there exist $\epsilon > 0$ (depending on $\nu$) and $\alpha_0$ (depending on both $\lambda$ and $\nu$) such that $1 - \nu - \log \frac{\alpha}{\alpha\nu + \lambda} \le -\epsilon$ for all $\alpha \ge \alpha_0$. Consequently, the bound in the proposition is essentially linear, i.e., for these $\alpha$ we have
Corollary.

$\Pr[ X \ge \alpha ] \le e^{-\Theta(\alpha)}$.

We still have to verify that our choice for $s$ is feasible, i.e., there must exist a $t \ge 1$ with $f(t) = s$. Let $t(s) := s e^{\nu(1-s)}$. A swift computation shows that $t'(s) > 0$ for $s < 1/\nu$. From elementary calculus we know that this implies that for these $s$, there exists a $t$ with $f(t) = s$. But our $s$ was $\frac{\alpha}{\alpha\nu + \lambda} < 1/\nu$ because $\lambda > 0$ (unless the queue were trivial). Moreover, we have

$\displaystyle t = s e^{\nu(1-s)} \ge s( 1 + \nu(1-s) ) = (1+\nu)s - \nu s^2 > 1$

where the last inequality holds whenever $1 < s < 1/\nu$ (because the two roots of the equation $(1+\nu)s -\nu s^2 =1$ are $s=1$ and $s=1/\nu$). By increasing $\alpha_0$ if necessary, we can assume that $s > 1$ holds.