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