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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.