The Secretary Problem with a Stochastic Signal

Learning-augmented approaches to the secretary problem typically use value estimates, rank predictions, or explicit recommendations. We study advice conveyed solely through timing: a content-free stochastic signal that arrives no later than the best of $n$ items. Under uniformly random arrival order, we characterize the exact finite-$n$ optimal policy and success probability for arbitrary known signal distributions, assuming independence of the signal and relative order conditional on the best item's position. For the $\alpha$-power family, where increasing $\alpha$ shifts the signal towards the best item's arrival, we derive optimal threshold policies and closed-form asymptotics. Specifically, the limiting success probability exceeds the classic $\frac{1}{e}$ benchmark for every $\alpha >0$, equals $\frac{1}{2}$ for the uniform case $\alpha =1$, and approaches $1$ as $\alpha \to \infty$. We quantify robustness to misspecifying $\alpha$ by showing that conservative estimates preserve the classic $\frac{1}{e}$ benchmark asymptotically. Under adversarial arrival order, we determine the exact worst-case guarantees for the $\alpha$-power family, including constant success probabilities when $\alpha =\Theta (n)$.