Counting Runs of Ones and Ones in Runs of Ones in Binary Strings

Frosso S. Makri, Zaharias M. Psillakis, Nikolaos Kollas

Departments of Mathematics and Physics, University of Patras Patras, Greece.

DOI: 10.4236/ojapps.2012.24B011                

Abstract

Consider a binary string (a symmetric Bernoulli sequence) of length . For a positive integer , we exactly enumerate, in all  possible binary strings of length , the number of all runs of 1s of length (equal, at least)  and the number of 1s in all runs of 1s of length at least . To solve these counting problems, we use probability theory and we obtain simple and easy to compute explicit formulae as well as recursive schemes, for these potential useful in engineering numbers.

Keywords

runs; symmetric Bernoulli trials; probability theory; combinatorial problems

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	ones in binary strings,” Comput. Math. Appl., vol. 58, pp. 1816-1829, 2009.
[2]	K. Sinha and B. P. Sinha, “Energy-efficient communication: understanding the distribution of runs in binary strings,” 1st International Conference on Recent Advances in Information Technology (RAIT-2012), pp. 177-181, 2012.
[3]	G. Benson, “Tandem repeats finder: a program to analyze DNA sequences,” Nucleic Acids Res., vol. 27, pp. 573-580, 1999.
[4]	W.Y. W. Lou, “The exact distribution of the “-tuple statistic for sequence homoloy,” Statist. Probab. Lett., vol. 61, pp. 51-59, 2003.
[5]	G. Nuel, L. Regad, J. Martin and A.C. Camproux, “Exact distribution of a pattern in a set of random sequences generated by a Markov source: applications to biological data,” Alg. Mol. Biol., vol. 5, pp. 1-18, 2010.
[6]	N. Balakrishnan and M. V. Koutras, Runs and Scans with Applications, New York: Wiley, 2002.
[7]	J. C. Fu and W. Y. W. Lou, Distribution Theory of Runs and Patterns and its Applications: A Finite Markov Imbedding Approach, New Jersey: World Scientific, 2003.
[8]	M. V. Koutras, “Applications of Markov chains to the distribution theory of runs and patterns,” in Handbook of Statistics, vol. 21, D. N. Shanbhag, C. R. Rao, Eds. North Holland: Elsevier, 2003, pp. 431-472.
[9]	S. Eryilmaz, “Success runs in a sequence of exchangeable binary trials,” J. Statist. Plann. Inference, vol. 137, pp. 2954-2963, 2007.
[10]	F. S. Makri, A.N. Philippou and Z. M. Psillakis, “Polya, inverse Polya, and circular Polya distributions of order for -overlapping success runs,” Commun. Statist. Theory Methods, vol. 36, pp. 657-668, 2007.
[11]	F. S. Makri, A. N. Philippou and Z. M. Psillakis, “Success run statistics defined on an urn model,” Adv. Appl. Probab., vol. 39, pp. 991-1019, 2007.
[12]	S. Eryilmaz, “Run statistics defined on the multicolor urn model,” J. Appl. Probab., vol. 45, pp. 1007-1023, 2008.
[13]	S. Demir and S. Eryilmaz, “Run statistics in a sequence of arbitrarily dependent binary trials,” Stat. Papers, vol. 51, pp. 959-973, 2010.
[14]	K. Inoue and S. Aki, “On the conditional and unconditional distributions of the number of success runs on a circle with applications,” Statist. Probab. Lett., vol. 80, pp. 874-885, 2010.
[15]	F. S. Makri, “On occurences of strings in linearly and circularly ordered binary sequences,” J. Appl. Probab., vol. 47, pp. 157-178, 2010.
[16]	F. S. Makri, “Minimum and maximum distances between failures in binary sequences,” Statist. Probab. Lett., vol. 81, pp. 402-410, 2011.
[17]	F. S. Makri and Z. M. Psillakis, “On runs of length exceeding a threshold: normal approximation,” Stat. Papers, vol. 52, pp. 531-551, 2011.
[18]	F. S. Makri and Z. M. Psillakis, “On success runs of length exceeded a threshold,” Methodol. Comput. Appl. Probab., vol. 13, pp. 269-305, 2011.
[19]	F. S. Makri and Z. M. Psillakis, “On success runs of a fixed length in Bernoull sequences: exact and aymptotic results,” Comput. Math. Appl., vol. 61, pp. 761-772, 2011.
[20]	S. D. Dafnis, A. N. Philippou and D. L. Anztoulakos, “Distributions of patterns of two successes separeted by a string of failures,” Stat. Papers, vol. 53, pp. 323-344, 2012.
[21]	M. V. Koutras and F. S. Milienos, “Exact and asymptotic results for pattern waiting times,” J. Statist. Plann. Inference, vol. 142, pp. 1464-1479, 2012.
[22]	F. S. Makri and Z. M. Psillakis, “Counting certain binary strings,” J. Statist. Plann. Inference, vol. 142, pp. 908-924, 2012.
[23]	A. M. Mood, “The distribution theory of runs,” Ann. Math. Stat., vol. 11, pp. 367-392, 1940.
[24]	J. C. Fu and M. V. Koutras, “Distribution theory of runs: a Markov chain approach,” J. Amer. Statist. Assoc., vol. 89, pp. 1050-1058, 1994.
[25]	D. L. Antzoulakos, “On waiting time problems associated with runs in Markov dependent trials,” Ann. Inst. Statist. Math., vol. 51, pp. 323-330, 1999.
[26]	Q. Han and S. Aki, “Joint distributions of runs in a sequence of multi-trials,” Ann. Inst. Statist. Math., vol. 51, pp. 419-447, 1999.
[27]	J. C. Fu, W. Y. W. Lou, Z. Bai and G. Li, “The exact and limiting distributions for the number of successes in success runs within a sequence of Markov-dependent two-state trials,” Ann. Inst. Statist. Math., vol. 54, pp. 719-730, 2002.
[28]	K. Sen, M. L. Agarwal and S. Chakraborty, “Lenths of runs and waiting time distributions by using Polya-Eggenberger sampling scheme,” Studia Sci. Math. Hungar., vol. 2, pp. 309-332, 2002.
[29]	D. L. Antzoulakos, S. Bersimis and M. V. Koutras, “On the distribution of the total number of run lengths,” Ann. Inst. Statist. Math., vol. 55, pp. 865-884, 2003.
[30]	D. E. Martin, “Distribution of the number of successes in success runs of length at least in higher-order Markovian sequences,” Methodol. Comput. Appl. Probab., vol. 7, pp. 543-554, 2005.
[31]	K. Sinha, Location and communication issues in mobile networks. Ph. D. Dissertaion, Department of Computer Science and Engineering, Jadavpur University, Calcutta, India , 2007.