IS_Math-2020-03

IS Math-2022-03

题目来源：Problem 3 日期：2024-07-07 题目主题：Math-概率论

具体题目

Consider hiring the best part-time worker by interviewing $n$ applicants, where $n\ge 2$. It is assumed that the absolute ranking (rank 1, rank 2, $\dots$, rank $n$) of the applicants is determined in advance, and that the relative ranking of the applicants already interviewed is available. The applicants are interviewed one by one, but the order of applicants is random and unknown. In the selection process, the decision to accept or reject an applicant is based on the relative ranking of the applicants already interviewed, and the following conditions are imposed:

• Immediately after an interview, the interviewed applicant is either accepted or rejected.
• Once an applicant is accepted, the selection process terminates.
• Previously rejected applicants cannot be recalled or accepted.
• If no applicants are accepted in the first $n-1$ interviews, the $n$-th applicant is accepted unconditionally.

Suppose that we use the following hiring strategy, where $1<r\le n$.

• Reject the first $r-1$ applicants unconditionally.
• Hereafter, accept the first subsequent applicant who is better than the best applicant among the above $r-1$ applicants (the applicant with the relative rank 1).

Let $P_n(r)$ be the probability of accepting the applicant with the absolute rank 1 in this strategy. Answer the following questions.

1. Calculate $P_4(2)$.
2. Show that $P_{10}(3)=\frac{2}{10}\times \left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{9}\right)$.
3. Derive the probability of accepting the applicant with the absolute rank 1 among $n$ applicants at the $k$-th interview. Note that $r\le k\le n$.
4. Consider the following recursive relation

$$P_n(r)=\left[A\right]+\left[B\right]\times P_n(r+1).$$

Express $A$ and $B$ by $n,r$ and some constants.

5. Let $q=\frac{r}{n}$. Explain that $P_n(r)$ approximately becomes $-q\ln q$ when $n$ is large enough. Moreover, calculate the value of $q\in (0,1]$ that maximizes $-q\ln q$. Note that $\ln$ stands for natural logarithm.

正确解答

1. Calculate $P_4(2)$

To calculate $P_4(2)$, we follow the strategy of rejecting the first $r-1=1$ applicant unconditionally and then accepting the first applicant who is better than the best applicant among the first 1 applicant.

• The absolute rank 1 applicant must appear in positions 2, 3, or 4 for us to accept them, as we reject the first applicant.

Let’s consider the possible scenarios:

1. If the rank 1 applicant appears in position 2, they are accepted immediately.
2. If the rank 1 applicant appears in position 3, they are accepted if the applicant in position 2 is worse than the applicant in position 1.
3. If the rank 1 applicant appears in position 4, they are accepted if the best applicant among the first three is worse than the applicant in position 1.

We calculate the probabilities for each scenario:

• Probability of rank 1 being in position 2: $\frac{1}{4}$
• Probability of rank 1 being in position 3: $\frac{1}{4}\times \frac{1}{2}=\frac{1}{8}$ (half the time, the applicant in position 2 is worse than the applicant in position 1)
• Probability of rank 1 being in position 4: $\frac{1}{4}\times \frac{1}{3}=\frac{1}{12}$ (one third of the time, the best applicant among the first three is worse than the applicant in position 1)

Adding these probabilities:

$$P_4(2)=\frac{1}{4}+\frac{1}{8}+\frac{1}{12}=\frac{11}{24}$$

2. Show that $P_{10}(3)=\frac{2}{10}\times \left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{9}\right)$

For $P_{10}(3)$, we reject the first $2$ applicants unconditionally and then accept the first subsequent applicant who is better than the best applicant among the first $2$ applicants. The absolute rank 1 applicant must appear in positions $3,4,\dots ,10$ for us to accept them.

The probability of the absolute rank 1 applicant being accepted when appearing in position $k$ is:

$$\frac{2}{k-1}$$

because the rank 1 applicant must be better than the best of the first $2$ applicants, and this has to hold for positions $3,4,\dots ,10$.

Summing these probabilities for $k=3$ to $10$:

$$P_{10}(3)=\sum _{k=3}^{10}\frac{2}{k-1}\cdot \frac{1}{10}=\frac{2}{10}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}\right)$$

3. Derive the probability of accepting the applicant with the absolute rank 1 among $n$ applicants at the $k$-th interview

The probability of accepting the absolute rank 1 applicant at the $k$-th interview, where $r\le k\le n$, is the probability that the rank 1 applicant appears in position $k$ and is better than all the first $r-1$ applicants. This can be expressed as:

$$P(\text{accept at }k)=\frac{1}{n}\times \frac{r-1}{k-1}$$

where $\frac{1}{n}$ is the probability that the rank 1 applicant is in position $k$, and $\frac{r-1}{k-1}$ is the probability that the best of the first $r-1$ applicants is better than others of the first $k-1$ applicants.

Summing this for all possible $k$:

$$P_n(r)=\sum _{k=r}^n\frac{1}{n}\times \frac{r-1}{k-1}=\frac{r-1}{n}\sum _{k=r}^n\frac{1}{k-1}$$

4. Express $A$ and $B$ by $n,r$ and some constants

Given the recursive relation:

$$P_n(r)=[A]+[B]\times P_n(r+1)$$

We need to express $A$ and $B$ in terms of $n$, $r$, and constants. From the previous derivation, we know:

$$P_n(r)=\frac{r-1}{n}\sum _{k=r}^n\frac{1}{k-1}$$

For $P_n(r+1)$:

$$P_n(r+1)=\frac{r}{n}\sum _{k=r+1}^n\frac{1}{k-1}$$

Using the recursive relation:

$$P_n(r)=\frac{r-1}{n}\sum _{k=r}^n\frac{1}{k-1}=\frac{r-1}{n}\left(\frac{1}{r-1}+\sum _{k=r+1}^n\frac{1}{k-1}\right)=\frac{r-1}{n}\frac{1}{r-1}+\frac{r-1}{n}\sum _{k=r+1}^n\frac{1}{k-1}=\frac{1}{n}+\frac{r-1}{r}\times P_n(r+1)$$

Thus, $A$ and $B$ can be identified as:

$$A=\frac{1}{n},B=\frac{r-1}{r}$$

5. Approximation of $P_n(r)$ as $-q\ln q$ and maximizing $-q\ln q$

Let $q=\frac{r}{n}$. When $n$ is large, the sum ${\sum }_{k=r+1}^n\frac{1}{k-1}$ can be approximated by the integral:

$$\sum _{k=r+1}^n\frac{1}{k-1}\approx {\int }_r^n\frac{1}{x}\mathrm{d}x=\ln n-\ln r=\ln \frac{n}{r}$$

Then:

$$P_n(r)\approx \frac{r-1}{n}\ln \frac{n}{r}\approx \frac{r}{n}\ln \frac{n}{r}=q\ln \frac{1}{q}=-q\ln q$$

To find the value of $q$ that maximizes $-q\ln q$, we take the derivative and set it to zero:

$$\frac{\mathrm{d}}{\mathrm{d}q}(-q\ln q)=-\ln q-1=0$$ $$\ln q=-1$$ $$q=e^{-1}=\frac{1}{e}$$

So, the value of $q\in (0,1]$ that maximizes $-q\ln q$ is $\frac{1}{e}$.

知识点

概率论最优停止问题积分近似法递归

难点解题思路

这道题目的难点在于理解和推导递推关系式 $P_n(r)=[A]+[B]\times P_n(r+1)$，以及利用积分近似法进行大 $n$ 情况下的概率近似计算。

解题技巧和信息

对于类似的最优停止问题，可以通过以下步骤解决：

1. 分析问题条件和决策策略。
2. 计算特定情形下的概率。
3. 推导一般情形下的概率公式。
4. 使用递推关系进行简化和计算。
5. 在大规模情况下，使用积分近似进行计算。

重点词汇

accept 接受

reject 拒绝

probability 概率

optimal 最优的

strategy 策略

recursive 递归的

approximate 近似的

natural logarithm 自然对数

参考资料

1. Sheldon Ross, “A First Course in Probability”, Chapter 5: The Odds Algorithm
2. Thomas Ferguson, “Optimal Stopping and Applications”, Chapter 1: The Secretary Problem