4 ms·

>I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right

>I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right there in your statement.

ddtaylor 8y ago
What I don't know is how to model the probability of the chain starting anywhere in the cycle.
- flyGuyOnTheSly 8y ago
  At the risk of sounding obtuse... is the answer you're looking for not exactly (1/2)^(100)?
- sigotirandolas 8y ago
  There's no 'start' of a cycle, they are circular. I.e. the cycle 1->2->3->1 is the same as 3->1->2->3). I.e. picking a locker at random is equivalent to picking a chain of length N with probability N/100. In fact, the prisoners aren't given any information about the cycles and can't communicate, so they can't choose a cycle "at random". Not sure if your question can be formulated as follows (which requires giving more information to the prisoners): Suppose that we color every group of lockers that form a cycle in a different color, and every prisoner then picks a random color and then picks a random locker among the lockers of that color. What is the chance of winning?
- daxfohl 8y ago
  I would assume it's much worse than the (1/2)^(100) approach of picking random each time. If you pick randomly with each of your 50 picks then you've got a 50% chance of winning. If you pick a random cycle and follow it, then you win iff the cycle you pick is your cycle and your number occurs within the first 50 of that cycle. So if the cycle that includes you is small, the first thing is less than 50%, and if the cycle that includes you is large, then the last thing is .. hmm well worth numbering: Say there's a 99 cycle and a 1 cycle. So 0.99 you're in the latter. And assuming that, 50/99 you pick a box that leads you to yourself in 50 picks. And 1/100 you're in the first, and assuming that 1/100 you pick it. So, 1/100 x 1/100 + 0.99 x 50/99 = .0001 + .5 = 0.5001. Hmm, I expected it to be under .5. So .. help?
  - daxfohl 8y ago
    I think my math for the above case is wrong, but I've got seven empty beer cans in front of me so. But even if it's right, you can somewhat rationalize. If there are two cycles each of len 50 then it's 50% chance. And if there are two cycles where one is 99 and the other is 1, then you've got very marginally better than 50% chance. And if it's one cycle of 100 you've got 50%. But if it's more than two cycles, say three of 33 or 34, then you can quickly see that you've only got a 33% chance of finding yourself. And plenty of outcomes like that exist. So it seems like 1 cycle (or apparently 2 with 99:1) is an upper bound. And the remainder only serve to lower the odds. And given they're plenty likely (I guess), your odds are even worse than randomly guessing with each pick.
    - daxfohl 8y ago
      Yeah I think I forgot to account for not ending up on your cycle in the 99 case (i.e. you're in the 99 but you chose the 1), so it should be .4901 or .4951 or something even in the 99:1 case.

>I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right there in your statement.

ddtaylor 8y ago

What I don't know is how to model the probability of the chain starting anywhere in the cycle.

flyGuyOnTheSly 8y ago
At the risk of sounding obtuse... is the answer you're looking for not exactly (1/2)^(100)?
sigotirandolas 8y ago
There's no 'start' of a cycle, they are circular. I.e. the cycle 1->2->3->1 is the same as 3->1->2->3). I.e. picking a locker at random is equivalent to picking a chain of length N with probability N/100. In fact, the prisoners aren't given any information about the cycles and can't communicate, so they can't choose a cycle "at random". Not sure if your question can be formulated as follows (which requires giving more information to the prisoners): Suppose that we color every group of lockers that form a cycle in a different color, and every prisoner then picks a random color and then picks a random locker among the lockers of that color. What is the chance of winning?
daxfohl 8y ago
I would assume it's much worse than the (1/2)^(100) approach of picking random each time. If you pick randomly with each of your 50 picks then you've got a 50% chance of winning. If you pick a random cycle and follow it, then you win iff the cycle you pick is your cycle and your number occurs within the first 50 of that cycle. So if the cycle that includes you is small, the first thing is less than 50%, and if the cycle that includes you is large, then the last thing is .. hmm well worth numbering: Say there's a 99 cycle and a 1 cycle. So 0.99 you're in the latter. And assuming that, 50/99 you pick a box that leads you to yourself in 50 picks. And 1/100 you're in the first, and assuming that 1/100 you pick it. So, 1/100 x 1/100 + 0.99 x 50/99 = .0001 + .5 = 0.5001. Hmm, I expected it to be under .5. So .. help?
- daxfohl 8y ago
  I think my math for the above case is wrong, but I've got seven empty beer cans in front of me so. But even if it's right, you can somewhat rationalize. If there are two cycles each of len 50 then it's 50% chance. And if there are two cycles where one is 99 and the other is 1, then you've got very marginally better than 50% chance. And if it's one cycle of 100 you've got 50%. But if it's more than two cycles, say three of 33 or 34, then you can quickly see that you've only got a 33% chance of finding yourself. And plenty of outcomes like that exist. So it seems like 1 cycle (or apparently 2 with 99:1) is an upper bound. And the remainder only serve to lower the odds. And given they're plenty likely (I guess), your odds are even worse than randomly guessing with each pick.
  - daxfohl 8y ago
    Yeah I think I forgot to account for not ending up on your cycle in the 99 case (i.e. you're in the 99 but you chose the 1), so it should be .4901 or .4951 or something even in the 99:1 case.