What is the optimal strategy for the "100 prisoners problem" when waiting prisoners are told how many drawers the currently active prisoner has opened

Question

Introduction: A description of the original problem can be found on Wikipedia. The best strategy is: each prisoner opens the drawer with their number first and then each subsequent drawer is determined by the previously found number. With this strategy they only loose if there exists a cycle of length greater than $50$ (mapping numbers to drawers). As described in The malicious director variant, if the prisoners' numbers are not distributed randomly, but in a way that purposefully creates such a cycle of length greater than $50$, then the prisoners can counteract this by randomly relabeling the drawers.

I'm interested in a variant of the problem, where after a prisoner has finished opening drawers (successfully), all waiting prisoners are told how many drawers that prisoner just opened. The waiting prisoners could use this information to decide whether to relabel drawers or not.

If the first prisoner has opened $n$ drawers ($n \leq 50$), this means that there exists a cycle of length $n$ and the waiting prisoners now must determine the conditional probability that besides the cycle of length $n$ another cycle of length greater than $50$ exists; if that probability is larger than the original probability ($\sum_{k=51}^{100}\frac{1}{k}$), then they should relabel the drawers. Let $N$ be the numbers of prisoners ($N=100$), $A$ the event that a cycle of length $n\leq \frac{N}{2}$ is reported by the first prisoner and $B$ the event that a cycle of length greater than $\frac{N}{2}$ exists. Then the prisoners need to estimate:

$$ P(B|A) = \frac{P(A\cap B)}{P(A)} $$

To estimate $P(A)$, one can consider the number of permutations that create (at least one) such cycle compared to the total number of permutations ($N!$). This involves choosing $n$ out of $N$ drawers, then permuting their numbers arbitrarily as well as the numbers of all other drawers:

$$ P(A) = \frac{{N \choose n} n! (N-n)!\frac{1}{n}}{N!} = \frac{1}{n} $$

The factor $\frac{1}{n}$ in the numerator accounts for the fact that there are $n$ distinct permutations that produce the same cycle (just shifting the numbers from one drawer to the next). That result, however, doesn't seem to be correct since for $n=1$ the probability $P(A)$ would be $1$ which is wrong. So I think this is the right approach, but I can't figure out what's the correct way to estimate $P(A)$ and $P(A\cap B)$.

Answer 1

The problem with your $P(A)$ estimation is that you count some permutations multiple times - if permutation has two cycles of length $n$, then you count it twice (for both cycles).

Standard way to estimate probability of random point to be in cycle of length $n$ is as follow: it first has $N$ options where to go, and it can go to any of $N - 1$ (except initial), then the next has to go to one of $N - 2$ of $N - 1$ options, and so on, until $n$-th point has to go to $1$ option of remaining $N - n + 1$. Multiplying, we get $\frac{N - 1}{N} \cdot \frac{N - 2}{N - 1} \cdot \ldots \cdot \frac{1}{N - n + 1} = \frac{1}{N}$.

However, you don't even need it, you can calculate $P(B | A)$ directly. Just note that after we reveal a cycle of length $n$, the rest $N - n$ elements form another uniformly distributed permutation, and thus probability of them to have a cycle of length at least $50$ is again $H_{N - n} - H_{50}$.

Answer 2

There is a simple answer to this which requires no calculation, assuming the original approach is optimal for $N$ prisoners/drawers when no additional information is given.

Let's say the first $k$ prisoners are reported to have opened $n_1,\ldots,n_k\le 50$ drawers each. From this, it is known that there are cycles of lengths $n_1,\ldots,n_k$, some of which may correspond to drawers in the same cycle.

Now, let's assume $S$ is the total number of drawers that has been opened. The exact number may be unknown to the prisoners unless the $n_i$ are all distinct: if $n_i=n_j$, they don't know if prisoner $i$ and $j$ are part of the same cycle or two different cycles. However, they know that $\sum_{n\in\{n_1,\ldots,n_k\}} n\le S\le\sum_i n_i$, which must be positive. These $S$ drawers are all part of cycles of length $\le50$, and these drawers are all "safe", as are the prisoner with those numbers, even if they don't know which are the "safe" numbers.

What remains uncertain are the cycles for the remaining $100-S$ drawers. However, nothing is known about these drawers since none of them have been opened yet: ie they are still as random as before, just fewer. So if the original solution is optimal for any number of drawers, then it must be optimal for $100-S$ drawers.

If $100-S$ drawers remain unopened, ie after excluding those that have already been opened and found to be part of "safe" cycles, the likelihood of having a cycle of length $>50$ within $100-S$ random drawers is less than for $100$ random drawers, so randomizing the numeration will be a bad strategy.