×

The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution. (English) Zbl 1533.60054

Summary: We solve the secretary problem in the case that the ranked items arrive in a statistically biased order rather than in uniformly random order. The bias is given by the left-to-right minimum exponentially tilted distribution with parameter \(q \in (0, \infty)\). That is, for \(\sigma \in S_n\), the probability of \(\sigma\) is proportional to \(q^{\mathrm{LR}_{n}^{-}(\sigma)}\), where the left-to-right minimum statistic \(\mathrm{LR}^-_n\) is defined by \[ \mathrm{LR}^-_n (\sigma) =|\{j \in [n] : \sigma_j = \min\{\sigma_i: 1 \leq i \leq j\}\}|, \,\,\sigma \in S_n.\] For \(q \in (0,1)\), higher ranked items tend to arrive earlier than in the case of the uniform distribution, and for \(q \in (1, \infty)\), they tend to arrive later, where the highest ranked item is denoted by 1 and the lowest ranked item is denoted by \(n\). In the classical problem, the asymptotically optimal strategy is to reject the first \(M_n^\ast\) items, where \(M_n^\ast \sim \frac{n}{e}\), and then to select the first item ranked higher than any of the first \(M_n^\ast\) items (if such an item exists). This yields \(e^{-1}\) as the limiting probability of success. With the above bias on arrivals, and for the parameter \(q=q_n\) depending on \(n\), we calculate the asymptotic behavior of the optimal strategy \(M_n^\ast\) and the corresponding limiting probability of success, for all regimes of \(\{q_n\}^\infty_{n=1}\). In particular, if the leading order asymptotic behavior of \(\{q_n\}^\infty_{n=1}\) is at least \(\frac{1}{\log n}\), and if also its order is no more than \(o(n)\), then the limiting probability of success logn when using an asymptotically optimal strategy is \(e^{-1}\); otherwise, this limiting probability of success is greater than \(e^{-1}\). Also, the limiting fraction of numbers, \(\lim_{n \rightarrow \infty} \frac{M_{n}^{\ast}}{n}\), that are summarily rejected by an asymptotically optimal strategy lies in \((0,1)\) if and only if \(\lim_{n \rightarrow \infty} q_n \in (0, \infty)\).

MSC:

60G40 Stopping times; optimal stopping problems; gambling theory
60C05 Combinatorial probability

References:

[1] Arratia, R., Barbour, A. D., and Tavaré, S. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich (2003). ISBN 3-03719-000-0. MR2032426. · Zbl 1040.60001
[2] Bóna, M. Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, second edition (2012). ISBN 978-1-4398-5051-0. MR2919720. · Zbl 1255.05001
[3] Bruss, F. T. Sum the odds to one and stop. Ann. Probab., 28 (3), 1384-1391 (2000). MR1797879. · Zbl 1005.60055
[4] Ferguson, T. S. Who solved the secretary problem? Statist. Sci., 4 (3), 282-296 (1989). MR1015277. Freeman, P. R. The secretary problem and its extensions: a review. Internat. Statist. Rev., 51 (2), 189-206 (1983). MR715534.
[5] Gilbert, J. P. and Mosteller, F. Recognizing the maximum of a sequence. J. Amer. Statist. Assoc., 61, 35-73 (1966). MR198637.
[6] Gnedin, A. and Derbazi, Z. Trapping the Ultimate Success. Mathematics, 10 (1), paper 158 (2022). DOI: 10.3390/math10010158. · doi:10.3390/math10010158
[7] Gnedin, A. V. and Krengel, U. A stochastic game of optimal stopping and order selection. Ann. Appl. Probab., 5 (1), 310-321 (1995). MR1325055. · Zbl 0824.62079
[8] Kesselheim, T., Kleinberg, R., and Niazadeh, R. Secretary problems with non-uniform arrival order. In STOC’15-Proceedings of the 2015 ACM Symposium on Theory of Computing, pp. 879-888. ACM, New York (2015). MR3388268. · Zbl 1321.68516
[9] Pfeifer, D. Extremal processes, secretary problems and the 1/e law. J. Appl. Probab., 26 (4), 722-733 (1989). MR1025389. · Zbl 0693.60030
[10] Pinsky, R. G. Problems from the discrete to the continuous. Probability, number theory, graph theory, and combinatorics. Universitext. Springer, Cham (2014). ISBN 978-3-319-07964-6; 978-3-319-07965-3. MR3288081. · Zbl 1311.11002
[11] Pinsky, R. G. Comparing the inversion statistic for distribution-biased and distribution-shifted permutations with the geometric and the GEM distributions. ALEA Lat. Am. J. Probab. Math. Stat., 19 (1), 209-229 (2022a). MR4359791. · Zbl 1480.60014
[12] Pinsky, R. G. The secretary problem with biased arrival order via a Mallows distribution. Adv. in Appl. Math., 140, Paper No. 102386, 9 (2022b). MR4440077. · Zbl 1492.60103
[13] Pitman, J. and Tang, W. Regenerative random permutations of integers. Ann. Probab., 47 (3), 1378-1416 (2019). MR3945749. · Zbl 1414.05019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.