Proving skip-lists strongly weight-balanced in expectation

Question

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 asked already about the claim for deterministic skip lists. This question is about the claim for skip lists.

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

• A limit theory for random skip lists
• Deterministic skip lists
• Skip trees, an alternative data structure to skip lists in a concurrent approach
• Exploring the Duality Between Skip Lists and Binary Search Trees

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$.

Answer 1

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.

Answer 2

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?

Answer 3

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.