On runs, bivariate Poisson mixtures and distributions that arise in Bernoulli arrays^{1}

Djilali AIT AOUDIA^{a}, Éric MARCHAND^{b,}^{2}, François PERRON^{c}, Latifa BEN HADJ SLIMENE^{b}

a Université du Québec à Montréal, Département de mathématiques, 201, Ave Président-Kennedy

Montréal, QC, CANADA, H2X 3Y7

b Université de Sherbrooke, Département de mathématiques, Sherbrooke, QC, CANADA, J1K 2R1

c Université de Montréal, Département de mathématiques et de statistique, Montréal, QC, CANADA, H3C 3J7

Summary

Distributional findings are obtained relative to various quantities arising in Bernoulli arrays {X_{k,j}, k ≥ 1, j = 1, …, r+1}, where the rows (X_{k,1}, …, X_{k,r+1}) are independently distributed as Multinomial(1, p_{k,1}, …, p_{k,r+1}) for k ≥ 1 with the homogeneity across the first r columns assumption p_{k,1} = ⋯ = p_{k,r}. The quantities of interest relate to the measure of the number of runs of length 2 and are \underline{S}_{n} = (S_{n,1}, …, S_{n,r}), \underline{S} = lim_{n→∞} \underline{S}_{n}, T_{n} = ∑_{j=1}^{r} S_{n,j}, and T = lim_{n→∞} T_{n}, where S_{n,j} = ∑_{k=1}^{n} X_{k,j}X_{k+1,j}. With various known results applicable to the marginal distributions of the S_{n,j}’s and to their limiting quantities S_{j} = lim_{n→∞} S_{n,j} , we investigate joint distributions in the bivariate (r = 2) case and the distributions of their totals T_{n} and T for r ≥ 2. In the latter case, we derive a key relationship between multivariate problems and univariate (r = 1) problems opening up the path for several derivations and representations such as Poisson mixtures. In the former case, we obtain general expressions for the probability generating functions, the binomial moments and the probability mass functions through conditioning, an analysis of a resulting recursive system of equations, and again by exploiting connections with the univariate problem. More precisely, for cases where p_{k,j} = \frac{1}{b+k} for j = 1, 2 with b ≥ 1, we obtain explicit expressions for the probability generating function of \underline{S}_{n}, n ≥ 1, and \underline{S}, as well as a Poisson mixture representation : \underline{S}|(V_{1} = v_{1}, V_{2} = v_{2}) ∼^{ind.} Poisson(v_{i}) with (V_{1}, V_{2}) ∼ Dirichlet(1, 1, b − 1) which nicely captures both the marginal distributions and the dependence structure. From this, we derive the fact that S_{1}|S_{1} + S_{2} = t is uniformly distributed on {0, 1, …, t} whenever b = 1. We conclude with yet another mixture representation for p_{k,j} = \frac{1}{b+k} for j = 1, 2 with b ≥ 1, where we show that \underline{S}|α ∼ p_{α}, α ∼ Beta(1, b) with p_{α} a bivariate mass function with Poisson(α) marginals given by p_{α}(s_{1}, s_{2}) = \frac{e^{−α}α^{s_{1}+s_{2}}}{(s_{1}+s_{2}+1)!} (s_{1} + s_{2} + 1 − α) .

AMS 2010 subject classifications: 60C05, 60E05, 62E15

Keywords and phrases: Arrays, Bernoulli, Binomial moments, Dirichlet, Multinomial, Poisson distribution, Poisson mixtures, Runs.

1. Introduction

Consider Bernoulli arrays (Ait Aoudia and Marchand, 2010) {X_{k,j}, k ≥ 1, j = 1, …, r + 1}, where the rows \underline{X}_{k} = (X_{k,1}, …, X_{k,r+1}) are independently distributed as Multinomial(1, p_{k,1}, …, p_{k,r+1}) for k ≥ 1 and which arise for instance in sampling with replacement one object at a time from an urn with r + 1 colours. Quantities of interest include the number of runs S_{n,j} = ∑_{k=1}^{n} X_{k,j}X_{k+1,j} of length 2 in the jth column, their total T_{n} = ∑_{j=1}^{r} S_{n,j} among the first r columns, and the limits S_{j} = lim_{n→∞} S_{n,j} and T = lim_{n→∞} T_{n}. A fascinating result is as follows.

1November 21, 2013

2Corresponding author: eric.marchand@usherbrooke.ca

Result A. For the case r = 1 with p_{k,1} = \frac{1}{k}, the distribution of S_{1} is Poisson(1).

This was recognized in the mid 1990’s by Persi Diaconis, as well as Hahlin (1995), and earlier versions are due to Arratia, Barbour, Tavaré (1992), Kolchin (1971), and Goncharov (1944). This elegant result has inspired much interest and lead to various findings relative to the distributions of S_{n,j} and S_{j} for various other configurations of the {p_{k,j}}’s, relationships and implications for Pólya urns, records, matching problems, marked Poisson processes, etc, as witnessed by the work of Chern, Hwang and Yeh (2000), Csörgó and Wu (2000), Holst (2007,2008), Huffer, Sethuraman and Sethuraman (2009), Joffe et al. (2004, 2000), Mori (2001), Sethuraman and Sethuraman (2004), among others. As an exemplar, a lovely generalization of Result A is the Poisson mixture representation

S_{1}|U ∼ P oisson(aU) with U ∼ Beta(a, b) , for p_{k,1} = \frac{a}{a + b + k − 1}, a ≥ 1, b ≥ 0 ,  (1.1)

as obtained by Mori (2001).

With known marginal distributions for the S_{n,j}’s and the S_{j}’s for various configurations of the p_{k,j}’s and a clearly negative pairwise dependence, further questions of interest concern the joint distribution of the vectors \underline{S}_{n} = (S_{n,1}, …, S_{n,r}) and \underline{S} = lim_{n→∞} \underline{S}_{n}. As well, the distribution of the totals T_{n} and T are also of related interest. With such Poisson distributions and Poisson mixtures arising naturally in these univariate (r = 1) situations, it seems natural to investigate multivariate versions of such results. Said otherwise, in what sense and for which configurations of the {p_{k,j}}’s, can analytical extensions of Result A and (1.1) be obtained?

In this paper, we obtain multivariate generalizations for the homogeneous along column case (i.e., first r row components identically distributed) where p_{k,1} = ⋯ = p_{k,r}. As in Joffe et al. (2004) and Ait Aoudia and Marchand (2010), we first obtain by conditioning a recursive system of equations involving the probability generating functions of the S_{n,j}’s in Section 2.1. This permits us, in Section 3, to obtain key result (Theorem 3.1) linking the multivariate r ≥ 2 distributions of T_{n} and T to univariate (r = 1) analogs. This is especially useful given that results like (1.1) are available and, hence, corollaries are derived. As an illustration, for p_{k,j} = \frac{λ}{λr+k−1}, we show that the distribution of T is Poisson(λ) and, for p_{k,j} = \frac{a}{k−1+rb}, we obtain a Poisson mixture representation for the distribution of T with a Beta mixing variable.

In Section 4, we obtain (Theorems 4.2 and 4.3) for the bivariate case with p_{k,j} = \frac{1}{b+k}, b ≥ 1, explicit expressions and representations for the distributions of \underline{S}_{n}, n ≥ 1, and \underline{S}. For instance, we show ( Theorem 4.3 (b)) that the distribution of \underline{S} is the mixture of two independent Poisson(V_{i}), i = 1, 2 with (V_{1}, V_{2}) having a Dirichlet distribution, with some definitions and preliminary results on such mixtures given earlier in Section 2.2. This represents a natural extension of (1.1) for a = 1 as one recovers the univariate result with the Beta marginals of the Dirichlet and the sought-after dependence structure as reflected by the dependence of the Dirichlet components V_{1} and V_{2}. Yet another mixture representation is given in part (d) of Theorem 4.3. But it is quite different as the mixing parameter is univariate and the dependence is reflected otherwise through a bivariate distribution with Poisson and non-independent marginals.

2. Preliminary results, definitions and notations

2.1. Definitions, recurrences for pgf’s and binomial moments

We work with the quantities \underline{X}_{k}, S_{n,j}, S_{j}, T_{n}, T, \underline{S}_{n} and \underline{S} as defined in the Introduction. Ait Aoudia and Marchand (2010) studied the distribution of T_{n} for the bivariate case (r = 2) and the homogeneous (in k) case with p_{k,1} = p, p_{k,2} = 1 − p (and p_{k,3} = 0) for all k. We obtain here representations and relationships for the distributions of the vectors \underline{S}_{n} and \underline{S} as well as those of the totals T_{n} and T for various non-homogeneous in k configurations of the p_{k,j}’s but with identically distributed components of \underline{X}_{k}, in other words

p_{k,1} = ⋯ = p_{k,r} = p_{k} (say).  (2.2)

We pursue by setting S_{0,j} = 0 for all j and by introducing the auxiliary random variables W_{n,1}, …, W_{n,r} where

W_{n,j} := S_{n−1,j} + X_{n,j} , n ≥ 1, j ∈ {1, …, r} .  (2.3)

By conditioning, we obtain the following recurrence for the probability generating functions (pgf) G_{0}, G_{1}, G_{2}, … of the random vectors \underline{S}_{0}, \underline{S}_{1}, \underline{S}_{2}, …, which also involves the array of pgf’s

H_{n,j}(t_{1}, …, t_{r}) = E[t_{j}^{W_{n,j}} ∏_{i≠j} t_{i}^{S_{n−1,i}}] ; n ≥ 1, j ∈ {1, …, r} .

Lemma 2.1. We have for all \underline{t} = (t_{1}, …, t_{r}), n ≥ 1, j ∈ \{1, …, r\},

(1) G_{n}(\underline{t}) = (1 − ∑_{i=1}^{r} p_{n+1,i}) G_{n−1}(\underline{t}) + ∑_{i=1}^{r} p_{n+1,i} H_{n,i}(\underline{t})

(2) H_{n+1,j}(\underline{t}) = (1 − ∑_{i=1}^{r} p_{n+1,i}) G_{n−1}(\underline{t}) + ∑_{i=1}^{r} p_{n+1,i} t_{i}^{1_{\{i=j\}}}H_{n,i}(\underline{t}) ,

with G_{1}(\underline{t}) = 1 + ∑_{j=1}^{r} p_{1,j} p_{2,j} (t_{j} − 1) and H_{1,j}(\underline{t}) = 1 + p_{1,j}(t_{j} − 1).

Proof. We condition on \underline{X}_{n+1}. We obtain with the independence of the \underline{X}_{k}’s and the definitions of the sequences S_{n} and W_{n,j}

L (\underline{S}_{n} | \underline{X}_{n+1} = (0, 0, …, 0)) = L (\underline{S}_{n−1}) ,
L (\underline{S}_{n} | \underline{X}_{n+1} = (1, 0, …, 0)) = L (W_{n,1}, S_{n−1,2}, …, S_{n−1,r}) ,
L (\underline{S}_{n} | \underline{X}_{n+1} = (0, 1, 0, ⋯, 0)) = L (S_{n−1,1}, W_{n,2}, …, S_{n−1,r}) ,
⋮
L (\underline{S}_{n} | \underline{X}_{n+1} = (0, …, 0, 1)) = L (S_{n−1,1}, …, S_{n−1,r−1}, W_{n,r}) .

Result (1) follows since

G_{n}(\underline{t}) = E(∏_{i=1}^{r} t_{i}^{S_{n,i}}) = E (E (∏_{i=1}^{r} t_{i}^{S_{n,i}}|\underline{X}_{n+1})) .

Equations (2) follow along the same lines by conditioning again on \underline{X}_{n+1}. Finally, the initial values for n = 1 follow from definitions.

A rearrangement of the above system of equations is as follows.

Lemma 2.2. We have for all \underline{t} = (t_{1}, …, t_{r}), n ≥ 2, j ∈ \{1, …, r\}:

(1′) G_{n}(\underline{t}) = G_{n−1}(\underline{t}) + ∑_{j=1}^{r} p_{n,j} p_{n+1,j} (t_{j} − 1) H_{n−1,j}(\underline{t})
(2′) H_{n,j}(\underline{t}) = G_{n−1}(\underline{t}) + p_{n,j} (t_{j} − 1) H_{n−1,j}(\underline{t}) .

Proof. Equation ( 2′) follows at once from the difference (2) - (1) in Lemma 2.1, while (1′) follows by rewriting (1) in Lemma 2.1 as G_{n}(\underline{t}) = G_{n−1}(\underline{t}) + ∑_{j=1}^{r} p_{n+1,j}(H_{n,j}(\underline{t}) − G_{n−1}(\underline{t})) and making use of (2′).

As in Holst (2008), we will make use of probability generating function and probability mass function representations of a non-negative integer valued random variable Z which involve the binomial moments E\binom{Z}{k}; k ∈ \{0, 1, 2, …\}; where \binom{z}{r} is taken to be equal to 0 for r > z. Indeed, the Taylor series expansion about 1 of the probability generating function ψ_{Z}, of an non-negative integer-valued random variable Z, having radius greater than 1 can be expressed as

ψ_{Z}(t) = E(t^{Z}) = ∑_{k≥0} E\binom{Z}{k} (t − 1)^{k} , t ∈ [0, 1],  (2.4)

and the probability function of Z can be written as

P (Z = i) = ∑_{k=i}^{∞}(−1)^{k−i}\binom{k}{i}E\binom{Z}{k} .  (2.5)

For the bivariate case with non-negative integer valued components Z_{1} and Z_{2}, analogous relationships are

E(t_{1}^{Z_{1}} t_{2}^{Z_{2}}) = ∑_{k≥0,l≥0} 𝔼\binom{Z_{1}}{k}\binom{Z_{2}}{l}(t_{1} − 1)^{k}(t_{2} − 1)^{l} , (t_{1}, t_{2}) ∈ [0, 1]^{2} ,  (2.6)

and ℙ (Z_{1} = x_{1}, Z_{2} = x_{2}) = ∑_{k≥x_{1},l≥x_{2}}(−1)^{k+l−x_{1}−x_{2}} 𝔼 [\binom{Z_{1}}{k}\binom{Z_{2}}{l}] \binom{k}{x_{1}}\binom{l}{x_{2}} ,  (2.7)

as long as the Taylor series expansion at (t_{1}, t_{2}) = (1, 1) of the probability generating function converges on an open set containing the origin.

2.2. Bivariate Poisson mixtures

We elaborate here on bivariate Poisson mixtures which will arise in the limiting distribution of \underline{S}_{n} in Section 4. We denote (γ)_{k} as an ascending factorial with (γ)_{0} = 1 and (γ)_{k} = ∏_{j=0}^{k−1}(γ + j) for k = 1, 2, . . .. As well, we denote _{1}F_{1}(γ_{1}, γ_{2}; z) as the Gauss hypergeometric function given by ∑_{k≥0} \frac{(γ_{1})_{k}}{(γ_{2})_{k}} \frac{z^{k}}{k!} ; z ∈ ℝ.

Definition 2.1. We will say that the distribution U = (U_{1}, U_{2}) is a bivariate Poisson mixture with mixing parameter F whenever there exists a bivariate random vector V = (V_{1}, V_{2}) on [0, ∞)×[0, ∞) with cdf F such that U_{i}|V ∼^{indep.} Poisson(V_{i}) .

The next lemma brings into play bivariate Dirichlet(a_{1}, a_{2}, a_{3}); a_{i} > 0; densities supported on the simplex S = {(v_{1}, v_{2}) : v_{1} ≥ 0, v_{2} ≥ 0, v_{1} + v_{2} ≤ 1} and given by

\frac{Γ(∑_{i} a_{i})}{∏_{i} Γ(a_{i})}v_{1}^{a_{1}−1}v_{2}^{a_{2}−1}(1 − v_{1} − v_{2})^{a_{3}−1} 𝕀_{S}(v_{1}, v_{2}) ,

as well as Dirichlet(a_{1}, a_{2}, 0) distributions defined as (V_{1}, V_{2}, V_{3}) = (V_{1}, 1−V_{1}, 0) with V_{1} ∼ Beta(a_{1}, a_{2}), and the bivariate hypergeometric or Humbert Φ_{2} function given by

Φ_{2}(a, b, c, x, y) = ∑_{j,k≥0} \frac{(a)_{j}(b)_{k}}{(c)_{j+k}} \frac{x^{j}y^{k}}{j!k!} .

The connection between these two entities, which we exploit in the following lemma, is that the probability generating function of a Dirichlet(a_{1}, a_{2}, a_{3}) random vector V is given by (Lee, 1971)

ψ_{V} (t_{1}, t_{2}) = E(t_{1}^{V_{1}} t_{2}^{V_{2}}) = Φ_{2}(a_{1}, a_{2}, a_{1} + a_{2} + a_{3}, log(t_{1}), log(t_{2})) , for t_{1}, t_{2} > 0 .  (2.8)

This is obtained in a straightforward manner by expanding the exponential terms in the evaluation of the moment generating function and is also valid for cases where a_{3} = 0 by a direct evaluation of E(t_{1}^{V_{1}}t_{2}^{1−V_{1}}).

Lemma 2.3. Consider a bivariate Poisson mixture distribution U with mixing variable V ∼ Dirichlet(a_{1}, a_{2}, a_{3}), and a_{1} > 0, a_{2} > 0, a_{3} ≥ 0. Then,

(a) U has probability generating function Φ_{2}(a_{1}, a_{2}, a_{1} +a_{2} +a_{3}, t_{1} −1, t_{2} −1), and probability mass function given by

P (U_{1} = i, U_{2} = j) = \frac{1}{i!j!} ∑_{k≥0,l≥0} \frac{(−1)^{k+l}}{k! l!} \frac{(a_{1})_{k+i}(a_{2})_{l+j}}{(a_{1} + a_{2} + a_{3})}_{k+l+i+j} .  (2.9)

(b) For cases where a_{1} = a_{2} = 1, the distribution of U_{1} + U_{2} is: (i) a Poisson mixture with U_{1} + U_{2}|W ∼ P oisson(W), W ∼ Beta(2, a_{3}) for a_{3} > 0; and (ii) Poisson(1) for a_{3} = 0.

Proof. (a) With the conditional Poisson representation of U and (2.8), we have E[t_{1}^{U_{1}}t_{2}^{U_{2}}] = E^{V} (E[t_{1}^{U_{1}}t_{2}^{U_{2}}|V]) = E^{V} [e^{V_{1}(t_{1}−1)+V_{2}(t_{2}−1)}] = ψ_{V} (e^{t_{1}−1}, e^{t_{2}−1}) = Φ_{2}(a_{1}, a_{2}, a_{1} + a_{2} + a_{3}, t_{1} − 1, t_{2} − 1).^{3} The probability function is obtained with the help of (2.6) and (2.7).

(b) With the conditional Poisson representation, we have U_{1} + U_{2}|V ∼ Poisson(V_{1} + V_{2}) so that the result is immediate when a_{3} = 0. For a_{3} > 0, the result follows by verifying directly that V_{1} + V_{2} ∼ Beta(2, a_{3}) whenever (V_{1}, V_{2}) ∼ Dirichlet(1, 1, a_{3}).

3. Distribution of the totals T_{n} and T

For studying the distribution of T_{n}, it suffices to consider the probability generating function G_{n}(t_{1}, …, t_{r}) of \underline{S}_{n} evaluated at t_{1} = ⋯ = t_{r}. Simplifications will thus follow when applying Lemma 2.2. Moreover, in the particular cases where we have assumption (2.2), the components S_{n,1}, …, S_{n,r} are equidistributed for a given n, and the same is true for the W_{n,j}’s, j = 1, …, r. As a consequence, the quantities H_{n,j}(t, …, t) will be, for fixed t and n ≥ 1 constant in j, j = 1, …, r. And this also leads to further simplifications when applying Lemma 2.2.

3We note here the general relationship between the probability generating function of the Poisson mixture U with the moment generating function of the mixing variable V, which also illustrates that the Poisson mixtures in Definition 2.1 are identifiable.

Our key finding, which we now proceed to describe, establishes a link between a multivariate problem with r ≥ 2 and an univariate problem where r = 1. This will be especially useful given the known results in the literature applicable to the distribution of T_{n} and T for r = 1.

Theorem 3.1. Let ψ_{n,p_{1},p_{2}, ... ,p_{n+1}}^{r}(·) be the probability generating function of T_{n} with assumption (2.2). Let ψ_{n,rp_{1},rp_{2}, ... ,rp_{n+1}}^{1}(·) be the probability generating function of S_{n}′ = ∑_{k=1}^{n} X_{k}X_{k+1} where X_{k} ∼^{ind.} Ber(rp_{k}), k ≥ 1.^{4} Then, we have for all n ≥ 1, r ≥ 2:

ψ_{n,p_{1},p_{2}, ... ,p_{n+1}}^{r}(u) = ψ_{n,rp_{1},rp_{2}, ... ,rp_{n+1}}^{1}(1 + \frac{u − 1}{r}) ; u ∈ [0, 1] ;  (3.10)
E\binom{T_{n}}{k} = E\binom{S′_{n}}{k} \frac{1}{r^{k}} ; k ∈ \{0, 1, 2, …\};  (3.11)
P (T_{n} = j) = ∑_{k=j}^{n}(−1)^{k−j}\binom{k}{j}E\binom{S′_{n}}{k} \frac{1}{r^{k}} ; j ∈ \{0, 1, …, n\} .  (3.12)

Furthermore, the above applies to T = lim_{n→∞} T_{n} by replacing T_{n} by T, S_{n}′ by S′ = lim_{n→∞} S′_{n}, and taking n → ∞; for u ∈ [−1, 1] in (3.10) and with (3.11) and (3.12) applicable as long as the probability generating function of S′ has radius of convergence about 1 greater than 1/r.

Proof. (3.11) and (3.12) follow from (3.10), (2.4) and (2.5). There remains (3.10). As remarked upon at the outset of this section, we have for fixed t: G_{n}(t, …, t) = ψ_{n,p_{1},p_{2}, ... ,,p_{n+1}}^{r}(t) = ψ_{n}(t) (say, for short), and H_{n,j}(t, …, t) = h_{n}(t) (say) by virtue of assumption (2.2). Rewrite Lemma 2.2’s system of equations as

ψ_{n}(t) = ψ_{n−1}(t) + (rp_{n}) (rp_{n+1}) \frac{t − 1}{r} h_{n−1}(t) ,

h_{n}(t) = ψ_{n−1}(t) + rp_{n} \frac{t − 1}{r} h_{n−1}(t) ,

for n ≥ 2, and with the initial values ψ_{1}(t) = 1 + rp_{1}p_{2}(t − 1) and h_{1}(t) = 1 + p_{1}(t − 1). Now, we set ψ_{n}(t) = a_{n}(\frac{t−1}{r}), h_{n}(t) = b_{n}(\frac{t−1}{r}), and p_{n}′ = rp_{n}, so that the above system of equations becomes

a_{n}(u) = a_{n−1}(u) + p_{n}′ p_{n+1}′ u b_{n−1}(u)
b_{n}(u) = a_{n−1}(u) + p_{n}′ u b_{n−1}(u) ,

for n ≥ 2, u ∈ ℝ. The last two systems of equations tell us that ψ_{n,p_{1},p_{2}, ... ,p_{n+1}}^{r}(ru + 1) = a_{n}(u) = ψ_{n,rp_{1},rp_{2}, ... ,rp_{n+1}}^{1}(u + 1), for all n ≥ 2 and the result follows. Finally, results carry over to T in the same manner by making use of (2.4) and (2.5), and with a radius of convergence greater than 1/r for the pgf of S′ implies a radius of convergence greater than 1 for the pgf of T.

Theorem 3.1 describes a powerful relationship between our r ≥ 2 problem of identifying the distribution of T_{n}, or of T, and a corresponding univariate or r = 1 problem for which there exists already a certain number of results in the literature. We conclude this section with applications of Theorem 3.1.

4Note that we must have rp_{k} ≤ 1 for all k ∈ {1, …, n + 1} given (2.2).

Example 3.1. (Constant case p_{k} = p) For the constant case p_{k} = p, p ≤ \frac{1}{r}, we have p′_{k} = rp and (e.g., Hirano et al, 1991; Holst, 2008)

E\binom{S′_{n}}{k} = (rp)^{k} ∑_{i=1}^{k} \binom{k − 1}{k − i} \binom{n + 1 − k}{i} (rp)^{i} ,

for k ≥ 1, with (3.11) and (3.12) yielding the binomial moments and probability mass function of T_{n}. For instance, we obtain for j = 0, 1, …, n,

P (T_{n} = j) = ∑_{k=j}^{n}(−1)^{k−j}\binom{k}{j}p^{k}\{𝕀_{\{k=0\}} + (∑_{i=1}^{k} \binom{k − 1}{k − i} \binom{n + 1 − k}{i} (rp)^{i})𝕀_{\{k≥1\}}\} .

To conclude, observe that for p = \frac{1}{r}, we have p′_{k} = 1 so that P (S′_{n} = n) = 1 and E(t^{S′_{n}}) = t^{n}. Theorem 3.1 still applies and (3.10) yielding E(u^{T_{n}}) = (1 + \frac{u−1}{r})^{n}, i.e., T_{n} ∼ Bin(n, \frac{1}{r}). This serves more as an illustration as the result here for the distribution of T_{n} follows at once from the representation T_{n} = ∑_{k=1}^{n} I_{\{\underline{X}_{k}=\underline{X}_{k+1}\}} with the indicator variables I_{\{\underline{X}_{k}=\underline{X}_{k+1}\}} independently distributed as Bernoulli(\frac{1}{r}).

Example 3.2. (Case where p_{k} = \frac{a}{r(a+b+k−1)}) In the setup for T_{n} with assumption (2.2), consider cases where p_{k} = \frac{a}{r(a+b+k−1)} with a > 0, b ≥ 0. The analysis for general a, b will cover many interesting particular cases which we will point out below. First, following Theorem 3.1, we consider the univariate sequence S′_{n} with p′_{k} = rp_{k} = \frac{a}{a+b+k−1}. From Holst (2008), we have for k ∈ \{1, …, n\}:

E\binom{S′_{n}}{k} = \frac{a^{k}}{(a + b + n)\underline{k}} ∑_{j=1}^{k} \binom{k − 1}{k − j} \binom{n + 1 − k}{j} \frac{(a)_{j}}{(a + b)_{j}} ,  (3.13)

and E\binom{S′}{k} = \frac{a^{k}}{k!} \frac{(a)_{k}}{(a + b)_{k}} .  (3.14)

Theorem 3.1 along with expressions (2.4) and (2.5) yield immediate expressions for the binomial moments, the probability generating function and the probability mass function of T_{n} through the binomial moment identity (3.11). Similarly, for the distribution of T, we obtain

E\binom{T}{k} = \frac{a^{k}}{r^{k} k!} \frac{(a)_{k}}{(a + b)_{k}} , k = 0, 1, …;
E(u^{T}) = _{1}F_{1}(a, a + b; \frac{a(u − 1)}{r}) ;
P (T = j) = ∑_{k≥j}(−1)^{k−j} \binom{k}{j}\frac{a^{k}}{r^{k} k!} \frac{(a)_{k}}{(a + b)_{k}} .

Moreover, it is straightforward to verify the following representation from the above, which constitutes a multivariate (r > 1) generalization of (1.1).

Corollary 3.1. For cases where p_{k} = \frac{a}{r(a+b+k−1)} with a > 0, b ≥ 0, the distribution of T admits the following Poisson mixture representation:

T |L = l ∼ P oisson(\frac{a l}{r}) , L ∼ Beta(a, b) .  (3.15)

We signal the following further applications.

(I) With b = 0 and a = rλ; λ > 0; , i.e., p_{k} = \frac{λ}{λ r+k−1}, we obtain that T has a Poisson distribution with mean equal to λ. When r = 1, this corresponds to result (1.1) with b = 0.

(II) For the distributions of T_{n} and T with the configuration p_{k} = \frac{a′}{k−1+rb′} with b′ ≥ a′, the results above also apply by taking a = ra′ and b = r(b′ − a′). Corollary 3.1 hence yields the representation T |L = l ∼ Poisson(a′ l), L ∼ Beta(ra′, r(b′ − a′)) , for such p_{k}’s.

4. Distributions of \underline{S}_{n} and \underline{S}: bivariate case with p_{k} = \frac{1}{b+k}

In this section, we obtain the probability generating functions of \underline{S}_{n} , n ≥ 1, and \underline{S} in the bivariate case (r = 2) with p_{k} = \frac{1}{b+k}, b ≥ 1. Moreover, by taking n → ∞ and by making use of a representation (Lemma 4.4) for the pgf of \underline{S} in terms of the marginal binomial moments, we arrive at explicit forms for the probability generating and mass functions of \underline{S}, as well as mixture representations (Theorem 4.3). This is achieved by first solving the recurrence given in Lemma 2.2 yielding explicit expressions for the probability generating functions G_{n}, H_{n+1,1} and H_{n+1,2} for n ≥ 1 (Theorem 4.2).

Theorem 4.2. Under assumption (2.2) with r = 2 and p_{k} = \frac{1}{b+k}, the probability generating functions G_{n}(\underline{t}) = E[t_{1}^{S_{n,1}} t_{2}^{S_{n,2}}], H_{n,1}(\underline{t}) = E[t_{1}^{W_{n+1,1}} t_{2}^{S_{n,2}}], and H_{n,2}(\underline{t}) = E[t_{1}^{S_{n,1}} t_{2}^{W_{n+1,2}}] are given by

G_{n}(\underline{t}) = \frac{b}{s_{1} − s_{2}} ∑_{k≥1}[𝕀(k ≤ n + 1) − \frac{s_{1} + s_{2}}{n + 1 + b}𝕀(k ≤ n) + \frac{s_{1}s_{2}}{(b + n)(b + n + 1)}𝕀(k ≤ n − 1)]\frac{s_{1}^{k} − s_{2}^{k}}{(b)_{k}}

H_{n+1 j}(\underline{t}) = \frac{s_{j}^{n+1}}{(1 + b)_{n+1}} + \frac{b}{s_{1} − s_{2}} ∑_{k≥1}[𝕀(k ≤ n + 1) − \frac{s_{3−j}}{n + 1 + b}𝕀(k ≤ n)]\frac{s_{1}^{k} − s_{2}^{k}}{(b)_{k}} ,

for s_{1} ≠ s_{2}, j = 1, 2, n ≥ 1, and s_{i} = t_{i} − 1.

Proof. We proceed by induction. A direct evaluation yields G_{1}(t_{1}, t_{2}) = 1 + \frac{1}{(1+b)_{2}} (s_{1} + s_{2}) and H_{2,j}(t_{1}, t_{2}) = 1 + \frac{1}{(1+b)}s_{j} + \frac{1}{(1+b)_{2}} s_{j}^{2} + \frac{1}{(1+b)_{2}} s_{3−j}, j = 1, 2, which matches the given formulas for n = 1. Now suppose the above formulas hold for n = 1, …, m. A slight reorganization of Lemma 2.2 tells us that

G_{n+1}(\underline{t}) = p_{n+2,3} G_{n}(t) + ∑_{j=1}^{2} p_{n+2,j} H_{n+1,j}(\underline{t})
H_{n+1 j}(\underline{t}) = G_{n}(\underline{t}) + p_{n+1}s_{j}H_{n,j}(\underline{t}), j = 1, 2,

for n ≥ 1, recalling that by definition p_{n+2,3} = 1 − p_{n+2,1} − p_{n+2,2} = 1 − \frac{2}{b+n+2}. With the following decomposition, which is verified directly,

\frac{s_{j}^{m+1}}{(b + 1)_{m+2}} = \frac{b}{s_{j} − s_{3−j}} [\frac{s_{j}^{m+2}}{(b)_{m+2}} − \frac{s_{1} + s_{2}}{m + b + 2} \frac{s_{j}^{m+1}}{(b)_{m+1}} + \frac{s_{1}s_{2}}{(m + b + 1)(m + b + 2)} \frac{s_{j}^{m}}{(b)_{m}}] ,

a calculation of p_{m+2,3}G_{m} + ∑_{j=1}^{2} p_{m+2,j}H_{m+1,j} yields the desired expression for G_{m+1}. Similarly, an evaluation of G_{m+1} + p_{m+2,j}s_{j}H_{m+1,j} leads to the desired expression for H_{m+2}.

Lemma 4.4. Suppose ψ is the probability generating function of a random vector (Z_{1}, Z_{2}) on ℕ^{2} satisfying the equation

ψ(t_{1}, t_{2})(t_{1} − t_{2}) = (t_{1} − 1) ψ(t_{1}, 1) − (t_{2} − 1) ψ(1, t_{2}) ,  (4.16)

(t_{1}, t_{2}) ∈ [−1, 1]^{2}, and that the Taylor series development at (1, 1) of ψ converges on an open set containing the origin. Then, ψ is given by

ψ(t_{1}, t_{2}) = ∑_{k,l≥0} E\binom{Z_{1}}{k + l} (t_{1} − 1)^{k} (t_{2} − 1)^{l} .  (4.17)

Proof. With the series representation (2.6) and the uniqueness of the coefficients, it suffices to show that

E\binom{Z_{1}}{k} \binom{Z_{2}}{l} = E\binom{Z_{1}}{k + l} , for all k, l ≥ 0 .  (4.18)

Now, equation (4.16) implies, for all (t_{1}, t_{2}), with c_{k,l} = E\binom{Z_{1}}{k} \binom{Z_{2}}{l} and s_{i} = t_{i} − 1,

∑_{k,l≥0} c_{k,l} s_{1}^{k+1} s_{2}^{l} − ∑_{k,l≥0} c_{k,l} s_{1}^{k} s_{2}^{l+1} = ∑_{k≥0} c_{k,0}s_{1}^{k+1} − ∑_{k≥0} c_{0,l}s_{2}^{l+1}
⟹ ∑_{k,l≥1} c_{k−1,l} s_{1}^{k} s_{2}^{l} = ∑_{k,l≥1} c_{k,l−1} s_{1}^{k} s_{2}^{l} .

But the above is equivalent to c_{k−1,l} = c_{k,l−1} for all k, l ≥ 1, which implies c_{0,k+l−1} = ⋯ = c_{k−1,l} = c_{k,l−1} = ⋯ = c_{k+l−1,0} for all k, l ≥ 1, which is (4.18).

The key result that follows concerns the limiting distribution of \underline{S}_{n} for the homogeneous bivariate case p_{k,1} = p_{k,2} = \frac{1}{b+k}. A first explicit form (equation 4.23) for the probability generating function is easily derived from Theorem 4.2. A second explicit form is obtained via Lemma 4.4 by verifying directly that the probability generating function of \underline{S} verifies (4.16). This permits to write down the probability generating function of \underline{S} in terms of the binomial moments of S_{1}, that either can be derived from our expressions or taken from known results in the univariate case.

Theorem 4.3. Under assumption (2.2) with r = 2 and with p_{k} = \frac{1}{b+k}, b ≥ 1,

(a) The probability generating and probability mass functions of \underline{S} are given by

G(t_{1}, t_{2}) = Φ_{2}(1, 1, b + 1, t_{1} − 1, t_{2} − 1) ,  (4.19)
and  ℙ (S_{1} = x_{1}, S_{2} = x_{2}) = \frac{1}{x_{1}! x_{2}!} ∑_{k≥0,l≥0} \frac{(−1)^{k+l}}{(b + 1)_{k+l+x_{1}+x_{2}}} (k + 1)_{x_{1}} (l + 1)_{x_{2}} ; (4.20)

(b) The distribution of \underline{S} is a bivariate Poisson mixture, as in Definition 2.1 and Lemma 2.3, with V ∼ Dirichlet (a_{1} = 1, a_{2} = 1, a_{3} = b − 1);

(c) For b = 1 and t ∈ ℕ, the distribution of S_{1}|S_{1} + S_{2} = t is uniform on {0, 1, …, t};

(d) The distribution of \underline{S} admits the representation

\underline{S}|α ∼ p_{α} , α ∼ Beta(1, b) ,  (4.21)

with p_{α} the bivariate probability mass function on ℕ^{2} given by

p_{α}(s_{1}, s_{2}) = \frac{e^{−α}α^{s_{1}+s_{2}}}{(s_{1} + s_{2} + 1)!} (s_{1} + s_{2} + 1 − α) ; α ∈ (0, 1] .  (4.22)

Proof. (a) The probability function in (4.20) follows from (4.19) and part (a) of Lemma 2.3. For establishing (4.19), start with Theorem 4.2, where we obtain (for t_{1} ≠ t_{2}):

G(t_{1}, t_{2}) = E(t_{1}^{S_{1}} t_{2}^{S_{2}}) = lim_{n→∞} G_{n}(t_{1}, t_{2}) = \frac{b}{t_{1} − t_{2}} (_{1}F_{1}(1, b, t_{1} − 1) −_{1}F_{1}(1, b, t_{2} − 1)) . (4.23)

From this expression, or alternatively from Holst (2008) and (2.4), we obtain

(t_{1} − 1)G(t_{1}, 1) = b _{1}F_{1}(1, b, t_{1} − 1) and (t_{2} − 1)G(1, t_{2}) = b _{1}F_{1}(1, b, t_{2} − 1) .

Now, observe that ψ ≡ G satisfies (4.16), so that (4.17) applies with E \binom{S_{1}}{k+l} = \frac{1}{(b+1)_{k+l}}; again derived from Holst (2008) or (4.23); yielding G(t_{1}, t_{2}) = ∑_{k,l≥0} \frac{1}{(b+1)_{k+l}} (t_{1} −1)^{k}(t_{2} −1)^{l} = Φ_{2}(1, 1, b+1, t_{1} − 1, t_{2} − 1) .

(b) Part (a) paired with Lemma 2.3 imply the given representation.

(c) Set t ∈ ℕ. It suffices to show that P (S_{1} = x, S_{2} = t − x) is independent of x ∈ {0, 1, …, t}. We have from the Poisson mixture representation in (b) with V ∼ Dirichlet (1, 1, 0) : P (S_{1} = x, S_{2} = t − x) = ∫_{0}^{1} \frac{e^{−v_{1}} v_{1}^{x}}{x!} \frac{e^{−(1−v_{1})} (1−v_{1})^{t−x}}{(t−x)!} dv_{1} = \frac{e^{−1}}{(t+1)!}, which is indeed independent of x. ^{5}

(d) Given that the probability generating function of \underline{S} is necessarily expressible as in (2.6), it will suffice given part (a) to show that

𝔼\binom{S_{1}}{k}\binom{S_{2}}{l} = \frac{1}{(b + 1)_{k+l}} ,  (4.24)

under representation (4.21)-(4.22). In turn, it will suffice to show that the mixed binomial moments of (S_{1}, S_{2}) under probability function p_{α} are given by

𝔼 [\binom{S_{1}}{k}\binom{S_{2}}{l}|α] = \frac{α^{k+l}}{(k + l)!} , for non negative integers k, l,  (4.25)

since this would imply along with representation (4.21) that 𝔼 [\binom{S_{1}}{k}\binom{S_{2}}{l}] = 𝔼(\frac{α^{k+l}}{(k+l)!}) = \frac{1}{(b+1)_{k+l}} , which is (4.24). Finally, manipulations lead to (4.25) as follows:

𝔼 [\binom{S_{1}}{k}\binom{S_{2}}{l}|α] = ∑_{s_{1}≥0,s_{2}≥0} \binom{s_{1} + k}{k} \binom{s_{2} + l}{l} p_{α}(s_{1} + k, s_{2} + l)

= ∑_{y≥0} \frac{e^{−α} α^{y+k+l}}{(y + k + l + 1)!}(y + l + k + 1 − α) ∑_{x=0}^{y} \binom{x + k}{k} \binom{y − x + l}{l}

= ∑_{y≥0} \frac{e^{−α} α^{y+k+l}}{(y + k + l + 1)!}(y + l + k + 1 − α) \binom{y + l + k + 1}{y}

= \frac{e^{−α} α^{k+l}}{(k + l + 1)!} ∑_{y≥0} \frac{α^{y}}{y!} (y + k + l + 1 − α) = \frac{α^{k+l}}{(k + l)!} .

The bivariate Poisson mixture representation of \underline{S} extends in a most interesting way the known marginal distribution representation for S_{1} and S_{2} (i.e., 1.1) expressible as a Beta mixture of Poisson distributions. Here S_{1} and S_{2} are clearly dependent but the representation tells us that they are conditionally independent and the dependence is reflected through the dependence of the mixing components of the Dirichlet. Similarly, we obtain from part (b) of the Theorem and Lemma 2.3 the mixture representation

5Summing this for all x yields a Poisson(1) distribution for T which is a particular case of Corollary 3.1 (application I).

T |W = w ∼ Poisson(w) , W ∼ Beta(2, b − 1) ,

with this, alternatively, following also from Corollary 3.1. In contrast to the Dirichlet mixing (when b > 1), the dependence in representation (d) is reflected through the conditional distributions of (S_{1}, S_{2}), and the mixing variable α is univariate. Furthermore, it is readily verified that the conditional marginal distributions of S_{i}|α are Poisson(α), which is consistent with the univariate result in (1.1). We conclude with some observations on the probability functions p_{α} in (4.22).

Remark 4.1. The bivariate probability function in (4.22) has a simple enough form so that is possibly has arisen in previous work, but we cannot identify such a source. Anyhow, it is most interesting that it arises here in a natural way from the Bernoulli array in the representation of \underline{S} for r = 2 and the configuration p_{k} = \frac{1}{b+k}, b ≥ 1. The probability generating function, using the binomial moments at the end of the proof of Theorem 4.3 and (2.6), may be written as

ψ_{α}(t_{1}, t_{2}) = E_{α}(t_{1}^{S_{1}} t_{2}^{S_{2}}) = ∑_{k,l≥0} α^{k+l} \frac{(t_{1} − 1)^{k} (t_{2} − 1)^{l}}{(k + l)!} .

As seen above, the marginals are Poisson(α) distributed. These distributions, as expanded on by Ait Aoudia and Marchand (2013) are governed by p_{α} possess at least two other interesting properties:

(i) the distribution of S_{1} + S_{2} (conditional on α) is given by the convolution of a Poisson(α) with a Bernoulli(α);

(ii) the correlation coefficient between S_{1} and S_{2} (conditional on α) is equal to −\frac{α}{2}.

Concluding Remarks

The main findings in this paper concern the numbers of runs of length 2 in Bernoulli arrays with independently distributed multinomial distributed rows and identically distributed row components. Exploiting the structure of the problem through a recurrence involving probability generating functions and building on known marginal distribution results in the literature, we have explored the distributions of totals across columns and joint distributions of column sums. Elegant representations have been obtained: (i) through Section 3’s correspondence between multivariate and univariate problems to describe the distribution of a total, and (ii) with Section 4’s bivariate distributions, where we have for instance obtained in a specific situation a bivariate Poisson mixture with a Dirichlet mixing parameter. Many other open and interesting problems can be envisioned. These include an analysis of the distributions of \underline{S}_{n} and \underline{S} for r > 2, closed form distributional results in the absence of assumption (2.2), and an extended framework for probability models other than multinomial.

Acknowledgments

We are indebted and thankful to an anonymous reviewer for constructive comments and for identifying a mistake in an earlier version of the manuscript. Éric Marchand’s and François Perron’s gratefully acknowledge the support for research provided by NSERC of Canada.

References

[1] Ait Aoudia, D. and Marchand É. (2013). On a simple construction of bivariate probability functions with fixed marginals. Unpublished manuscript.

[2] Ait Aoudia, D. and Marchand É. (2010). On the number of runs for Bernoulli arrays. Journal of Applied Probability, 47, 367-377.

[3] Arratia, R., Barbour, A.D., and Tavaré, S. (1992). Poisson process approximations for the Ewens sampling formula. Annals of Applied Probability, 2, 519-535.

[4] Chern, H.-H., Hwang, H.-K., and Yeh, Y.-N. (2000). Distribution of the number of consecutive records. Random Structures Algorithms, 17, 169-196.

[5] Csörgó, M. and Wu, B.W. (2000). On sums of overlapping products of independent Bernoulli random variables. Ukran’ski Matematicheski Zhurnal, 52, 1304-1309.

[6] Goncharov, V. (1944). On the field of combinatory analysis. Soviet Math. Izv., Ser. Math., 8, 3-48. In Russian.

[7] Hahlin, L.O. (1995). Double Records. Research Report # 12, Department of Mathematics, Uppsala University.

[8] Hirano, K., Aki, S., Kashiwagi, N., and Kuboki, H. (1991). On Ling’s binomial and negative binomial distributions of order k. Statistics & Probability Letters, 11, 503-509.

[9] Holst, L. (2008). The number of two-consecutive successes in a Hoppe-Polyá urn. Journal of Applied Probability, 45, 901-906.

[10] Holst, L. (2007). Counts of failure strings in certain Bernoulli sequences. Journal of Applied Probability, 44, 824-830.

[11] Huffer, W. F., Sethuraman, J. and Sethuraman, S. (2009). A study of counts of Bernoulli strings via conditional Poisson processes. Proceedings of the American Mathematical Society, 137, 2125-2134.

[12] Joffe, A., Marchand É., Perron, F., and Popadiuk, P. (2004). On sums of products of Bernoulli variables and random permutations. Journal of Theoretical Probability, 17, 285-292.

[13] Joffe, A., Marchand É., Perron, F., and Popadiuk, P. (2000). On sums of products of Bernoulli variables and random permutations. Research Report # 2686, Centre de Recherches Mathématiques, Montréal, Canada.

[14] Kolchin, V.F. (1971). A problem of the allocation of particles in cells and cycles of random permutations. Theory of Probability and its Applications, 16, 74-90.

[15] Lee, P.A. (1971). A diagonal expansion for the 2-variate Dirichlet probability density function. SIAM Journal on Applied Mathematics, 21, 155-165.

[16] Mori, T.F. (2001). On the distribution of sums of overlapping products. Acta Scientiarum Mathematica (Szeged), 67, 833-841.

[17] Sethuraman, J. and Sethuraman, S. (2004). On counts of Bernoulli strings and connections to rank orders and random permutations. A Festschrift for Herman Rubin. IMS Lecture Note Monograph Series, 45, Institute of Mathematical Statistics, pp. 140-152.