Such a sequence, called a finite Bernoulli sequence,

is of particular importance in studies of applied probability

because of its simplicity, and also since it may be considered as

a special case of a sequence with dependent elements; e.g. a

Markovian or an exchangeable one.

For a Bernoulli sequence of length , let

denote the probability mass function (PMF) of the RV

; i.e.

,

, . (2)

Then, the expected value of

,

(3)

is given by (see Makri et al. [11])

In the sequel, we consider a symmetric () finite

Bernoulli sequence (i.e. a finite binary string) of length for

which we obtain our main results. Since the cardinality of a

proper sample space is (i.e. there are binary strings that

are equally likely to occur) the classical definition of

probability implies that

. (5)

The numbers

,

, for admit the

following interpretation: (i)

, is the number of

all binary strings of length with exactly

, 1-runs of length [exactly (),

at least ()] , among all the possible binary strings of

length , . (ii)

is the number of all binary

strings of length with exactly n, 1s

contained in all 1-runs of length at least , among all the

possible binary strings of length , .

Simple explicit expressions of

(not repeated here) are

given in Makri and Psillakis [19]. The authors provided an

explicit formula of

, for in terms of binomial

coefficients. Their method is based on the solution of a

combinatorial problem; specifically, the allocation of balls into

cells under certain constrains (see Lemma 2.2 of [11]). An

explicit expression of

, in terms of binomial coefficients

too, is given by Sinha and Sinha [1] who used a generating

function approach. The latter expression contains an additional

sum; therefore it may be evaluated slower computationally than

that provided in [19].

The numbers

allow us to establish (we do not actually

need their specific expressions according to the new proposed

approach) respective numbers referring to all possible

binary strings of length . They are defined as

, (6)

i.e.

is the total number of occurrences of all 1-runs of

length [exactly (), at least ()] , and the total

number of 1s in all 1-runs of length at least [], in all

possible binary strings of length , .

Since

, hence

by (5) and (6),

. Therefore (4) implies

(7)

Readily, by symmetry,

provides the respective

numbers associated with 0-runs and 0s in 0-runs.

By (7) it is noted that for a fixed ,

,

decreases exponentially as increases, and for a fixed

, as , it holds

(8)

Furthermore,

, since ,

.

Table I presents the three numbers

in binary

strings of length bits, , and for . The

entries of the table confirm the previously noted behavior of

the depicted numbers.

Sinha [31] was the first who addressed the usefulness of the

number

and also provided its formula. Then, Sinha and

Sinha [1] obtained an explicit expression of

whereas

Copyright © 2012 SciRes.

45

Makri and Psillakis [19] derived the same formula for it and

they also established an explicit expression of

. In both

papers ([1] and [19]) the approach was relied on the definition

of

via

, . Recently, Sinha and Sinha [2]

reestablished

solving explicitly a recursive generation

scheme for it.

The proposed, in the present note, approach is a new one

and treats under the same frame all the numbers

in a

simple, unified and systematic way. Accordingly, by (7) we

effortless get a recursive scheme for

, . It gives a

way to generate

from

and it offers further insight in

understanding the interdependencies among the studied

numbers. Specifically, it holds

(9)

with

. We note that

for the particular case we capture by the relevant entries

of (9) and (7), Theorems 2 and 3 of [2], respectively.

TABLE I. NUMBERS OF OCCURRENCES OF 1-RUNS,

AND

NUMBER OF 1S,

, IN BINARY STRINGS OF LENGTH

4

1

12

20

32

2

5

8

20

3

2

3

10

4

1

1

4

16

1

147456

278528

524288

2

69632

131072

376832

3

32768

61440

237568

4

15360

28672

139264

5

7168

13312

77824

6

3328

6144

41984

7

1536

2816

22016

8

704

1280

11264

9

320

576

5632

10

144

256

2752

11

64

112

1312

12

28

48

608

13

12

20

272

14

5

8

116

15

2

3

46

16

1

1

16

3. Conlusions

In this note we stated three run statistics which are

important in many areas of applied probability. We defined

them on a binary (0-1) sequence, and we then provided

explicitly their mean values for a Bernoulli sequence. After that,

we considered binary strings (symmetric Bernoulli sequences)

and we showed how the analytic expressions of the means of

these RVs provide eventually the respective explicit

expressions of three numbers studied recently by different

methods. Finally, as a byproduct of our approach, we proposed

a unified recursive scheme which clarifies further the

interdependencies among these numbers. The examined

numbers are potential useful in many engineering applications

like the ones mentioned briefly in the Introduction. Early

results are encouraging in this direction.

REFERENCES

[1] K. Sinha and B. P. Sinha, “On the distribution of runs of

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.

46

Copyright © 2012 SciRes.

[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.

Copyright © 2012 SciRes.

47