Heavy traffic approximation

• Comment: Will try to find cause of "lengthy HTML comment" warning and fix. Also: This article about queuing theory needs more detail in order to confirm accuracy, as my initial impression. Am starting review now.FeralOink (talk) 06:09, 24 August 2012 (UTC)

---

Heavy Traffic Limit Theorem is also known as diffusion limit theorem, which is often used to approximate the queue-length process and workload process of a queuing system under the heavy traffic condition by using creative probability arguments on random walk, stochastic convergence and so on. In real life, many service organizations like call centers, restaurants and so on want to inform their customers about the waiting time.However, the queuing dynamics are complex and it is difficult to calculate the waiting time of the customers directly. The heavy traffic limit theorem can give a very simple approximation for the average waiting time of the customers during the peak time of the service organizations when the heavy traffic condition is satisfied. The limit result for the waiting time in queue of customers in the context of G/G/1 queue will be discussed below;

Heavy traffic condition

Let $\lambda _{n}$ and $\mu _{n}$ be the inter-arrival rate and the service rate for queue n respectively. The heavy traffic condition is given by

${\sqrt {n}}[\lambda _{n}-\mu _{n}]\rightarrow \theta$, as $n\rightarrow \infty$

Main results

Theorem 1. Consider a sequence of $G/G/1$ queues indexed by $j$.

For queue $j$

let $T_{j}$ denote the random inter-arrival time, $S_{j}$ denote the random service time;
let $\rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}$ denote the traffic intensity with ${\frac {1}{\lambda _{j}}}=E(T_{j})$ and ${\frac {1}{\mu _{j}}}=E(S_{j})$;
let $W_{q,j}$ denote the waiting time in queue for a customer in steady state;
Let $\alpha _{j}=-E[S_{j}-T_{j}]$ and $\beta _{j}^{2}=Var[S_{j}-T_{j}]$;

Suppose that $T_{j}{\xrightarrow {d}}T$, $S_{j}{\xrightarrow {d}}S$, and $\rho _{j}\rightarrow 1$. then

${\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}exp(1)$

provided that:

(a) $var[S-T]>0$
(b) for some $\delta >0$, $E[S_{j}^{2+\delta }]$ and $E[T_{j}^{2+\delta }]$ are both less than some constant $C$ for all $j$.

Heuristic argument

• Waiting time in queue

Let $U^{(n)}=S^{(n)}-T^{(n)}$ be the difference between the nth service time and the nth inter-arrival time;
Let $W_{q}^{(n)}$ be the waiting time in queue of the nth customer;

Then by definition:

$W_{q}^{(n)}=\max(W_{q}^{(n-1)}+U^{(n-1)},0)$

After recursive calculation, we have:

$W_{q}^{(n)}=\max(U^{(1)}+...+U^{(n-1)},U^{(2)}+...+U^{(n-1)},...,U^{(n-1)},0)$

• Random walk

Let $P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}$, with $U^{(i)}$ are i.i.d;
Define $\alpha =-E[U^{(i)}]$ and $\beta ^{2}=var[U^{(i)}]$;

Then we have

$E[P^{(k)}]=-k\alpha$

$var[P^{(k)}]=k\beta ^{2}$

$W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)}$;

we get $W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}$ by taking limit over $n$.

Thus the waiting time in queue of the nth customer $W_{q}^{(n)}$ is the supremum of a random walk with a negative drift.

• Brownian motion approximation

Random walk can be approximated by a Brownian motion when the jump sizes approach 0 and the times between the jump approach 0.

We have $P^{(0)}=0$ and $P^{(k)}$ has independent and stationary increments. When the traffic intensity $\rho$ approaches 1 and k approach to $\infty$ , we have $P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)$ after replaced k with continuous value t according to functional central limit theorem . Thus the waiting time in queue of the nth customer can be approximated by the supremum of a Brownian motion with a negative drift.

• Supremum of Brownian motion

Theorem 2. Let $X$ be a Brownian motion with drift $\mu$ and standard deviation $\sigma$ starting at the origin, and let $M_{t}=sup_{0\leq s\leq t}X(s)$

if $\mu \leq 0$

$lim_{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;$

otherwise

$lim_{t\rightarrow \infty }P(M_{t}\geq x)=1,x\geq 0.$

Conclusion

$W_{q}^{(\infty )}\thicksim \exp({\frac {2\alpha }{\beta ^{2}}})$ under heavy traffic condition

Thus, the heavy traffic limit theorem (Theorem 1) is heuristically argued.Formal proofs usually follow a different approach which involves characteristic functions (e.g. Kingman 1962a; Asmussen,2003,p.289).

Example

Consider an M/G/1 queue with arrival rate $\lambda$,the mean of the service time $E[S]={\frac {1}{\mu }}$, and the variance of the service time $var[S]=\sigma _{B}^{2}$. What is average waiting time in queue in the steady state?

The exact average waiting time in queue in steady state is give by:

$W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}$

The corresponding heavy traffic approximation:

$W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.$

The relative error of the heavy traffic approximation:

${\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}$

Thus when $\rho \rightarrow 1$, we have :

${\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0$.