Comment by gjm11 | Hacker News Reader

Comment by gjm11 | Hacker News Reader

Parent Full thread

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?

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.

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.

How about this: People shoot in a random order (now everyone has the same chance of making it to the next round. Is it 1/e?)

  import numpy as np


  class Shooter:
      def __init__(self):
          self.dead = False
          self.right = None  # The person to the right


  def simulate(n):
      # Simulates a round with n shooters
      # Returns the ratio of survivors

      shooters = [Shooter() for i in range(n)]
      for i, shooter in enumerate(shooters):
          shooter.right = shooters[(i+1) % len(shooters)]

      np.random.shuffle(shooters)

      HIT_PROBABILITY = 1/6
      survivors = n
      for shooter in shooters:
          if not shooter.dead:
              if np.random.random() < HIT_PROBABILITY:
                  shooter.right.dead = True
                  survivors = survivors - 1
      return survivors/n

Simulations suggest that the survival probabilities do not converge to 6/7 if you add shuffling. This makes sense, since the survival probability for the random shuffling version must be strictly less than if you are guaranteed to go first.

  >>>sum([simulate(10000) for j in range(1000)])/1000
  0.8463075999999998

Yeah I don’t understand the question either :( I’m very interested to here the full problem and solution

Personally, I'd like to see a careful statement of the full problem but not the solution :-).

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."

Reply on news.ycombinator.com