Re: Proving Veritasiums riddle using Perl (simulating "100 prisoners problem")

> still absolutely boggles my mind that this actually works at all

Without having read the solution.

I think it's easy to see that there are strategies performing better that 0.5**N.

Consider N=2 prisoners.

A strategy where both prisoners choose the same box is doomed to fail, because the box can't hold both numbers. It will perform worse than on average.

Hence the inverse strategy to always choose different boxes will perform better. And indeed it's easy to see that the success rate would be 50%. (Either both fail, or both succeed) ą That's far better than 0.5**2 = 25% of random picks. ˛

This could be generalized to bigger N by choosing a strategy where overlaps like in the failing strategy are minimized.

Now I'll try watching the solution :)

Updates

See also 100 prisoners problem for references.

ą) in math lingo, the two experiments are not statistically independent anymore.

˛) this gain is possible because there is extra information available to couple the experiments, because the boxes are ordered.

Now imagine the warden would change the order of the boxes after each pick, and erase that information.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

see Wikisyntax for the Monastery}

Comment on Re: Proving Veritasiums riddle using Perl (simulating "100 prisoners problem")

Replies are listed 'Best First'.
Re^2: Proving Veritasiums riddle using Perl (simulating "100 prisoners problem") by LanX (Saint) on May 02, 2025 at 16:04 UTC
I watched the video, and was very confused. Turns out the solution is right, but his explanation was - mildly phrased - flawed, when calculating the probability of cycles ("loops") of length N to N/2+1. I had to reconstruct the correct solution. But that's YouTube nowadays, trimmed to maximum emotional show effect for the sake of clicks FWIW: if you still struggle to understand the solution, try the case N=4. There are only 24 = 4! possible configurations of the boxes, this easily fits on a piece of paper. And you can see why there are exactly N!/C configurations with a cycle length C, for N >= C > N/2. In the case of N=4 there are 6 cases with C=4 (6=4!/4)† 8 cases with C=3 (8=4!/3)† Hence the survival rate is at 10/24. Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery} †) updated	[reply]

Replies are listed 'Best First'.

Re^2: Proving Veritasiums riddle using Perl (simulating "100 prisoners problem")
by LanX (Saint) on May 02, 2025 at 16:04 UTC

I watched the video, and was very confused. Turns out the solution is right, but his explanation was - mildly phrased - flawed, when calculating the probability of cycles ("loops") of length N to N/2+1.

I had to reconstruct the correct solution.

But that's YouTube nowadays, trimmed to maximum emotional show effect for the sake of clicks

FWIW: if you still struggle to understand the solution, try the case N=4. There are only 24 = 4! possible configurations of the boxes, this easily fits on a piece of paper.

And you can see why there are exactly N!/C configurations with a cycle length C, for N >= C > N/2. In the case of N=4 there are

6 cases with C=4 (6=4!/4)†
8 cases with C=3 (8=4!/3)†

Hence the survival rate is at 10/24.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

see Wikisyntax for the Monastery}

†) updated

[reply]