Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it true that $\frac1{n!} \int_0^\infty x^{n-k} (x-1)^k e^{-x}\,dx \approx e^{-k/n}$ when $k$ and $n$ are large integers with $k \le n$?

This quantity is the probability that a random permutation of $n$ elements does not fix any of the first $k$ elements.

share|improve this question
    
My few tries on mathematica seem to suggest it is correct. –  picakhu Dec 20 '10 at 7:05
1  
Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, Mike's equivalent of $S_{n,k}/n!$ implies that the limit you asked for is $(2-a)/\mathrm{e}$ (I think). On the other hand, Shai's answer implies that this limit is $\mathrm{e}^{-a}$. You accepted Shai's answer and also agreed with the part of Mike's answer which yields the limit $(2-a)/\mathrm{e}$. How is this possible? Which answer do you think is correct? –  Did Mar 6 '11 at 12:38
add comment

5 Answers 5

up vote 7 down vote accepted

Here's a heuristic idea, based on the strong law of large numbers (SLLN). A rigorous proof can be made using the central limit theorem (CLT), as in my new answer.

First write $$ I = \frac{1}{{n!}}\int_0^\infty {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} = \int_0^\infty {\bigg(1 - \frac{1}{x}} \bigg)^k \frac{{x^n e^{ - x} }}{{\Gamma (n + 1)}}\,{\rm d}x. $$ Now, if $X_1,\ldots,X_{n+1}$ are i.i.d. exponential(1) random variables, then their sum $X_1 + \cdots + X_{n+1}$ has gamma density $x^n e^{-x} / \Gamma(n+1)$, $x > 0$. Hence, $$ I = {\rm E} \bigg[ 1 - \frac{1}{{X_1 + \cdots + X_{n + 1} }}\bigg]^k = {\rm E}\bigg[1 - \frac{{n + 1}}{{X_1 + \cdots + X_{n + 1} }}\frac{1}{{n + 1}}\bigg]^k . $$ By SLLN, $(n + 1)^{ - 1} \sum\nolimits_{i = 1}^{n + 1} {X_i }$ converges almost surely to ${\rm E}[X_1 ] = 1$ as $n \to \infty$. So this suggests the approximation $$ I \approx \bigg(1 - \frac{1}{{n + 1}}\bigg)^k = \bigg(1 - \frac{1}{{n + 1}}\bigg)^{n(k/n)} \approx e^{ - k/n}. $$

share|improve this answer
add comment

A rigorous proof can be made using the central limit theorem (CLT), as follows.

Since $$ \frac{1}{{n!}}\int_0^1 {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \to 0 $$ as $n \to \infty$, it suffices to consider the integral from $1$ to $\infty$. Let $c>0$ be arbitrary but fixed, and let $X_i$ be as in my previous answer. Define $f_n {(x)} = x^n e^{-x} / \Gamma(n+1)$, $x>0$, and put $n'=n+1$. Then, since $f_n$ is the density of $\sum\nolimits_{i = 1}^{n'} {X_i }$, $$ \frac{1}{{n!}}\int_1^{n' - c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \int_0^{n' - c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} \le - c \bigg). $$ By the CLT, since the $X_i$ have unit mean and unit variance, the probability on the right-hand side tends to $\Phi(-c)$ as $n \to \infty$, where $\Phi$ denotes the distribution function of the standard normal distribution. Similarly, $$ \frac{1}{{n!}}\int_{n' + c\sqrt {n'} }^\infty {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \int_{{n'} + c\sqrt {n'} }^\infty {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} > c \bigg), $$ and, by the CLT, the probability on the right-hand side tends to $1 - \Phi(c)$ as $n \to \infty$. Next, note that $$ \bigg(1 - \frac{1}{{n' - c\sqrt {n'} }}\bigg)^k \int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} \leq \frac{1}{{n!}}\int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} $$ and $$ \frac{1}{{n!}}\int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n - k} (x - 1)^k e^{ - x} \,{\rm d}x} \leq \bigg(1 - \frac{1}{{n' + c\sqrt {n'} }}\bigg)^k \int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x}. $$ By the CLT, $$ \int_{n' - c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(-c \leq \frac{{\sum\nolimits_{i = 1}^{n'} {X_i } - n'}}{{\sqrt {n'} }} \leq c \bigg) \to 2 \Phi(c) -1 $$ as $n \to \infty$. Combining it all, and noting that $$ \bigg(1 - \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^k = \bigg(1 - \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^{n(k/n)} \approx e^{ - k/n}, $$ the result follows by choosing $c$ sufficiently large. [Note that first we choose $c$ sufficiently large, then we let $n \to \infty$.]

share|improve this answer
    
Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, Mike's equivalent of $S_{n,k}/n!$ implies that the limit asked by the OP is $(2-a)/\mathrm{e}$ (I think). On the other hand, your answer implies that this limit is $\mathrm{e}^{-a}$. Which one is correct? –  Did Mar 6 '11 at 12:34
    
@Didier: I'll check this, and let you know (hopefully today). –  Shai Covo Mar 6 '11 at 13:19
    
@Didier: I confirmed my answer using WolframAlpha and Wims Function Calculator. –  Shai Covo Mar 6 '11 at 16:54
    
Great. See my comment to Mike's post. –  Did Mar 7 '11 at 13:22
add comment

Update: This argument only holds for some cases. See italicized additions below.

Let $S_{n,k}$ denote the number of permutations in which the first $k$ elements are not fixed. I published an expository paper on these numbers earlier this year. See "Deranged Exams," (College Mathematics Journal, 41 (3): 197-202, 2010). Aravind's formula is in the paper, as are several others involving $S_{n,k}$ and related numbers.

Theorem 7 (which I also mention in this recent math.SE question) is relevant to this question. It's $$S_{n+k,k} = \sum_{j=0}^n \binom{n}{j} D_{k+j},$$ where $D_n$ is the number of derangements on $n$ elements. See the paper for a simple combinatorial proof of this.

Since $D_n$ grows as $n!$ via $D_n = \frac{n!}{e} + O(1)$ (see Wikipedia's page on the derangement numbers), and if $k$ is much larger than $n$, the dominant terms in the probability $\frac{S_{n+k,k}}{(n+k)!}$ are the $j = n$ and $j = n-1$ terms from the Theorem 7 expression. Thus we have $$\frac{S_{n+k,k}}{(n+k)!} \approx \frac{D_{n+k} + n D_{n+k-1}}{(n+k)!} \approx \frac{1}{e}\left(1 + \frac{n}{n+k}\right) \approx e^{-1} e^{\frac{n}{n+k}} = e^\frac{-k}{n+k},$$ where the second-to-last step uses the first two terms in the Maclaurin series expansion for $e^x$.

Again, this argument holds only for (in my notation) $k$ much larger than $n$.

share|improve this answer
    
I agree with everything except $1 + \frac{n}{n+k} \approx e^{\frac{n}{n+k}}$, which doesn't hold because $\frac{n}{n+k}$ is not close to 0. –  Dave Radcliffe Dec 23 '10 at 4:26
    
@Dave R: I've thought about this for the past couple of hours and almost posted a more precise estimate, but I think the simplest way past the difficulty really is that my argument works unless $n$ is large relative to $k$ (which would make $\frac{n}{n+k} \approx 1$). But if this is the case, then Hans Lundmark's answer (in my notation) shows that the probability is approximately $1 - \frac{k}{n+k} \approx e^{\frac{-k}{n+k}}$. So I think between my answer and Hans's you have the argument you need. (And I will now upvote Hans's and Aravind's answers accordingly.) –  Mike Spivey Dec 23 '10 at 7:08
    
@Mike Fix $a\in(0,1)$. If $k$ and $n$ go to infinity with $k/n\to a$, your equivalent of $S_{n,k}/n!$ implies that the limit asked by the OP is $(2-a)/\mathrm{e}$ (I think). On the other hand, Shai's answer implies that this limit is $\mathrm{e}^{-a}$. Which one is correct? –  Did Mar 6 '11 at 12:34
    
@Didier: Good question. Let me think about it. –  Mike Spivey Mar 6 '11 at 14:13
    
@Didier: With your comment and the OP's I'm realizing that my argument only applies for certain values of $n$ and $k$. In my notation, we need $k$ to remain much larger than $n$ in order to have the approximation $1 + \frac{n}{n+k} \approx e^{\frac{n}{n+k}}$ be a good one. So one can't hold that ratio you mention constant and then use my argument to get an accurate limiting value. I haven't checked Shai's work myself, but if I had to choose between $(2-a)/e$ and $e^{-a}$ for the limiting value, I would go with the latter. –  Mike Spivey Mar 7 '11 at 3:42
show 1 more comment

This is not an answer but an observation that the quantity is equal to $\sum_{i=0}^{k} \frac{{(-1)}^i}{n!}{k \choose i}(n-i)!$.

share|improve this answer
add comment

Continuing Aravind's observation, write it like $$ 1 - \frac{k}{n} + \frac{1}{2!} \left( \frac{k}{n} \right)^2 \frac{1-1/k}{1-1/n} - \frac{1}{3!} \left( \frac{k}{n} \right)^3 \frac{(1-1/k)(1-2/k)}{(1-1/n)(1-2/n)} $$ $$+ \dots + (-1)^k \frac{1}{k!} \left( \frac{k}{n} \right)^k \frac{(1-1/k)(1-2/k)\dots (1-(k-1)/k)}{(1-1/n)(1-2/n) \dots (1-(k-1)/n)}. $$ If $k$ and $n$ are large, this seems to be close to the $k$th degree Maclaurin polynomial for $e^z$ evaluated at $z=-k/n$ (although I don't have an estimate of the error).

share|improve this answer
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.