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!

  • 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
    @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...