Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor?

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees, deterministic skip lists, and skip lists in the expected sense.

I believe that skip lists have this property in expectation, but I can't find a rigorous reason. The probability the other way around (what is the height, given the length) can be calculated directly to within a constant factor. A sophisticated analysis is given in The binomial transform and the analysis of skip lists.

Edit:

There are several different notions for defining "descendants" in skip lists; this term is not used in Pugh's original paper. Some possible interpretations of "descendants" come from viewing skip lists as trees. Different ways of doing this are included in

Using the notion from "Deterministic skip lists", I think this is another way of asking the same question:

If I take a fair coin, then flip it some number of times such that my last result is tails, and the longest continuous sequence of heads was of length $n$, what is the expected value of the number of times I saw tails?

I'd also be interested in non-constructive proofs of strong weight-balance in expectation, even without a closed form solution for $d$.

• For trees, height coincides with maximum number of steps to find any element. This is not the case for the height of skip list towers. For example, assume the first element has a tower of height $n-1$ ($n$ the list's length), linking to every other element in the list. The height of the associated tree would be 1 resp 2 (how do you count?) then. So, what quantitiy do you want to investigate? Tower height or lookup-cost? – Raphael Oct 26 '10 at 18:23
• I think I see what you mean, Raphael -- in the context of the original definition of strongly weight-balanced, skip-list "height" is not tree "height". I am interested in both, really, although my question was meant to be about tower height. – jbapple Oct 26 '10 at 19:05
• $P(h(x) = n | l(x) = j) = P(h(x) \leq n | l(x) = j) * P(h(x) \geq n | l(x) = j)$ does not hold; the events are not independent. – Raphael Oct 28 '10 at 8:38
• Of course, Raphael, thank you. Editing now. – jbapple Oct 28 '10 at 10:23
• Taking your reformulated question "If I take a fair coin[...]", you may get a reasonable answer at mathoverflow, if you get nothing here. If you do post there, please put a link here as well. – Raphael Nov 1 '10 at 14:38

As you asked it, the question about the expected length (given the height) does not make sense without a prior distribution on the length of the string.

You should instead consider the number of times you get tails before you get $h$ heads in a row, since this will give you the number of descendants of a node of height $h$ in a skip list. Let's represent this value with the random variable $X=X(h)$. When we start, or right after we get tails, the probability of starting and finishing a run of $h$ or more heads before getting tails again is $2^{-h}$. If we hit tails before getting $h$ heads in a row, we're back to square one. Thus $X$ is actually distributed as $\mathrm{Geometric}(2^{-h})$ and we have $\mathrm{E}(X) = (1-2^{-h})2^h$.

Edit:

Sorry, this gives you the expected number of towers in the left subtree. The number of nodes in the left subtree will be of the same order of magnitude though, since towers in between the first and last will have geometrically distributed height with expected value 2. Also, if you want to consider the right subtree as well, which probably makes more sense, you simply go until you get $h+1$ heads in a row instead of just $h$. In this case you get the number of descendants as defined in Devroye's paper that you linked to.

• "You should instead consider the number of times you get tails before you get h heads in a row, since this will give you the number of descendants of a node of height h in a skip list." Can you explain that in more detail? There are several different translations of skip lists to trees, and they give different nodes different descendants. I will edit the question to try and be more specific. – jbapple Nov 2 '10 at 9:24
• OK, I've added some information about possible different meanings of "descendants". I suspect your interpretation matches that of at least two of others. – jbapple Nov 2 '10 at 10:11
• Consider a node at the top of a tower of height $h$ at horizontal index $i$, with the next tower of height $h$ or more having index $j>i$. The descendants of the node are exactly the nodes in all towers having index at least $i$ and strictly less than $j$. In Devroye's paper, this is equivalent to the set of descendants in a node's left subtree. – James King Nov 2 '10 at 12:08

In your reformulation of the question, do you fix the number of times you flip the coin? If not, is it not necessary to give a distribution for when you stop flipping the coin?

• No, I don't fix the number of times I flip the coin. Maybe it is necessary to give a distribution, but I'm not sure. Is my translation of the problem incorrect? Does the original formulation have a well-defined answer without fixing some sort of distribution? – jbapple Nov 2 '10 at 1:41
• I think the (reformulated) question doesn't make sense without some extra information. I don't really know anything about the original question, so I can't comment on the translation. – VPatel Nov 4 '10 at 9:40

Let $H_i$ for $i \in \mathbb{N}^+$ i.i.d. random variables over $\mathbb{N}^+$ with $Pr[H_i = k] = 2^{-k-1}$ (height of tower $i$). Let $H = \max \{H_i \mid i=1,\dots,N\}$ with $N \in \mathbb{N}^+$. Then:

$Pr[H \geq k \mid N] = 1 - \prod_{i=1}^{N} Pr[H_i < k] = 1 - (1 - 2^{-k})^n$.

Now we can compute the likelihood of $H=k$ given $N$: $Pr[H = k \mid N] = Pr[H \geq k \mid N] - Pr[H \geq k + 1 \mid N] = (1-2^{-k-1})^n - (1-2^{-k})^n$. The zero of this expression's first partial derivative w.r.t. $N$ is found at $N^*_k = \frac{\ln\left( \frac{\ln(1 - 2^{-k})}{\ln(1 - 2^{-k - 1})}\right) }{ \ln(1 - 2^{-k-1}) - \ln(1 - 2^{-k})}$ (using Wolfram Alpha). Note that I was not able/eager enough to check wether or not that is really a maximum. If it is, $N^*_k$ is maximum likelihood estimator for skip list length $N$ given maximum tower height $k$.

Some values, rounded to the nearest integer:

k    N^*_k
1    2
2    5
3    11
4    22
5    44
10   1419
20   1.5e6


This feels reasonable; you might want to check wether $\mathbb{E}[k \mid N^*_k] \approx k$. I expect the expected height of a skip list for fixed length to be a standard result.

Does someone have a good idea how to get an asymptotic for $N^*_k$? The expression I found is not very helpful.