4
$\begingroup$

Allow me to preface this by saying this is not a homework problem. If I had had this thought four years ago when I was taking calculus, I probably could do it...

I'm trying to calculate the limit as $n \to \infty$ of $1-\left(\frac{n-1}{n}\right)^n$ - - it's a constant I'm inclined to call "natural chance of success". I have estimated this value to be ~0.632121 but would very much like to see how it could be calculated aside from the brute-force method i employed earlier.

The background of this would be... consider n = 2 (a coin). You are given two flips of the coin to get what you pick - what is the chance you'll get your chosen outcome, assuming of course it's a fair coin. The best way to go about this would be to say there's a 1/2 chance of failing, and you have 2 flips. This means you have $(1/2)^2$ chance of failure, being 1/4. 1-1/4 is 3/4, so your chance of success here is 3/4.

Now consider n = 6 (standard die). You get six rolls to get the number of your choice (assuming a fair die again). Again, you have a 5/6 chance to not get your choice, and 6 rolls at 5/6 chance would be $(5/6)^6$, or ~.334, giving you a ~.665 chance of success.

And I'm curious as n increases to infinity, what is your chance of success? Now again, I've estimated this with a double precision float (in Java) to be 0.63212 (actually, this was the point at which it could simply gain no more precision on the value, n = 296536) but this doesn't really give insight to the derivation of the number, merely its value.

So I'm hoping someone a little fresher on their integrals than I can help me out here.

Thanks!

  • 3
    Answer is (1 - 1/e). See http://en.wikipedia.org/wiki/Poisson_distribution and http://en.wikipedia.org/wiki/E_%28mathematical_constant%292010-10-05
  • 1
    For these sorts of questions, its useful to know the formula $e^x = \lim_{n \to \infty} (1 - x/n)^n$. (This is where leonbloy's answer comes from; it is the case $x = -1$.)2010-10-05
  • 2
    Matt E: shouldn't you have a "+" sign instead of a "-"? $e^x = \lim_{n \to \infty} (1 + x/n)^n$.2010-10-05
  • 1
    @zar: Thanks very much! (And I wish the edit option for comments didn't disappear after 5 minutes!). I was anticipating about the $x = -1$ case and made an unfortunate typo. (Just to be clear: zar is completely correct, and my formula is mis-typed.)2010-10-06
  • 0
    @everyone One of the things I loved about math (and love about computers) is the many different ways a problem can be solved. I appreciate all your efforts and assistance. Interestingly enough, the notion of this constant (and the application mentioned) came up in casual conversation the other day, after it was posted. (i.e. how many hands of poker to get a royal flush. Someone said ~650k, because there's a ~1/650k chance to get it. Then I reminded them of the "63% rule" as we called it). Thanks again! :)2010-10-16

4 Answers 4

11

You are essentially trying to find the limit of $\left(1-\frac{1}{n}\right)^n$ as $n\to\infty$. Rewrite this as $e^{n\ln(1 - \frac{1}{n})}$. Since the exponential function is continuous, you have $$\lim_{n\to\infty} e^{n\ln(1-\frac{1}{n})} = e^{\lim_{n\to\infty}(n\ln(1-\frac{1}{n})}.$$

To compute that limit, rewrite and use L'Hopital's: $$\begin{array}{rcl} \lim_{n\to\infty}n\ln\left(1 - \frac{1}{n}\right) & = & \lim_{n\to\infty}\frac{\ln(1-\frac{1}{n})}{\frac{1}{n}}\\ & = & \lim_{n\to\infty} \frac{\left(\frac{1}{1-\frac{1}{n}}\right)\left(1-\frac{1}{n}\right)'}{(n^{-1})'}\\ & = & \lim_{n\to\infty}\frac{\quad\frac{n^{-2}}{1-\frac{1}{n}}\quad}{-n^{-2}}\\ & = & \lim_{n\to\infty}\frac{-1}{1-\frac{1}{n}} = -1. \end{array}$$ So, since you wanted $1$ minus this limit, your limit equals $1-e^{-1}$.

  • 0
    And so it is that `1 - (1 / e) = 0.632120559`. Thank you so much for the detailed explanation!2010-10-05
  • 1
    That's an approximation, not the exact value. "=" is inappropriate; you want either $\approx$, or indicate that the decimal does not terminate.2010-10-05
  • 4
    This is my opinion: Try to avoid l'Hopital - think instead - log(1-1/n) / (1/n) is of the form -(f(x+h)-f(x))/h. It tends to the derivative of -log(x) at x=1 -- that is -12010-10-05
  • 0
    @AD: good point! Thanks.2010-10-06
7

If you know one of the definitions for the number $e$:

$$ e=\lim_{n\to\pm\infty}\Big(1+\frac{1}{n}\Big)^n, $$

then you could calculate your limit in the following way:

$$ \lim_{n\to\infty}\Big(1-\frac{1}{n}\Big)^n = \lim_{n\to\infty}\left[\Big(1+\frac{1}{-n}\Big)^{-n}\right]^{-1} = \frac{1}{e}. $$

5

If you expand $\lim_{n\to\infty}\Big(1-\frac{1}{n}\Big)^n,$ by using the binomial formula, you get $1 - \frac{n}{n} + \frac{n*(n-1)}{2*n^2} - \frac{n*(n-1)*(n-2)}{6*n^3} + ...$ As n goes to infinity, this approaches $1 - \frac{n}{n} + \frac{n*n}{2*n^2} - \frac{n*n*n}{6*n^3} + ... $, which equals $1 - 1 + \frac{1}{2} - \frac{1}{6} + ...$ This is exactly the Taylor expansion of $e^x$ when $x=-1$

Surprisingly, wolfram alpha can actually match constants to approximations, like so: http://www.wolframalpha.com/input/?i=0.632121

That may be a resource that you could find use for in the future.

3

Your question is motivated by probability, but in itself it's pure and elemental calculus:

$\lim_{x\to \infty} (1 - \frac{1}{x})^x = e ^{-1}$

From that, your number is 0.63212...