寻找第一本稀有书

The Elusive Book

专题: Algorithmic Programming / 算法编程
难度: L6
来源: QuantQuestion

题目详情

一排共有 52 个书架，其中只有 4 个书架含有某本稀有书。访问者从上到下逐个检查书架，直到第一次找到该书。

问：期望需要检查多少个书架才能找到第一本？

In the grand library of Bibliopolis, there are 52 shelves of books in a particular section. Only four of these shelves contain a rare book titled "The Secrets of Bibliopolis". A visitor, unfamiliar with the library, starts examining one shelf at a time, from top to bottom, searching for this elusive book. On average, how many shelves does the visitor need to examine before finding the first copy of "The Secrets of Bibliopolis"?

解析

把含书的 4 个位置视为在 52 个位置中均匀随机。

设最先出现的含书位置为第 $T$ 个书架，则 $T$ 是 4 个位置的最小值，其期望为经典结果：

E[T]=\frac{52+1}{4+1}=\frac{53}{5}=10.6.

Original Explanation

To determine the expected shelf position for the book:

For the first copy of the book to be on the $i$ th shelf, the first $i - 1$ shelves should not contain the book, and the $i$ th shelf should have it.
The probability that the first $i - 1$ shelves don’t have the book is:

\frac{52 - 4}{52} \times \frac{52 - 5}{52 - 1} \times \cdots \times \frac{52 - (i - 1)}{52 - (i - 2)}

The probability that the $i$ th shelf has the book is:

\frac{4}{52 - (i - 1)}

The expected value is the sum over all possible shelf positions $i$ of the product of $i$ and the probability that the first book is on the $i$ th shelf.

Python Code

expected_value = 0
for i in range(1, 53):
    # Probability that first i-1 shelves don’t have the book
    prob_no_book = 1
    for j in range(i - 1):
        prob_no_book *= (48 - j) / (52 - j)
    # Probability that ith shelf has the book
    prob_book = 4 / (52 - i + 1)
    expected_value += i * prob_no_book * prob_book

print(expected_value)