<p>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.</p>

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

<p>Edit: </p>

<p>Sorry, this gives you the expected number of <em>towers</em> in the left subtree.  The number of <em>nodes</em> 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.</p>

CC BY-SA 2.5
2010-11-02T09:24:52.487Z
"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
CC BY-SA 2.5
2010-11-02T10:11:57.507Z
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
CC BY-SA 2.5
2010-11-02T12:08:05.177Z
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
CC BY-SA 2.5
2010-11-02T01:45:17.750Z
2010-11-02T12:17:12.997Z
2010-11-02T12:17:12.997Z
James King
<p>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?</p>

CC BY-SA 2.5
2010-11-02T01:41:54.907Z
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
CC BY-SA 2.5
2010-11-04T09:40:25.657Z
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
CC BY-SA 2.5
2010-11-01T23:57:13.657Z
2010-11-01T23:57:13.657Z
VPatel
<p>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:</p>

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

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

<p>Some values, rounded to the nearest integer:</p>

<pre><code>k    N^*_k
1    2
2    5
3    11
4    22
5    44
10   1419
20   1.5e6
</code></pre>

<p>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.</p>

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

CC BY-SA 2.5
2010-11-04T15:55:31.940Z
2010-11-05T20:55:09.420Z
2010-11-05T20:55:09.420Z
Raphael
<p>Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor?</p>

<p>In section 2.2 of <a href="http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/" rel="nofollow noreferrer">Cache-Oblivious B-Trees</a>, <em>Strongly Weight-Balanced Search Trees</em> are defined as:</p>

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

<p>They claim:</p>

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

<p><a href="https://cstheory.stackexchange.com/questions/1876/strongly-weight-balanced-deterministic-skip-lists">I asked already about the claim for deterministic skip lists.</a> This question is about the claim for skip lists.</p>

<p>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 <a href="http://captura.uchile.cl/jspui/bitstream/2250/6130/1/Poblete_Patricio.pdf" rel="nofollow noreferrer">The binomial transform and the analysis of skip lists</a>.</p>

<p><strong>Edit:</strong></p>

<p>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</p>

<ul>
<li><a href="http://cg.scs.carleton.ca/~luc/devroye_1992_a_limit_theory_for_random_skip_lists.pdf" rel="nofollow noreferrer">A limit theory for random skip lists</a></li>
<li><a href="http://portal.acm.org/citation.cfm?id=139404.139478" rel="nofollow noreferrer">Deterministic skip lists</a></li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.514" rel="nofollow noreferrer">Skip trees, an alternative data structure to skip lists in a concurrent approach</a></li>
<li><a href="http://www.cs.clemson.edu/~bcdean/paper11.html" rel="nofollow noreferrer">Exploring the Duality Between Skip Lists and Binary Search Trees</a></li>
</ul>

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

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

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

CC BY-SA 2.5
2010-10-26T18:23:45.490Z
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
CC BY-SA 2.5
2010-10-26T19:05:11.600Z
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
CC BY-SA 2.5
2010-10-28T08:38:49.527Z
$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
CC BY-SA 2.5
2010-10-28T10:23:57.503Z
Of course, Raphael, thank you. Editing now.
jbapple
CC BY-SA 2.5
2010-11-01T14:38:38.037Z
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.
Simd
CC BY-SA 2.5
2010-11-03T18:07:35.007Z
That question "If I take a fair coin[...]" cannot be answered because it isn't well-formulated.  There needs to be a prior distribution on the possible strings.  If, on the other hand, we ask something like "If I repeatedly flip a fair coin and stop when I get heads $n$ times in a row, how is the total number of coin flips distributed?" we can give an answer because the 'stopping event' of getting heads $n$ times in a row implicitly gives a prior distribution on the possible flip sequences.
James King
CC BY-SA 2.5
2010-11-03T19:44:29.020Z
You need a distribution over $N$ (total number of tosses) for an expected value as has been pointed out. You can see that if you try to calculate the dependent probabilities. I am in the process of computing an MLE for the maximum tower height; this should work without a prior.
Raphael
<ds.data-structures><randomized-algorithms><skip-lists>
Proving skip-lists strongly weight-balanced in expectation
jbapple
# Proving skip-lists strongly weight-balanced in expectation

(Asked by: username_0 on 2010-10-24)

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](http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/), *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.](https://cstheory.stackexchange.com/questions/1876/strongly-weight-balanced-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](http://captura.uchile.cl/jspui/bitstream/2250/6130/1/Poblete_Patricio.pdf).

**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](http://cg.scs.carleton.ca/~luc/devroye_1992_a_limit_theory_for_random_skip_lists.pdf)
* [Deterministic skip lists](http://portal.acm.org/citation.cfm?id=139404.139478)
* [Skip trees, an alternative data structure to skip lists in a concurrent approach](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.514)
* [Exploring the Duality Between Skip Lists and Binary Search Trees](http://www.cs.clemson.edu/~bcdean/paper11.html)

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

**Tags:** ds.data-structures, randomized-algorithms, skip-lists

> **Comments:**
> **username_1**: 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?  
> **username_0**: I think I see what you mean, username_1 -- 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.  
> **username_1**: $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.  
> **username_0**: Of course, username_1, thank you. Editing now.  
> **username_2**: 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.  
> **username_3**: That question "If I take a fair coin[...]" cannot be answered because it isn't well-formulated.  There needs to be a prior distribution on the possible strings.  If, on the other hand, we ask something like "If I repeatedly flip a fair coin and stop when I get heads $n$ times in a row, how is the total number of coin flips distributed?" we can give an answer because the 'stopping event' of getting heads $n$ times in a row implicitly gives a prior distribution on the possible flip sequences.  
> **username_1**: You need a distribution over $N$ (total number of tosses) for an expected value as has been pointed out. You can see that if you try to calculate the dependent probabilities. I am in the process of computing an MLE for the maximum tower height; this should work without a prior.  

---

## 3 answers

### Answer by username_3 on 2010-11-02. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: "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.  
> **username_0**: OK, I've added some information about possible different meanings of "descendants". I suspect your interpretation matches that of at least two of others.  
> **username_3**: 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.  

---

### Answer by username_4 on 2010-11-01. Score: 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?

> **Comments:**
> **username_0**: 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?  
> **username_4**: 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.  

---

### Answer by username_1 on 2010-11-04. Score: 1

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.


---

