100 prisoners riddle - Dependency of probabilities

Question

I am referring to the well-known riddle of the title (if you don't know what I am talking about here it is: https://en.wikipedia.org/wiki/100_prisoners_problem - See sections "Problem" and "Solutions"). It is a subject that has already been discussed a lot and I already get the most of it but here is what I don't fully understad "intuitively":

If we take the "naive" approach where every prisoner opens $50$ boxes randomly his probability of success is $1/2$ and is INDEPENDENT for every prisoner each time. With the optimal solution's approach (called "loop approach") I have read that the first prisoners's try still has a probability of $1/2$, but the next ones have a differnt probability because (as a lot of people have highlighted) they are not independent anymore. So what is this new DEPENDENT probability for the 2nd, 3rd, etc prisoners and to what exactly is it dependent to?

Answer 1

If prisoner #1 succeeds by finding a cycle of length $n$, then:

1. The other $n-1$ prisoners in that cycle will all also succeed by making their way through the same cycle.
2. The prisoners not in that cycle may still be in a long cycle (and thus will fail when it is their turn) but it becomes gradually less likely: Instead of the probability of a cycle of length at least $50$ in a pool of $100$ items, it is now a cycle of length at least $50$ in a pool of $100 - n$ items.

A prisoner who succeeds but is not in any previously found cycle will similarly ensure that all other prisoners in the new cycle will succeed, and reduce the pool of items that remain to be permuted, and thus further reduce the likelihood that a long cycle exists.