Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Some examples indicate something like $n-f(p)$... –  draks ... Mar 8 '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 8 '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. Mar 8 '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 8 '12 at 20:02
add comment

1 Answer

up vote 4 down vote accepted

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$).

share|improve this answer
    
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 8 '12 at 21:49
1  
@KirthiRaman: I don't understand your comment. Please clarify. –  Robert Israel Mar 8 '12 at 22:07
    
$ \frac{\log n}{\log(1/p)} =\frac{\log n}{-\log p} = - \frac{\log n}{\log p}$ –  Kirthi Raman Mar 8 '12 at 22:52
    
Yes, I know that. So? –  Robert Israel Mar 8 '12 at 23:08
    
Oops! for $0<p<1$, $log p < 0$. So my comment does not make sense then –  Kirthi Raman Mar 9 '12 at 2:06
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.