Montana Duck Hunters

Date: 11/27/2001 at 21:49:34
From: Nanette Mattos
Subject: Probability

Montana duck hunters area all perfect shots.  Ten Montana hunters are 
in a duck blind when 10 ducks fly over. All 10 hunters pick a duck at 
random to shoot at, and all 10 hunters fire at the same time. How many 
ducks could be expected to escape, on average, if this experiment were 
repeated a large number of times?

Text answer: 3.49 (theoretical probability)

I have presented this problem to many high school mathematics 
teachers, and we are stumped. The closest solution I can come up with 
is 4.99, using many sample spaces, Pascal's triangle, etc.  I hope you 
can help me understand what I'm doing wrong.

Thank you, 
Nanette

Date: 11/28/2001 at 00:29:33
From: Doctor Schwa
Subject: Re: Probability

Hi Nanette,

This is certainly a classic problem! I find several references to it 
online, such as

   Virtual Laboratories - Kyle Siegrist  

   Expected Value > Definitions and Properties
   http://www.math.uah.edu/stat/expect/expect1.html   

   Finite Sampling Models > The Number of Distinct Sample Values
   http://www.math.uah.edu/stat/urn/urn8.html   

Here are my various attempts at solving this problem. It starts out
pretty long and messy, gets an answer using a computer to help, but 
then I find a pattern in that answer, and use the pattern to figure it 
out.

The first hunter kills one duck.

The second hunter kills 9/10 of a duck on average (he has a 1/10
chance of shooting at the same duck).

The third hunter, well, now that's tricky. If there's one duck dead so 
far, that's a (1/10) chance, and then the third hunter kills 9/10 of
a duck. If there are two ducks dead, then the third hunter kills 8/10 
of a duck.

This looks pretty messy. Is there any way to streamline it?

Sure!  Let f(n,d) = the probability that d ducks are dead after
n hunters have shot.

Then f(1,1) = 1.
f(2,1) = 1/10 and f(2,2) = 9/10.

For the third hunter to end up with 1 dead you must have had two
hunters with 1 dead and then hit the same one, so
f(3,1) = 1/10 * f(2,1).

To end up with 2 dead, you can either have 1 dead after two hunters
and then hit any other duck (9/10 chance), or have 2 dead and hit one
of them again (2/10 chance).

f(3,2) = 9/10 * f(2,1) + 2/10 * f(2,2).
Similarly
f(3,3) = 8/10 * f(2,2).

I'll do one more and hope for a pattern:
f(4,1) =                 1/10 * f(3,1) [I inserted that space for a  
                                          reason.]
f(4,2) = 9/10 * f(3,1) + 2/10 * f(3,2)
f(4,3) = 8/10 * f(3,2) + 3/10 * f(3,3)
f(4,4) = 7/10 * f(3,3)

I see enough of a pattern now that I can put this into an Excel 
spreadsheet easily enough, and get (out of 10^10 possibilities) 

        10 ways that  1 duck dies
     45990 ways that  2 ducks die
   6717600 ways that  3 ducks die
 171889200 ways that  4 ducks die
1285956000 ways that  5 ducks die
3451442400 ways that  6 ducks die
3556224000 ways that  7 ducks die
1360800000 ways that  8 ducks die
 163296000 ways that  9 ducks die
   3628800 ways that 10 ducks die.

A little expected value computation means that on average 6.513215599 
ducks die, so 3.486784401 ducks live.

The spreadsheet is at 

   http://mathforum.org/dr.math/gifs/mattos11.27.01.xls   

(Download the file, then open it with Excel.)

That's not a very elegant method, though. I wonder if there's an 
easier way. With numbers that ugly, I'm not so sure.

Ah, now I see something (and I added the calculation to the 
spreadsheet):
with 1 hunter, the expected number dead is 1.
With 2 hunters, the expected number dead (out of 10) is 1 + 9/10.
With 3 hunters, the expected number dead is 1 + (9/10) + (9/10)^2
and so on.

That is a great clue to a nice proof! You might want to stop here and 
try to figure it out for yourself.

Okay, the first hunter certainly kills a duck.
The second hunter has a 9/10 chance of killing a duck.
What's the chance that the third hunter kills a duck? Well, suppose
the third hunter shoots at duck number k. What's the chance that
neither of the first two hunters shot that same duck? (9/10)^2, of
course. Hence the expected number of ducks killed by n hunters is
1 + (9/10) + (9/10)^2 + ... + (9/10)^(n-1).

That formula checks out in the small cases, and as n goes to infinity
its limit is indeed 10 ducks killed, so I think this answer makes 
sense.

Now to try to figure out the standard deviation...

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 11/28/2001 at 15:37:45
From: Doctor Anthony
Subject: Re: Probability

Suppose there are p people and N ducks. From the point of view of a 
particular duck the probability that someone will shoot at that duck 
is 1/N. We have p independent trials, so this is binomial probability.

The expected number shooting at any duck is p/N.

The probability that no one will shoot at that particular duck is

   P(0) = (1 - 1/N)^p  = [(N-1)/N]^p

The expected nunber of ducks with no one shooting at them

     =  N.[(N-1)/N]^p

        (N-1)^p
     =  ---------
         N^(p-1)

If p = 10 and N = 10 this expression gives

          9^10
         ------  =  3.48678
          10^9

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/