Secretary Problems with Random Number of Candidates: How Prior Distributional Information Helps

We study variants of the secretary problem, where $N$, the number of candidates, is a random variable, and the decision maker wants to maximize the probability of success -- picking the largest number among the $N$ candidates -- using only the relative ranks of the candidates revealed so far. We consider three forms of prior information about $\mathbf p$, the probability distribution of $N$. In the full information setting, we assume $\mathbf p$ to be fully known. In that case, we show that single-threshold type of strategies can achieve $1/e$-approximation to the maximum probability of success among all possible strategies. In the upper bound setting, we assume that $N\leq \overline{n}$ (or $\mathbb E[N]\leq \barμ$), where $\bar{n}$ (or $\barμ$) is known. In that case, we show that randomization over single-threshold type of strategies can achieve the optimal worst case probability of success of $\frac{1}{\log(\bar{n})}$ (or $\frac{1}{\log(\barμ)}$) asymptotically. Surprisingly, there is a single-threshold strategy (depending on $\overline{n}$) that can succeed with probability $2/e^2$ for all but an exponentially small fraction of distributions supported on $[\bar{n}]$. In the sampling setting, we assume that we have access to $m$ samples $N^{(1)},\ldots,N^{(m)}\sim_{iid} \mathbf p$. In that case, we show that if $N\leq T$ with probability at least $1-O(ε)$ for some $T\in \mathbb N$, $m\gtrsim \frac{1}{ε^2}\max(\log(\frac{1}ε),ε\log(\frac{\log(T)}ε))$ is enough to learn a strategy that is at least $ε$-suboptimal, and we provide a lower bound of $Ω(\frac{1}{ε^2})$, showing that the sampling algorithm is optimal when $ε=O(\frac{1}{\log\log(T)})$.