Secretary Problem

Relevant wiki: Conditional Probability

When sample size is $r$ , the probability of selecting the best applicant is

$\begin{aligned} p_r&=\sum_{j=r+1}^6P(j^\text{th}\text{ applicant is best and the administrator selects it}) \\&=\sum_{j=r+1}^6P(j^\text{th}\text{ applicant is best})\,P(\text{the administrator selects }j^\text{th }\text{applicant}\,|\,j^\text{th}\text{ applicant is best}) \\&=\sum_{j=r+1}^6P(j^\text{th}\text{ applicant is best})\,P(\text{the best of the first }j-1\text{ applicants is in the first }r\text{ applicants}) \\&=\sum_{j=r+1}^6\left(\frac 16\right)\left(\frac r{j-1}\right) =\left(\frac r6\right)\sum_{j=r+1}^6\frac 1{j-1} \end{aligned}$

Therefore, we get

The table above shows that the optimal sample size is $\boxed2$ .

---

Try Secretary Problem 2 .

Here is an alternative conditional probability approach. If the sample is of size $m$ , let $M_m$ be the maximum score of the candidates in the sample. Then $P[M_m=j] \; = \; \frac{\binom{j-1}{m-1}}{\binom{6}{m}} \hspace{2cm} m \le j \le 6$ Let $A_m$ be the event that the best candidate is selected, given a sample of size $m$ . If $M_m=6$ , the probability of $A_m$ is $0$ . If $M_m=j$ , where $m \le j \le 5$ , then there are $6-j$ candidates left who rank better than the top score of the sample, and $A_m$ only occurs if the best of these remaining candidates is interviewed before the other $5-j$ . Thus $P[A_m|M_m=j] \; = \; \left\{ \begin{array}{lll} 0 & \hspace{1cm} & j = 6 \\ \frac{1}{6-j} & & m \le j \le 5 \end{array}\right.$ and hence $P[A_m] \; = \; \sum_{j=m}^5 \frac{\binom{j-1}{m-1}}{(6-j)\binom{6}{m}}$ The values of $P[A_m]$ for $m=1,2,3,4$ are $\tfrac{274}{720}$ , $\tfrac{308}{720}$ , $\tfrac{282}{720}$ , $\tfrac{216}{720}$ , making the optimal sample size $\boxed{2}$ .