1
$\begingroup$

Suppose $p \in (0,1)$. I would like to find an asymptotic equivalent of

$$f(N)=\sum_{k=1} ^N\binom{N}{k}\frac{(-1)^{k+1}}{1-p^k}.$$

It looks like this sequence tends to infinity but extremely slowly.

$\endgroup$
2
  • $\begingroup$ Intuitively, it'll go to infinity since for large $k$, $1-p^k$ is about $1$, and $\sum_{k=1}^N{N\choose k}(-1)^{k+1}=0$. Since the sum contains small values for $k$, the first couple of terms will have the largest impact on the outcome and the first couple of terms get quite large as $N$ gets large. $\endgroup$ – vrugtehagel Mar 19 '18 at 16:45
  • $\begingroup$ I know for a fact it tends to infinity because this sum is actually the expected value of a ceartain random variable. But as for the asymptotic behavior, it's not so easy I think. $\endgroup$ – Joshua Benabou Mar 19 '18 at 16:57
3
$\begingroup$

A good asymptotic approximation is $$ \sum_{k=1}^n\binom{N}{k} \frac{(-1)^{k+1}}{1-p^k} \sim \frac{\log{N}+\gamma}{\log{(1/p)}} + \frac{1}{2}, \, \, \, 0<p<1.$$

Use a geometric series for the factor involving $p$ to get the identity, $$ \sum_{k=1}^n\binom{N}{k} \frac{(-1)^{k+1}}{1-p^k} = \sum_{k=0}^\infty \Big(1-(1-p^k)^N \Big).$$

Szpankowski in 'Average case Analysis of Algorithms on Sequences' shows how to solve this for $p=1/2$ in his Example 10.6. In fact, I reference this example as a solution to MSE 2794835. The modifications necessary for $p$ in your range appear straightforward, although I expect the approximation to break down for $p$ very near the endpoints. It is also interesting that oscillatory terms appear as corrections if an even more accurate approximation as a function of $N$ is desired.

$\endgroup$
3
  • $\begingroup$ The constants are really not useful of $\sim.$ If true, it is true without $\gamma$ and $\frac12.$ What can we say about the error of this estimate? For $p=1/2$ and $n=3$ to $40000$, my data has that the difference between the sum and $\log_2(N)$ decreases and less than $\frac{1}{2}.$ But this estimate gives $\log_2(N)+\frac{1}{2}+\frac{\gamma}{\log 2}> \log_2(N)+\frac{1}{2}.$ $\endgroup$ – Thomas Andrews Apr 29 at 21:18
  • $\begingroup$ Also, shouldn't the upper bound of the sum be $N$? $\sum_{k=1}^{N}$ rather than $\sum_{k=1}^{n}?$ $\endgroup$ – Thomas Andrews Apr 29 at 21:20
  • $\begingroup$ On the other hand, $\frac{\lambda}{2}-\frac{1}{2}\approx 0.3327$ is almost exactly what I am seeing as the difference. $\endgroup$ – Thomas Andrews Apr 29 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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