# On the Expected Number of Limited Length Binary Strings Derived by Certain Urn Models

Authors: Frosso S. Makri; Zaharias M. Psillakis
Journal: Journal of Probability
 (2014)

---

## Abstract

The expected number of 0-1 strings of a limited length is a potentially useful index of the behavior of stochastic processes describing the occurrence of critical events (e.g., records, extremes, and exceedances). Such model sequences might be derived by a Hoppe-Polya or a Polya-Eggenberger urn model interpreting the drawings of white balls as occurrences of critical events. Numerical results, concerning average numbers of constrained length interruptions of records as well as how on the average subsequent exceedances are separated, demonstrate further certain urn models.


---

## Body

## 1. Introduction and Preliminaries

Recently, some researches associated with the number of patterns which consist of runs of zeros (0s) between subsequent ones (1s) in sequences of binary random variables (RVs) have appeared in the literature. The 0-1 sequences {Xn}n≥1 may have several internal structures including among others sequences of independent but not necessarily identically distributed (INID) RVs, with P(X1=x1,X2=x2,…,Xn=xn)=∏i=1n‍pi, xi∈{0,1}, and pi=P(Xi=1)=1-P(Xi=0)=1-qi, i=1,2,…,n, and sequences of exchangeable (EXCH) or symmetrically dependent RVs, the joint distribution of which is invariant under any permutation of its arguments; that is, for any n>0 and any vector (x1,x2,…,xn), xi∈{0,1}, it holds that pn(s)=P(Xπ1=x1,Xπ2=x2,…,Xπn=xn)=P(X1=x1,X2=x2,…,Xn=xn) for any permutation (π1,π2,…,πn) of the set {1,2,…,n} and s=∑i=1n‍xi. A common ground for both INID and EXCH sequences is sequences of independent and identically distributed (IID) RVs with probability of 1s p, 0<p<1, since an IID sequence is an INID sequence with pi=p=1-q or an EXCH sequence with pn(s)=psqn-s.In population genetics and evolution of species, urn models are frequently used as probabilistic models/devices to explain/apply some theories. Among the plethora of such models (see, e.g., Johnson and Kotz [1], Blom et al. [2], and Mahmoud [3]) we consider in the sequel two of them: the Hoppe-Polya urn model (HPUM) and the Polya-Eggenberger urn model (PEUM). The first one, introduced by Holst [4, 5] as a generalization of the Hoppe urn model, is a device to produce certain INID binary sequences whereas the second one supplies a mechanism for producing particular EXCH binary sequences.Special cases ofPEUM are models of a (F/R-TM) fixed/random threshold (see, e.g., Eryilmaz and Yalcin [6], Makri and Psillakis [7], and Eryilmaz et al. [8]), whereas a special case of HPUM is the (RIM) record indicator model (see, e.g., Holst [5, 9, 10], Demir and Eryılmaz [11], and Makri and Psillakis [7]). F/R-TM and RIM find potential applications in the frequency analysis and risk managing of the occurrence of critical events (records, extremes, and exceedances) in several scientific disciplines like physical sciences (e.g., seismology, meteorology, and hydrology) and stochastic financial analysis (e.g., insurance and financial engineering). For details see the cited works.In this paper we wish to use the expected number of an overlapping enumerative statistic (RV) as an index of the average occurrence of some special events over time or space. The statistic counts 0-1 strings of a limited length on sequences derived by the urn models which are discussed in Section2. In Section 3 we first define the statistic on any 0-1 sequence and then we provide its expected value for any INID and EXCH 0-1 sequence. Accordingly, the latter fact covers as particular cases the HPUM and PEUM, respectively. Finally, in Section 4 certain HPUM and PEUM associated with interpretations of special events, specifically the RIM and F/R-TM, are considered. Extensive numerics, concerning the average number of limited length interruptions of records and how on the average subsequent exceedances are separated, demonstrate further 0-1 sequences related to RIM and F/R-TM.Throughout the paperI(A) is the indicator of an event A; that is, I(A)=1 if the event A occurs, and I(A)=0 otherwise and ⌊x⌋ stands for the greatest integer less than or equal to a real number x. Also, we apply the conventions ∑i=ab‍=0, ∏i=ab‍=1, for a>b; that is, an empty sum (product) is to be interpreted as a zero (unity).


## 2. 0-1 Sequences Derived by Certain Urn Models

An urn that initially containsw white and b black balls, w>0, b≥0, is considered. A ball is drawn at random (all balls being equal likely) from the urn and its color is observed. We describe two drawing (or sampling) schemes that yield binary sequences different in structure. To this end we suppose the following.(i)
Every time a white ball or a black ball is drawn from the urn, it is replaced together with a new ball of a color not already in the urn; otherwise the ball is replaced together with a copy of it. This drawing scheme is called Hoppe-Polya urn model and it is denoted asHPUM(w,b). If b=0, that is, there is no black ball, the so-called Hoppe urn model HPUM(w,0) is obtained.(ii)
Forw>0, b>0 we assume that all balls emanating from a draw of a white or a black ball are colored white or, respectively, black. Every time a ball is drawn from the urn, it is replaced together with c (c: an integer) balls of the same color of the ball drawn. This scheme is the well-known Polya-Eggenberger urn model denoted as PEUM(w,b,c). Certain values of the parameter c that define various sampling schemes of special interest are c=-1 (sampling without replacement), c=0 (sampling with replacement), c=1 (Polya sampling), and c=w=b>0.We note in passing that inPEUM(w,b,c) there is a fixed set of admissible colors that appear in the urn, whereas in HPUM(w,b) an infinite set of admissible colors is considered. Interpreting colors as species, the Darwinian theory and the Mendelian theory of evolution of species may be captured, respectively (for details see Mahmoud [3]).A{0,1}-valued sequence of RVs {Xn}n≥1 where 1 denotes the drawing of a white ball and 0 anything else in a HPUM(w,b) or a PEUM(w,b,c), is considered. Then {Xn}n≥1 constitutes an INID sequence with
(1)pn=P(Xn=1)=ww+b+n-1,n=1,2,…
for HPUM(w,b) and an EXCH sequence with
(2)pn(s)=∑j=0n-s(-1)j(n-sj)λs+j,s=0,1,…,n,n=1,2,…,λi=pi(i)=∏j=0i-1(w+jc)∏j=0i-1(w+b+jc),i=0,1,…,n
for PEUM(w,b,c), respectively. For c=0, it holds
(3)λi=λ1i,i=1,2,…,n,λ1=p=ww+b,λ0=1,pn(s)=ps(1-p)n-s,
and hence, an IID sequence with probability of 1s p is derived.Next, we consider certain 0-1 stochastic processes{Xi}i≥1 describing the occurrences of critical events which are associated with particular HPUM and PEUM. The connection between the urn models and the model processes is achieved by interpreting the occurrence of a critical event (Xi=1) as a drawing of a white ball from the related urn model. More explicitly we have the following models.(A)
Let{Yi}i≥1 be a sequence of IID RVs with continuous cumulative distribution function (CDF). Then the (upper) records of the sequence are those elements with values strictly larger than all previous ones. We define the sequence {Xi}i≥1 of record indicators or record indicator model (RIM) X1=1 and Xi=I(Yi>max⁡{Y1,Y2,…,Yi-1}), i=2,3,… . Then {Xi}i=1n constitutes an INID sequence derived by n repetitions of a HPUM(1,0). By symmetry lower records of {Yi}i≥1 are obtained by considering the (upper) records of the sequence {-Yi}i≥1. Namely, they are Yis with Xi=1.(B)
We assume that being associated with a process{Yi}i≥1 with continuous CDF, 1 occurs at a step i if a value of the process exceeds a threshold (i.e., a critical level) u at that step. In this way, a {0,1}-valued sequence Xi=I(Yi>u), i=1,2,…, is generated depending on the type of the threshold (fixed or random) used. Examples of model of exceedances over fixed or random threshold are among others as follows. (a) If u is fixed and Yi’s are IID RVs, then the so-called fixed threshold model (FTM) is derived. (b) Suppose that two independent samples of size m (≥1) and n (≥1), each one of independent elements, of the process {Yi}i≥1, are considered, specifically the samples (Y1,Y2,…,Ym) and (Ym+1,Ym+2,…,Ym+n). The jth order statistic Yj:m of the first sample is chosen as a random threshold; that is, u=Yj:m, j=1,2,…,m. Then the model sequence which is generated by this random threshold model (RTM) is Xi=I(Ym+i>Yj:m), i=1,2,…,n.Both models, FTM and RTM, are derived byn repetitions of a PEUM(w,b,c) with initial composition w and b such that λ1=w/(w+b). Specifically, FTM corresponds to c=0 (drawings with replacements so that the urn composition remains constant) and λ1=p, whereas RTM corresponds to c=1 (drawings such that the number of balls in the urn increases) and w=m+1-j,  b=j, so that λ1=1-j/(m+1). If m→∞, j→∞ so that j/(m+1)→1-p,  0<p<1, with n remaining fixed, then n repetitions of a RTM(m,j) give same results as n repetitions of a FTM(p). This is so because as w→∞, b→∞ so that w/(w+b)→p, then for fixed n>0 the Polya-Eggenberger distribution has as a limit the Binomial distribution with parameters n and p (cf. Johnson and Kotz [1], page 371).


## 3. Counting 0-1 Strings of a Limited Length

In frequency analysis of 0-1 sequences{Xn}n≥1, like the ones derived by the models (A) and (B) or more generally of that associated with HPUM and PEUM, may be useful to define a statistic (RV) denoting the distance (or the time) between two subsequent drawings of white balls. Measuring this distance as the number of consecutive 0s (nonwhite balls) between subsequent 1s (white balls) we equivalently face the problem of counting runs of 0s of a limited length between subsequent 1s. The number, Mn;k,l, of such 0-1 strings of limited (or constrained) length d+2, 0≤k≤d≤l≤n-2, in the first n (≥2)  0-1 trials (i.e., ball drawings) can be written as
(4)Mn;k,l=∑i=k+2n‍Ii,Ii=∑r=1βi-k‍Xi-k-r∏j=i-k-r+1i-1‍(1-Xj)Xi,
where
(5)βi=i-1fori=k+2,k+3,…,l+1;(6)l+1fori=l+2,l+3,…,n.
Readily, for n<k+2, Mn;k,l=0. The support (range set) of Mn;k,l is
(7)R(Mn;k,l)={0,1,…,⌊n-1k+1⌋},0≤k≤l≤n-2.
It should be mentioned that the counting of 0-1 strings via Mn;k,l is considered in the overlapping sense; that is, 1 which is not at either end of the sequence may contribute towards counting two possible strings, the one which ends with the occurrence of it and the next one which starts with it.The study, viaMn;k,l, of constrained (k,l) strings of the form 100⋯0︸k≤d≤l1 where 1 is followed by at least k and at most l 0s before the next 1 in a 0-1 sequence covers as particular cases strings that have been considered recently by several authors. Specifically, Mn;0,l, Mn;k,k, and Mn;k,n-2 enumerate strings of two subsequent 1s separated by a run of 0s of length at most, exactly, and at least equal to a nonnegative integer number, that is, strings of the form 100⋯0︸d≤l1, 100⋯0︸d=k1, and 100⋯0︸d≥k1, respectively. Some relevant contributions on the subject are the works of Sarkar et al. [12], Sen and Goyal [13], Holst [4], Dafnis et al. [14], Huffer and Sethuraman [15], and Makri and Psillakis [16].Applications of constrained(k,l) strings of the general (k≤d≤l) or the restricted forms (d≤l, d=k, d≥k) were found in information theory and data compression (see Zehavi and Wolf [17], Jacquet and Szpankowski [18], and Stefanov and Szpankowski [19]) in urn models, record models, and random permutations (see Chern et al. [20], Joffe et al. [21], Chern and Hwang [22], Holst [5, 9, 10, 23], and Huffer et al. [24]) in system reliability (see Eryilmaz and Zuo [25], Eryilmaz and Yalcin [6], and Makri [26]) and in biomedical engineering (see Dafnis and Philippou [27]).Recently, Makri and Psillakis [28] obtained the probability mass function fn;k,l(x)=P(Mn;k,l=x), x∈R(Mn;k,l) as well as the expected value μn;k,l=E(Mn;k,l) of Mn;k,l defined on any 0-1 INID or EXCH sequence. Accordingly, with βi given by (5) and (6), it holds that
(8)E(Mn;k,l)=∑i=k+2n‍∑r=1βi-k‍ci,r,ci,r=pi-k-r(∏j=i-k-r+1i-1‍qj)pi
for a HPUM(w,b) and
(9)E(Mn;k,l)=∑i=k+2n‍∑j=k+2βi+1‍pj(2),
for a PEUM(w,b,c), respectively.SinceMn;k,l=Mn;0,l-Mn;0,k+Mn;k,k, it holds that
(10)μn;k,l=μn;0,l-μn;0,k+μn;k,k,0≤k≤l≤n-2.
Equation (10) offers an alternative way to compute μn;k,l in cases for which we have available μn;0,l, 0≤l≤n-2, and μn;k,k, 0≤k≤n-2. In this direction the result of Holst [4] for a HPUM(w,0) which is as follows:
(11)μn;k,k=w(n-1)k+1_(k+1)(w+n-1)k+1_,
where xm_=∏r=1m‍(x-r+1) is helpful. Furthermore, he reestablished that Mn;k,k is a Poisson RV with μn;k,k=w/(k+1) when n tends to infinity.As it is observed from (8) and (9), both expressions of μn;k,l are closed formulae proper for applications concerning large 0-1 sequences where μn;k,l may be used to extract information for their stochastic behavior. For instance, μn;k,l is a potentially useful device to a trader (a human or a computer system) making transactions in a certain capital market (e.g., a stock market, a bond market, or an exchange market). It is assumed that the trader relies his/her/its buy-sell strategy on the expected value of Mn;k,l, whereas the interpretation of what Mn;k,l counts depends on the particular sequence on which Mn;k,l is defined.


## 4. Numerical Results

In this section we consider two numerical examples that clarify further the theoretical results of Sections2 and 3. In both examples 0-1 sequences of large or very large size are concerned. Moreover, the selected values of the urn parameters demonstrate the flexibility of the models as well as their applicability for a variety of situations.Example 1.
In a RIM sequence of lengthn, n≫1, Mn;k,l helps in understanding how the rather few records Sn=∑i=1n‍Xi, with E(Sn)≃ln⁡n+γ (see, e.g., Blom et al. [2], page 110) where γ (≃0.577216) is the Euler’s constant, are distributed among the many nonrecord elements of the sequence. Consequently, μn;k,l indicates how many on the average strings of two subsequent records interrupted by at least k and at most l nonrecords occur in such a sequence.In Table1 we compute, via (8), μn;k,l for various values of 0≤k≤l≤n-2. The RIM sequences used have lengths n=102, 103, 104, and 105. They approximately contain on the average 5, 7, 10, and 12 records, respectively. The entries k=l of the table confirm that for n≫1 it holds μn;k,k≃1/(k+1), k≥0. Hence, μn;k,l≃μ~n;k,l=μn;0,l-μn;0,k+(k+1)-1, n≫1, because of (10) and the Poisson approximation of (11). Consequently, a precompiled computation of μn;0,l, 0≤l≤n-2, for large enough n, yields approximately μn;k,l for 0<k<l≤n-2, too. For instance, let n=105, let k=10, and let l=998. Then by the respective entries of the table we find μ~105;10,998=4.545623, whereas a direct computation, via (8) or the usage of the exact value μ105;10,10=0.090899 in (10), gives μ105;10,998=4.545613. That is, the relative error between μ105;10,998 and μ~105;10,998 is 0.0002%. The value μ105;10,998≃5 means that in a 0-1 sequence of 105 elements containing on the average 12 records occur on the average 5 strings of 2 subsequent records separated by at least 10 and at most 998 nonrecord elements.Table 1
Expected valuesμn;k,l of Mn;k,l defined on a RIM.
n
k
l
=
0
l
=
1
l
=
10
l
=
98
l
=
998
l
=
9998
1
0
2
0
0.990000
1.480000
2.909877
4.187378
1
0
3
0.999000
1.498000
3.008877
5.078378
6.485471
1
0
4
0.999900
1.499800
3.018777
5.167478
7.384571
8.787606
1
0
5
0.999990
1.499980
3.019767
5.176388
7.474481
9.687516
1
0
2
1
0.490000
1.919877
3.197378
1
0
3
0.499000
2.009877
4.079378
5.486471
1
0
4
0.499900
2.018877
4.167578
6.384671
7.787706
1
0
5
0.499990
1
0
2
10
0.080909
1.358409
1
0
3
0.089909
2.159409
3.566503
1
0
4
0.090809
2.239509
4.456603
5.859638
1
0
5
0.090899
1
0
2
98
0.000101
1
0
3
0.009101
1.416194
1
0
4
0.010001
2.227094
3.630130
1
0
5
0.010091
1
0
3
998
0.000001
1
0
4
0.000901
1.403936
1
0
5
0.000991
1
0
4
9998
0.1
×
1
0
-
7
1
0
5
0.000090Example 2.
We consider aF/R-TM sequence of length n, n≫1, with an exceedance probability λ1, 0<λ1<1. In a RTM there are infinitely many different selections of the parameters m and j which give the same value of λ1. Let N, ΛN be positive integers such that 1-λ1=ΛN/10N and Δ=gcd(10N,ΛN) be their greatest common devisor. Then for every pair (m,j) such that m=(10N/Δ)(1-r)-1,  j=(ΛN/Δ)(1-r), for r=0,-1,-2,…,λ1 is constant. Therefore, for a given λ1 what values (small, moderate, or large) of the size m and the threshold j should be used depends on the demanded consideration (short, middle, or long) of the past sequence’s data. Readily, in a FTM sequence there is not such a need since p=λ1. In both sequences (FTM or RTM) the expected value of Mn;k,l might be helpful in predicting how many on the average strings of two subsequent exceedances (e.g., of a stock prices) over a threshold (fixed or random) are separated by at least k and at most l nonthreshold exceedances.In Table2 we compute, via (9), the expected value μn;k,l(α) of Mn;k,l defined on a FTM(α=F) and on a RTM(α=R) with the same exceedance probability λ1=0.50, 0.85 for various values of 0≤k≤l≤n-2. The F/R-TM sequences which have been used have lengths n=102, 103, and 104 and sets of pairs (m,j) that give a selected value of λ1 are depicted for r=0, -10, -50, and -500, as well. The entries of the table confirm that, for large m, j the dependence in structure of a RTM relaxes loosing its sensitivity with respect to the initial sample sequence’s size and threshold. Eventually, it degenerates becoming a FTM and therefore E(Mn;k,l(R)) tends to E(Mn;k,l(F)). This situation is more apparent if n is smaller than or equal to m and j. If n is larger than m and j, the expected value E(Mn;k,l(R)) departs, even a little, from that of E(Mn;k,l(F)) with the same λ1 showing that in this case the dependency of RTM on its m and j counts. For instance, this is the case for λ1=0.50, n=104, and (m,j)=(1,1), (21,11), and (101,51).Table 2
Expected valuesμn;k,l(α) of Mn;k,l defined on a FTM (α=F) and on a RTM (α=R).
n
k
l
μ
n
;
k
,
l
(
F
)
μ
n
;
k
,
l
(
R
)
λ
1
=
0.50
r
0
−10
−50
−500
m
1
21
101
1001
j
1
11
51
501
1
0
2
0
0
24.750000
33.000000
25.826087
24.990291
24.774676
10
48.978760
48.512821
48.921634
48.968795
48.977823
98
49.000000
49.009901
49.000000
49.000000
49.000000
10
10
0.021729
0.103730
0.046343
0.027280
0.022293
98
0.042969
0.600810
0.124709
0.058486
0.044400
1
0
3
0
0
249.750000
333.000000
260.608696
252.174757
249.999003
10
498.759033
492.743590
498.101519
498.645178
498.748350
10
10
0.241455
1.152681
0.514980
0.303150
0.247725
1
0
4
0
0
2499.750000
3333.000000
2608.434783
2524.019417
2502.242273
10
4996.571768
4935.051282
4989.900378
4995.409015
4996.453615
10
10
2.438721
11.642191
5.201346
3.061847
2.502044
λ
1
=
0.85
r
0
−10
−50
−500
m
19
219
1019
10019
j
3
33
153
1503
1
0
2
0
0
71.527500
72.128571
71.584615
71.539863
71.528760
10
84.000000
83.999932
84.000000
84.000000
84.000000
98
84.000000
80.000000
84.000000
84.000000
84.000000
1
0
3
0
0
721.777500
727.842857
722.353846
721.902253
721.790211
10
848.999999
848.999227
848.999998
848.999999
848.999999
10
10
0.000004
0.001072
0.000011
0.000005
0.000004
1
0
4
0
0
7224.277500
7284.985714
7230.046154
7225.526151
7224.404720
10
8498.999993
8498.992180
8498.999975
8498.999990
8498.999992
10
10
0.000042
0.010830
0.000109
0.000052
0.000043



---

*Source: 646140-2014-10-27.xml*