Large deviations and fluid approximations in control of stochastic systems

R.R. Weber, In F.P. Kelly, editor, Probability Statistics and Optimization, a Tribute to Peter Whittle, pages 159-171. Wiley, 1994.

Abstract

Large deviation and fluid approximations can provide valuable insight to the
behaviour of stochastic systems.  This paper summarises some of the key ideas
and discusses a number of examples, including a probabilistic analysis of the
first-fit decreasing bin packing algorithm, and comments on ideas of Whittle
relating to risk-sensitive control of Markov processes.  In a final example, a
large deviations analysis is used to estimate the frequency of overflow when a
number of stationary traffic sources are routed through a switch with a finite
buffer.  we show that the buffer overflow frequency is asymptotically less that a
specified amount if an only if the sum of the effective bandwidths for the
different traffic sources is less than the bandwidth of the switch and we
suggest a simple approximation for these effective bandwidths.

back to list of papers