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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059943 Toss a fair coin and calculate the expected time until the n-th possible finite sequence of Heads and Tails first appears (ordered by length of sequence and alphabetical order so H, T, HH, HT, TH, TT, HHH, etc.). 4
2, 2, 6, 4, 4, 6, 14, 8, 10, 8, 8, 10, 8, 14, 30, 16, 18, 16, 18, 20, 18, 16, 16, 18, 20, 18, 16, 18, 16, 30, 62, 32, 34, 32, 38, 32, 34, 32, 34, 36, 42, 32, 34, 36, 34, 32, 32, 34, 36, 34, 32, 42, 36, 34, 32, 34, 32, 38, 32, 34, 32, 62, 126, 64, 66, 64, 70, 64, 66, 64, 70, 72 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Note the apparent paradox: HHHHHH, HTHTHT and HHHFFF are all equally likely to appear in six tosses of the coin (1/64) and in a long sequence each is expected to appear as a subsequence roughly as many times as the others, but the expected time for HHHHHH to first appear (126) is almost twice as long as for HHHFFF (64), with HTHTHT between the two (84). This is related to the fact that in a sequence of, say, 8 successive tosses, HHHHHH could appear as a subsequence 3 times simultaneously, HTHTHT twice but HHHTTT only once.

REFERENCES

M. Gardner, Chapter 5 in Time Travel and Other Mathematical Bewilderments, W. H. Freeman, 1988, pp. 63-67.

Michael Hochster in sci.math and sci.stat.math quoting from Stochastic Processes by Sheldon Ross.

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

FORMULA

a(n) = 2*A059942(n). For the n-th sequence S (e.g., the 35th is HHTHH), create the set X consisting of subsequences of S which appear both at the beginning and end of S (e.g., X={H, HH, HHTHH}), then a(n) = sum_x(2^length(x)|x is in X) (e.g., a(35)=2^1+2^2+2^5=38).

EXAMPLE

a(35)=38 since the expected time from xxxHHTH to completion of xxxHHTHH is 20, from xxxHHT to completion is 30, from xxxHH to completion is 32, from xxxH to completion is 36 and from xxx to completion is 38 (xxx is an earlier subsequence, perhaps empty, which cannot contribute to completion).

MATHEMATICA

a[n_] := (id = Drop[ IntegerDigits[n+1, 2], 1]+1; an={}; Do[PrependTo[an, If[Take[id, k] == Take[id, -k], 1, 0]], {k, 1, Length[id]}]; 2*FromDigits[an, 2]); Table[a[n], {n, 1, 72}] (* Jean-Fran├žois Alcover, Nov 21 2011 *)

PROG

(Haskell)

a059943 = (* 2) . a059942  -- Reinhard Zumkeller, Apr 03 2014

CROSSREFS

Cf. A007931, A059941, A059942.

Sequence in context: A193819 A182786 A009279 * A264695 A112336 A028390

Adjacent sequences:  A059940 A059941 A059942 * A059944 A059945 A059946

KEYWORD

nice,nonn

AUTHOR

Henry Bottomley, Feb 14 2001

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 February 16 21:59 EST 2019. Contains 320200 sequences. (Running on oeis4.)