## Winning the Hand of the Princess Saralinda
*P. W. Glynn and W. Whitt*
*Applied Probability and Stochastic Processes* [J.G. Shanthikumar, U. Sumita, eds.] Kluwer Academic Publishers, Boston, 231-246 (1999)
Suitors come to the castle in order to try to win the hand of the Princess Saralinda. The
first suitor to perform n amazing feats will succeed. If the number n of feats is large and the
times to perform the feats are all i.i.d., then how long is it before a suitor will win the hand
of the Princess? We develop asymptotics describing the distribution of this random time as
the number of feats gets large; e.g., we show that this time is of order nm-σ(n logn)^{1/2}, where
m and σ^{2} are the mean and variance of the time to perform a single feat, provided that the
time to perform a single feat has a finite moment generating function and the suitor arrival
process obeys a strong law of large numbers. The −(log n)^{1/2} term reflects the fact that there is
an arrival process of suitors instead of just one. The asymptotic effect of the arrival process
is equivalent to having αn^{1/2} suitors present at time 0 with no additional arrivals. We also
obtain large deviations results that depend on the full interarrival-time distribution. |