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
    Some examples indicate something like $n-f(p)$...2012-03-08
  • 0
    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$.2012-03-08
  • 0
    Roughly speaking: Since $0 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
  • 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
    Since $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
  • 0
    Yes, I know that. So?2012-03-08
  • 0
    Oops! for $0, $log p < 0$. So my comment does not make sense then2012-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
  • 0
    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)}$.2012-03-09
  • 0
    Now 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
  • 0
    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).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