login
A158466
Numerators of EH(n), the expected value of the height of a probabilistic skip list with n elements and p=1/2.
3
0, 2, 8, 22, 368, 2470, 7880, 150266, 13315424, 2350261538, 1777792792, 340013628538, 203832594062416, 131294440969788022, 822860039794822168, 177175812995012739374, 231553634961214157747264, 1813465925343969651214825522, 14983458468103810854318443432
OFFSET
0,2
COMMENTS
A probabilistic skip list is a data structure for sorted elements with O(log n) average time complexity for most operations. The probability p is a fixed internal parameter of the skip list.
n fair coins are flipped in a single toss. Those that show tails are collected and reflipped in another single toss. The process is repeated until all the coins show heads. H(n) is the discrete random variable that denotes the number of tosses required. P(H(n)<= k) = (1-(1/2)^k)^n. - Geoffrey Critzer, Dec 13 2009
LINKS
P. V. Poblete, J. I. Munro and T. Papadakis, The binomial transform and the analysis of skip lists, Theor. Comput. Sci. 352, 1 (Mar. 2006), 136-158.
William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, 668-676, June 1990
Wikipedia, Skip list
FORMULA
EH(n) = Sum_{k>0} k * ((1-(1/2)^k)^n - (1-(1/2)^(k-1))^n).
EH(n) = -Sum_{k=1..n} (-1)^k * C(n,k) / (1-(1/2)^k).
EXAMPLE
0, 2, 8/3, 22/7, 368/105, 2470/651, 7880/1953, 150266/35433, 13315424/3011805, 2350261538/513010785, 1777792792/376207909 ... = A158466/A158467
MAPLE
EH:= n-> -add((-1)^k *binomial(n, k) /(1-(1/2)^k), k=1..n):
seq(numer(EH(n)), n=0..20);
MATHEMATICA
Table[Sum[x*((1-2^(-x))^n-(1-2^-(x-1))^n), {x, 1, Infinity}], {n, 0, 20}] (* Geoffrey Critzer, Dec 13 2009 *)
CROSSREFS
Denominators of EH(n): A158467.
Cf. A278327.
Sequence in context: A238530 A303287 A321068 * A065694 A178129 A203298
KEYWORD
frac,nonn
AUTHOR
Alois P. Heinz, Mar 19 2009
STATUS
approved