From: "r.e.s." Subject: Re: Probability formula Date: Thu, 21 Oct 1999 12:40:01 -0700 Newsgroups: sci.math Keywords: Limiting approximation of elementary probability Eric Holmquist wrote ... [...] : formula: Np = -lnR : : it can be used to calculate the fraction R of numbers not yet drawn, : when N total drawings and p = probability of success in one drawing : with replacement. [...] : can somebody tell me where this formula can be found in a textbook or : trestice on probability? Sorry, I don't have a reference, but this should be in many introductory texts. Here are a few comments though: First of all, R is a random variable and cannot be "calculated". Second, if we're interested in, say, the expected value of R, then we can find it as follows: Suppose N independent drawings (with replacement) are made from the set {1,2,...M}. Then R=[I(1)+I(2)+...+I(M)]/M, where I(k)=1 if the number "k" is not among those drawn, and I(k)=0 otherwise. Now I(k) has, for each k=1..M, the same expectation: E(I(k))=pr("k" is not among those drawn)=(1-1/M)^N. Therefore E(R)=(1-1/M)^N. This is an exact result, and your formula corresponds to the approximation E(R)=(1-1/M)^N ~ exp(-N/M). ------Aside about the quality of the approximation: It appears that the magnitude of the error of this approximation is at most 1/(M*e) for any natural numbers N,M; more precisely, exp(-N/M) - (1-1/M)^N <= 1/(M*e), for N=1,2,3,..., M=1,2,3,.... (And interestingly, for fixed M, the error appears to be of greatest magnitude when N=M, with the stated bound, 1/e, occuring only when N=M=1.) A few comparisons: M N E(R)=(1-1/M)^N exp(-N/M) error 1/(M*e) ----------------------------------------------------- 2 1 0.500 0.607 0.107 0.184 2 2 0.250 0.368 0.118 0.184 2 4 0.063 0.135 0.073 0.184 2 8 0.004 0.018 0.014 0.184 5 2 0.640 0.670 0.030 0.074 5 5 0.328 0.368 0.040 0.074 5 10 0.107 0.135 0.028 0.074 5 20 0.012 0.018 0.007 0.074 10 5 0.590 0.607 0.016 0.037 10 10 0.349 0.368 0.019 0.037 10 20 0.122 0.135 0.014 0.037 10 50 0.005 0.007 0.002 0.037 ----------------------------------------------------- -- r.e.s. rs.1@mindspring.com "I am but mad north-northwest. When the wind is southerly, I know a hawk from a handsaw." ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~