Summary
For an infinite sequence of independent coin tosses withP(Heads)=p∈(0,1), the longest run of consecutive heads in the firstn tosses is a natural object of study. We show that the probabilistic behavior of the length of the longest pure head run is closely approximated by that of the greatest integer function of the maximum ofn(1-p) i.i.d. exponential random variables. These results are extended to the case of the longest head run interrupted byk tails. The mean length of this run is shown to be log(n)+klog(n)+(k+1)log(1−p)−log(k!)+k+γ/λ−1/2+ r1(n)+ o(1) where log=log1/p , γ=0.577 ... is the Euler-Mascheroni constant, λ=ln(1/p), andr 1(n) is small. The variance is π2/6λ2+1/12 +r 2(n)+ o(1), wherer 2(n) is again small. Upper and lower class results for these run lengths are also obtained and extensions discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anderson, C.W.: Extreme value theory for a class of discrete distributions with applications to some stochastic processes. J. Appl. Probal.7, 99–113 (1970)
Barndorff-Nielsen, O.: On the rate of growth of the partial maxima of a sequence of independent and identically distributed random variables. Math. Scand9, 383–394 (1961)
Boyd, D.W.: Losing runs in Bernoulli trials. Unpublished manuscript (1972)
Carrier, G.F., Crook, M., Pearson, C.E.: Functions of a complex variable. Theory and technique. New York: McGraw Hill Book Co. 1966
Deheuvels, P.: On the Erdös-Rényi theorem for random sequences and its relationships with the theory of runs and spacing. Probab. Th. Rel. Fields70, 91–115 (1985)
Erdös, P., Révész, P.: On the length of the longest head run, pp. 219–228 in Topics in Information Theory. Colloquia Math. Soc. J. Bolyai 16 Keszthely (Hungary) (1975)
Ferguson, T.S.: On the distribution of max and mex. Manuscript (1984)
Guibas, L.J., Odlyzko, A.M.: Long repetitive patterns in random sequences. Z. Wahrscheinlichkeitstheorie verw. Gebiete53, 241–262 (1980)
Kendall, M., Stuart, A.: The Advanced Theory of Statistics. 4th Ed. Vol. 1 London and Wycombe: Charles Griffin and Co. Ltd. 1977
O'Brien, G.L.: Path properties of successive sample minima from stationary processes. Z. Wahrscheinlichkeitstheorie verw. Gebiete38, 313–327 (1977)
Robbins, H., Siegmund, D.: On the law of the iterated logarithm for maxima and minima. Proc. 6th Berkeley Sympos. Math. Statist. Probab. Univ. Calif.3, 51–70 (1972)
Rogosinski, W.: Fourier Series, New York: Chelsea Publishing Company 1959
Samarova, S.S.: On the asymptotic behaviour of the maximal sojourn time of an ergodic Markov chain in a fixed state. Russian Math. Surveys35(6), 103–104 (1980)
Solov'ev, A.O.: A combinatorial identity and its application to the problem concerning the first occurrence of a rare event. Theory Probab. Appl.11, 276–282 (1966)
Watson, G.S.: Extreme values in samples fromm-dependent stationary stochastic processes. Ann. Math. Statist. 798–800 (1954)
Author information
Authors and Affiliations
Additional information
This work was supported by a grant from the System Development Foundation
Rights and permissions
About this article
Cite this article
Gordon, L., Schilling, M.F. & Waterman, M.S. An extreme value theory for long head runs. Probab. Th. Rel. Fields 72, 279–287 (1986). https://doi.org/10.1007/BF00699107
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00699107