Challenge X: French fish

  • Thread starter micromass
  • Start date
  • #1
22,089
3,293
Find the following limit:

[tex]\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!}[/tex]
 

Answers and Replies

  • #2
611
23
Find the following limit:

[tex]\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!}[/tex]
I have the vaguest feeling that the limit is 1. I'm too tired to prove it right now. I'll get back to it soon. :tongue:

Edit: Probably not. Looking at it now, as shown below, it is an upper bound. Taking the expansion out a couple terms, it looks like it's less than 0.6.

Why is this called french fish? Is this hinting at using something by Poisson?
 
Last edited:
  • #3
35,152
11,405
Well, 1 is an upper limit:
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} \leq \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^\infty \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} 1 = 1$$

It is interesting that
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^{n-1} \frac{n^k}{k!}$$ but I am not sure how to convert this to a lower limit on the limit.

Edit: Okay, that approach does not work. And the limit is not 1. I guess 1/2.

The question can be re-phrased as "in a Poisson distribution with expectation value n, what is the probability to get at most the expectation value?" - and then the limit of n->infinity. As the Poisson distribution approaches a Gaussian distribution, I would expect 1/2 as limit.
 
Last edited:
  • #4
22,089
3,293
Well, 1 is an upper limit:
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} \leq \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^\infty \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} 1 = 1$$

It is interesting that
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^{n-1} \frac{n^k}{k!}$$ but I am not sure how to convert this to a lower limit on the limit.

Edit: Okay, that approach does not work. And the limit is not 1. I guess 1/2.

The question can be re-phrased as "in a Poisson distribution with expectation value n, what is the probability to get at most the expectation value?" - and then the limit of n->infinity. As the Poisson distribution approaches a Gaussian distribution, I would expect 1/2 as limit.
Right. The limit is indeed 1/2. And an application of the central limit theorem gives the answer. Well done!
 
  • #5
300
22
I worked out that the limit is less than or equal to 0.5:

Reversing it and using the Taylor series for e:
[tex]\frac{e^{n}}{ \sum_{k=0}^n \frac{n^k}{k!}}=1+\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}[/tex]
Introducing [itex]x=\frac{n^n}{n!}[/itex]
[tex]\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}=\frac{x \frac{n}{n+1}+x \frac{n}{n+1} \frac{n}{n+2}+...}{x+x+x\frac{n-1}{n}+x\frac{n-1}{n}\frac{n-2}{n}+...}=\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{2+\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}[/tex]
The number of terms in the numerator is infinity, the denominator goes until the terms reach zero. For very large n we have a lot of terms close to 1, so we can neglect the 2. Since [itex]\frac{n}{n+a} > \frac{n-a}{n}[/itex] and replacing some of the terms in the numerator like that to get a 1 the result is:
[tex]\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}>1+\frac{\sum_{k=1}^\infty \frac{(n)!n^k}{(2n+k)!}}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}[/tex]
For large n the numerator of the second term goes to zero.

When I discarded the 2, maybe the denominator and numerator are quite equal, their difference is small and the 2 makes the denominator actually bigger. But in the limit it should be negligible, so the limit of the reciprocal is 2 or larger and the limit of the original expression is 0.5 or smaller.
 
  • #6
lurflurf
Homework Helper
2,440
138
You really like Obfuscation.
since
$$e^{-n} \sum_{k=0}^n \frac{n^k}{k!}=\left( 1+ \gamma(n+1,n)/\Gamma(n+1,n) \right)^{-1}$$
Why not just ask
$$\lim_{n\rightarrow \infty} \gamma(n+1,n)/\Gamma(n+1,n)=\lim_{n\rightarrow \infty} \int_0^n t^n e^{-t} \mathrm{d}t {\huge/} \int_n^\infty t^n e^{-t} \mathrm{d}t=1$$
 
  • #7
22,089
3,293
You really like Obfuscation.
You don't seem to grasp the concept of a challenge :tongue:
 
  • #8
22,089
3,293
Well done by mfb for finding the solution. The (partial) solution by chingel is also very nice!

And a special thanks to lurflurf for showing another neat interpretation of this problem!
 

Related Threads on Challenge X: French fish

Replies
9
Views
4K
  • Last Post
Replies
9
Views
7K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
3K
Replies
18
Views
2K
  • Last Post
Replies
15
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
86
Views
14K
Top