login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 0..100

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

Adjacent sequences:  A158463 A158464 A158465 * A158467 A158468 A158469

KEYWORD

frac,nonn

AUTHOR

Alois P. Heinz, Mar 19 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 02:51 EST 2019. Contains 319323 sequences. (Running on oeis4.)