Difficulty: Intermediate-Hard | Prerequisites: Geometric distribution, expected value, indicator random variables, union bound, logarithms, linked lists.
Skip lists are a probabilistic data structure that provides expected O(log n) search in a sorted linked list by maintaining multiple "express lane" levels. The standard skip list uses a fair coin (p = 1/2) to promote items to higher levels. This problem generalises to an arbitrary promotion probability p ∈ (0,1), revealing the space-time trade-off: smaller p means fewer copies (less memory) but more levels and more items to scan per level (slower search).
Each item always appears on level 1. On each subsequent level, it appears independently with probability p. The number of copies of an item follows a geometric distribution. The entire analysis builds on this one observation.
Skip list
A layered linked list where each item appears on level 1 and is promoted to each subsequent level independently with probability p. Think of it as a linked list with random "express lanes" that let you skip ahead.
Promotion probability (p)
The probability an item on level i is also copied to level i + 1. In the standard skip list, p = 1/2. Smaller p means fewer copies but potentially slower search.
Geometric distribution
The number of trials until the first failure, where each trial succeeds with probability p. The number of levels an item appears on follows Geometric(1 - p) shifted by 1 (since it always appears on level 1).
Indicator random variable
A 0/1 variable used throughout this analysis. For example, I_i = 1 if level i has at least one item, 0 otherwise. The expected number of levels is then Σ E[I_i] = Σ Pr[level i is nonempty].
An item always appears on level 1. It appears on level 2 with probability p, on level 3 with probability p², and so on. The total number of copies is 1 + X where X ~ Geometric(1 - p) starting from 0. Equivalently:
Expected copies = 1 + p + p² + p³ + ... = 1/(1 - p)
This is a geometric series with ratio p.
There are n items, each with an expected 1/(1 - p) copies. By linearity of expectation:
Expected total size = n/(1 - p)
As p → 0, each item has close to 1 copy (almost never promoted), so total size → n. The structure shrinks toward a plain linked list.
An item reaches level i if it is promoted i - 1 times, each with probability p. So the probability a given item appears on level i is p^(i-1).
Expected items on level i = n · p^(i-1)
Define I_i = 1 if level i has at least one item. The number of levels L = Σ_{i=1}^{∞} I_i.
By linearity of expectation: E[L] = Σ_{i=1}^{∞} Pr[level i is nonempty].
Pr[level i is nonempty] = 1 - Pr[no item reaches level i] = 1 - (1 - p^(i-1))^n.
Using the union bound: Pr[level i is nonempty] ≤ n · p^(i-1).
When n · p^(i-1) < 1, i.e. i > 1 + log_{1/p}(n), the expected contribution drops below 1. The sum of the tail terms is a convergent geometric series.
So E[L] = O(log_{1/p}(n)) = O(log(n) / log(1/p)).
As p → 0, log(1/p) → ∞, so the expected number of levels grows. With very small p, items rarely get promoted, but the few that do must climb many levels for the structure to cover the data, resulting in a taller (but sparser) skip list.
On level i, the find operation scans backwards from y through items that precede y on that level. An item x preceding y on level i is accessed during find(y) only if no item between x and y on level 1 also appears on level i (otherwise the search would have dropped down to level i at that intermediate item instead).
For each item on level i that precedes y, the probability it is accessed is (1 - p)^(distance - 1) in the worst case, where distance is measured on level i. More precisely, the expected number of items scanned on level i is bounded by:
Expected items scanned on level i ≤ 1/p
This is because, scanning backwards, each step continues with probability (1 - p) (the next item was not promoted to level i + 1) and stops otherwise. This is a geometric random variable with expected value 1/p.
As p → 0, 1/p → ∞, so you scan more items per level. This is the other side of the trade-off: fewer levels but more work per level.
⚠️ Know all five key formulas: copies per item (1/(1-p)), total size (n/(1-p)), items on level i (n·p^(i-1)), expected levels (O(log n / log(1/p))), items scanned per level (1/p).
⚠️ Students often forget that the item always appears on level 1. The number of copies is 1/(1-p), not p/(1-p).
⚠️ A common mistake in part (d) is summing Pr[level i nonempty] without using the union bound to bound each term. The union bound gives Pr[nonempty] ≤ n · p^(i-1), which makes the sum tractable.
⚠️ Students sometimes confuse the space-time trade-off direction. Smaller p means less space (fewer copies) but more time (more scanning per level), and also more levels.
Quick Self-Test
Fill in the blank: For p = 1/3, the expected number of copies per item is ______. (1/(1 - 1/3) = 3/2)
True or False: As p increases toward 1, the expected total size of the skip list decreases. (False: it increases, approaching infinity.)
Fill in the blank: The expected number of items on level 3 is ______. (n · p²)
Practice Q&A
Q: Derive the expected number of copies of any particular item in a skip list with promotion probability p.
A: The item is on level 1 for certain. It is on level k (for k ≥ 2) with probability p^(k-1), since it must be promoted k-1 times. The expected number of copies is Σ_{k=1}^{∞} p^(k-1) = 1/(1-p).
Q: What is the expected total size of a skip list with n items and promotion probability p?
A: By linearity of expectation, it is n · (expected copies per item) = n/(1-p). As p → 0, this approaches n (a flat list). As p → 1, it blows up (every item appears on every level).
Q: Derive an upper bound on the expected number of levels.
A: Let I_i = 1 if level i is nonempty. E[# levels] = Σ Pr[I_i = 1] ≤ Σ min(1, n · p^(i-1)) by the union bound. The terms where n · p^(i-1) ≥ 1 contribute at most 1 + log_{1/p}(n) terms of value at most 1. The remaining terms form a convergent geometric series with sum O(1). Total: O(log n / log(1/p)).
Q: Why does the expected number of items scanned per level equal 1/p?
A: Walking backwards from y on level i, each predecessor was promoted to level i but not to level i+1 with probability 1-p. The search continues past each such item. The number of steps is geometric with success probability p, giving expected value 1/p.
Skip lists connect to balanced BSTs (same O(log n) search guarantee, achieved probabilistically rather than through rotations) and to the coupon collector problem (the analysis of expected levels uses similar union-bound reasoning). The space-time trade-off controlled by p is analogous to tuning the branching factor in B-trees.
Skip list, promotion probability, geometric distribution, expected copies, expected levels, expected size, space-time trade-off, indicator random variable, union bound, linked list, balanced BST, B-tree, randomised data structure, EECS 376