MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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)$. – user2529 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)$. – user2529 Sep 28 '13 at 11:37
up vote 3 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|cite|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. – user2529 Sep 28 '13 at 11:43

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|cite|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$. – user2529 Sep 27 '13 at 16:53

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|cite|improve this answer

Your Answer

 
discard

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