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 is fixed. Any help is much appreciated.
Asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$
6
$\begingroup$
asymptotics
-
0@ThomasAndrews so my asymptotic is right...sorry I just looked at some examples, as I already wrote. No thinking involved... – 2012-03-08
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$).
-
0@RobertIsrael: Phew - now I can drink the coffee slowly, rather than chugging it. That helps a huge amount, much appreciated! – 2012-03-09