# Bound on the expectancy of the maximum level in skip list

Let $M$ be a random variable for the maximum level of skip list, $M$ is a positive integer, $k$ is an integer from 0 to $\infty$, and

$$\Pr(M>k) = 1 - (1-p^k)^n \leq np^k$$

In the article Skip Lists: A Probabilistic Alternative to Balanced Trees, it is mentioned in page 4 above the head line: 'Number of comparisons,' that from the bound $np^k$ on the probability we can get that $\mathbb{E}(M) \leq L(n) + 1/(1-p)$ , where $L(n) = \log$ in base $1/p$ of $n$; $p$ is the probability that we go up a level in a certain node of the list

Here is my question: How is the $\mathbb{E}(M)$ bound calculated?

I can't get to it, only to a larger bound which is:

\begin{align*}\mathbb{E}(M) &= \Pr(M=1)+2\Pr(M=2) + \dots \\ & = \Pr(M>0)-\Pr(M>1) + 2\Pr(M>1)-2\Pr(M>2)+ \dots \\ &= \Pr(M>0) + \Pr(M>1) + \Pr(M>2)+ \dots \\ &\leq \sum np^k = n \sum p^k = {n \over (1-p)}\end{align*}

• The details matter: I notice you write summations without specifying the indexes or their limits. This hides the fact that the sum is intended to begin at $L(n)$, which will multiply the value you computed by $p^{L(n)}=1/n$. – whuber Nov 8 '14 at 18:58
• i love you whuber – TheLastOfTheMoops Nov 8 '14 at 19:21