First, let's work out the chance that there will be a cycle of length 10. There are 10! (ten factorial, or \(10 \times 9 \times 8 ... \times 2 \times 1 \)) ways to order the 10 numbers. If we want a cycle of length 10, there are \(\binom{10}{10} =1\) ways to pick which 10 numbers go into the cycle (in this case all 10 of them must go in).
Then there are 10! ways we can order the numbers in the cycle, but not all of these are unique. For example, the ordering 1,2,3,4,5,6,7,8,9,10 is equivalent to the ordering 2,3,4,5,6,7,8,9,10,1. For any given ordering, it can be shifted to create a total of 10 identical orderings. This means the number of unique cycles of length 10 is \(\frac{10!}{10}=9!\).
The probability of getting a cycle of length 10 is the number of unique cycles of length 10 over the total number of permutations, or \(\frac{9!}{10!}=\frac{1}{10}\).
We can use a general formula to find the chance of getting a cycle of length \( l \) where \( l \) is between 6 and 10. This formula only works for cycles greater than half the length of the whole chain. There can be multiple short cycles of the same length in the same shuffling (2 cycles of length 5, 2 cycles of length 4 with 2 leftover, etc) and this formula relies on the fact that there can only be one cycle of length l at a time.
For a cycle of length \( l \) there are \(\binom{10}{l}\) ways to pick \( l \) boxes to form the cycle. There are\(\ (l\ -\ 1)!\ \) unique cycles and \((10-l)!\)\) ways to arrange the numbers that aren't part of the cycle. (We don't care how those numbers are arranged since they are guaranteed to form short cycles). This means there are \(\binom{10}{l}\left(l-1\right)!\left(10-l\right)!=\frac{10!}{l}\) possible permutations that give a cycle of length 10. Since there are \(10!\) total permutations, the chance of getting a cycle of length l is \(\frac{1}{l}\).
The chance that there are no cycles longer than 5 is the same as 1 - (the chance of getting a cycle of length 6,7,8,9, or 10). Therefore the probability that there are no long cycles is \(1 - ( \frac{1}{10} + \frac{1}{9} + \frac{1}{8} + \frac{1}{7} + \frac{1}{6}) \approx 35.4%\). This means about 35.4% of the time, following the cyclical strategy will lead to a success!
We know the formula for the probability of success is \(1-\left(\sum_{i=n}^{2n}{1/i} \right ) \) where \( 2n )\ is the total number of prisoners. We can calculate this for 100 prisoners to find that the probability of success is about 31.2%. As the number of prisoners increases, the probability of success will level out to about 30.7% (the proof for this is beyond the scope of what we're looking at, but it can be found in this video if you're interested.).
Back to top