Winning the Hand of the Princess SaralindaP. 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 αn1/2 suitors present at time 0 with no additional arrivals. We also obtain large deviations results that depend on the full interarrival-time distribution. |