This is a classic problem in probability and combinatorics, not necessarily tied to mathematical finance or being a wall quant, first let’s define the problem and state the general strategy.
The warden takes one prisoner out of the cell each day, chosen at random with replacement (meaning each prisoner has an equal chance of being chosen every day, regardless of how many times they have been chosen before). There is a common room with one light bulb, initially turned off, that the prisoner can choose to toggle (switch on or off) or leave unchanged. The goal is to find a strategy that guarantees that once every prisoner has been to the common room at least once, eventually they will all know this fact.
Here’s the strategy:
1. Nominate one prisoner as the "counter."
2. Every prisoner (excluding the counter) follows this rule: If the light bulb is off when they enter the room for the first time, they turn it on, but only once. After that, they never turn the light bulb on again.
3. The counter’s job is to turn the light bulb off when he sees it on and count the number of times he has done this.
4. Once the counter has turned off the light bulb 99 times, he declares that every prisoner has been to the room at least once.
Now let’s analyze this strategy’s correctness and efficiency.
Correctness:
The key to the strategy is that a non-counter prisoner turns the light bulb on only once, the first time they see it off. Therefore, each non-counter prisoner makes exactly one "contribution" towards the counter’s count. Once the counter has counted to 99, it means all the non-counter prisoners have made their contributions, so they must have been to the common room at least once.
Efficiency:
While it’s impossible to determine the exact number of days this strategy will take (since it depends on the random sampling of prisoners), we can calculate the expected number of days. Let En be the expected number of days for the counter to reach a count of n.
The probability that the counter is picked on a given day is $\frac{1}{100}$. If he finds the light bulb on, he knows another prisoner who hasn’t toggled the light yet was picked on one of the previous days. There are 100 − n − 1 such prisoners, and the probability that one of them was picked on previous day is $\frac{100 - n - 1}{100}$.
The probability for the counter to find the light bulb on and increase his count by one is $\frac{1}{100} \cdot \frac{100 - n - 1}{100} = \frac{100 - n - 1}{100^2}$. Therefore,
$$E_n = \frac{100^2}{100 - n - 1}$$
To find the total expected number of days, sum up En for n going from 0 to 98:
$$E_{total} = \sum_{n=0}^{98} \frac{100^2}{100 - n - 1} = 100^2 \sum_{n=0}^{98} \frac{1}{100 - n - 1}$$
While a closed-form expression for this harmonic number series does not exist, we can approximate it by using the integral of logarithmic function:
$$\sum_{n=0}^{98} \frac{1}{100 - n - 1} \approx \int_{0}^{99} \frac{dx}{100 - x} = \ln \frac{100}{1} = \ln{100}$$
So, the total expected number of days:
Etotal ≈ 1002 ⋅ ln 100 ≈ 46000
Hence, in about 46,000 days, this strategy guarantees that all prisoners know that all of them have visited the common room at least once.