Wikipedia:Reference desk/Archives/Mathematics/2013 February 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 15

How do you solve ${\frac {n!}{(n-r)!n^{r}}}\geq 1-\epsilon$ for n?

How do you solve ${\frac {n!}{(n-r)!n^{r}}}\geq 1-\epsilon$ for $n$, given $r$ and $\epsilon$? The parameter values of interest are of the order $r\sim 10^{9}$ and $\epsilon \sim 10^{-5}$. Can someone give a good approximation formula that can be evaluated without overflows or gross loss of precision during computation? Thanks. --173.49.13.216 (talk) 03:56, 15 February 2013 (UTC)

I'm not a specialist of this kind of thing, but this can be rewritten (exactly) as

$\left(1-{\frac {1}{n}}\right)\left(1-{\frac {2}{n}}\right)\cdots \left(1-{\frac {r-1}{n}}\right)\geq 1-\epsilon$

$\log \left(1-{\frac {1}{n}}\right)+\log \left(1-{\frac {2}{n}}\right)+\cdots +\log \left(1-{\frac {r-1}{n}}\right)\geq \log(1-\epsilon ).$

In approximate terms, we can write this as

$-{\frac {1}{n}}-{\frac {2}{n}}-\cdots -{\frac {r-1}{n}}\geq \log(1-\epsilon )$

$-{\frac {r(r-1)}{2n}}\geq \log(1-\epsilon )$

$n\geq {\frac {r(r-1)}{-2\log(1-\epsilon )}}\approx {\frac {r^{2}}{2\epsilon }}$

In linearizing the logarithms, the error in the terms on the left is at most about ${\frac {r}{2n}}$ times their value. Given the approximate value of n, the error on the left is, in proportion, about ${\frac {\epsilon }{r}}$. In other words, in using the formula $n\geq {\frac {r(r-1)}{-2\log(1-\epsilon )}}$ you commit an error of at most about ${\frac {\epsilon }{r}}\approx 10^{-14}$ times the vaue of n. (In fact, a more careful calculation shows that the error is about 2/3 of this, and that it results in an underestimation of the minimum possible n.) If you replace r - 1 with r, this rises to about 1/r, or 10^-9. If you replace $\log(1-\epsilon )$ with $\epsilon$, the error rises to about $\epsilon /2=5\times 10^{-6}$ times the value of n. 64.140.122.50 (talk) 05:58, 15 February 2013 (UTC)

I forgot to mention this - I'm using natural logarithms here. 64.140.122.50 (talk) 06:08, 15 February 2013 (UTC)

Thanks. Your formula is more than good enough. --173.49.13.216 (talk) 12:15, 15 February 2013 (UTC)