Alternative solution for 100 prisoners problem

Question

I recently heard about the 100 prisoners problem ( https://en.wikipedia.org/wiki/100_prisoners_problem ) and have two questions about it.

1. Let's assume a cycle with length $l$ > 50, then there are $\binom{100}{l}$ possibilities to choose numbers for such a cycle. After choosing $l$ numbers I would assume that there are $l\ !$ possibilities to arrange them in a cycle. We still have $(100-l)$ remaining numbers, which we can arrange by $(100-l)!$ possibilities. All together I get \begin{align} \binom{100}{l}\cdot l\ !\cdot(100-l)! \end{align} possibilities for getting a cycle with $l\ >\ 0$. But I found out that the correct formula is \begin{align} \binom{100}{l}\cdot \color{red}{(l-1)\ !}\cdot(100-l)! \end{align} $\mathbf{Why}$ $\color{red}{(l-1)\ !}$ $\mathbf{?}$
2. It has been shown that the optimal policy "wins" in about 30 %, independently of the number of prisoners. Furthermore it has been shown that this is an optimum, thus there is no better policy. But if we get cycles with $l>50$, this policy $\mathbf{always}$ fails. I wonder if there could be another policy which works as good as the already known policy, but whose success is $\mathbf{independent}$ of the length of the cycles.

Answer 1

Ad 1.

$l$ numbers can be permutated in $l!$ ways, but some of these permutations represents the same cycle, eg. permutations $4,5,6,1,2,3$ and $2,3,4,5,6,1$ represents the same cycle $(1,2,3,4,5,6)$. There are exactly $l$ permutations in this equivalence class, so the number of cycles is equal to $\frac{l!}{l}=(l-1)!$

Ad 2.

This $31\%$ is probability where every prisoner draws his number, ie. in our permutation there is no cycle with length $l>50$. No matter of the length of cycles, if prosoners choose this strategy they have $31\%$ chance to win.

To show what I mean, assume that you have to guess the number drawn on 6 sided dice. Let's say, that your strategy is to say, that the drawn number is $5$. It gives you $16,6\%$ chances to win and $83,4\%$ chances to loose. Saying that your strategy fails when the drawn number is different than $5$ is the same as saying, that your strategy works perfectly when the drawn number is $5$.

As far as you don't know what the number is, you have $16,6\%$ chances to win.

As far, as the prosoners don't know if there is a cycle with length $l>50$, they have $31\%$ chance to win.

Answer 2

1. You can always choose some person to "start" the cycle, and the remaining can be arranged in $(l-1)!$ ways. For example, there are only 1 way to organize 2 persons into a cycle.

2. There's a nice way to overcome this by randomizing the algorithm. Namely, the prisoners should choose a random permutation $\sigma$ beforehand and apply it. Namely, the prisoner $k$ should start from $\sigma(k)$ and then at each step she should open the box $\sigma(x)$, where $x$ is her number. This randomized strategy has the same probability of succeeding, no matter what the initial position is.