I'm looking for pointers as to how to evaluate the asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$ for large $n$ where $0<p<1$ is fixed.
Any help is much appreciated.
Asked
Active
Viewed 216 times
6
-
Some examples indicate something like $n-f(p)$... – draks ... Mar 08 '12 at 19:42
-
That's obvious, @draks - the formula $Z_n(p)=\sum_k (1-p^k)^{n-k}$ is a polynomial in $p$ and $Z_n(0)=n$. – Thomas Andrews Mar 08 '12 at 19:45
-
Roughly speaking: Since $0<p<1$ we have $p^k$ decrease pretty fast to $0$, hence $1-p^k$ increase pretty fast to $1$, so the terms is "some what just below" $(1-p^n)$ - which would lead to the geometric sum $\sum_1^n(1-p^n)^{n-k}=\sum_0^{n-1}(1-p^n)^k=(1-(1-p^n)^n/p^n$. – AD - Stop Putin - Mar 08 '12 at 19:46
-
@ThomasAndrews so my asymptotic is right...sorry I just looked at some examples, as I already wrote. No thinking involved... – draks ... Mar 08 '12 at 20:02
1 Answers
4
Note that $f(k,n) = (1-p^k)^{n-k}$ is an increasing function of $k$ for fixed $n$. For $k = \frac{\log n}{\log(1/p)} + t$ Maple says we have, as $n \to \infty$, $f(k,n) \approx e^{-p^t} + O(1/n)$. This goes exponentially to $1$ as $t \to +\infty$ and very rapidly to $0$ as $t \to -\infty$, so I suspect the sum will be $n - \frac{\log n}{\log(1/p)} + O(1)$ as $n \to \infty$ (i.e. the error made by approximating $f(k,n)$ by $0$ for $k < \frac{\log n}{\log(1/p)}$ and $1$ for $k > \frac{\log n}{\log(1/p)}$ will be bounded as $n \to \infty$).
Robert Israel
- 448,999
-
Since $n$ and $k$ are non-negative integers, and $0<p<1$, it has to be the later, i.e. $f(n,k) \approx 1$ for $k > \frac{\log n}{\log(1/p)}$ – Kirthi Raman Mar 08 '12 at 21:49
-
1
-
$ \frac{\log n}{\log(1/p)} =\frac{\log n}{-\log p} = - \frac{\log n}{\log p}$ – Kirthi Raman Mar 08 '12 at 22:52
-
-
Oops! for $0<p<1$, $log p < 0$. So my comment does not make sense then – Kirthi Raman Mar 09 '12 at 02:06
-
@RobertIsrael: Thanks for the helpful comments. I too had thought about splitting the summation into two parts, one with terms close to zero, the other with terms close to one, but didn't see how to choose the splitting point appropriately. How did you decide on $\frac{\log n}{\log\frac{1}{p}}$? – PeterR Mar 09 '12 at 16:06
-
Once you decide you want $k = o(n)$, note that $(1-p^k)^{n-k}$ is to first order $\exp(n \log(1-p^k)) \approx \exp(n p^k)$. $n p^k \approx 1$ for $k \approx \frac{\log n}{\log (1/p)}$. – Robert Israel Mar 09 '12 at 16:13
-
-
@RobertIsrael: Thanks much. There are still (at least) two things I'm not getting. You say $\exp(n \log(1-p^k)) \approx \exp(n p^k)$, shouldn't it be $\exp(n \log(1-p^k)) \approx \exp(-n p^k)$ (negative sign)? And why are we solving $npk \approx 1$ Since this is the size of the term $f(k,n)$, wouldn't we want it to be $\exp(n p^k) \approx 1$? – PeterR Mar 09 '12 at 20:36
-
Sorry, typo: I meant $\exp(-np^k)$. It doesn't have to be $n p^k = 1$, it could be any positive constant (changing $k$ by an additive constant). – Robert Israel Mar 09 '12 at 20:41
-
@RobertIsrael: Phew - now I can drink the coffee slowly, rather than chugging it. That helps a huge amount, much appreciated! – PeterR Mar 09 '12 at 20:48