Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Fix a positive integer $k$. Let $$ f(n):= \frac{k!\binom{n}{k}}{n^k} $$ Then $\lim_{n\to \infty} f(n) = 1$. Hence $f(n) \ge 1-\epsilon$ for large $n$.

Define $n_0(\epsilon)$ as the least positive integer such that $n\ge n_0$ implies $f(n)\ge 1 -\epsilon$. Is there an asymptotic for $n_0(\epsilon)$ as $\epsilon\to 0$? A lower bound for $n_0(\epsilon)$ for fixed small $\epsilon$ would be useful too.

share|improve this question
    
For fixed k, this is a rational function of n. The asymptotics for $n\to\infty$ is therefore quite straightforward. –  Michael Renardy Sep 27 '13 at 15:40
    
Yes, the asymptotic for $f(n)$ can be found. The difficulty is in finding an asymptotic for inverse function $n_0(\epsilon)$. –  Colin Tan Sep 27 '13 at 16:02
2  
Why is this a difficulty? You expand f(n)-1 in powers of 1/n, and then you want to expand 1/n in powers of f(n)-1. This is what the inverse function theorem does for you. –  Michael Renardy Sep 27 '13 at 17:04
    
Michael, you are right. With Liviu's answer, I see that I can write down the Taylor expansion of $n_0(\epsilon)$. –  Colin Tan Sep 28 '13 at 11:37
add comment

3 Answers

up vote 4 down vote accepted

The approximation coming from the normal approximation of the binomial distribution is $$ k = \sqrt{-2n\ln(1-\epsilon)}.$$ To get more terms write $\Delta=-\ln(1-\epsilon)$, then by expanding $-\ln(1-i/n)$ as a Taylor series in $i$ and summing over $i=0\ldots k-1$, you get a series $$ \Delta = 1/2\,{\frac {k\, ( k-1 ) }{n}}+1/12\,{\frac {k\, ( 2\, k-1) ( k-1 ) }{n^2}}+1/12\,{\frac {{k}^{2} ( k-1) ^{2}}{{n}^{3}}} + \cdots $$ which converges if $k=O(n^c)$ for $c<1$ (but is useless if $c$ is too close to 1). The dominant term for moderately small $k$ is $k^2/2n$. You can use a series reversion method to get more terms of the inverse. I think (without much checking) that $$ k = \sqrt{2n\Delta} + \frac{3-2\Delta}{6} + \text{smaller terms},$$ and note that we are already running into the issue of $k$ being an integer.

share|improve this answer
    
Using your series for $\Delta$ is helpful. With that, I would be able to get an expression of $n$ in terms of $\Delta$ and $k$, which is my intended goal. –  Colin Tan Sep 28 '13 at 11:43
add comment

Following Vidit's idea, allow for $t=\frac{1}{n}$ to be real and positive. Then

$$ f_k(n)=f_k(t)=\prod_{j=1}^k\Bigl(\, 1-(j-1)t\,\Bigr). $$

Then $\newcommand{\eps}{\varepsilon}$

$$\eps=\eps(t)= 1-f(t) $$

satisfies $\eps(0)=0$ and

$$ \frac{d\eps}{dt}|_{t=0} =\sum_{j=1}^n (j-1)=\frac{k(k-1)}{2} \neq 0. $$

Thus $t\mapsto \eps(t)$ is strictly increasing for $t$ small and thus $t\mapsto \eps(t)$ is locally invertible near $t=0$. You are asking for its inverse

$$ t=t(\eps) $$

or more precisely its Taylor expansion near $\eps=0$. This can be found by implicit differentiation from the equation

$$\eps =1-f((t) \Rightarrow 1 =-\frac{df}{ft}(0)\cdot \frac{dt}{d\eps}. $$

Hence

$$\frac{1}{n_0(\eps)}=t=\frac{2\eps}{k(k-1)}+O(\eps^2). $$

Hence

$$n_0(\eps)=\eps^{-1}\frac{k(k-1)}{2}\bigl( 1+O(\eps)\bigr). $$

share|improve this answer
add comment

Too long to fit in a comment and render all the math correctly... but why can't we just expand out $f_k(n)$ to $$ f_k(n) = \frac{n!}{n^k(n-k)!} = \prod_{j=1}^{k}\left(1-\frac{j-1}{n}\right) $$ Since the terms in this product expansion are indexed in decreasing order, for any $k$ we immediately have, for instance: $$ \left(1-\frac{k-1}{n}\right)^{k-1} \leq f_k(n) \leq \left(1-\frac{1}{n}\right)^{k-1}.$$ On the other hand, if we want to be more refined (as indicated by your comment), one can keep track of the product more carefully. Isolating the $n^{-1}$ terms gives us: $$f_k(n) = 1 - \left(\frac{1}{n}+\cdots + \frac{k-1}{n}\right) +\text{O}(n^{-2})$$ and of course the expression in parentheses is just $\frac{k(k-1)}{2n}$.

share|improve this answer
    
Thank you Vidit. Your computation gives a lower bound for $n_0(\epsilon)$. But this lower bound may not be sharp asymptotically in $\epsilon$. –  Colin Tan Sep 27 '13 at 16:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.