cp's OEIS Frontend

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

%I A158466 #20 Feb 09 2017 17:34:30
%S A158466 0,2,8,22,368,2470,7880,150266,13315424,2350261538,1777792792,
%T A158466 340013628538,203832594062416,131294440969788022,822860039794822168,
%U A158466 177175812995012739374,231553634961214157747264,1813465925343969651214825522,14983458468103810854318443432
%N A158466 Numerators of EH(n), the expected value of the height of a probabilistic skip list with n elements and p=1/2.
%C A158466 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 A158466 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 A158466 Alois P. Heinz, <a href="/A158466/b158466.txt">Table of n, a(n) for n = 0..100</a>
%H A158466 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 A158466 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 A158466 Wikipedia, <a href="https://en.wikipedia.org/wiki/Skip_list">Skip list</a>
%F A158466 EH(n) = Sum_{k>0} k * ((1-(1/2)^k)^n - (1-(1/2)^(k-1))^n).
%F A158466 EH(n) = -Sum_{k=1..n} (-1)^k * C(n,k) / (1-(1/2)^k).
%e A158466 0, 2, 8/3, 22/7, 368/105, 2470/651, 7880/1953, 150266/35433, 13315424/3011805, 2350261538/513010785, 1777792792/376207909 ... = A158466/A158467
%p A158466 EH:= n-> -add((-1)^k *binomial(n,k) /(1-(1/2)^k), k=1..n):
%p A158466 seq(numer(EH(n)), n=0..20);
%t A158466 Table[Sum[x*((1-2^(-x))^n-(1-2^-(x-1))^n), {x, 1, Infinity}], {n, 0, 20}] (* _Geoffrey Critzer_, Dec 13 2009 *)
%Y A158466 Denominators of EH(n): A158467.
%Y A158466 Cf. A278327.
%K A158466 frac,nonn
%O A158466 0,2
%A A158466 _Alois P. Heinz_, Mar 19 2009