# SCS

## Seminar

### Simulation-based computation of the workload correlation function in a Lévy-driven queue

Mandjes, M; Glynn, P (Stanford; Amsterdam)
Wednesday 23 June 2010, 09:00-09.50

Seminar Room 1, Newton Institute

#### Abstract

In this paper we consider a single-server queue with Lévy input, and in particular its workload process $(Q_t)_{t\ge 0}$, focusing on its correlation structure. With the correlation function defined as $r(t):= {\mathbb C}{\rm ov}(Q_0,Q_t)/{\mathbb V}{\rm ar}\, Q_0$ (assuming the workload process is in stationarity at time 0), we first study its transform $\int_0^\infty r(t) e^{-\vartheta t}{\rm d}t$, both for the case that the Lévy process has positive jumps, and that it has negative jumps. These expressions allow us to prove that $r(\cdot)$ is positive, decreasing, and convex, relying on the machinery of completely monotone functions. For the light-tailed case, we estimate the behavior of $r(t)$ for $t$ large. We then focus on techniques to estimate $r(t)$ by simulation. Naive simulation techniques require roughly $(r(t))^{-2}$ runs to obtain an estimate of a given precision, but we develop a coupling technique that leads to substantial variance reduction (required number of runs being roughly $(r(t))^{-1}$). If this is augmented with importance sampling, it even leads to a logarithmically efficient algorithm. We present a set of simulation experiments, underscoring the superior performance of our techniques.

#### Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.