login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

%I #20 Feb 09 2017 17:34:30

%S 0,2,8,22,368,2470,7880,150266,13315424,2350261538,1777792792,

%T 340013628538,203832594062416,131294440969788022,822860039794822168,

%U 177175812995012739374,231553634961214157747264,1813465925343969651214825522,14983458468103810854318443432

%N Numerators of EH(n), the expected value of the height of a probabilistic skip list with n elements and p=1/2.

%C 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.

%C 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

%H Alois P. Heinz, <a href="/A158466/b158466.txt">Table of n, a(n) for n = 0..100</a>

%H P. V. Poblete, J. I. Munro and T. Papadakis, <a href="http://dx.doi.org/10.1016/j.tcs.2005.10.041">The binomial transform and the analysis of skip lists</a>, Theor. Comput. Sci. 352, 1 (Mar. 2006), 136-158.

%H William Pugh, <a href="http://doi.acm.org/10.1145/78973.78977">Skip lists: a probabilistic alternative to balanced trees</a>, Communications of the ACM, v.33 n.6, 668-676, June 1990

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Skip_list">Skip list</a>

%F EH(n) = Sum_{k>0} k * ((1-(1/2)^k)^n - (1-(1/2)^(k-1))^n).

%F EH(n) = -Sum_{k=1..n} (-1)^k * C(n,k) / (1-(1/2)^k).

%e 0, 2, 8/3, 22/7, 368/105, 2470/651, 7880/1953, 150266/35433, 13315424/3011805, 2350261538/513010785, 1777792792/376207909 ... = A158466/A158467

%p EH:= n-> -add((-1)^k *binomial(n,k) /(1-(1/2)^k), k=1..n):

%p seq(numer(EH(n)), n=0..20);

%t Table[Sum[x*((1-2^(-x))^n-(1-2^-(x-1))^n), {x, 1, Infinity}], {n, 0, 20}] (* _Geoffrey Critzer_, Dec 13 2009 *)

%Y Denominators of EH(n): A158467.

%Y Cf. A278327.

%K frac,nonn

%O 0,2

%A _Alois P. Heinz_, Mar 19 2009

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)