Analysis of Skiplists

In this lesson, we analyze the expected height, size, and length of the search path in a skiplist. This section requires a background in basic probability. Several proofs are based on the following basic observation about coin tosses.

Lemma 1: Let $T$ be the number of times a fair coin is tossed up to and including the first time the coin comes up heads. Then $E[T] = 2.$

Proof: Suppose we stop tossing the coin the first time it comes up heads. Define the indicator variable

$$I_i = \begin{cases} 0 \text{\ \ \ if the coin is tossed less than $i$ times}\\ 1 \text{\ \ \ if the coin is tossed $i$ or more times} \end{cases}$$

Note that $I_i = 1$ if and only if the first $i -1$ coin tosses are tails, so $E[I_i] = \Pr \{I_i = 1\} = 1/2^{i-1}.$ Observe that $T$ , the total number of coin tosses, can be written as $T = \sum^\infty_{i = 1} I_i.$ Therefore,

$$\begin{split} E[T] & = E \left[ \sum^\infty_{i=1} I_i \right] \\ & = \sum^\infty_{i=1} E[I_i] \\ & = \sum^\infty_{i=1} 1/2^{i-1} \\ & = 1 + 1/2 + 1/4 + 1/8 + \cdots \\ & = 2 \end{split}$$ ...