1
$\begingroup$

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)$.

$\endgroup$
6
  • 1
    $\begingroup$ If there is a cycle of length $>50$ then more than half the prisoners are in that cycle, so it would be bizarre to choose $30$ in a row, all outside the cycle. Or am I missing something? $\endgroup$
    – lulu
    Jul 28 at 22:42
  • $\begingroup$ What are the options? Either it is random or the warden messed with it? If the warden didn't mess with anything, the first prisoner has a $50/50$ chance of ending the game. If the warden messed with things, that probability decreases. Maybe add the possibility of a sympathetic warden who made sure no cycle has length $>50$? Otherwise, just always assume the warden sucks. $\endgroup$ Jul 29 at 1:49
  • $\begingroup$ @lulu You are right, so in such a situation, the prisoners should actually not relabel the drawers. Anyway, I tried to estimate the conditional probability that a cycle of length $>50$ exists after the first prisoner has opened $n\leq 50$ drawers to see whether for any $n$ this conditional probability would be larger than the original probability, but I got stuck in estimating the "ingredients" for the conditional probability. I updated my question accordingly. $\endgroup$
    – a_guest
    Jul 29 at 7:55
  • $\begingroup$ @SlipEternal The numbers are distributed randomly, but even if they are not, the prisoners can just use an initial random relabeling of the drawers to account for that. So the assumption is that they are random. If it is guaranteed that no cycle of length $>50$ exists, then obviously they should never relabel. $\endgroup$
    – a_guest
    Jul 29 at 7:57
  • 1
    $\begingroup$ But my point works more broadly. Even seeing a single success is pretty strong evidence that there is no long cycle. After all, saying the probability of no long cycle is about $\frac 13$, then the revised probability after you see a success is at least $\left( \frac 13\right) \big / \left(\frac 13+\frac 23\times \frac 12\right)=\frac 12$. So you are far better off sticking with what you have. That is to say, I can't imagine any scenario in which you should reshuffle. $\endgroup$
    – lulu
    Jul 29 at 9:06

2 Answers 2

1
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ In your formula, either it should start with $\frac{n+1}{N}$ or it should end with $\frac{N-n}{N-n+1}$ but the way it is currently written I can't make sense of it (the denominator gets reduced by $n-1$ but the numerator gets reduced by $N-1$). Anyway, I think the last paragraph really is the answer for the question. $\endgroup$
    – a_guest
    Aug 1 at 7:26
  • $\begingroup$ This is because the last term isn't of the same form as previous. Second-to-last term is $\frac{N - n + 1}{N - n + 2}$. This different comes from the fact that the last point has to go exactly to the first point, while the rest can go to any point except the first. $\endgroup$
    – mihaild
    Aug 1 at 9:21
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.