Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

The N Targets Problem


Date: 11/15/2001 at 06:26:51
From: Jocelyn Bouliane
Subject: Expected number of shots to hit all targets

THE n TARGETS PROBLEM

There are n targets, the probability of each to be hit by a cannon 
being equal to one another, that is 1/n.

Let X be the number of firings required to hit all the targets. (Of 
course, a given target can be hit more than once, since the result of 
a firing is deemed to be independent of all the previous ones.)

What is then the expectation E(X) of X?


Date: 11/16/2001 at 06:59:58
From: Doctor Mitteldorf
Subject: Re: Expected number of shots to hit all targets

Dear Jocelyn,

To figure in detail the probabilities for each possible number of 
targets hit is a complicated but interesting problem, involving the 
T function. You can read about it in the Dr. Math archives:

   Collecting a Set of Coupons
   http://mathforum.org/dr.math/problems/amal2.2.3.00.html   

But if you just need the expected value, then your question can be 
answered with a different approach. We'll do it in two stages.


Stage 1: We start with the question: suppose the probability of 
success on each trial is p. What's the expectation value of the number 
of trials it takes to achieve first success?

Answer: the probability for 1 is p, for 2 is p(1-p), for 3 it's p(1-
p)^2. So the expectation value for the number of trials is the sum
                                 
 1*p + 2*p(1-p) + 3*p(1-p)^2 + ...    

Let's define q to be (1-p) and write the sum as

      inf
 p *  SUM [nq^(n-1)]
      n=1

The form nq^(n-1) is the derivative with respect to q of q^n. This 
suggests a trick by which the sum can be evaluated. We'll define S1 as 
the sum

S1 = SUM [nq^(n-1)] 

and we'll define S0 as the sum

S0 = SUM [q^n]

Then S1 = dS0/dq. But we know how to evaluate S0 from a more standard 
trick: If we multiply S0 by q, we get back the same summation but with 
the first term missing:

          inf         inf 
qS0 = q * SUM [q^n] = SUM [q^n]
          n=1         n=2

q*S0 = S0 - q   ==>  S0 = q/(1-q)

Then S1 is the derivative with respect to q:

S1 = dS0/dq = 1/(1-q) + q/(1-q)^2 = 1/(1-q)^2

Now we can remember that q was defined as 1-p, and go back to the 
expectation value for the number of trials, which was p*S1, or 
p/(1-q)^2, or simply 1/p. 


Now we get to Stage 2: Suppose there are N targets and we've already 
hit n of them. What is the expectation value for the number of shots 
it takes to hit one more?  The probability of success in any given 
trial is n/N, so this is our p from stage 1. The expected number of 
shots required to go from n to n-1 is 1/p = (N/n).  

The expected number of shots required to go from n = 0 to n = N is a 
sum over these values:
               N               N 
Your answer = SUM [N/n] = N * SUM [1/n]
              n=1             n=1

I don't think this sum can be simplified further; the answer you seek 
is that the expected number of shots to hit N targets is N times the 
sum of the reciprocals of the numbers from 1 to N.

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Calculus
High School Probability

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/