
























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 a Mallows distribution with parameter $q\in(0,1)$, so that higher ranked items tend to arrive later and lower ranked items tend to arrive sooner. In the classical problem, the asymptotically optimal strategy is to reject the first $M_n^*$ items, where $M_n^*\sim\frac ne$, and then to select the first item ranked higher than any of the first $M_n^*$ items (if such an item exists). This yields $\frac1e$ as the limiting probability of success. The Mallows distribution with parameter $q=1$ is the uniform distribution. For the regime $q_n=1-\frac cn$, with $c>0$, the case of weak bias, the optimal strategy occurs with $M_n^*\sim n\Big(\frac1c\log\big(1+\frac{e^c-1}e\big)\Big)$, with the limiting probability of success being $\frac1e$. For the regime $q_n=1-\frac c{n^α}$, with $c>0$ and $α\in(0,1)$, the case of moderate bias, the optimal strategy occurs with $n-M_n\sim\frac{n^α}c$, with the limiting probability of success being $\frac1e$. For fixed $q\in(0,1)$, the case of strong bias, the optimal strategy occurs with $M_n^*=n-L$ where $\frac{L-1}L<q\le \frac L{L+1}$, with limiting probability of success being $(1-q)q^{L-1}L>\frac1e$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。