|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
frac,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|