2023/07/20 by Ross G. Pinsky, Pinsky, Ross G., Tomer Zilca +1
Computer Science · #60C05 #60G40 #Combinatorics (math.CO) #Cryptography and Data Security #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2307.10611
openalex publication_date 2023/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the classical secretary problem, n ranked items arrive one by one, and each item's rank relative to its predecessors is noted. The observer must select or reject each item as it arrives, with the object of selecting the item of highest rank. For Mn∈\0,1,⋯, n-1\, let S(n,Mn) denote the strategy whereby the observer rejects the first Mn items, and then selects the first later-arriving item whose rank is higher than that of any of the first Mn items (if such an item exists). If the ranked items arrive in a uniformly random order, it is well-known that the limiting optimal probability of success is \frac1e, which occurs if Mn∼\frac ne. It has been shown that when the ranked items arrive according to certain non-uniform distributions on the set of permutations, \frac1e serves as a lower bound for the optimal probability. There is a fundamental reason for this phenomenon. We consider certain distributions for which that reason does not apply. We begin by noting a cooked-up class of distributions for which S(n,M) yields the lowest possible probability of success -- namely \frac1n, for all M. We then consider the uniform distribution over all permutations avoiding a particular pattern of length three. In the case of the pattern 231 or 132, for any choice of Mn, the strategy S(n,Mn) yields the very same probability of success; namely (n+1)/(2(2n-1)), which gives a limiting probability of \frac14. For the pattern 213, the optimal strategy is obtained for M∈\0,1\, also yielding a limiting probability of \frac14. For the pattern 123, the optimal strategy is obtained for M=1, yielding a limiting probability of \frac34. For the other two patterns, 312 and 321, an optimal strategy will yield a limiting probability of at least \frac716.