6
$\begingroup$

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.

  • 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 1

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