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*}$$

  • $\begingroup$ 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$. $\endgroup$ – whuber Nov 8 '14 at 18:58
  • $\begingroup$ i love you whuber $\endgroup$ – TheLastOfTheMoops Nov 8 '14 at 19:21

Your Answer

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

Browse other questions tagged or ask your own question.