##
**Perfect sampling for infinite server and loss systems.**
*(English)*
Zbl 1331.65025

From the text: “We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss system. We use a variation of dominated coupling from the past. We simulate a coupled stationary infinite server system backwards in time. We detect coalescence by observing a time interval on which all customers initially present in the infinite server system leave and no loss of customer occurs.”

“We summarize our contributions as follows:

(1) The design and analysis of the first exact sampling algorithm for the infinite server systems whose running time is shown to be basically linear in the arrival rate. This is essentially optimal, as the steady state of the infinite server systems, encoding the remaining service time of each customer, requires on average a vector which grows linearly in the arrival rate.

(2) The design and analysis of the first exact sampling algorithm for many-server loss systems under non-Markovian arrivals and in a heavy-traffic environment. In the quality-driven regime, where service utilization is strictly less than \(100 \%\), we show that our algorithm has sublinear coalescence time. In the quality-and-efficiency-driven regime, where service utilization converges to \(100 \%\) at a square root speed as a function of the arrival rate, we show that our algorithm has subexponential coalescence time.”

“We summarize our contributions as follows:

(1) The design and analysis of the first exact sampling algorithm for the infinite server systems whose running time is shown to be basically linear in the arrival rate. This is essentially optimal, as the steady state of the infinite server systems, encoding the remaining service time of each customer, requires on average a vector which grows linearly in the arrival rate.

(2) The design and analysis of the first exact sampling algorithm for many-server loss systems under non-Markovian arrivals and in a heavy-traffic environment. In the quality-driven regime, where service utilization is strictly less than \(100 \%\), we show that our algorithm has sublinear coalescence time. In the quality-and-efficiency-driven regime, where service utilization converges to \(100 \%\) at a square root speed as a function of the arrival rate, we show that our algorithm has subexponential coalescence time.”

Reviewer: Rózsa Horvàth-Bokor (Budakalász)

### MSC:

65C50 | Other computational problems in probability (MSC2010) |

65C05 | Monte Carlo methods |

60K25 | Queueing theory (aspects of probability theory) |