4 ms·

The murder question sounds quite interesting, but I'm not sure I understand it. You have n people (initially n=13) in a circle, firing shots that are fatal with

by gjm11 7y ago

The murder question sounds quite interesting, but I'm not sure I understand it. You have n people (initially n=13) in a circle, firing shots that are fatal with probability p (here we apparently fix p=1/6, but I guess that for large n the final answer doesn't depend on p provided it's neither 0 nor 1?), and then 1 fires at 2, then 2 (if alive) or 3 (if not) fires at 3/4, and so on. And you're person 1 (this isn't stated explicitly, though...) so you're the last to have a chance to get shot at, and then you live if person n dies or if person n lives but misses. So, let's see. Suppose n is very large; then the probability that you live is approximately equal to the probability that your predecessor does; call that q. Then, as above, you live iff your predecessor dies (probability 1-q) or your predecessor lives but fails to kill you (probability q(1-p)). So q = 1-q+q(1-p) = 1-pq and 1 = 1/(1+p). That's a long way from 1/e, and a quick simulation seems to confirm this answer. It doesn't change a lot if we assume that a random person always fires first, instead of you, or if we assume that you're always last (which I think was the situation in that movie). If everyone has a revolver with n slots and one bullet, and they all fire at _you_, then you have a 1/e chance of survival for large n, but that sounds too different (and too easily found to be 1/e) to be the right thing. The probability p(n) that a permutation of n things is a derangement -- which tends to 1/e as n->oo -- satisfies the recurrence relation p(n) = [(n-1)p(n-1)+p(n-2)]/n; is it possible that the correct statement of the problem here leads to that same recurrence?

josh2600 7y ago
Ok, I talked to the engineer. I got it mostly right but everyone shoots to the right as soon as the lights go out. The question is "what's the probability you die?". Edit: You can also challenge people to think about the problem where everyone fires at exactly the same time OR random order since people have different reaction times. Edit 2: "The probability p(n) that a permutation of n things is a derangement -- which tends to 1/e as n->oo -- satisfies the recurrence relation p(n) = [(n-1)p(n-1)+p(n-2)]/n; is it possible that the correct statement of the problem here leads to that same recurrence?" <--- My engineer says that derangements are the correct key to the convergence.
- gjm11 7y ago
  I think I still don't understand what's happening in this scenario. If everyone shoots simultaneously (so in particular everyone does get the chance to shoot) then I die iff the one person shooting at me hits me. Probability equals probability that a given shot hits (so in this case 1/6). No dependence at all on the number of people. If everyone shoots sequentially, this seems just like what I described above. Probability of death is now p/(1+p) instead of p, at least if you're first to shoot and n is very large. (Unless something's very broken in the heuristic argument I gave. Let's try another. First approximation says a fraction p of people die. But that's not quite right because people who die don't get to shoot, so next approximation says we get p(1-p). Next approximation says we get p(1-p(1-p)). Etc. We can either solve the obvious equation, or else notice that we're getting more and more terms of the binomial expansion of p/(1+p). I don't see anything here that doesn't look, in a crude approximation, like a fraction p of people dying (p, again, is probability that a given shot hits, which in this case is 1/6). I must be misunderstanding something in the problem statement here. Perhaps it would be clearer if I'd seen the movie? Oh, what about this version? You shoot first, things proceed cyclically, and we keep going until just one person is left. What's the chance that it's you? Naively it seems like this should be approximately 1/n no matter what p is; shooting first could confer some advantage but surely it can't be much for large n. So this can't yield anything like 1/e either. Drat.
  - sinsterizme 7y ago
    Yeah I don’t understand the question either :( I’m very interested to here the full problem and solution
    - gjm11 7y ago
      Personally, I'd like to see a careful statement of the full problem but not the solution :-).
      - josh2600 7y ago
        From the engineer: "The current statement of the problem is that you have n participants, with 6 slots (1 loaded) in their revolver, each firing to the person on the right."

by gjm11 7y ago

josh2600 7y ago

Ok, I talked to the engineer. I got it mostly right but everyone shoots to the right as soon as the lights go out. The question is "what's the probability you die?". Edit: You can also challenge people to think about the problem where everyone fires at exactly the same time OR random order since people have different reaction times. Edit 2: "The probability p(n) that a permutation of n things is a derangement -- which tends to 1/e as n->oo -- satisfies the recurrence relation p(n) = [(n-1)p(n-1)+p(n-2)]/n; is it possible that the correct statement of the problem here leads to that same recurrence?" <--- My engineer says that derangements are the correct key to the convergence.

gjm11 7y ago
I think I still don't understand what's happening in this scenario. If everyone shoots simultaneously (so in particular everyone does get the chance to shoot) then I die iff the one person shooting at me hits me. Probability equals probability that a given shot hits (so in this case 1/6). No dependence at all on the number of people. If everyone shoots sequentially, this seems just like what I described above. Probability of death is now p/(1+p) instead of p, at least if you're first to shoot and n is very large. (Unless something's very broken in the heuristic argument I gave. Let's try another. First approximation says a fraction p of people die. But that's not quite right because people who die don't get to shoot, so next approximation says we get p(1-p). Next approximation says we get p(1-p(1-p)). Etc. We can either solve the obvious equation, or else notice that we're getting more and more terms of the binomial expansion of p/(1+p). I don't see anything here that doesn't look, in a crude approximation, like a fraction p of people dying (p, again, is probability that a given shot hits, which in this case is 1/6). I must be misunderstanding something in the problem statement here. Perhaps it would be clearer if I'd seen the movie? Oh, what about this version? You shoot first, things proceed cyclically, and we keep going until just one person is left. What's the chance that it's you? Naively it seems like this should be approximately 1/n no matter what p is; shooting first could confer some advantage but surely it can't be much for large n. So this can't yield anything like 1/e either. Drat.
- sinsterizme 7y ago
  Yeah I don’t understand the question either :( I’m very interested to here the full problem and solution
  - gjm11 7y ago
    Personally, I'd like to see a careful statement of the full problem but not the solution :-).
    - josh2600 7y ago
      From the engineer: "The current statement of the problem is that you have n participants, with 6 slots (1 loaded) in their revolver, each firing to the person on the right."