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
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$).
-
0Since $n$ and $k$ are non-negative integers, and $0
, it has to be the later, i.e. $f(n,k) \approx 1$ for $k > \frac{\log n}{\log(1/p)}$
– 2012-03-08 -
1@KirthiRaman: I don't understand your comment. Please clarify. – 2012-03-08
-
0$ \frac{\log n}{\log(1/p)} =\frac{\log n}{-\log p} = - \frac{\log n}{\log p}$ – 2012-03-08
-
0Yes, I know that. So? – 2012-03-08
-
0Oops! for $0
, $log p < 0$. So my comment does not make sense then
– 2012-03-09 -
0@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}}$? – 2012-03-09
-
0Once 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)}$. – 2012-03-09
-
0Now I am with you, removed my post..! – 2012-03-09
-
0@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$? – 2012-03-09
-
0Sorry, 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). – 2012-03-09
-
0@RobertIsrael: Phew - now I can drink the coffee slowly, rather than chugging it. That helps a huge amount, much appreciated! – 2012-03-09
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$.
– 2012-03-08