This is the expected value of the height of a skip list with $n$ elements. I have a formula for this value, but it is defined by a summation. It is, where $n$ is the number of elements,
$$f_p(n) =\sum_{k=1}^{n}\frac{\left(-1\right)^{k+1}\binom{n}{k}}{1-p^{k}}$$
I want to get a closed form for this value, in terms of $n$. I have tried using Pascal's identity, but have gotten nowhere. The first $100$ values of the numerators and denominators of this for $p = 1/2$ can be found under the OEIS, respectively A158466 and A158467. Is it possible to get a closed formula for this value and if so, what is it?
Edit: About two years later, I am still interested in the problem, but I doubt there is a closed formula. Would it be possible to find the asymptotic growth instead?
From the Wikipedia page on skip lists, the growth rate is $O(\ln(n))$, but what is the exact value of $$\lim_{n \to \infty}\frac{f_p(n)}{\ln(n)}$$
as well as the additional constant (i.e. what are the values of $c_1, c_2$ such that $f_p(n) = c_1\ln(n) + c_2 + o(1)$)? Further expansion would also be appreciated.
Looking at the graphs, it seems that $f_p(n) \sim -\log_p(n)$, which means $c_1 = – \frac{1}{\ln(p)}=-\log_p(e)$, but I couldn't find a value for $c_2$ or prove that that is the correct value for $c_1$.
Best Answer
An alternative expression for $f_p(n)$ is obtained in my later answer: $$f_p(n)=\frac12-\frac{H_n}{\ln p}+\frac{1}{\pi}\Im\sum_{m=1}^\infty\frac1m\prod_{k=1}^n\left(1+\frac{2m\pi i}{k\ln p}\right)^{-1},\quad H_n=\sum_{k=1}^n\frac1k.$$ This confirms the value of $c_1=-1/\ln p$. But, as for the "remainder", $$\lim_{n\to\infty}e^{z\ln n}\prod_{k=1}^n\left(1+\frac{z}{k}\right)^{-1}=e^{-\gamma z}\prod_{k=1}^\infty\left(1+\frac{z}{k}\right)^{-1}e^{z/k}=\Gamma(1+z),$$ so that the absolute value of each term of the $\sum_{m=1}^\infty$ tends to a finite limit as $n\to\infty$ and, while these limits are exponentially decaying with $m$, the terms themselves are oscillating like $\exp(\ldots i\ln n)$.
Thus, the "remainder" $f_p(n)+\ln n/\ln p$ oscillates around $1/2-\gamma/\ln p$, and there's no $c_2$.