The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution
Ross G. Pinsky · Latin American Journal of Probability and Mathematical Statistics · 2023
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 ∈ (0, ∞).That is, for σ ∈ S n , the probability of σ is proportional to q LR - n (σ) , where the left-to-right minimum statistic LR - n is defined by LR - n (σ) = |{j ∈ [n] : σ j = min{σ i : 1 ≤ i ≤ j}}|, σ ∈ S n .For q ∈ (0, 1), higher ranked items tend to arrive earlier than in the case of the uniform distribution, and for q ∈ (1, ∞), 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 items, where M * n ∼ n e , and then to select the first item ranked higher than any of the first M * n 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 and the corresponding limiting probability of success, for all regimes of {q n } ∞ n=1 .In particular, if the leading order asymptotic behavior of {q n } ∞ n=1 is at least 1 log n , and if also its order is no more than o(n), then the limiting probability of success 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→∞ M * n n , that are summarily rejected by an asymptotically optimal strategy lies in (0, 1) if and only if lim n→∞ q n ∈ (0, ∞).