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.

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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search