Can you solve this probability problem?

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • ms61853
    Restricted User
    • 04-10-07
    • 731

    #1
    Can you solve this probability problem?
    As an introduction consider this one dimensional problem:

    You have a number of birds sitting on a wire. At a given instant, each birds turns and looks at the bird sitting closest to it. It's pretty easy to show that 25% of the birds will not be looked at by another bird.

    So lets extend this type of problem into 2 dimensions:

    You have a number of hunters standing in an infinitely large field. At a given instant, each hunter turns and shoots the hunter standing closest to him (many will obviously be shot more than once). What percentage of the hunters will not be shot at all? Assume the number of hunters is large enough that any boundary conditions can be ignored.

    I believe the answer to this problem is 1/e or about 37%. Does anybody solve this and come up with something different?
  • Ganchrow
    SBR Hall of Famer
    • 08-28-05
    • 5011

    #2
    With the birds on the wire, the problem is solved by realizing that any given bird has a ½ probability of being seen by the bird on its right and a ½ probability of being seen by the bird on its left. Hence, the probability of the bird being seen at all would be (1 - ½)2.

    Now consider hypothetical hunters (birds) who can only shoot (see) along the 4 cardinal directions of the compass. Such a hunter would have a 1 4 probability of being shot by the nearest hunter to his N, S, E, & W. Since there are 4 such hunters he has a probability of (1 - 1 4 )4 of surviving.

    By identical logic if we continue increasing the number of cardinal direction from 2 (in others words we continue looking at increasing fractional dimensions between 1 and 2) then it should be readily apparent that a given hunter will in the case of n cardinal directions have a probability of (1 - 1 n )n = ( n-1 n )n of not being seen.

    As we increase to full dimensionality of 2, we'd also be increasing the number of cardinal directions. Hence we take the limn→∞( n-1 n )n.

    If we let L equal our limit, take the log of both sides, and pass the limit through the log then:
    log(L) = limn→∞(n * (log(n-1) - log(n)) )
    log(L) = lim((log(n-1) - log(n) / 1 n )
    log(L) = lim( d dx (log(n-1) - log(n)) / d dx ( 1 n ) ) (by l'Hôpital's rule)
    log(L) = lim( ( 1 n-1 - 1 n ) / - 1 )
    log(L) = limn→∞ -n n-1 = -1
    So limn→∞( n-1 n )n = exp(-1) = 1 e .

    Note, however, that the inductive reasoning used above to derive this result implicitly assumes a discrete number of cardinal directions and completely ignores the topology of the real number line. If directionality were continuous then the above results might not hold under certain circumstances.
    Comment
    • ms61853
      Restricted User
      • 04-10-07
      • 731

      #3
      Originally posted by Ganchrow
      With the birds on the wire, the problem is solved by realizing that any given bird has a ½ probability of being seen by the bird on its right and a ½ probability of being seen by the bird on its left. Hence, the probability of the bird being seen at all would be (1 - ½)2.

      Now consider hypothetical hunters (birds) who can only shoot (see) along the 4 cardinal directions of the compass. Such a hunter would have a 1 4 probability of being shot by the nearest hunter to his N, S, E, & W. Since there are 4 such hunters he has a probability of (1 - 1 4 )4 of surviving.

      By identical logic if we continue increasing the number of cardinal direction from 2 (in others words we continue looking at increasing fractional dimensions between 1 and 2) then it should be readily apparent that a given hunter will in the case of n cardinal directions have a probability of (1 - 1 n )n = ( n-1 n )n of not being seen.

      As we increase to full dimensionality of 2, we'd also be increasing the number of cardinal directions. Hence we take the limn→∞( n-1 n )n.

      If we let L equal our limit, take the log of both sides, and pass the limit through the log then:
      log(L) = limn→∞(n * (log(n-1) - log(n)) )
      log(L) = lim((log(n-1) - log(n) / 1 n )
      log(L) = lim( d dx (log(n-1) - log(n)) / d dx ( 1 n ) ) (by l'Hôpital's rule)
      log(L) = lim( ( 1 n-1 - 1 n ) / - 1 )
      log(L) = limn→∞ -n n-1 = -1
      So limn→∞( n-1 n )n = exp(-1) = 1 e .

      Note, however, that the inductive reasoning used above to derive this result implicitly assumes a discrete number of cardinal directions and completely ignores the topology of the real number line. If directionality were continuous then the above results might not hold under certain circumstances.
      Interesting. You approached this in a much more complicated sense than I would have thought to do yet we arrived at the same answer.

      I saw this problem years ago in the now defunct OMNI magazine as an "unsolvable" easily stated problem. I recently thought about it and after working on it for a while came with this solution:

      Look at the probability that any one random hunter will not be hit by another hunter. This should extrapolate into the percentage of total hunters that will be hit.

      Take another random hunter. Look at the probability that he will shoot the hunter in question. Consider that there are "N" hunters available. Given N hunters, there are N -1 hunters available for the second random hunter to shoot. Thus the chances of him shooting the first random hunter are (N-2)/(N-1).

      Thus the probability that the random hunter in question will be hit by any other specific random hunter is (N-2)/(N-1).

      Now, since there are (N - 2) other hunters, the total probability that any one hunter will be hit is ((N-2)/(N-1))^(N-2)

      If you say boundary conditions don't matter, then saying that the number of hunters available is is essentially infiinite is reasonable.

      As N goes to infinity, ((N-2)/(N-1))^(N-2) (essentially ((N-1)/N)^N)), the result is 1/e. (Admittedly, I had to look this up.)

      Now the big question I have wondered is, how does this change over 3 dimensions (say spaceships firing on each other.)
      Comment
      • Ganchrow
        SBR Hall of Famer
        • 08-28-05
        • 5011

        #4
        Originally posted by ms61853
        Look at the probability that any one random hunter will not be hit by another hunter. This should extrapolate into the percentage of total hunters that will be hit.

        Take another random hunter. Look at the probability that he will shoot the hunter in question. Consider that there are "N" hunters available. Given N hunters, there are N -1 hunters available for the second random hunter to shoot. Thus the chances of him shooting the first random hunter are (N-2)/(N-1).

        Thus the probability that the random hunter in question will be hit by any other specific random hunter is (N-2)/(N-1).
        FWIW, it's actually 1/(N-1).

        Originally posted by ms61853
        Now, since there are (N - 2) other hunters, the total probability that any one hunter will be hit is ((N-2)/(N-1))^(N-2)
        Because the probability of the random hunter in question being hit by any other specific random hunter is actually 1/(N-1), technically the the correct probability of a given hunter surviving given N hunters would be (N/(N-1)) ^ (N-1). Although your answer of ((N-1)/(N-2)) ^ (N-2) is close enough for our ultimate purposes as the two plims are clearly equal (just set N' to (N-1)).

        Originally posted by ms61853
        As N goes to infinity, ((N-2)/(N-1))^(N-2) (essentially ((N-1)/N)^N)), the result is 1/e. (Admittedly, I had to look this up.)
        Yeah you could look it up, but isn't using l'Hôpital's rule much cooler?

        Originally posted by ms61853
        Now the big question I have wondered is, how does this change over 3 dimensions (say spaceships firing on each other.)
        It wouldn't change at all over any finite-dimensional space ≥ 2. Remember ... the cardinality of the number of points on a circle is equivalent to the cardinality of the number of points on a sphere is equivalent to the cardinality of the number of points on a hypersphere is equivalent to the cardinality of the number of points on an N-sphere for all finite integers N > 0. (A 0-sphere would just be two equidistant points on a line).
        Comment
        • ms61853
          Restricted User
          • 04-10-07
          • 731

          #5
          Thus the chances of him shooting the first random hunter are (N-2)/(N-1)

          Yes, that should have read NOT shooting the first random hunter.
          Comment
          Search
          Collapse
          SBR Contests
          Collapse
          Top-Rated US Sportsbooks
          Collapse
          Working...