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