Runs in coin tossing: a general approach for deriving distributions for functionals. (English) Zbl 1345.60041

Summary: We take a fresh look at the classical problem of runs in a sequence of independent and identically distributed coin tosses and derive a general identity/recursion which can be used to compute (joint) distributions of functionals of run types. This generalizes and unifies already existing approaches. We give several examples, derive asymptotics, and pose some further questions.


60G40 Stopping times; optimal stopping problems; gambling theory
60G50 Sums of independent random variables; random walks
60F99 Limit theorems in probability theory
60E10 Characteristic functions; other transforms
Full Text: DOI arXiv Euclid


[1] Ahlfors, L. V. (1978). Complex Analysis. McGraw-Hill, New York.
[2] Balakrishnan, N. and Koutras, M. V. (2002). Runs and Scans with Applications. John Wiley, New York. · Zbl 0991.62087
[3] Erdős, P. and Rényi, A. (1970). On a new law of large numbers. J. Analyse Math. 23, 103-111. · Zbl 0225.60015
[4] Erdős, P. and Révész, P. (1977). On the length of the longest headrun. In Topics in Information Theory (Colloq. Math. Soc. János Bolyai 16 ), North-Holland, Amsterdam, pp. 219-228.
[5] Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York. · Zbl 0155.23101
[6] Fu, J. C. and Lou, W. Y. W. (2003). Distribution Theory of Runs and Patterns and Its Applications. World Scientific, River Edge, NJ. · Zbl 1030.60063
[7] Gordon, L., Schilling, M. F. and Waterman, M. S. (1986). An extreme value theory for long head runs. Prob. Theory Relat. Fields 72, 279-287. · Zbl 0587.60031
[8] Graham, R. L., Knuth, D. E. and Patashnik, O. (1994). Concrete Mathematics, 2nd edn. Addison-Wesley, Reading, MA. · Zbl 0836.00001
[9] Grimmett, G. R. and Stirzaker, D. R. (2001). Probability and Random Processes, 3rd edn. Oxford University Press. · Zbl 1015.60002
[10] Guibas, L. J. and Odlyzko, A. M. (1980). Long repetitive patterns in random sequences. Z. Wahrscheinlichkeitsth. 53, 241-262. · Zbl 0424.60036
[11] Makri, F. S. and Psillakis, Z. M. (2011). On success runs of length exceeded a threshold. Methodol. Comput. Appl. Prob. 13, 269-305. · Zbl 1230.60012
[12] Murray, D. B. and Teare, S. W. (1993). Probability of a tossed coin landing on edge. Phys. Rev. E 48, 2547-2552. · Zbl 1316.60078
[13] Muselli, M. (1996). Simple expressions for success run distributions in Bernoulli trials. Statist. Prob. Lett. 31, 121-128. · Zbl 0879.60012
[14] Philippou, A. N. and Makri, F. S. (1986). Success runs and longest runs. Statist. Prob. Lett. 4, 101-105, 211-215. · Zbl 0584.60024
[15] Révész, P. (1980). Strong theorems on coin tossing. In Proceedings of the International Congress of Mathematicians Acad. Sci. Fennica, Helsinki, pp. 749-754.
[16] Von Mises, R. (1921). Zur theorie der iterationen. Z. Angew. Math. Mech. 1, 298-307. · JFM 48.0604.01
[17] Von Mises, R. (1981). Probability, Statistics and Truth. Dover, New York. · Zbl 0556.60004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.