# Applications of Fuss-Catalan Numbers to Success Runs of Bernoulli Trials

Authors: S. J. Dilworth; S. R. Mane
Journal: Journal of Probability and Statistics
 (2016)

---

## Abstract

In a recent paper, the authors derived the exact solution for the probability mass function of the geometric distribution of orderk, expressing the roots of the associated auxiliary equation in terms of generating functions for Fuss-Catalan numbers. This paper applies the above formalism for the Fuss-Catalan numbers to treat additional problems pertaining to occurrences of success runs. New exact analytical expressions for the probability mass function and probability generating function and so forth are derived. First, we treat sequences of Bernoulli trials with r
≥
1 occurrences of success runs of length k with l-overlapping. The case l
<
0, where there must be a gap of at least l trials between success runs, is also studied. Next we treat the distribution of the waiting time for the r
t
h nonoverlapping appearance of a pair of successes separated by at most k
-
2 failures (k
≥
2).


---

## Body

## 1. Introduction

In a recent paper [1], the authors derived the exact analytical solution for the probability mass function of the geometric distribution of order k. The roots of the auxiliary equation of the associated recurrence relation were derived in terms of generating functions for Fuss-Catalan numbers. (See the text by Graham et al. [2] for details about Fuss-Catalan numbers.) In this paper, we employ our formalism for the Fuss-Catalan numbers to treat additional problems pertaining to occurrences of success runs in sequences of Bernoulli trials. Throughout our paper, we treat only sequences of independent identically distributed (i.i.d.) Bernoulli trials with constant success probability p (and failure probability q
=
1
-
p). The theory of success runs is discussed extensively in the texts by Balakrishnan and Koutras [3] and Johnson et al. [4]. Our formalism provides a new perspective to treat problems of success runs in sequences of Bernoulli trials and complements and extends results derived by previous authors (especially Feller [5, pp. 322–326]). Citations and comparisons to the works of others will be presented in Sections 3 and 4, after we have derived our results.We treat two main problems in this paper. First, we consider sequences with multipler
≥
1 occurrences of success runs of length k. The success runs are permitted to overlap, with a maximum of l
≥
0 overlaps between success runs. This is known as “l-overlapping.” The case l
<
0 is perhaps surprising at first sight but is also of interest. In this case there must be a gap or “buffer” of at least |
l
| trials (of arbitrary outcomes) between success runs. We call this “|
l
|-buffering.” We also consider the scenario in which the length of the sequence n is held fixed and the number of success runs r
≥
0 is allowed to vary. This is the binomial distribution of order k with l-overlapping success runs. An encyclopedia article on binomial distributions of order k has been published by Philippou and Antzoulakos [6]. Using Fuss-Catalan numbers, we present new concise expressions for the probability mass functions of these distributions.In Section4 we study a different problem. We analyze the distribution of the waiting time for the r
t
h nonoverlapping appearance of a pair of successes separated by at most k
-
2 failures (k
≥
2). Our main reference for this problem is the elegant analysis by Koutras [7], who also gives an excellent bibliography on the subject. For r
=
1 and k
≥
2, the problem is a special case of the detection waiting game when a 2-out-of-k moving (or sliding) window detector is employed. See Koutras [7] for additional details and references. Note that our material in Section 4 is self-contained and is a different problem from that mentioned above.


## 2. Notation and Definitions

We summarize the basic notation and definitions presented in our earlier paper [1]. For a sequence of independent identically distributed Bernoulli trials with success probability p (and failure probability q
=
1
-
p), let X
k be the waiting time for the first run of k consecutive successes. Then X
k is said to have the geometric distribution of order k. This distribution was studied by Feller in his classic text [5, pp. 322–326]. It is also known as the negative binomial distribution of order k with parameter (
1
,
p
); see Philippou [8]. The probability mass function f
k of X
k satisfies the recurrence relation, for n
>
k,(1)
f
k
n
=
q
f
k
n
-
1
+
p
q
f
k
n
-
2
+
p
2
q
f
k
n
-
3
+
⋯
+
p
k
-
1
q
f
k
n
-
k
.The initial conditions are f
k
(
n
)
=
0 for n
=
1
,
…
,
k
-
1 and f
k
(
k
)
=
p
k. We define the auxiliary polynomial(2)
A
p
,
k
z
=
z
k
-
q
z
k
-
1
-
q
p
z
k
-
2
-
q
p
2
z
k
-
3
-
⋯
-
q
p
k
-
1
.The auxiliary equation is A
p
,
k
(
z
)
=
0. We will drop the subscripts p and k unless necessary. Feller [5] proved that the roots of the auxiliary equation are distinct and also that there is a unique positive real root, and it lies in (
0,1
), and the real positive root has a strictly larger magnitude than all the other roots. Additional properties of the roots were derived in [1]. We denote the roots by λ
j
(
p
,
k
), j
=
0,1
,
…
,
k
-
1, where λ
0 is the positive real root. We call λ
0 the “principal root” and the other roots “secondary roots.” Unless required, we will omit the arguments p and k. It is useful to multiply A
(
z
) by (
z
-
p
) to obtain the polynomial(3)
B
z
=
z
-
p
A
z
=
z
k
z
-
1
+
p
k
1
-
p
.Remark 1 (Fuss-Catalan numbers and roots of auxiliary polynomial).
Relevant definitions, formulas, and identities for the Fuss-Catalan numbers can be found in the text by Graham et al. [2]. The Fuss-Catalan numbers are given by(4)
A
m
ν
,
r
=
r
m
!
∏
j
=
1
m
-
1
m
ν
+
r
-
j
=
r
Γ
m
+
1
Γ
m
ν
+
r
Γ
m
ν
-
1
+
r
+
1
.The first form (finite product) is valid in general, while the second form (Gamma functions) is well defined provided m
ν
+
r
≠
0. The generating function of the Fuss-Catalan numbers is B
ν
(
z
) and [2, p. 363] (5a)
B
ν
z
=
∑
m
=
0
∞
A
m
ν
,
1
z
m
,
(5b)
B
ν
z
r
=
∑
m
=
0
∞
A
m
ν
,
r
z
m
.We will also require the following formula:(6)
B
ν
z
-
1
=
z
B
ν
z
ν
.It was proved in [1] that, for all 0
<
p
<
1,(7)
λ
j
=
1
-
1
B
1
+
1
/
k
e
2
π
i
j
/
k
p
q
1
/
k
1
≤
j
<
k
.For k
/
(
k
+
1
)
<
p
<
1, the above expression also applies for λ
0, while, for 0
<
p
<
k
/
(
k
+
1
),(8)
λ
0
=
1
B
k
+
1
p
k
q
.For ease of reference, we list several relevant properties of the roots in the following. The proofs of all the results were given in [1], or references cited therein, and are omitted in the following.Remark 2.
All the roots of the auxiliary equation are distinct.Remark 3.
Forp
∈
(
0,1
), the auxiliary equation has a unique positive real root, which lies in (
0,1
). We denote the positive real root by λ
0, or λ
0
(
p
,
k
), as stated above. For any p
∈
(
0,1
), exactly one of the three following statements is true: (i)
0
<
p
<
k
/
(
k
+
1
)
<
λ
0
<
1,
(ii)
0
<
λ
0
<
k
/
(
k
+
1
)
<
p
<
1,
(iii)
λ
0
=
p
=
k
/
(
k
+
1
).Remark 4.
Forp
∈
(
0,1
), the principal root λ
0 has a strictly greater magnitude than all the other roots of the auxiliary equation; that is, 0
<
z
r
<
λ
0
<
1, where z
r
∈
C
∖
λ
0 is a root of A
(
z
). We employ the term “secondary roots” for the set {
λ
j
,
j
=
1
,
…
,
k
-
1
}.Remark 5.
For anyp
∈
(
0,1
), the secondary roots λ
j, j
=
1
,
…
,
k
-
1 satisfy the inequality(9)
0
<
λ
j
<
min
⁡
p
,
λ
0
≤
k
k
+
1
≤
max
⁡
p
,
λ
0
<
1
.The inequalities involving k
/
(
k
+
1
) are strict if p
≠
k
/
(
k
+
1
).Remark 6.
Forp
∈
(
0,1
), let R
(
p
) denote the set of k
+
1 roots of the equation z
k
(
1
-
z
)
=
p
k
(
1
-
p
). Let p
1
,
p
2
∈
(
0,1
). Then R
(
p
1
)
=
R
(
p
2
) if p
2
=
p
1 or p
2
=
λ
0
(
p
1
); otherwise R
(
p
1
)
∩
R
(
p
2
)
=
⌀.In addition to the above properties of the roots, we will also need the following two results, which were not proved in [1], as well as a lemma about sums of series.Proposition 7 (distinctness of roots for differentk).
Consider fixedp
∈
(
0,1
). Suppose z
r is a root of the auxiliary equation A
(
z
)
=
0 for k
=
k
1. Then z
r is not a root for any other value of k.Proof.
We are given that(10)
z
r
k
1
1
-
z
r
=
p
k
1
q
.Suppose that z
r is also a root for k
=
k
2
≠
k
1. Then by hypothesis(11)
z
r
k
2
1
-
z
r
=
p
k
2
q
.From (9), z
r
≠
0 and z
r
≠
1 for 0
<
p
<
1; hence we can divide the two equations to deduce(12)
z
r
k
2
-
k
1
=
p
k
2
-
k
1
.Hence |
z
r
|
=
|
p
|. Also from (9), |
z
r
|
<
p for all the secondary roots. Thus the only possibility is that z
r is the positive real root. Hence z
r
=
p, but this is a root if and only if p
=
k
/
(
k
+
1
) (see Remark 3). However, for arbitrary p
∈
(
0,1
), the constraint p
=
k
/
(
k
+
1
) has either no solution for k or at most one solution for k.Proposition 8 (comparison of principal roots for differentk, for fixed p).
For fixedp
∈
(
0,1
), if k
1
<
k
2 the principal roots λ
0
(
p
,
k
1
) and λ
0
(
p
,
k
2
), for k
=
k
1
,
k
2 respectively, satisfy the inequality(13)
λ
0
p
,
k
1
<
λ
0
p
,
k
2
.Proof.
To exhibit the dependence onk, we denote the auxiliary polynomial by A
p
,
k
(
z
). Then from (2)(14)
A
p
,
k
+
1
z
=
z
A
p
,
k
z
-
q
p
k
.Then set z
=
λ
0
(
p
,
k
) to obtain(15)
A
p
,
k
+
1
λ
0
p
,
k
=
λ
0
p
,
k
A
p
,
k
λ
0
p
,
k
-
q
p
k
=
-
q
p
k
<
0
.Now A
p
,
k
+
1
(
z
) has exactly one real root in z
∈
(
0,1
), which is λ
0
(
p
,
k
+
1
). Also A
p
,
k
+
1
(
0
)
<
0 and A
p
,
k
+
1
(
1
)
>
0. It follows that(16)
λ
0
p
,
k
<
λ
0
p
,
k
+
1
.By extension, this establishes (13) for all k
1
<
k
2.Lemma 9.
Forn
≥
m
≥
1 and ξ
≠
1,(17)
ξ
m
-
1
∑
i
=
m
n
i
-
1
m
-
1
ξ
i
-
m
=
1
m
-
1
!
d
m
-
1
d
x
m
-
1
1
-
ξ
x
n
1
-
ξ
x
x
=
1
.Next, for j
≥
n
≥
0 and ξ
≠
1,(18)
d
n
d
x
n
x
j
1
-
ξ
x
x
=
1
=
n
!
∑
i
=
0
n
j
i
ξ
n
-
i
1
-
ξ
n
-
i
+
1
.The expressions on the right hand sides of both equations are clearly well defined for all ξ
≠
1.Proof.
To derive (17) we define the sum(19)
Z
x
=
1
+
ξ
x
+
ξ
x
2
+
⋯
+
ξ
x
n
-
1
m
-
1
!
=
1
-
ξ
x
n
m
-
1
!
1
-
ξ
x
.Then differentiate the sum in (19) m
-
1 times to obtain(20)
d
m
-
1
Z
x
d
x
m
-
1
=
ξ
m
-
1
m
-
1
m
-
1
+
m
m
-
1
ξ
x
+
m
+
1
m
-
1
ξ
x
2
+
⋯
+
n
-
1
m
-
1
ξ
x
n
-
m
.Evaluation at x
=
1 yields (17). The derivation of (18) is an application of Leibniz’s rule:(21)
d
n
d
x
n
x
j
1
-
ξ
x
=
∑
i
=
0
n
n
i
d
i
x
j
d
x
i
d
n
-
i
d
x
n
-
i
1
1
-
ξ
x
=
∑
i
=
0
n
n
!
i
!
n
-
i
!
j
!
j
-
i
!
x
j
-
i
n
-
i
!
ξ
n
-
i
1
-
ξ
x
n
-
i
+
1
=
n
!
∑
i
=
0
n
j
!
i
!
j
-
i
!
ξ
n
-
i
x
j
-
i
1
-
ξ
x
n
-
i
+
1
.Evaluation at x
=
1 yields (18).


## 3. Multipler
≥
1 Success Runs in Sequences of Bernoulli Trials

### 3.1. Probability Generating Function, Mean, and Variance

We now turn to the first problem of interest in this paper, namely, the waiting time to obtainr
>
1 success runs of length k. We begin by displaying the following expressions for the case r
=
1. They were derived by Feller [5] and will be required in the following.Remark 10 (probability generating function forr
=
1).
Lets
∈
C. The probability generating function (p.g.f.) for the geometric distribution of order k is [5, eq. (
7.6
)](22)
ϕ
s
,
k
=
p
k
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
=
p
k
s
k
1
-
q
s
1
+
p
s
+
⋯
+
p
k
-
1
s
k
-
1
.The p.g.f. exists for |
s
|
<
1
/
λ
0
(
p
,
k
) [5]. The mean and variance are given by [5, eq. (
7.7
)](23)
μ
k
=
1
-
p
k
q
p
k
,
σ
2
k
=
1
q
p
k
2
-
2
k
+
1
q
p
k
-
p
q
2
.The dependences on p and k will be omitted in the following unless necessary.We now calculate the probability generating function, mean, and variance for multipler
>
1 overlapping runs. The success runs have length k and there can be at most 0
≤
l
<
k overlaps between consecutive success runs. We denote the waiting time by X
r
,
k
,
l. The case l
=
0 of nonoverlapping runs was extensively analyzed by Philippou [8], who named the distribution as the negative binomial distribution of order k with vector parameter (
r
,
p
). Ling (1989) [9] and Hirano et al. [10] derived results for the special case l
=
k
-
1. The text by Balakrishnan and Koutras [3] lists the special cases l
=
0 and l
=
k
-
1 as, respectively, Type I and Type III negative binomial distributions of order k.Proposition 11 (probability generating function forr
≥
1).
Let the probability generating function forr
≥
1 success runs of length k with at most l overlaps be ϕ
r
,
k
,
l
(
s
). We will omit the subscripts k and l unless necessary. Then(24)
ϕ
r
,
k
,
l
s
=
ϕ
s
,
k
r
ϕ
s
,
l
r
-
1
.Notice that, for r
=
1, we obtain ϕ
1
,
k
,
l
(
s
)
=
ϕ
(
s
,
k
) (see (22)), as required.Proof.
DefineX
j
(
=
X
j
,
k
,
l
) as the waiting time to complete j success runs. So suppose we have completed j
-
1 success runs. Hence by definition the last k trials are all successes. Then exactly one of the following k
-
l
+
1 mutually exclusive events will occur:(i)
The nextk
-
l trials are all successes. This yields the j
t
h success run.
(ii)
The nextκ trials are successes, followed by a failure, where κ
=
0,1
,
…
,
k
-
l
-
1. Then we restart the waiting time for the next success run from scratch (conditioned on an initial failure). We denote this additional waiting time by Y
j. Clearly, Y
j has the same distribution as X
1.Since the events are mutually exclusive, we add the probabilities to obtain(25)
E
exp
⁡
t
X
j
=
p
k
-
l
E
exp
⁡
t
X
j
-
1
+
k
-
l
+
∑
κ
=
0
k
-
l
-
1
p
κ
q
E
exp
⁡
t
X
j
-
1
+
Y
j
+
κ
+
1
=
p
k
-
l
e
t
k
-
l
E
exp
⁡
t
X
j
-
1
+
∑
κ
=
0
k
-
l
-
1
p
κ
q
e
t
κ
+
1
E
exp
⁡
t
X
j
-
1
E
exp
⁡
t
Y
j
=
E
exp
⁡
t
X
j
-
1
p
k
-
l
e
t
k
-
l
+
ϕ
e
t
∑
κ
=
0
k
-
l
-
1
p
κ
q
e
t
κ
+
1
.Now set s
=
e
t and note that ϕ
j
(
s
)
=
E
(
exp
⁡
(
t
X
j
)
). Hence we obtain the following recurrence relation and solution for ϕ
r
(
s
): (26a)
ϕ
r
s
=
ϕ
r
-
1
s
p
s
k
-
l
+
ϕ
s
∑
κ
=
0
k
-
l
-
1
p
κ
q
s
κ
+
1
,
(26b)
=
ϕ
s
p
s
k
-
l
+
ϕ
s
q
s
1
-
p
s
k
-
l
1
-
p
s
r
-
1
.Define Z as the term in the brackets. After some tedious algebra we obtain(27)
Z
=
p
s
k
-
l
+
p
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
q
s
1
-
p
s
k
-
l
1
-
p
s
=
p
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
1
-
s
+
q
p
l
s
l
+
1
p
s
l
1
-
p
s
=
ϕ
s
,
k
ϕ
s
,
l
.In the last line it is necessary to exhibit the dependences on k and l explicitly. Then (24) follows immediately.Proposition 12 (domain of convergence).
The probability generating function forr
≥
1 success runs ϕ
r
,
k
,
l
(
s
) converges for(28)
s
<
1
λ
0
p
,
k
.Hence the domain of convergence of the probability generating function is the same for all r
≥
1.Proof.
Clearly, the functionϕ
r
,
k
,
l
(
s
) is well defined if and only if the sums of the series for ϕ
(
s
,
k
) and ϕ
(
s
,
l
) both converge. It was proved by Feller [5] that ϕ
(
s
,
k
) exists for s
<
1
/
λ
0
(
p
,
k
). Hence ϕ
r
,
k
,
l
(
s
) exists if(29)
s
<
min
⁡
1
λ
0
p
,
k
,
1
λ
0
p
,
l
.However, because l
<
k, it follows from Proposition 8 that λ
0
(
p
,
l
)
<
λ
0
(
p
,
k
). Hence 1
/
λ
0
(
p
,
k
)
<
1
/
λ
0
(
p
,
l
). This proves (28).Proposition 13 (mean and variance).
The meanμ
r
,
k
,
l and variance σ
r
,
k
,
l
2 for the waiting time for r
≥
1 success runs are given by (30a)
μ
r
,
k
,
l
=
r
μ
k
-
r
-
1
μ
l
,
(30b)
σ
r
,
k
,
l
2
=
r
σ
2
k
-
r
-
1
σ
2
l
.Proof.
We puts
=
e
t and differentiate with respect to t and evaluate at t
=
0. We differentiate ln
⁡
ϕ
r
(
e
t
) to obtain(31)
ϕ
r
′
e
t
ϕ
r
e
t
=
r
ϕ
′
e
t
,
k
ϕ
e
t
,
k
-
r
-
1
ϕ
′
e
t
,
l
ϕ
e
t
,
l
.Evaluating at t
=
0 and noting that ϕ
(
1
,
k
)
=
ϕ
(
1
,
l
)
=
1 yield(32)
μ
r
,
k
,
l
=
r
μ
k
-
r
-
1
μ
l
.This proves (30a). We differentiate again to obtain(33)
ϕ
r
′
′
e
t
ϕ
r
e
t
-
ϕ
r
′
2
e
t
ϕ
r
e
t
2
=
r
ϕ
′
′
e
t
,
k
ϕ
e
t
,
k
-
ϕ
′
2
e
t
,
k
ϕ
e
t
,
k
2
-
r
-
1
ϕ
′
′
e
t
,
l
ϕ
e
t
,
l
-
ϕ
′
2
e
t
,
l
ϕ
e
t
,
l
2
. We again evaluate at t
=
0 to obtain(34)
σ
r
,
k
,
l
2
=
r
σ
2
k
-
r
-
1
σ
2
l
.This proves (30b).We now show that various results derived by other authors are special cases of our results above. As stated above, the casel
=
0 of nonoverlapping runs was solved by Philippou [8], while Ling (1989) [9] and Hirano et al. [10] treated the case l
=
k
-
1 of overlapping runs.Remark 14 (Philippou (1984)).
Philippou [8, Lemma 2.2] stated “Let X be a r
v distributed as N
B
k
(
x
;
r
,
p
). Then its probability generating function, to be denoted by γ
k
,
r
(
s
), is given by”(35)
γ
k
,
r
s
=
p
k
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
r
,
s
≤
1
.The mean and variance are given by [8, Proposition 2.1] (36a)
E
X
=
r
1
-
p
k
q
p
k
,
(36b)
σ
2
X
=
r
1
-
2
k
+
1
q
p
k
-
p
2
k
+
1
q
2
p
2
k
.Proof.
By definition, Philippou’s notationγ
k
,
r
(
s
) is the same as our ϕ
r
,
k
,
l
(
s
) with l
=
0. From (22), it is easy to show that ϕ
(
s
,
l
)
=
1 for l
=
0, whence ϕ
r
,
k
,
0
(
s
)
=
ϕ
(
s
,
k
)
r and (35) follows. Note that Philippou [8] stated the domain of convergence to be |
s
|
≤
1, but we have shown that it is |
s
|
≤
1
/
λ
0
(
p
,
k
), which is a larger domain. Next, it is also easy to show that μ
(
l
)
=
σ
2
(
l
)
=
0 for l
=
0, whence μ
r
,
k
,
0
=
r
μ
(
k
) and σ
r
,
k
,
0
2
=
r
σ
2
(
k
) which yield (36a) and (36b), respectively.Remark 15 (Ling (1989)).
Ling (1989) [9, Theorem 4.1] stated that, for |
s
|
≤
1, (37a)
ϕ
r
k
s
=
s
ϕ
r
-
1
k
s
p
+
q
ϕ
1
k
s
,
(37b)
ϕ
r
k
s
=
ϕ
1
k
s
s
p
+
q
ϕ
1
k
s
r
-
1
.Proof.
Ling wroteϕ
r
(
k
)
(
s
) and ϕ
1
(
k
)
(
s
) where we have written ϕ
r
,
k
,
l
(
s
) and ϕ
(
s
), but the connection between the notations is clear. Setting l
=
k
-
1 in (26a) yields(38)
ϕ
r
s
=
ϕ
r
-
1
s
p
s
+
q
s
ϕ
s
=
s
ϕ
r
-
1
s
p
+
q
ϕ
s
.This yields (37a). Next (37b) follows immediately by solving the recurrence relation(39)
ϕ
r
s
=
ϕ
s
s
p
+
q
ϕ
s
r
-
1
.Similar to Philippou [8], Ling (1989) [9] also stated the domain of convergence to be |
s
|
≤
1, but we have shown that it is larger, given by |
s
|
≤
1
/
λ
0
(
p
,
k
).Remark 16 (Hirano et al. (1991)).
Hirano et al. [10, Theorem 4.1] stated that “Let ϕ
r
N
B
(
t
) be the p.g.f. of N
B
k
I
I
I
(
r
,
p
).” They wrote(40)
ϕ
r
N
B
t
=
p
t
+
q
t
ϕ
1
N
B
t
r
-
1
ϕ
1
N
B
t
.They also wrote(41)
ϕ
1
N
B
t
=
p
t
k
1
-
q
∑
i
=
0
k
-
1
p
i
t
i
+
1
.Then they derived the solution(42)
ϕ
r
N
B
t
=
p
t
-
1
p
t
k
+
r
-
1
-
q
p
k
-
1
t
k
+
t
-
1
r
-
1
-
q
p
k
t
k
+
1
+
t
-
1
r
.They also gave expressions for the mean and variance. The mean is(43)
E
N
r
k
=
q
r
+
p
-
p
k
p
k
q
.Proof.
The connection between the notations is that they writeϕ
r
N
B
(
t
) and ϕ
1
N
B
(
t
) where we write ϕ
r
(
s
) and ϕ
(
s
), respectively. They employ t as the independent variable, where we use s. It is simple to derive that their expression for ϕ
1
N
B
(
t
) in (42) equals that for ϕ
(
s
,
k
) in (22). Next, (40) is simply (39) with the changes of notation listed above. Next, setting l
=
k
-
1 and changing the independent variable from s to t,(44)
ϕ
r
,
k
,
k
-
1
t
=
ϕ
t
,
k
r
ϕ
t
,
k
-
1
r
-
1
=
p
t
k
r
1
-
p
t
r
1
-
t
+
q
p
k
t
k
+
1
r
1
-
t
+
q
p
k
-
1
t
k
r
-
1
p
t
k
-
1
r
-
1
1
-
p
t
r
-
1
=
p
t
-
1
p
t
k
+
r
-
1
-
q
p
k
-
1
t
k
+
t
-
1
r
-
1
-
q
p
k
t
k
+
1
+
t
-
1
r
.This is exactly (42). From (30a), the mean for l
=
k
-
1 is(45)
μ
r
,
k
,
k
-
1
=
r
μ
k
-
r
-
1
μ
k
-
1
=
r
1
-
p
k
p
k
q
-
r
-
1
1
-
p
k
-
1
p
k
-
1
q
=
q
r
+
p
-
p
k
p
k
q
.This is exactly (43). Hirano et al. [10] also displayed an expression for the variance. The proof of equivalence with our expression involves merely tedious algebra and is omitted.


### 3.2. Probability Mass Function

We derive an expression forf
r
,
k
,
l
(
n
), the probability mass function (p.m.f.) that the r
t
h success run of length k with l-overlapping occurs at the n
t
h Bernoulli trial, where r
≥
1 and n
≥
1. Clearly f
r
,
k
,
l
(
n
)
=
0 for n
<
l
+
r
(
k
-
l
)
=
r
k
-
(
r
-
1
)
l and f
r
,
k
,
l
(
n
)
=
p
r
k
-
(
r
-
1
)
l for n
=
r
k
-
(
r
-
1
)
l. An expression for the p.m.f. for the case r
=
1 was derived in [1]. By definition, the probability generating function is related to the probability mass function via(46)
ϕ
r
,
k
,
l
s
=
∑
n
=
0
∞
s
n
f
r
,
k
,
l
n
.We derived an expression for ϕ
r
,
k
,
l
(
s
) above and we will use it to derive an expression for f
r
,
k
,
l
(
n
) in the following. From the second form for ϕ
(
s
,
k
) in (22), with z
=
1
/
s,(47)
ψ
z
=
ϕ
1
z
=
p
k
A
p
,
k
z
.Hence for r
≥
1 success runs,(48)
ψ
r
,
k
,
l
z
≡
ϕ
r
,
k
,
l
1
z
=
ψ
z
,
k
r
ψ
z
,
l
r
-
1
=
p
r
k
-
r
-
1
l
A
p
,
l
z
r
-
1
A
p
,
k
z
r
.The right hand side is a rational function of two polynomials. From Proposition 7, the auxiliary polynomials A
p
,
l
(
z
) and A
p
,
k
(
z
) have no roots in common. Furthermore, because l
<
k, the numerator polynomial is of a lower degree than the denominator polynomial. We also know that all the roots of the auxiliary polynomials are distinct. Hence we can expand ψ
r
,
k
,
l
(
z
) as a sum of partial fractions with repeated roots (of the denominator polynomial)(49)
ψ
r
,
k
,
l
z
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
j
m
z
-
λ
j
p
,
k
m
.Here the coefficients a
j
m are parameters which depend on r, k, and l but not on z. For brevity, we drop the subscripts k and l on ψ
r
,
k
,
l and also write the roots as λ
j in the following. The coefficients a
j
m can be evaluated explicitly in terms of the roots {
λ
i
(
p
,
k
)
,
i
=
0
,
…
,
k
-
1
} via the standard residues formula(50)
a
j
m
=
1
r
-
m
!
d
r
-
m
d
z
r
-
m
z
-
λ
j
r
ψ
r
z
z
=
λ
j
.Returning to the use of s
=
1
/
z, we see that(51)
ϕ
r
s
=
ψ
r
1
s
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
j
m
s
m
1
-
λ
j
s
m
.We expand the right hand side using the negative binomial theorem and equate f
r
,
k
,
l
(
n
) to the coefficient of s
n.Proposition 17.
The probability mass functionf
r
,
k
,
l
(
n
) for the r
t
h success run of length k with l-overlapping is given by(52)
f
r
,
k
,
l
n
=
∑
j
=
0
k
-
1
∑
m
=
1
r
n
-
1
m
-
1
a
j
m
λ
j
p
,
k
n
-
m
.Hence f
r
,
k
,
l
(
n
) is given by a sum of exactly r
k terms, independently of n. Recall from above that f
r
(
n
)
=
0 for n
<
r
k
-
(
r
-
1
)
l so the above formula is only required for n
≥
r
k
-
(
r
-
1
)
l; hence the binomial coefficients are well defined.The derivation of the above expression has already been given above, where all notation has been defined and explained.


### 3.3. Binomial Distribution of Orderk with l-Overlapping

Consider a sequence of Bernoulli trials of fixed lengthn
>
0 and let N
n
,
k
,
l denote the number of success runs of length k with a maximum of l overlaps between success runs. This is the binomial distribution of order k with l-overlapping success runs and has been reviewed in the encyclopedia article by Philippou and Antzoulakos [6]. Good overviews have also been given by Makri and Philippou [11] and Makri et al. [12]; see the bibliographies in both references. Ling (1988) [13] introduced the case of l
=
k
-
1 and called it the “Type II binomial distribution of order k.”The caser
=
0 is the probability that the longest success run in the first n trials has length less than k. It is also known as the probability that the waiting time to attain the first success run of length k exceeds n trials. This scenario has been solved by many authors. For example, Feller [5] presented an asymptotic solution in terms of the principal root. In our paper [1], we extended Feller’s solution to include all the roots. Solutions have also been derived by Burr and Cane [14], Godbole [15], Philippou and Makri [16], and Muselli [17], all of whom expressed their results using (possibly nested) binomial or multinomial sums.Letg
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
), where r
=
0,1
,
…, be the probability mass function for N
n
,
k
,
l. We derive an expression for g
n
,
k
,
l
(
r
) in the following. Note that, to obtain a nontrivial distribution, we must have n
≥
l
+
r
(
k
-
l
) so for fixed n we must have 0
≤
r
≤
r
∗
≡
(
n
-
l
)
/
(
k
-
l
).Proposition 18.
The probability mass functiong
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
) for the binomial distribution of order k with l-overlapping is given by(53)
g
n
,
k
,
l
r
=
f
r
+
1
,
k
,
l
n
+
k
+
1
p
k
q
-
f
r
,
k
,
l
n
+
l
+
1
p
l
q
.Here r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
). Note that the last term vanishes for r
=
0; hence the above expression agrees with our result in [1].Proof.
We solve the problem as follows. Suppose ther
t
h success run is completed on the n
t
h trial. Then by definition the outcomes of the last k trials are all successes. There are now two mutually exclusive and exhaustive possibilities, according as the (
r
-
1
)
t
h success run is contiguous with (and possibly overlaps) the r
t
h success run, or there is at least one failure between the runs. (i)
In the former case, the(
r
-
1
)
t
h success run terminates at the trial n
-
k
+
l. (This event is null if r
=
1.) The outcome of the n
-
k
t
h trial is a success.
(ii)
In the latter case, the outcome of the(
n
-
k
)
t
h trial is a failure. The first n
-
k
-
1 trials contain exactly r
-
1 success runs.Since the events are mutually exclusive and exhaustive, we add the probabilities to obtain(54)
f
r
,
k
,
l
n
=
p
k
-
l
f
r
-
1
,
k
,
l
n
-
k
+
l
+
p
k
q
g
n
-
k
-
1
,
k
,
l
r
-
1
.Rearranging terms and replacing n by n
+
k
+
1 and r by r
+
1 yield (53). Our expression for g
n
,
k
,
l
(
r
) is given by a sum of exactly k
(
r
+
1
) terms, independently of n. Note, however, that f
r
+
1
,
k
,
l
(
n
+
k
+
1
) and f
r
,
k
,
l
(
n
+
l
+
1
) must be calculated for each r. In practice, this means we must calculate f
r
,
k
,
l
(
n
) in (52) for r
=
1
,
…
,
r
∗. This requires a total of r
∗
(
r
∗
+
1
)
/
2 sums, to obtain the full probability mass distribution.We now summarize results for the p.m.f. and p.g.f. derived by other authors. Aki and Hirano (2000) [18, Proposition 2.2] derived an expression for the p.g.f. as a nested sum of multinomial terms. Makri and Philippou [11, Theorem 2.1] derived the p.m.f. P
(
N
n
,
k
,
l
=
x
), x
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
) as a sum of multinomial terms. They also derived an alternative expression for the p.m.f. [11, Theorem 2.2] in terms of C
(
n
,
m
,
r
), which is the number of possible ways of distributing n identical balls into m urns such that the maximum allowed number of balls in any one urn is r [11, Lemma 2.1]. They also calculated the mean [11, Proposition 2.1](55)
E
N
n
,
k
,
l
=
p
l
∑
r
=
1
r
∗
1
+
1
-
p
n
-
l
-
r
k
-
l
p
r
k
-
l
.The special case l
=
0 is Proposition 2.4 of Aki and Hirano (1988) [19]; see also Antzoulakos and Chadjiconstantinidis [20]. The special case l
=
k
-
1 is equivalent to Theorem 4.1(i) of Ling (1988) [13](56)
E
N
n
,
k
,
k
-
1
=
n
-
k
+
1
p
k
.Ling (1988) [13, Theorem 3.1] gave a recursive relation for the p.m.f. and also an explicit expression for the p.m.f. [13, Theorem 3.2], in terms of nested multinomial sums. Ling derived the mean [13, Theorem 4.1(i)] and the variance [13, Theorem 4.1(ii)] and a recurrence relation for the m.g.f. [13, Theorem 4.1(iii)]. Inoue and Aki [21, Proposition 3] derived an explicit expression for the p.g.f. ϕ
n
(
+
)
(
z
) in terms of restricted multiple sums and multinomials. They stated that their expression for the special case l
=
k
-
1 was derived by Inoue and Aki [21, Proposition 4]. Hirano et al. [10] studied the case l
=
k
-
1 in some detail. They give an explicit expression for the p.g.f. ϕ
n
(
t
) in terms of restricted multiple sums and multinomials [10, Theorem 2.2]. Hirano et al. [10, Theorem 2.3] give an explicit expression for the p.m.f. in terms of nested multinomial sums, but different from Ling (1988) [13, Theorem 3.1]. Han and Aki [22, Theorem 2.1] presented a recurrence formula to calculate the p.m.f.


### 3.4. Success Runs withl
<
0

The casel
<
0 is not without interest. In this scenario, there must be a gap or buffer of at least l trials (of arbitrary outcomes) between success runs. We call this scenario “l-buffering.” First, we derive the probability mass function, probability generating function, mean, and variance of the negative binomial distribution of order k for r
≥
1 success runs of length k with l-overlapping. Next, we treat sequences with a fixed total length n and study the binomial distribution of order k with buffer l. The value of r of the number of success runs spans the interval 0
≤
r
≤
(
n
-
l
)
/
(
k
-
l
). This is the same formula as for l
≥
0. We derive an expression for the probability mass function for the above distribution.Most of the published literature for the casel
<
0 has treated sequences of fixed length n. Inoue and Aki [21, Section 4.2] published results for sequences of Markov trials. They derived an expression for the p.g.f. as a nested sum of multinomial terms [21, Proposition 4]. Han and Aki [22] treated sequences of i.i.d. Bernoulli trials. They derived a recurrence relation for the p.g.f. [22, Theorem 4.1].The results for the negative binomial case (fixedr
≥
1, variable n
≥
1) are straightforward to derive for l
<
0. The following results are stated without proof.Proposition 19.
Forl
<
0, the probability mass function f
r
,
k
,
l
(
n
) for r success runs of length k with |
l
|-buffering satisfies the obvious identity(57)
f
r
,
k
,
l
n
=
f
r
,
k
,
0
n
+
r
-
1
l
.The probability generating function is then given by(58)
ϕ
r
,
k
,
l
s
=
ϕ
r
,
k
,
0
s
s
r
-
1
l
=
ϕ
s
,
k
r
s
r
-
1
l
.The domain of convergence of the p.g.f. is clearly the same as in the case l
≥
0 (see (28)) and is |
s
|
<
1
/
λ
0
(
p
,
k
). It follows easily from (58) that the mean and variance are given by (59a)
μ
r
,
k
,
l
=
r
μ
k
+
r
-
1
l
,
(59b)
σ
r
,
k
,
l
2
=
r
σ
2
k
.For sequences of fixed lengthn, the analysis of the binomial distribution of order k is nontrivial for l
<
0. We first state the following obvious result for all l.Remark 20.
For anyl
∈
Z, let h
r
,
k
,
l
(
n
) be the probability of attaining, after n trials, r or fewer success runs of length k with l-overlapping for l
≥
0 or |
l
|-buffering for l
<
0. Then clearly(60)
h
r
,
k
,
l
n
=
∑
j
=
1
∞
f
r
,
k
,
l
n
+
j
.Hence, for fixed n, the probability mass function g
n
,
k
,
l
(
r
) for r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
) is given by(61)
g
n
,
k
,
l
r
=
h
r
,
k
,
l
n
-
h
r
-
1
,
k
,
l
n
=
∑
j
=
1
∞
f
r
,
k
,
l
n
+
j
-
f
r
-
1
,
k
,
l
n
+
j
.The above expression is valid for alll
∈
Z but requires the summation of an infinite series. For l
≥
0, (53) offers a more concise expression for g
n
,
k
,
l
(
r
). For l
<
0, we can also derive a more concise expression for g
n
,
k
,
l
(
r
) as follows.Proposition 21.
For fixedn and fixed l
<
0, the probability mass function g
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
) for the binomial distribution of order k with |
l
|-buffering is given by(62)
g
n
,
k
,
l
r
=
f
r
+
1
,
k
,
l
n
+
k
-
l
-
p
k
+
1
f
r
,
k
,
l
n
p
k
q
+
∑
j
=
1
l
-
1
f
r
+
1
,
k
,
l
n
+
j
.Here r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
). Note by definition that f
r
,
k
,
l
(
n
)
=
0 for r
=
0.Proof.
We omit the indicesk and l in the following. Consider f
r
(
n
), where r success runs have taken place, ending at trial n. Hence the last k outcomes are all successes. We then have the following mutually exclusive and exhaustive possibilities. (i)
The outcome of trialn
-
k is a success. Then the (
r
-
1
)
t
h success run must end at trial n
-
k
+
l. The |
l
| trials in the sequence from n
-
k
+
l
+
1 through n
-
k constitute the buffer between the two success runs. The probability of this event is p
k
+
1
f
r
-
1
(
n
-
k
+
l
). (This event is null if r
=
1. Note that f
0
,
k
,
l
(
n
-
k
+
l
)
=
0.)
(ii)
The outcome of trialn
-
k is a failure. Then we must attain r
-
1 success runs by trial n
-
k
+
l. However, we must subtract the possibility that the r
t
h success run ends at one of the trials n
-
k
+
l
+
1 through n
-
k
-
1. (Note that if l
=
-
1, this set is empty.) The probability of this event is p
k
q
(
g
n
-
k
+
l
(
r
-
1
)
-
∑
j
=
1
|
l
|
-
1
f
r
(
n
-
k
+
l
+
j
)
).The events are mutually exclusive and exhaustive (noting that there can be at most one success run completed from trials n
-
k
+
l
+
1 through n
-
k
-
1 because of the buffering requirement); hence we add the probabilities to obtain(63)
f
r
n
=
p
k
+
1
f
r
-
1
n
-
k
+
l
+
p
k
q
g
n
-
k
+
l
r
-
1
-
∑
j
=
1
l
-
1
f
r
n
-
k
+
l
+
j
.Rearranging terms and replacing n by n
+
k
-
l and r by r
+
1 yield (62). For l
=
-
1, the last sum is absent and the above expression is the same as (53).


## 3.1. Probability Generating Function, Mean, and Variance

We now turn to the first problem of interest in this paper, namely, the waiting time to obtainr
>
1 success runs of length k. We begin by displaying the following expressions for the case r
=
1. They were derived by Feller [5] and will be required in the following.Remark 10 (probability generating function forr
=
1).
Lets
∈
C. The probability generating function (p.g.f.) for the geometric distribution of order k is [5, eq. (
7.6
)](22)
ϕ
s
,
k
=
p
k
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
=
p
k
s
k
1
-
q
s
1
+
p
s
+
⋯
+
p
k
-
1
s
k
-
1
.The p.g.f. exists for |
s
|
<
1
/
λ
0
(
p
,
k
) [5]. The mean and variance are given by [5, eq. (
7.7
)](23)
μ
k
=
1
-
p
k
q
p
k
,
σ
2
k
=
1
q
p
k
2
-
2
k
+
1
q
p
k
-
p
q
2
.The dependences on p and k will be omitted in the following unless necessary.We now calculate the probability generating function, mean, and variance for multipler
>
1 overlapping runs. The success runs have length k and there can be at most 0
≤
l
<
k overlaps between consecutive success runs. We denote the waiting time by X
r
,
k
,
l. The case l
=
0 of nonoverlapping runs was extensively analyzed by Philippou [8], who named the distribution as the negative binomial distribution of order k with vector parameter (
r
,
p
). Ling (1989) [9] and Hirano et al. [10] derived results for the special case l
=
k
-
1. The text by Balakrishnan and Koutras [3] lists the special cases l
=
0 and l
=
k
-
1 as, respectively, Type I and Type III negative binomial distributions of order k.Proposition 11 (probability generating function forr
≥
1).
Let the probability generating function forr
≥
1 success runs of length k with at most l overlaps be ϕ
r
,
k
,
l
(
s
). We will omit the subscripts k and l unless necessary. Then(24)
ϕ
r
,
k
,
l
s
=
ϕ
s
,
k
r
ϕ
s
,
l
r
-
1
.Notice that, for r
=
1, we obtain ϕ
1
,
k
,
l
(
s
)
=
ϕ
(
s
,
k
) (see (22)), as required.Proof.
DefineX
j
(
=
X
j
,
k
,
l
) as the waiting time to complete j success runs. So suppose we have completed j
-
1 success runs. Hence by definition the last k trials are all successes. Then exactly one of the following k
-
l
+
1 mutually exclusive events will occur:(i)
The nextk
-
l trials are all successes. This yields the j
t
h success run.
(ii)
The nextκ trials are successes, followed by a failure, where κ
=
0,1
,
…
,
k
-
l
-
1. Then we restart the waiting time for the next success run from scratch (conditioned on an initial failure). We denote this additional waiting time by Y
j. Clearly, Y
j has the same distribution as X
1.Since the events are mutually exclusive, we add the probabilities to obtain(25)
E
exp
⁡
t
X
j
=
p
k
-
l
E
exp
⁡
t
X
j
-
1
+
k
-
l
+
∑
κ
=
0
k
-
l
-
1
p
κ
q
E
exp
⁡
t
X
j
-
1
+
Y
j
+
κ
+
1
=
p
k
-
l
e
t
k
-
l
E
exp
⁡
t
X
j
-
1
+
∑
κ
=
0
k
-
l
-
1
p
κ
q
e
t
κ
+
1
E
exp
⁡
t
X
j
-
1
E
exp
⁡
t
Y
j
=
E
exp
⁡
t
X
j
-
1
p
k
-
l
e
t
k
-
l
+
ϕ
e
t
∑
κ
=
0
k
-
l
-
1
p
κ
q
e
t
κ
+
1
.Now set s
=
e
t and note that ϕ
j
(
s
)
=
E
(
exp
⁡
(
t
X
j
)
). Hence we obtain the following recurrence relation and solution for ϕ
r
(
s
): (26a)
ϕ
r
s
=
ϕ
r
-
1
s
p
s
k
-
l
+
ϕ
s
∑
κ
=
0
k
-
l
-
1
p
κ
q
s
κ
+
1
,
(26b)
=
ϕ
s
p
s
k
-
l
+
ϕ
s
q
s
1
-
p
s
k
-
l
1
-
p
s
r
-
1
.Define Z as the term in the brackets. After some tedious algebra we obtain(27)
Z
=
p
s
k
-
l
+
p
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
q
s
1
-
p
s
k
-
l
1
-
p
s
=
p
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
1
-
s
+
q
p
l
s
l
+
1
p
s
l
1
-
p
s
=
ϕ
s
,
k
ϕ
s
,
l
.In the last line it is necessary to exhibit the dependences on k and l explicitly. Then (24) follows immediately.Proposition 12 (domain of convergence).
The probability generating function forr
≥
1 success runs ϕ
r
,
k
,
l
(
s
) converges for(28)
s
<
1
λ
0
p
,
k
.Hence the domain of convergence of the probability generating function is the same for all r
≥
1.Proof.
Clearly, the functionϕ
r
,
k
,
l
(
s
) is well defined if and only if the sums of the series for ϕ
(
s
,
k
) and ϕ
(
s
,
l
) both converge. It was proved by Feller [5] that ϕ
(
s
,
k
) exists for s
<
1
/
λ
0
(
p
,
k
). Hence ϕ
r
,
k
,
l
(
s
) exists if(29)
s
<
min
⁡
1
λ
0
p
,
k
,
1
λ
0
p
,
l
.However, because l
<
k, it follows from Proposition 8 that λ
0
(
p
,
l
)
<
λ
0
(
p
,
k
). Hence 1
/
λ
0
(
p
,
k
)
<
1
/
λ
0
(
p
,
l
). This proves (28).Proposition 13 (mean and variance).
The meanμ
r
,
k
,
l and variance σ
r
,
k
,
l
2 for the waiting time for r
≥
1 success runs are given by (30a)
μ
r
,
k
,
l
=
r
μ
k
-
r
-
1
μ
l
,
(30b)
σ
r
,
k
,
l
2
=
r
σ
2
k
-
r
-
1
σ
2
l
.Proof.
We puts
=
e
t and differentiate with respect to t and evaluate at t
=
0. We differentiate ln
⁡
ϕ
r
(
e
t
) to obtain(31)
ϕ
r
′
e
t
ϕ
r
e
t
=
r
ϕ
′
e
t
,
k
ϕ
e
t
,
k
-
r
-
1
ϕ
′
e
t
,
l
ϕ
e
t
,
l
.Evaluating at t
=
0 and noting that ϕ
(
1
,
k
)
=
ϕ
(
1
,
l
)
=
1 yield(32)
μ
r
,
k
,
l
=
r
μ
k
-
r
-
1
μ
l
.This proves (30a). We differentiate again to obtain(33)
ϕ
r
′
′
e
t
ϕ
r
e
t
-
ϕ
r
′
2
e
t
ϕ
r
e
t
2
=
r
ϕ
′
′
e
t
,
k
ϕ
e
t
,
k
-
ϕ
′
2
e
t
,
k
ϕ
e
t
,
k
2
-
r
-
1
ϕ
′
′
e
t
,
l
ϕ
e
t
,
l
-
ϕ
′
2
e
t
,
l
ϕ
e
t
,
l
2
. We again evaluate at t
=
0 to obtain(34)
σ
r
,
k
,
l
2
=
r
σ
2
k
-
r
-
1
σ
2
l
.This proves (30b).We now show that various results derived by other authors are special cases of our results above. As stated above, the casel
=
0 of nonoverlapping runs was solved by Philippou [8], while Ling (1989) [9] and Hirano et al. [10] treated the case l
=
k
-
1 of overlapping runs.Remark 14 (Philippou (1984)).
Philippou [8, Lemma 2.2] stated “Let X be a r
v distributed as N
B
k
(
x
;
r
,
p
). Then its probability generating function, to be denoted by γ
k
,
r
(
s
), is given by”(35)
γ
k
,
r
s
=
p
k
s
k
1
-
p
s
1
-
s
+
q
p
k
s
k
+
1
r
,
s
≤
1
.The mean and variance are given by [8, Proposition 2.1] (36a)
E
X
=
r
1
-
p
k
q
p
k
,
(36b)
σ
2
X
=
r
1
-
2
k
+
1
q
p
k
-
p
2
k
+
1
q
2
p
2
k
.Proof.
By definition, Philippou’s notationγ
k
,
r
(
s
) is the same as our ϕ
r
,
k
,
l
(
s
) with l
=
0. From (22), it is easy to show that ϕ
(
s
,
l
)
=
1 for l
=
0, whence ϕ
r
,
k
,
0
(
s
)
=
ϕ
(
s
,
k
)
r and (35) follows. Note that Philippou [8] stated the domain of convergence to be |
s
|
≤
1, but we have shown that it is |
s
|
≤
1
/
λ
0
(
p
,
k
), which is a larger domain. Next, it is also easy to show that μ
(
l
)
=
σ
2
(
l
)
=
0 for l
=
0, whence μ
r
,
k
,
0
=
r
μ
(
k
) and σ
r
,
k
,
0
2
=
r
σ
2
(
k
) which yield (36a) and (36b), respectively.Remark 15 (Ling (1989)).
Ling (1989) [9, Theorem 4.1] stated that, for |
s
|
≤
1, (37a)
ϕ
r
k
s
=
s
ϕ
r
-
1
k
s
p
+
q
ϕ
1
k
s
,
(37b)
ϕ
r
k
s
=
ϕ
1
k
s
s
p
+
q
ϕ
1
k
s
r
-
1
.Proof.
Ling wroteϕ
r
(
k
)
(
s
) and ϕ
1
(
k
)
(
s
) where we have written ϕ
r
,
k
,
l
(
s
) and ϕ
(
s
), but the connection between the notations is clear. Setting l
=
k
-
1 in (26a) yields(38)
ϕ
r
s
=
ϕ
r
-
1
s
p
s
+
q
s
ϕ
s
=
s
ϕ
r
-
1
s
p
+
q
ϕ
s
.This yields (37a). Next (37b) follows immediately by solving the recurrence relation(39)
ϕ
r
s
=
ϕ
s
s
p
+
q
ϕ
s
r
-
1
.Similar to Philippou [8], Ling (1989) [9] also stated the domain of convergence to be |
s
|
≤
1, but we have shown that it is larger, given by |
s
|
≤
1
/
λ
0
(
p
,
k
).Remark 16 (Hirano et al. (1991)).
Hirano et al. [10, Theorem 4.1] stated that “Let ϕ
r
N
B
(
t
) be the p.g.f. of N
B
k
I
I
I
(
r
,
p
).” They wrote(40)
ϕ
r
N
B
t
=
p
t
+
q
t
ϕ
1
N
B
t
r
-
1
ϕ
1
N
B
t
.They also wrote(41)
ϕ
1
N
B
t
=
p
t
k
1
-
q
∑
i
=
0
k
-
1
p
i
t
i
+
1
.Then they derived the solution(42)
ϕ
r
N
B
t
=
p
t
-
1
p
t
k
+
r
-
1
-
q
p
k
-
1
t
k
+
t
-
1
r
-
1
-
q
p
k
t
k
+
1
+
t
-
1
r
.They also gave expressions for the mean and variance. The mean is(43)
E
N
r
k
=
q
r
+
p
-
p
k
p
k
q
.Proof.
The connection between the notations is that they writeϕ
r
N
B
(
t
) and ϕ
1
N
B
(
t
) where we write ϕ
r
(
s
) and ϕ
(
s
), respectively. They employ t as the independent variable, where we use s. It is simple to derive that their expression for ϕ
1
N
B
(
t
) in (42) equals that for ϕ
(
s
,
k
) in (22). Next, (40) is simply (39) with the changes of notation listed above. Next, setting l
=
k
-
1 and changing the independent variable from s to t,(44)
ϕ
r
,
k
,
k
-
1
t
=
ϕ
t
,
k
r
ϕ
t
,
k
-
1
r
-
1
=
p
t
k
r
1
-
p
t
r
1
-
t
+
q
p
k
t
k
+
1
r
1
-
t
+
q
p
k
-
1
t
k
r
-
1
p
t
k
-
1
r
-
1
1
-
p
t
r
-
1
=
p
t
-
1
p
t
k
+
r
-
1
-
q
p
k
-
1
t
k
+
t
-
1
r
-
1
-
q
p
k
t
k
+
1
+
t
-
1
r
.This is exactly (42). From (30a), the mean for l
=
k
-
1 is(45)
μ
r
,
k
,
k
-
1
=
r
μ
k
-
r
-
1
μ
k
-
1
=
r
1
-
p
k
p
k
q
-
r
-
1
1
-
p
k
-
1
p
k
-
1
q
=
q
r
+
p
-
p
k
p
k
q
.This is exactly (43). Hirano et al. [10] also displayed an expression for the variance. The proof of equivalence with our expression involves merely tedious algebra and is omitted.


## 3.2. Probability Mass Function

We derive an expression forf
r
,
k
,
l
(
n
), the probability mass function (p.m.f.) that the r
t
h success run of length k with l-overlapping occurs at the n
t
h Bernoulli trial, where r
≥
1 and n
≥
1. Clearly f
r
,
k
,
l
(
n
)
=
0 for n
<
l
+
r
(
k
-
l
)
=
r
k
-
(
r
-
1
)
l and f
r
,
k
,
l
(
n
)
=
p
r
k
-
(
r
-
1
)
l for n
=
r
k
-
(
r
-
1
)
l. An expression for the p.m.f. for the case r
=
1 was derived in [1]. By definition, the probability generating function is related to the probability mass function via(46)
ϕ
r
,
k
,
l
s
=
∑
n
=
0
∞
s
n
f
r
,
k
,
l
n
.We derived an expression for ϕ
r
,
k
,
l
(
s
) above and we will use it to derive an expression for f
r
,
k
,
l
(
n
) in the following. From the second form for ϕ
(
s
,
k
) in (22), with z
=
1
/
s,(47)
ψ
z
=
ϕ
1
z
=
p
k
A
p
,
k
z
.Hence for r
≥
1 success runs,(48)
ψ
r
,
k
,
l
z
≡
ϕ
r
,
k
,
l
1
z
=
ψ
z
,
k
r
ψ
z
,
l
r
-
1
=
p
r
k
-
r
-
1
l
A
p
,
l
z
r
-
1
A
p
,
k
z
r
.The right hand side is a rational function of two polynomials. From Proposition 7, the auxiliary polynomials A
p
,
l
(
z
) and A
p
,
k
(
z
) have no roots in common. Furthermore, because l
<
k, the numerator polynomial is of a lower degree than the denominator polynomial. We also know that all the roots of the auxiliary polynomials are distinct. Hence we can expand ψ
r
,
k
,
l
(
z
) as a sum of partial fractions with repeated roots (of the denominator polynomial)(49)
ψ
r
,
k
,
l
z
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
j
m
z
-
λ
j
p
,
k
m
.Here the coefficients a
j
m are parameters which depend on r, k, and l but not on z. For brevity, we drop the subscripts k and l on ψ
r
,
k
,
l and also write the roots as λ
j in the following. The coefficients a
j
m can be evaluated explicitly in terms of the roots {
λ
i
(
p
,
k
)
,
i
=
0
,
…
,
k
-
1
} via the standard residues formula(50)
a
j
m
=
1
r
-
m
!
d
r
-
m
d
z
r
-
m
z
-
λ
j
r
ψ
r
z
z
=
λ
j
.Returning to the use of s
=
1
/
z, we see that(51)
ϕ
r
s
=
ψ
r
1
s
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
j
m
s
m
1
-
λ
j
s
m
.We expand the right hand side using the negative binomial theorem and equate f
r
,
k
,
l
(
n
) to the coefficient of s
n.Proposition 17.
The probability mass functionf
r
,
k
,
l
(
n
) for the r
t
h success run of length k with l-overlapping is given by(52)
f
r
,
k
,
l
n
=
∑
j
=
0
k
-
1
∑
m
=
1
r
n
-
1
m
-
1
a
j
m
λ
j
p
,
k
n
-
m
.Hence f
r
,
k
,
l
(
n
) is given by a sum of exactly r
k terms, independently of n. Recall from above that f
r
(
n
)
=
0 for n
<
r
k
-
(
r
-
1
)
l so the above formula is only required for n
≥
r
k
-
(
r
-
1
)
l; hence the binomial coefficients are well defined.The derivation of the above expression has already been given above, where all notation has been defined and explained.


## 3.3. Binomial Distribution of Orderk with l-Overlapping

Consider a sequence of Bernoulli trials of fixed lengthn
>
0 and let N
n
,
k
,
l denote the number of success runs of length k with a maximum of l overlaps between success runs. This is the binomial distribution of order k with l-overlapping success runs and has been reviewed in the encyclopedia article by Philippou and Antzoulakos [6]. Good overviews have also been given by Makri and Philippou [11] and Makri et al. [12]; see the bibliographies in both references. Ling (1988) [13] introduced the case of l
=
k
-
1 and called it the “Type II binomial distribution of order k.”The caser
=
0 is the probability that the longest success run in the first n trials has length less than k. It is also known as the probability that the waiting time to attain the first success run of length k exceeds n trials. This scenario has been solved by many authors. For example, Feller [5] presented an asymptotic solution in terms of the principal root. In our paper [1], we extended Feller’s solution to include all the roots. Solutions have also been derived by Burr and Cane [14], Godbole [15], Philippou and Makri [16], and Muselli [17], all of whom expressed their results using (possibly nested) binomial or multinomial sums.Letg
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
), where r
=
0,1
,
…, be the probability mass function for N
n
,
k
,
l. We derive an expression for g
n
,
k
,
l
(
r
) in the following. Note that, to obtain a nontrivial distribution, we must have n
≥
l
+
r
(
k
-
l
) so for fixed n we must have 0
≤
r
≤
r
∗
≡
(
n
-
l
)
/
(
k
-
l
).Proposition 18.
The probability mass functiong
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
) for the binomial distribution of order k with l-overlapping is given by(53)
g
n
,
k
,
l
r
=
f
r
+
1
,
k
,
l
n
+
k
+
1
p
k
q
-
f
r
,
k
,
l
n
+
l
+
1
p
l
q
.Here r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
). Note that the last term vanishes for r
=
0; hence the above expression agrees with our result in [1].Proof.
We solve the problem as follows. Suppose ther
t
h success run is completed on the n
t
h trial. Then by definition the outcomes of the last k trials are all successes. There are now two mutually exclusive and exhaustive possibilities, according as the (
r
-
1
)
t
h success run is contiguous with (and possibly overlaps) the r
t
h success run, or there is at least one failure between the runs. (i)
In the former case, the(
r
-
1
)
t
h success run terminates at the trial n
-
k
+
l. (This event is null if r
=
1.) The outcome of the n
-
k
t
h trial is a success.
(ii)
In the latter case, the outcome of the(
n
-
k
)
t
h trial is a failure. The first n
-
k
-
1 trials contain exactly r
-
1 success runs.Since the events are mutually exclusive and exhaustive, we add the probabilities to obtain(54)
f
r
,
k
,
l
n
=
p
k
-
l
f
r
-
1
,
k
,
l
n
-
k
+
l
+
p
k
q
g
n
-
k
-
1
,
k
,
l
r
-
1
.Rearranging terms and replacing n by n
+
k
+
1 and r by r
+
1 yield (53). Our expression for g
n
,
k
,
l
(
r
) is given by a sum of exactly k
(
r
+
1
) terms, independently of n. Note, however, that f
r
+
1
,
k
,
l
(
n
+
k
+
1
) and f
r
,
k
,
l
(
n
+
l
+
1
) must be calculated for each r. In practice, this means we must calculate f
r
,
k
,
l
(
n
) in (52) for r
=
1
,
…
,
r
∗. This requires a total of r
∗
(
r
∗
+
1
)
/
2 sums, to obtain the full probability mass distribution.We now summarize results for the p.m.f. and p.g.f. derived by other authors. Aki and Hirano (2000) [18, Proposition 2.2] derived an expression for the p.g.f. as a nested sum of multinomial terms. Makri and Philippou [11, Theorem 2.1] derived the p.m.f. P
(
N
n
,
k
,
l
=
x
), x
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
) as a sum of multinomial terms. They also derived an alternative expression for the p.m.f. [11, Theorem 2.2] in terms of C
(
n
,
m
,
r
), which is the number of possible ways of distributing n identical balls into m urns such that the maximum allowed number of balls in any one urn is r [11, Lemma 2.1]. They also calculated the mean [11, Proposition 2.1](55)
E
N
n
,
k
,
l
=
p
l
∑
r
=
1
r
∗
1
+
1
-
p
n
-
l
-
r
k
-
l
p
r
k
-
l
.The special case l
=
0 is Proposition 2.4 of Aki and Hirano (1988) [19]; see also Antzoulakos and Chadjiconstantinidis [20]. The special case l
=
k
-
1 is equivalent to Theorem 4.1(i) of Ling (1988) [13](56)
E
N
n
,
k
,
k
-
1
=
n
-
k
+
1
p
k
.Ling (1988) [13, Theorem 3.1] gave a recursive relation for the p.m.f. and also an explicit expression for the p.m.f. [13, Theorem 3.2], in terms of nested multinomial sums. Ling derived the mean [13, Theorem 4.1(i)] and the variance [13, Theorem 4.1(ii)] and a recurrence relation for the m.g.f. [13, Theorem 4.1(iii)]. Inoue and Aki [21, Proposition 3] derived an explicit expression for the p.g.f. ϕ
n
(
+
)
(
z
) in terms of restricted multiple sums and multinomials. They stated that their expression for the special case l
=
k
-
1 was derived by Inoue and Aki [21, Proposition 4]. Hirano et al. [10] studied the case l
=
k
-
1 in some detail. They give an explicit expression for the p.g.f. ϕ
n
(
t
) in terms of restricted multiple sums and multinomials [10, Theorem 2.2]. Hirano et al. [10, Theorem 2.3] give an explicit expression for the p.m.f. in terms of nested multinomial sums, but different from Ling (1988) [13, Theorem 3.1]. Han and Aki [22, Theorem 2.1] presented a recurrence formula to calculate the p.m.f.


## 3.4. Success Runs withl
<
0

The casel
<
0 is not without interest. In this scenario, there must be a gap or buffer of at least l trials (of arbitrary outcomes) between success runs. We call this scenario “l-buffering.” First, we derive the probability mass function, probability generating function, mean, and variance of the negative binomial distribution of order k for r
≥
1 success runs of length k with l-overlapping. Next, we treat sequences with a fixed total length n and study the binomial distribution of order k with buffer l. The value of r of the number of success runs spans the interval 0
≤
r
≤
(
n
-
l
)
/
(
k
-
l
). This is the same formula as for l
≥
0. We derive an expression for the probability mass function for the above distribution.Most of the published literature for the casel
<
0 has treated sequences of fixed length n. Inoue and Aki [21, Section 4.2] published results for sequences of Markov trials. They derived an expression for the p.g.f. as a nested sum of multinomial terms [21, Proposition 4]. Han and Aki [22] treated sequences of i.i.d. Bernoulli trials. They derived a recurrence relation for the p.g.f. [22, Theorem 4.1].The results for the negative binomial case (fixedr
≥
1, variable n
≥
1) are straightforward to derive for l
<
0. The following results are stated without proof.Proposition 19.
Forl
<
0, the probability mass function f
r
,
k
,
l
(
n
) for r success runs of length k with |
l
|-buffering satisfies the obvious identity(57)
f
r
,
k
,
l
n
=
f
r
,
k
,
0
n
+
r
-
1
l
.The probability generating function is then given by(58)
ϕ
r
,
k
,
l
s
=
ϕ
r
,
k
,
0
s
s
r
-
1
l
=
ϕ
s
,
k
r
s
r
-
1
l
.The domain of convergence of the p.g.f. is clearly the same as in the case l
≥
0 (see (28)) and is |
s
|
<
1
/
λ
0
(
p
,
k
). It follows easily from (58) that the mean and variance are given by (59a)
μ
r
,
k
,
l
=
r
μ
k
+
r
-
1
l
,
(59b)
σ
r
,
k
,
l
2
=
r
σ
2
k
.For sequences of fixed lengthn, the analysis of the binomial distribution of order k is nontrivial for l
<
0. We first state the following obvious result for all l.Remark 20.
For anyl
∈
Z, let h
r
,
k
,
l
(
n
) be the probability of attaining, after n trials, r or fewer success runs of length k with l-overlapping for l
≥
0 or |
l
|-buffering for l
<
0. Then clearly(60)
h
r
,
k
,
l
n
=
∑
j
=
1
∞
f
r
,
k
,
l
n
+
j
.Hence, for fixed n, the probability mass function g
n
,
k
,
l
(
r
) for r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
) is given by(61)
g
n
,
k
,
l
r
=
h
r
,
k
,
l
n
-
h
r
-
1
,
k
,
l
n
=
∑
j
=
1
∞
f
r
,
k
,
l
n
+
j
-
f
r
-
1
,
k
,
l
n
+
j
.The above expression is valid for alll
∈
Z but requires the summation of an infinite series. For l
≥
0, (53) offers a more concise expression for g
n
,
k
,
l
(
r
). For l
<
0, we can also derive a more concise expression for g
n
,
k
,
l
(
r
) as follows.Proposition 21.
For fixedn and fixed l
<
0, the probability mass function g
n
,
k
,
l
(
r
)
=
P
(
N
n
,
k
,
l
=
r
) for the binomial distribution of order k with |
l
|-buffering is given by(62)
g
n
,
k
,
l
r
=
f
r
+
1
,
k
,
l
n
+
k
-
l
-
p
k
+
1
f
r
,
k
,
l
n
p
k
q
+
∑
j
=
1
l
-
1
f
r
+
1
,
k
,
l
n
+
j
.Here r
=
0,1
,
…
,
(
n
-
l
)
/
(
k
-
l
). Note by definition that f
r
,
k
,
l
(
n
)
=
0 for r
=
0.Proof.
We omit the indicesk and l in the following. Consider f
r
(
n
), where r success runs have taken place, ending at trial n. Hence the last k outcomes are all successes. We then have the following mutually exclusive and exhaustive possibilities. (i)
The outcome of trialn
-
k is a success. Then the (
r
-
1
)
t
h success run must end at trial n
-
k
+
l. The |
l
| trials in the sequence from n
-
k
+
l
+
1 through n
-
k constitute the buffer between the two success runs. The probability of this event is p
k
+
1
f
r
-
1
(
n
-
k
+
l
). (This event is null if r
=
1. Note that f
0
,
k
,
l
(
n
-
k
+
l
)
=
0.)
(ii)
The outcome of trialn
-
k is a failure. Then we must attain r
-
1 success runs by trial n
-
k
+
l. However, we must subtract the possibility that the r
t
h success run ends at one of the trials n
-
k
+
l
+
1 through n
-
k
-
1. (Note that if l
=
-
1, this set is empty.) The probability of this event is p
k
q
(
g
n
-
k
+
l
(
r
-
1
)
-
∑
j
=
1
|
l
|
-
1
f
r
(
n
-
k
+
l
+
j
)
).The events are mutually exclusive and exhaustive (noting that there can be at most one success run completed from trials n
-
k
+
l
+
1 through n
-
k
-
1 because of the buffering requirement); hence we add the probabilities to obtain(63)
f
r
n
=
p
k
+
1
f
r
-
1
n
-
k
+
l
+
p
k
q
g
n
-
k
+
l
r
-
1
-
∑
j
=
1
l
-
1
f
r
n
-
k
+
l
+
j
.Rearranging terms and replacing n by n
+
k
-
l and r by r
+
1 yield (62). For l
=
-
1, the last sum is absent and the above expression is the same as (53).


## 4. Pairs of Successes Separated by At Mostk
-
2 Failures

In this section we study a different problem. We treat the distribution of waiting time for ther
t
h nonoverlapping appearance of a pair of successes separated by at most k
-
2 failures (k
≥
2). Our main reference is the elegant analysis by Koutras [7], who also gives an excellent bibliography on the subject. To avoid cluttering the notation in this paper with too many symbols, we will reuse some of the symbols such as f
r
,
k
(
n
) for the probability mass function, and so forth. It should be understood that we are treating a new problem, and the following notation is self-contained. We begin with r
=
1. Koutras [7] gave a recurrence relation for the probability mass function f
r
,
k
(
n
). We will suppress the indices r and k unless required. We derive the exact solutions for the roots of the auxiliary polynomial associated with the recurrence relation, in terms of Fuss-Catalan numbers. We also derive various pertinent properties of the roots. We then solve a Vandermonde matrix system of equations to derive an expression for the p.m.f. as a sum over powers of the roots. We also derive an expression for the probability of the waiting time to exceed n trials.Let us denote the waiting time byT
r
,
k. Note that Koutras [7] writes T
k
,
r, but we write T
r
,
k to maintain consistency with the notation in the earlier parts of our paper. We begin with the case r
=
1 and drop the subscripts.Remark 22 (Koutras [7], Theorem 3.1).
The probability mass functionf
(
n
)
=
P
(
T
=
n
) satisfies the recurrence relation [7, eq. 3.1](64)
f
n
=
q
f
n
-
1
+
p
q
k
-
1
f
n
-
k
n
>
k
.The initial conditions are [7, eq. 3.2](65a)
f
0
=
f
1
=
0
,
(65b)
f
n
=
n
-
1
p
2
q
n
-
2
,
1
<
n
≤
k
.The auxiliary polynomial associated with the above recurrence relation is(66)
A
z
=
z
k
-
q
z
k
-
1
-
p
q
k
-
1
.The auxiliary equation is A
(
z
)
=
0.Proposition 23 (properties of roots).
For fixed0
<
p
<
1, the roots of the auxiliary polynomial have the following properties: (a)
There are no repeated roots.
(b)
There is a unique positive real root.
(c)
The positive real root lies in(
q
,
1
).
(d)
Ifk is odd, there are no other real roots. If k is even, there is exactly one negative real root.
(e)
The magnitude of the positive real root exceeds that of all the other roots.Proof.
BothA
(
z
) and A
′
(
z
) must vanish simultaneously at a repeated root. Next(67)
A
′
z
=
k
z
k
-
1
-
q
k
-
1
z
k
-
2
=
k
z
k
-
2
z
-
q
k
-
1
k
.Hence A
′
(
z
) vanishes at z
=
0 (not a root of A
(
z
)) or z
=
q
(
k
-
1
)
/
k. Note that 0
<
q
(
k
-
1
)
/
k
<
q. Now for 0
<
z
<
q,(68)
z
k
-
q
z
k
-
1
=
z
-
q
z
k
-
1
<
0
.Hence for 0
<
z
<
q,(69)
A
z
=
z
-
q
z
k
-
1
-
p
q
k
-
1
<
-
p
q
k
-
1
<
0
.Hence A
(
z
)
≠
0 for z
=
q
(
k
-
1
)
/
k. Hence A
(
z
) has no repeated roots. Next note that A
(
0
)
=
-
p
q
k
-
1, A
(
q
)
=
-
p
q
k
-
1, and A
(
1
)
=
p
(
1
-
q
k
-
1
). Hence A
(
z
) has an odd number of positive real roots for z
∈
(
q
,
1
). Now from (67), A
′
(
z
)
>
0 for z
>
q
(
1
-
1
/
k
), so A
′
(
z
)
>
0 for z
>
q. It follows that A
(
z
) has exactly one positive real root, and it lies in the interval z
∈
(
q
,
1
). Also if k is odd then A
(
z
)
<
0 for z
<
0 and there are no negative real roots. If k is even then A
(
z
) increases as z decreases through negative values; hence for even k, A
(
z
) has exactly one negative real root. Next, if z
r is a root, by the triangle inequality,(70)
z
r
k
=
q
z
r
k
-
1
+
p
q
k
-
1
≤
q
z
r
k
-
1
+
p
q
k
-
1
.Hence(71)
z
r
k
-
q
z
r
k
-
1
-
p
q
k
-
1
≤
0
.The inequality is strict unless z
r is real and positive (so that both z
r
k and z
r
k
-
1 are real and positive) and we have shown that there is only one real positive root. Hence the real positive root has a larger magnitude than all the other roots.We will call the positive real root the “principal root” and refer to all the other roots as “secondary roots.” We will denote the roots byμ
j
(
p
,
k
), j
=
0
,
…
,
k
-
1, where the principal root is μ
0. Although our the following analysis is for 0
<
p
<
1, it is helpful to note the following limiting cases for p
=
0 and p
=
1.Proposition 24 (limiting cases for roots).
Ifp
=
0, the principal root is μ
0
=
1. If p
=
1, the principal root is μ
0
=
0. All the secondary roots vanish for both p
=
0 and p
=
1. None of the roots vanish if 0
<
p
<
1.Proof.
We have already seen thatA
(
0
)
=
-
p
q
k
-
1; hence obviously z
=
0 is not a root if 0
<
p
<
1. If p
=
1, the auxiliary equation is z
k
=
0; hence all the roots vanish. If p
=
0, the auxiliary equation is z
k
-
1
(
z
-
1
)
=
0, so one root is z
=
1 and the others are all z
=
0. Hence μ
0
=
1 for p
=
0 and μ
0
=
0 for p
=
1, and all the secondary roots vanish for both p
=
0 and p
=
1.Proposition 25 (principal root decreases monotonically with increasingp).
For fixedk
≥
2, let 0
<
p
1
<
p
2
<
1 and denote the respective principal roots by μ
(
p
1
) and μ
(
p
2
). Then μ
(
p
2
)
<
μ
(
p
1
).Proof.
Note that the auxiliary polynomial can be expressed in the following alternative form:(72)
A
p
z
=
z
k
-
q
z
k
-
1
-
p
q
k
-
1
=
z
k
-
1
-
p
z
k
-
1
-
p
q
k
-
1
=
z
k
-
1
z
-
1
+
p
z
k
-
1
-
q
k
-
1
.For brevity write μ
∗
=
μ
0
(
p
1
). Then by definition(73)
0
=
A
p
1
μ
∗
=
μ
∗
k
-
1
μ
∗
-
1
+
p
1
μ
∗
k
-
1
-
q
1
k
-
1
.Then because q
2
<
q
1, it follows that μ
∗
k
-
1
-
q
2
k
-
1
>
μ
∗
k
-
1
-
q
1
k
-
1 and so (because p
2
>
p
1) it also follows that p
2
(
μ
∗
k
-
1
-
q
2
k
-
1
)
>
p
1
(
μ
∗
k
-
1
-
q
1
k
-
1
). Hence(74)
A
p
2
μ
∗
=
μ
∗
k
-
1
μ
∗
-
1
+
p
2
μ
∗
k
-
1
-
q
2
k
-
1
=
A
p
1
μ
∗
︸
=
0
+
p
2
μ
∗
k
-
1
-
q
2
k
-
1
-
p
1
μ
∗
k
-
1
-
q
1
k
-
1
︸
>
0
>
0
.Hence A
p
2
(
μ
0
(
p
1
)
)
>
0. Since we know A
p
2
(
q
2
)
<
0 and A
p
2
(
1
)
>
0 and also q
2
<
q
1
<
μ
0
(
p
1
)
<
1 and the real positive root μ
0
(
p
2
) is unique, it follows that μ
0
(
p
2
)
<
μ
0
(
p
1
).As already stated earlier in this paper, details about the Fuss-Catalan numbers can be found in the text by Graham et al. [2]. See the expressions above, in (4), (5a), and (5b), which will be essential in the following. We require the following lemma for the domain of convergence of the generating functions of the Fuss-Catalan numbers.Lemma 26 (domain of convergence).
The generating function of the Fuss-Catalan numbersB
ν
(
z
) converges for(75)
z
≤
ρ
∗
≡
ν
-
1
ν
-
1
ν
ν
.The proof was derived in our earlier paper [1, Corollary 22 and Proposition 23] and is omitted. The proof was actually derived for B
k
+
1
(
z
) but note (this is important) that k does not have to be an integer; hence we write ν above. It was also proved in [1] that the domain of convergence includes the circle of convergence.Proposition 27 (solutions for roots using Fuss-Catalan numbers).
Definep
∗
=
ρ
∗
/
(
1
+
ρ
∗
). For 0
<
p
≤
p
∗, the principal and secondary roots are given by (76a)
μ
0
p
,
k
=
q
B
k
-
p
/
q
,
(76b)
μ
j
p
,
k
=
q
-
q
B
k
/
k
-
1
e
π
i
2
j
-
1
/
k
-
1
p
/
q
1
/
k
-
1
1
≤
j
≤
k
-
1
.For p
∗
≤
p
≤
1, the principal and secondary roots are given by(77)
μ
j
p
,
k
=
q
1
-
B
1
/
k
-
e
-
2
π
i
j
/
k
q
/
p
1
/
k
0
≤
j
≤
k
-
1
.For p
=
p
∗, either set of solutions may be employed.Proof.
It is simpler to setz
=
q
ζ and solve for ζ. Then the auxiliary equation is(78)
ζ
k
-
ζ
k
-
1
-
p
q
=
0
.We also require ω
k
=
e
2
π
i
/
k and ω
k
-
1
=
e
2
π
i
/
(
k
-
1
). It is simpler to begin with the case p
∗
≤
p
<
1, because all the roots are given by a unified formula. We rewrite (78) in the form ζ
k
(
1
-
1
/
ζ
)
=
p
/
q. Now take the k
t
h root to obtain ζ
(
1
-
1
/
ζ
)
1
/
k
=
ω
k
j
(
p
/
q
)
1
/
k. Next put (
1
-
1
/
ζ
)
1
/
k
=
C
1
/
k, so ζ
=
1
/
(
1
-
C
) and then(79)
C
ζ
-
1
=
-
ω
k
-
j
q
p
1
/
k
C
ζ
1
/
k
.We now employ (6) with ν
=
1
/
k and ζ
=
-
ω
k
-
j
(
q
/
p
)
1
/
k. Then(80)
C
ζ
=
B
1
/
k
-
ω
k
-
j
q
p
1
/
k
. This yields (77). We must establish the set of values of p where the above result is valid. Using (75), the above solution is valid for(81)
q
p
≤
1
/
k
-
1
1
/
k
-
1
1
/
k
1
/
k
k
=
k
k
k
-
1
k
-
1
=
1
ρ
∗
. Hence (
1
-
p
)
/
p
≤
1
/
ρ
∗ or p
∗
≤
p
<
1. This establishes (77).
Next we derive (76a). We rewrite (78) in the form ζ
k
-
1
(
ζ
-
1
)
=
p
/
q. Then put ζ
=
1
/
D
~ and we obtain(82)
D
~
ζ
-
1
=
-
p
q
D
~
ζ
k
.We now employ (6) with ν
=
k and ζ
=
-
(
p
/
q
). Then(83)
D
~
ζ
=
B
k
-
p
q
.The domain of convergence is clearly |
p
/
(
1
-
p
)
|
≤
ρ
∗ or 0
<
p
≤
p
∗. This establishes (76a). We now solve for the remaining (secondary) roots. We again rewrite (78) in the form ζ
k
-
1
(
ζ
-
1
)
=
p
/
q. We now take the (
k
-
1
)
t
h root to obtain(84)
ζ
ζ
-
1
1
/
k
-
1
=
ω
k
-
1
j
p
q
1
/
k
-
1
.Now put (
ζ
-
1
)
1
/
(
k
-
1
)
=
(
-
1
/
D
)
1
/
(
k
-
1
) and then ζ
=
1
-
1
/
D. Hence(85)
1
-
D
-
1
1
D
1
/
k
-
1
=
-
1
-
1
/
k
-
1
ω
k
-
1
j
p
q
1
/
k
-
1
. After some algebra this yields(86)
D
ζ
-
1
=
e
π
i
2
j
-
1
/
k
-
1
p
q
1
/
k
-
1
D
ζ
k
/
k
-
1
.We now employ (6) with ν
=
k
/
(
k
-
1
) and ζ
=
e
π
i
(
2
j
-
1
)
/
(
k
-
1
)
(
p
/
q
)
1
/
(
k
-
1
). Then(87)
D
=
B
k
/
k
-
1
e
π
i
2
j
-
1
/
k
-
1
p
q
1
/
k
-
1
.This yields (76b). Note that this solution yields only k
-
1 distinct roots. If k is odd all the roots are complex. If k is even, then for j
=
k
/
2 we obtain e
π
i
(
2
j
-
1
)
/
(
k
-
1
)
=
e
i
π
=
-
1; hence ζ
=
-
(
p
/
q
)
1
/
(
k
-
1
), which yields the negative real root. For all k, we can index the roots by 1
≤
j
≤
k
-
1. Using (75), the above solution is valid for(88)
p
q
≤
k
/
k
-
1
-
1
k
/
k
-
1
-
1
k
/
k
-
1
k
/
k
-
1
k
-
1
=
k
-
1
k
-
1
k
k
=
ρ
∗
.Hence p
/
(
1
-
p
)
≤
ρ
∗ or 0
<
p
≤
p
∗. This establishes (76b).We now derive an expression for the probability mass function in terms of a sum over the roots.Proposition 28.
The probability mass functionf
(
n
) is given by(89)
f
n
=
p
2
q
k
-
1
∑
j
=
0
k
-
1
1
-
μ
j
μ
j
n
-
k
+
1
μ
j
-
q
2
k
μ
j
-
q
+
q
.Proof.
It is known from the theory of recurrence relations that we may express the p.m.f. in the form(90)
f
n
=
∑
i
=
0
k
-
1
c
i
μ
i
n
-
1
.We must solve for the coefficients c
i. Because there are no repeated roots, c
i do not depend on n. We can derive the solution using a Vandermonde matrix(91)
1
1
⋯
1
μ
0
μ
1
⋯
μ
k
-
1
μ
0
2
μ
1
2
⋯
μ
k
-
1
2
⋮
⋮
μ
0
k
-
1
μ
1
k
-
1
⋯
μ
k
-
1
k
-
1
c
0
c
1
c
2
⋮
c
k
-
1
=
p
2
0
1
2
q
⋮
k
-
1
q
k
-
2
.To solve this we need the Lagrange basis polynomials L
i
(
z
). The Lagrange basis polynomials have degree k
-
1 and have the property L
i
(
μ
j
)
=
δ
i
j for i
,
j
=
0
,
…
,
k
-
1. They can be written as(92)
L
i
z
=
∏
j
≠
i
z
-
μ
j
∏
j
≠
i
μ
i
-
μ
j
.Let us write L
i
(
z
)
=
∑
j
=
0
k
-
1
‍
L
i
j
z
j. Then(93)
c
i
=
∑
j
=
0
k
-
1
L
i
j
f
j
+
1
=
p
2
∑
j
=
0
k
-
1
L
i
j
j
q
j
-
1
=
p
2
L
i
′
q
.Next express the ratio in (92) as L
i
(
z
)
=
N
i
(
z
)
/
D
i. Note that D
i
=
N
i
(
μ
i
). Then(94)
D
i
=
A
′
μ
i
=
k
μ
i
-
q
+
q
μ
i
k
-
2
. Next N
i
(
z
)
=
A
(
z
)
/
(
z
-
μ
i
) so(95)
N
i
z
=
z
k
-
q
z
k
-
1
-
p
q
k
-
1
z
-
μ
i
. Differentiate with respect to z to obtain(96)
N
i
′
z
=
k
z
-
k
-
1
q
z
k
-
2
z
-
μ
i
-
z
k
-
q
z
k
-
1
-
p
q
k
-
1
z
-
μ
i
2
. Then after some algebra we obtain(97)
N
i
′
q
=
k
q
-
k
-
1
q
q
k
-
2
q
-
μ
i
+
p
q
k
-
1
q
-
μ
i
2
=
1
-
μ
i
q
k
-
1
q
-
μ
i
2
. Hence the coefficient c
i is given by(98)
c
i
=
p
2
L
i
′
q
=
1
-
μ
i
μ
i
-
q
2
k
μ
i
-
q
+
q
p
2
q
k
-
1
μ
i
k
-
2
. Then(99)
f
n
=
p
2
q
k
-
1
∑
j
=
0
k
-
1
1
-
μ
j
μ
j
n
-
k
+
1
μ
j
-
q
2
k
μ
j
-
q
+
q
. This establishes (89).The probability generating functionϕ
(
s
) was derived by Koutras [7, Theorem 3.2]:(100)
ϕ
s
=
p
s
2
1
-
q
s
-
p
q
k
-
1
s
k
∑
i
=
0
k
-
2
q
s
i
=
p
s
2
1
-
q
s
-
p
q
k
-
1
s
k
1
-
q
s
k
-
1
1
-
q
s
,
s
≤
1
.Koutras stated that the p.g.f. exists for |
s
|
≤
1. Using our solutions for the roots above, we can state the full domain of convergence. Note that(101)
ϕ
s
=
∑
n
=
0
∞
s
n
f
n
=
∑
j
=
0
k
-
1
c
j
1
-
μ
j
s
. The series in the above sum converge for |
s
|
<
min
⁡
{
1
/
μ
j
}, j
=
0
,
…
,
k
-
1. Since the principal root μ
0 has the largest magnitude of all the roots, the p.g.f. in (100) exists in the domain(102)
s
<
1
μ
0
p
,
k
.This is a larger domain than |
s
|
≤
1 and is clearly the maximal domain where the p.g.f. exists. We can also see this using (100). The denominator of ϕ
(
s
) is A
(
1
/
s
)
=
s
-
k
∏
j
=
0
k
-
1
‍
(
1
-
μ
j
s
). Then ϕ
(
s
) exists in an open neighborhood of s
=
0 until one of the factors in the product vanishes, which also yields |
s
|
<
min
⁡
{
1
/
μ
j
}, j
=
0
,
…
,
k
-
1, thence (102). We have given an explicit expression for the principal root μ
0
(
p
,
k
) in Proposition 27.The probability for the waiting timeP
(
T
>
n
) is clearly given by the sum P
(
T
>
n
)
=
∑
i
=
1
∞
‍
f
(
n
+
i
), so(103)
P
T
>
n
=
p
2
q
k
-
1
∑
j
=
0
k
-
1
μ
j
n
-
k
+
2
μ
j
-
q
2
k
μ
j
-
q
+
q
.Asymptotically, the sum is dominated by the principal root; hence for sufficiently large n we may retain only the principal root(104)
P
T
>
n
≍
p
2
q
k
-
1
μ
0
n
-
k
+
2
μ
0
-
q
2
k
μ
0
-
q
+
q
.Next we treat the case ofr
>
1 nonoverlapping appearances of a pair of successes separated by at most k
-
2 failures. Following Koutras [7], the probability mass function and probability generating function are defined via (also following Koutras we drop the subscript k and write T
r
=
T
r
,
k, etc.) (105a)
f
r
n
=
P
T
r
=
n
,
(105b)
ϕ
r
s
=
∑
n
=
0
∞
s
n
f
r
n
.Following the procedure in the earlier part of our paper, we will derive an expression for the p.m.f. f
r
(
n
) via the p.g.f. ϕ
r
(
s
) and a partial fraction decomposition. Since the enumeration is nonoverlapping and the trials are i.i.d. random variables, the p.g.f. is given by [7, Theorem 4.1] ϕ
r
(
s
)
=
ϕ
(
s
)
r. Then we set z
=
1
/
s and obtain(106)
ψ
r
z
=
ϕ
r
1
z
=
p
2
r
∑
i
=
0
k
-
2
q
i
z
k
-
2
-
i
z
k
-
q
z
k
-
1
-
p
q
k
-
1
r
. This is a rational function of two polynomials in z. The numerator of the term inside the brackets has degree k
-
2 while the denominator has degree k. Note also that the numerator equals (
z
k
-
1
-
q
k
-
1
)
/
(
z
-
q
) and vanishes at z
∗
=
q
e
2
π
i
j
/
(
k
-
1
), j
=
1
,
…
,
k
-
1. However, at such values the denominator equals (
z
∗
-
1
)
q
k
-
1, which is nonzero. Hence the numerator and denominator have no roots in common. Furthermore, the denominator polynomial has no repeated roots. Hence we may employ exactly the same reasoning as was used to derive (49), to obtain(107)
ψ
r
z
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
~
j
m
z
-
μ
j
m
.Here we employ the notation a
~
j
m to avoid confusion with a
j
m in (49). The coefficients a
~
j
m depend on r and k but not on z. As with a
j
m, the coefficients a
~
j
m are given via the standard residues formula(108)
a
~
j
m
=
1
r
-
m
!
d
r
-
m
d
z
r
-
m
z
-
μ
j
r
ψ
r
z
z
=
μ
j
. Then (see (51))(109)
ϕ
r
s
=
ψ
r
1
s
=
∑
j
=
0
k
-
1
∑
m
=
1
r
a
~
j
m
s
m
1
-
μ
j
s
m
. We expand the right hand side using the negative binomial theorem and equate f
r
(
n
) to the coefficient of s
n
(110)
f
r
n
=
∑
j
=
0
k
-
1
∑
m
=
1
r
n
-
1
m
-
1
a
~
j
m
μ
j
n
-
m
.Hence f
r
(
n
) is given by a sum of exactly r
k terms, independently of n. Note that f
r
(
n
)
=
0 for n
<
2
r, because of the nonoverlapping enumeration. An alternative method to derive the probability mass function f
r
(
n
) for r
>
1 was given by Koutras, where the p.m.f. is obtained via a recurrence relation (unnumbered equations after Theorem  4.1 in [7]). Our expression in (110) is essentially the solution of that recurrence.Next consider a fixed number of trialsn. Following Koutras [7], let N
n
,
k denote the number of occurrences of a strand of k (at most) trials containing two successes in the first n outcomes. Then [7, eq. 2.1](111)
P
N
n
,
k
≥
r
=
P
T
r
,
k
≤
n
.Note that trivially P
(
N
n
,
k
≥
r
)
=
1 for r
=
0. For r
≥
1, the right hand side is easily evaluated using (110). Clearly P
(
N
n
,
k
≥
r
)
=
0 and P
(
T
r
,
k
≤
n
)
=
0 for n
<
2
r, because of the nonoverlapping enumeration. Then for r
≥
1 and n
≥
2
r, using (110),(112)
P
N
n
,
k
≥
r
=
∑
i
=
2
r
n
f
r
,
k
i
=
∑
i
=
2
r
n
∑
j
=
0
k
-
1
∑
m
=
1
r
i
-
1
m
-
1
a
~
j
m
μ
j
i
-
m
.We now use (17) and (18) to evaluate the sum over i (note that m
≤
r so all the binomial coefficients are nonzero, also μ
j
≠
0):(113)
S
j
m
≡
∑
i
=
2
r
n
i
-
1
m
-
1
μ
j
i
-
m
=
1
m
-
1
!
μ
j
m
-
1
d
m
-
1
d
x
m
-
1
1
-
μ
j
x
n
1
-
μ
j
x
x
=
1
-
d
m
-
1
d
x
m
-
1
1
-
μ
j
x
2
r
-
1
1
-
μ
j
x
x
=
1
=
1
m
-
1
!
μ
j
m
-
1
d
m
-
1
d
x
m
-
1
μ
j
x
2
r
-
1
-
μ
j
x
n
1
-
μ
j
x
x
=
1
=
1
μ
j
m
-
1
∑
i
=
0
m
-
1
μ
j
2
r
-
1
2
r
-
1
i
-
μ
j
n
n
i
μ
j
m
-
1
-
i
1
-
μ
j
m
-
i
=
∑
i
=
0
m
-
1
μ
j
2
r
-
1
2
r
-
1
i
-
μ
j
n
n
i
1
μ
j
i
1
-
μ
j
m
-
i
. This is a sum of exactly m terms, independently of n. Note also that μ
j
≠
1 for 0
≤
j
≤
k
-
1; hence the right hand side is well defined for all the roots. Substituting in (112) yields(114)
P
N
n
,
k
≥
r
=
∑
j
=
0
k
-
1
∑
m
=
1
r
i
-
1
m
-
1
a
~
j
m
S
j
m
.Because each S
j
m is itself a sum of m terms, the number of summands on the right hand side is O
(
k
r
2
). However, the overall computational complexity is independent of n.



---

*Source: 2071582-2016-01-12.xml*