  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{\mu}$), where $\bar{n}$
(or $\bar{\mu}$) 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{\mu})}$) 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(\epsilon)$
for some $T\in \mathbb N$, $m\gtrsim
\frac{1}{\epsilon^2}\max(\log(\frac{1}{\epsilon}),\epsilon
\log(\frac{\log(T)}{\epsilon}))$ is enough to learn a strategy that is at least
$\epsilon$-suboptimal, and we provide a lower bound of
$\Omega(\frac{1}{\epsilon^2})$, showing that the sampling algorithm is optimal
when $\epsilon=O(\frac{1}{\log\log(T)})$.
