On the number of runs for Bernoulli arrays

Djilali Ait Aoudia Éric Marchand ^{1}

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

Abstract

We introduce and motivate the study of (n+1)×r arrays X with Bernoulli entries X_{k,j} and independently distributed rows. We study the distribution of S_{n} = ∑_{j=1}^{r} ∑_{k=1}^{n} X_{k,j}X_{k+1,j} representing the number of consecutive pairs of successes (or runs of length 2) when reading the array down the columns and across the rows. With the case r = 1 having been studied by several authors, and permitting some initial inferences for the general case r > 1, we pursue by obtaining various distributional properties and representations of S_{n} for the case r = 2, and with a more explicit analysis for the case of multinomial and identically distributed rows. Applications are also given in cases where the array the array X arises from a Pólya sampling scheme. AMS 2000 subject classifications: 60C05, 60E05, 60K99. Keywords and phrases: Bernoulli; multinomial; Pólya urn; probability generating function, runs.

1. Introduction

For an array X of Bernoulli random variables X_{k,j}; k ⩾ 1 and j = 1, …, r; such that the random vectors \underline{X}_{k} = (X_{k,1}, …, X_{k,r})′ are independent, we study the distributional properties of S_{n} = ∑_{k=1}^{n} \underline{X}k^{′}\underline{X}_{k+1}, n ≥ 1, which counts the number of pairs of consecutive Bernoulli successes (or runs of length 2) in the array X reading down the lines and across the columns. Alternatively, we may write

1Corresponding author: eric.marchand@usherbrooke.ca

S_{n} = ∑_{j=1}^{r} ∑_{k=1}^{n} X_{k,j}X_{k+1,j} = ∑_{j=1}^{r} Z_{j}  (1)

with

Z_{j} = ∑_{k=1}^{n} X_{k,j}X_{k+1,j}.  (2)

As an illustration, the array

X = ( \begin{matrix}1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \end{matrix} )

where n = 3, r = 5, yields Z_{1} = 1, Z_{2} = 0, Z_{3} = 0, Z_{4} = 2, Z_{5} = 1, and S_{3} = ∑_{j=1}^{5} Z_{j} = 4.

Example 1 A class of applications where S_{n} arises consists of n + 1 draws with replacement from an urn with r columns of cardinalities α_{1}, ⋯, α_{r} (α_{i} > 0), where we define

X_{k,j} = I_{{kth draw is of type j}},  1 ≤ k ≤ n, 1 ≤ j ≤ r.  (3)

We thus have \underline{X}_{k} ∼ Multinomial(1, θ_{k,1}, …, θ_{k,r}), with θ_{k,j} = α_{j}/ ∑_{j=1}^{r} α_{j}, and S_{n} counting the number of pairs of consecutive draws with matching colours. Observe that the independence of the vectors \underline{X}_{k} is a consequence of the independent draws with replacement. In this illustration, the random vectors \underline{X}_{k} are also identically distributed but this need not be the case as we can envisage non-identical draws such as single draws from several distinct non-homogeneous urns.

Remark 1 Our setup does not directly encompass Pólya urn sampling schemes where the rows of X are dependent. However, by de Finetti’s representation theorem, the study of Example 1’s class of applications, along with the results of this paper, do indeed lead to implications for Pólya urns (for r = 2), as expanded upon in Section 3.

More generally, the spectrum of distribution of S_{n} is governed, of course, by the possible distributions for the random matrix X, subject to the rows \underline{X}_{1}, …, \underline{X}_{n+1}, being independent, but not necessarily identically distributed. The univariate column case (i.e., r = 1 or as pertaining to the marginal distribution of Z_{j}) has generated much recent interest, analysis, and interpretation, as witnessed by the contributions of Holst (2008, 2007), Joffe et al., (2004), Mori (2001), Huffer, Sethuraman and Sethuraman (2009), Sethuraman and Sethuraman (2004), among others. In particular, for r = 1 and P (X_{k,1} = 1) = a/(a + b + k − 1) with a > 0, b ≥ 0, the limiting distribution of S_{n} admits the representation:

S|L ∼ P oisson(aL) with L ∼ Beta(a, b),  (4)

(Holst, 2008; Joffe et al., 2004, a = 1; Mori 2001, b = 0), while the constant case P (X_{k,1} = 1) = p relates to type II Binomial distributions (see Joffe et al., 2004 and the references therein). Even though the marginal distributions of Z_{1}, …, Z_{r} are known in the above cases, the difficulty of studying the distribution of S_{n}, as given in (1), is of course that the columns of X, and consequently Z_{1}, …, Z_{r}, are not assumed to be independent. Nevertheless, it is worthwhile first summarizing results that may be inferred in cases where the columns are either independent, or in perfect dependence.

Example 2 (independent columns and P (X_{k,j} = 1) = a_{j}/(a_{j} + b_{j} + k − 1)) Whenever the columns are independent, representation (1) implies that an efficient analysis of S_{n} passes through the convolution of r independent one dimensional problems. For instance, whenever the X_{k,j}’s, k ≥ 1, j = 1, …, r, are independent, and P (X_{k,j} = 1) = a_{j}/(a_{j} + b_{j} + k − 1), the distribution of S = lim_{n→∞} S_{n} admits the following representation:

S|Y ∼ P oisson(Y)  with  Y = ∑_{j=1}^{r} a_{j}L_{j},

and L_{1}, ⋯, L_{r} independent random variables such that L_{j} ∼ Beta(a_{j}, b_{j}). This may be established by exploiting representations (1) and (4), the independence of the Z_{j}’s, so that for all t ∈ ℜ

E[t^{S}] = E[t^{∑_{j=1}^{n} Z_{j}}] = ∏_{j=1}^{r} E[t^{Z_{j}}]
= ∏_{j=1}^{r} E [E[t^{Z_{j}}]|L_{j}] = ∏_{j=1}^{r} E[e^{a_{j}L_{j}(t−1)}]
= E[e^{∑_{j=1}^{r} a_{j}L_{j}(t−1)}] = E[e^{Y (t−1)}] .

Example 3 Whenever the X_{k,j}’s, j = 1, ⋯, r, are equal with probability one (i.e., P (\underline{X}_{k} = (1, ⋯, 1)) + P (\underline{X}_{k} = (0, ⋯, 0)) = 1) for all k ∈ \{1, ⋯, n + 1\}), it follows that P (Z_{1} = ⋯ = Z_{r}) = 1 and hence L (S_{n}) = L (rZ_{1}). In such cases, univariate results, such as (4) apply directly.

The findings that follow in this paper relate to the bidimensional case (r = 2). In section 2, we give a general recurrence (Lemma 1) for the probability generating function (pgf) of S_{n}. We then obtain more explicit representations (Corollary 1) for the particular case of multinomial rows (as in Example 1), which will lead to an explicit expression (Theorem 1) for the probability mass function of S_{n} in the identically distributed case. The family of distributions thus obtained is quite interesting on its own and may be viewed as one that contains (for fixed n) the Binomial(n, 1/2) distribution. These distributions also admit a large n normal approximation (Remark 5). Via de Finetti’s representation theorem, the last results of Section 2 permit us to obtain useful representations for the distribution of S_{n} when arising from a Pólya urn sampling scheme. This development is presented in Section 3.

2. The bidimensional case (r = 2)

We begin by analyzing the general bidimensional case (r = 2) where

f_{i,j}^{(k)} = P (\underline{X}_{k} = (i, j)) , 1 ≤ k ≤ n + 1, i, j = 0, 1 .

Define S_{n} as in (1) above with S_{0} = 0 in other words

S_{n} = S_{n−1} + X_{n,1}X_{n+1,1} + X_{n,2}X_{n+1,2} ; n ≥ 1.  (5)

To derive a useful expression for the probability generating function (pgf) φ_{S_{n}}(t)(= E[t^{S_{n}}]) of S_{n}, we introduce the auxiliary random variables W_{l,n}; l = 1, 2, 3; defined for n ≥ 0 as

W_{1,n} := S_{n} + X_{n+1,1} + X_{n+1,2} ,  W_{2,n} := S_{n} + X_{n+1,1} ,  W_{3,n} := S_{n} + X_{n+1,2} . (6)

We denote their pgf’s as φ_{W_{l,n}}, and we also write

\underline{φ}_{n}(·) = (φ_{S_{n}}(·), φ_{W_{1,n}}(·), φ_{W_{2,n}}(·), φ_{W_{3,n}}(·))′; n ≥ 0.

The next result establishes an explicit recurrence and expression for \underline{φ}_{n}(·) , n ≥ 1 .

Lemma 1 We have for n ≥ 1, t ≥ 0:

\underline{φ}_{n}(t) = M_{n+1} \underline{φ}_{n−1}(t)  (7)

and

\underline{φ}_{n}(t) = M_{n+1} ⋯ M_{2}\underline{φ}_{0}(t) = M_{n+1} ⋯ M_{1}1,  (8)

with

M_{n} = ( \begin{matrix}f_{0,0}^{(n)} & f_{1,1}^{(n)} & f_{1,0}^{(n)} & f_{0,1}^{(n)} \\ f_{0,0}^{(n)} & t^{2}f_{1,1}^{(n)} & tf_{1,0}^{(n)} & tf_{0,1}^{(n)} \\ f_{0,0}^{(n)} & tf_{1,1}^{(n)} & tf_{1,0}^{(n)} & f_{0,1}^{(n)} \\ f_{0,0}^{(n)} & tf_{1,1}^{(n)} & f_{1,0}^{(n)} & tf_{0,1}^{(n)} \end{matrix} )

and 1 = (1, 1, 1, 1)′.

Proof. We condition on \underline{X}_{n+1}. For S_{n}, n ≥ 1, we obtain from (5) and (6) and the independence of the \underline{X}_{k}’s:

L (S_{n} | \underline{X}_{n+1} = (1, 1)) = L (S_{n−1} + X_{n,1} + X_{n,2}) = L (W_{1,n−1}) ,

L (S_{n} | \underline{X}_{n+1} = (1, 0)) = L (S_{n−1} + X_{n,1}) = L (W_{2,n−1}) ,
L (S_{n} | \underline{X}_{n+1} = (0, 1)) = L (S_{n−1} + X_{n,2}) = L (W_{3,n−1}) ,
and L (S_{n} | \underline{X}_{n+1} = (0, 0)) = L (S_{n−1}) .

Since

φ_{S_{n}}(t) = E [E [t^{S_{n}}|\underline{X}_{n+1}]] ,

the above translates to

φ_{S_{n}}(t) = (f_{0,0}^{(n+1)}, f_{1,1}^{(n+1)}, f_{1,0}^{(n+1)}, f_{0,1}^{(n+1)}) \underline{φ}_{n−1}(t),

(i.e., the scalar product of the first row of M_{n+1} and \underline{φ}_{n−1}(t)). The rest of the system is obtained along the same lines. Finally (8) follows from (7), with \underline{φ}_{0}(t) derived directly as M_{1}1 from the definitions of W_{l,0} in (6), and since S_{0} = 0. □ We now pursue with further analysis for multinomial distributed rows \underline{X}_{k}, where, for all k ∈ {1, …, n + 1},

f_{1,0}^{(k)} = 1 − f_{0,1}^{(k)} = p_{k} (say).  (9)

This corresponds to non-homogeneous (or non-identically distributed) draws in Example 1. We do not assume for the time being that the \underline{X}_{k}’s are identically distributed, but the more explicit results that follow later (e.g., part (b) of Corollary 1) do apply to cases where

f_{1,0}^{(k)} = 1 − f_{0,1}^{(k)} = p,  (10)

for all k ∈ {1, …, n + 1}. We require the following result.

Lemma 2 If A is a 2 × 2 matrix with distinct eigenvalues λ_{1} and λ_{2} and I_{2} is the 2 × 2 identity matrix, then for all n ≥ 2

A^{n} = (\frac{λ_{2}^{n} − λ_{1}^{n}}{λ_{2} − λ_{1}} ) A − λ_{1}λ_{2} (\frac{λ_{2}^{n−1} − λ_{1}^{n−1}}{λ_{2} − λ_{1}} ) I_{2} .  (11)

Proof. See for instance Ardakov (1997). The next result consists of specializations of Lemma 1 in cases where (9) or (10) hold. In such cases with the two first columns of M_{n} becoming 0 vectors, we obtain a useful and more explicit representation for the pgf of S_{n}.

Corollary 1 (a) Under assumption (9), we have for all n ≥ 1, t ≥ 0:

φ_{S_{n}}(t) = p_{n+1}φ_{W_{2,n−1}}(t) + (1 − p_{n+1})φ_{W_{3,n−1}}(t)  (12)

with

[ \begin{matrix}φ_{W_{2,n}}(t) \\ φ_{W_{3,n}}(t) \end{matrix} ] = [ \begin{matrix}tp_{n+1} & 1 − p_{n+1} \\ p_{n+1} & t(1 − p_{n+1}) \end{matrix} ] [ \begin{matrix}φ_{W_{2,n−1}}(t) \\ φ_{W_{3,n−1}}(t) \end{matrix} ] ,  (13)

and (φ_{W_{2,0}}(t), φ_{W_{3,0}}(t))′ = (p_{1}t + (1 − p_{1}), p_{1} + (1 − p_{1})t)′.

(b) For all p ∈ [0, 1] , n ≥ 1, t ≥ 0, set

λ_{1} = (t + \sqrt{t^{2} − 4p(1 − p)(t^{2} − 1)})/2, λ_{2} = t − λ_{1}, α_{n} = \frac{λ_{1}^{n} − λ_{2}^{n}}{λ_{1} − λ_{2}} .

Under assumption (10), we have for all n ≥ 1, t ≥ 0:

φ_{S_{n}}(t) = α_{n} [2p(1 − p) + t(1 − 2p(1 − p))] + α_{n−1}p(1 − p)(1 − t^{2}).  (14)

Proof. (a) The result follows directly from Lemma 1, and since W_{2,0} = X_{1,1}, W_{3,0} = X_{1,2}.

(b) From part (a), we have for all n ≥ 1 and under assumption (10):

[ \begin{matrix}φ_{W_{2,n−1}}(t) \\ φ_{W_{3,n−1}}(t) \end{matrix} ] = B^{n−1} [ \begin{matrix}φ_{W_{2,0}}(t) \\ φ_{W_{3,0}}(t) \end{matrix} ] = B^{n} [ \begin{matrix}1 \\ 1 \end{matrix} ] ,

with

B = [ \begin{matrix}tp & 1 − p \\ p & t(1 − p) \end{matrix} ] .

Observe that λ_{1} and λ_{2} are the eigenvalues of B, so that

B^{n} = α_{n}B − (t^{2} − 1)p(1 − p)α_{n−1}I_{2},

by virtue of Lemma 2. From this, we obtain

[ \begin{matrix}φ_{W_{2,n−1}}(t) \\ φ_{W_{3,n−1}}(t) \end{matrix} ] = α_{n} [ \begin{matrix}tp + 1 − p \\ p + t(1 − p) \end{matrix} ] + α_{n−1} [ \begin{matrix}(1 − t^{2}) p(1 − p) \\ (1 − t^{2}) p(1 − p) \end{matrix} ] .

and the result follows by applying (12). □ Before proceeding with an evaluating of the probability mass function of S_{n}, a couple of observations merit mention.

Remark 2 (The probabilities P (S_{n} = 0) and P (S_{n} = n)) S_{n} is supported on {0, 1, …, n} and it is easy to evaluate P (S_{n} = n) directly, obtaining P (S_{n} = n) = P (⋂_{k=1}^{n+1}{X_{k,1} = 1})+P (⋂_{k=1}^{n+1}{X_{k,1} = 0}) = ∏_{k=1}^{n+1} p_{k} +∏_{k=1}^{n+1}(1−p_{k}), under (9); and P (S_{n} = n) = p^{n+1} + (1 − p)^{n+1} under (10). Consider now φ_{S_{n}}(0) = P (S_{n} = 0). Under assumption (10), relationship (14) applies with t = 0, λ_{1} = −λ_{2} = \sqrt{p(1 − p)}, and α_{n} = ((p(1 − p))^{(n−1)/2} for odd n, and α_{n} = 0 for even n. We therefore obtain from (14)

P (S_{n} = 0) = 2 (p(1 − p))^{(n+1)/2} I_{{n odd}} + (p(1 − p))^{n/2} I_{{n even}} .  (15)

Alternatively, since the event {S_{n} = 0} is equivalent to the event of alternating 0’s and 1’s in the first column of X, we may infer directly for odd n: P (S_{n} = 0) = P (X_{1,1} = 1, X_{1,2} = 0, …, X_{1,n} = 1, X_{1,n+1} = 0) + P (X_{1,1} = 0, X_{1,2} = 1, …, X_{1,n} = 0, X_{1,n+1} = 1) = 2[p(1 − p)]^{\frac{n+1}{2}} ; and similarly P (S_{n} = 0) = [p(1 − p)]^{\frac{n}{2}} as above in (15) for even n. For the non-homogeneous case in (9), we may proceed in an analogous manner to evaluate P (S_{n} = 0) either directly as in (15), or by making use of (13) with t = 0, obtaining

P (S_{n} = 0) = (1 − p_{n+1})^{[n even ]} ∏_{k=1}^{⌈n/2⌉} p_{2k}(1 − p_{2k−1}) + (p_{n+1})^{[n even ]} ∏_{k=1}^{⌈n/2⌉} p_{2k−1}(1 − p_{2k}),

where ⌈x⌉ is the ceiling function given by ⌈x⌉ = min {y ∈ Z : y ≥ x} .

Remark 3 (The case p = 1/2). For the homogeneous case in (10) with p = 1/2, we can show that S_{n} ∼ Bin(n, 1/2). Indeed, evaluating (14) with p = 1/2, we obtain

α_{n} = (\frac{t + 1}{2})^{n} − (\frac{t − 1}{2})^{n} ,

and

φ_{S_{n}}(t) = α_{n} (\frac{t + 1}{2}) − α_{n−1} (\frac{t − 1}{2}) (\frac{t + 1}{2}) = (\frac{t + 1}{2})^{n} ,

which implies S_{n} ∼ Bin(n, 1/2). Alternatively, setting Y_{k} = I_{{X_{k+1}=X_{k}}}, we have

S_{n} =^{d} ∑_{k=1}^{n} Y_{k}  (16)

with Y_{k} ∼ Ber(p^{2} + (1 − p)^{2}), for all k ≥ 1. Observe that ∀k ≥ 1, ∀i_{l} ∈ {0, 1}, l = 1, ⋯, k,

P (Y_{k+1} = 1|X_{k} = i_{k}, ⋯, X_{1} = i_{1}) = P (Y_{k+1} = 1|X_{k} = i_{k}) = p^{i_{k}}(1 − p)^{1−i_{k}}.

We thus infer for p = 1/2 that the Y_{k}’s are independent Ber(1/2), and that consequently S_{n} ∼ Bin(n, 1/2), by virtue of (16). Finally, notice that, for p ∈ (0, 1), E(S_{n}) = ∑_{k=1}^{n} E(Y_{k}) = n(p^{2} + (1 − p)^{2}), which equals np iff p = 1/2, and implies S_{n} ∼ Bin(n, 1/2) if and only if p = 1/2.

We pursue with an expansion of φ_{S_{n}} as given in (14) in order to derive an explicit form for the probability function of S_{n}.

Theorem 1 Let ρ = 4p(1 − p), n, k be non negative integers, and

a_{n,k}(ρ) = (\frac{ρ}{1 − ρ})^{⌈ \frac{n}{2} ⌉−k−1} ∑_{j=⌈ \frac{n}{2} ⌉−k−1}^{⌈ \frac{n}{2} ⌉−1} \binom{j}{⌈\frac{n}{2}⌉ − k − 1} \binom{n}{2j + 1} ) (1 − ρ)^{j} 1_{\{0≤k≤⌈ \frac{n}{2} ⌉−1\}}.

Under assumption (10), we have for all p ∈ (0, 1), p ≠ \frac{1}{2}, (a) P (S_{n} = 2k) = \frac{ρa_{n,k}(ρ)}{2^{n}}, and P (S_{n} = 2k + 1) = \frac{1}{2^{n}} [(2 − ρ)a_{n,k}(ρ) + ρa_{n−1,k}(ρ) − ρa_{n−1,k−1}(ρ)],

for n odd; and

(b) P (S_{n} = 2k) = \frac{1}{2^{n}} [(2 − ρ)a_{n,k−1}(ρ) + ρa_{n−1,k}(ρ) − ρa_{n−1,k−1}(ρ)], and P (S_{n} = 2k + 1) = \frac{ρa_{n,k}(ρ)}{2^{n}}, for n even.

Proof. Begin with standard operations to express α_{n} as a polynomial in t. Write Corollary 1’s λ_{1} and λ_{2} as λ_{1} = (t + Δ)/2, λ_{2} = (t − Δ)/2, with Δ = \sqrt{ρ + t^{2}(1 − ρ)}, so that λ_{1} − λ_{2} = Δ, and

α_{n} = \frac{λ_{1}^{n} − λ_{2}^{n}}{λ_{1} − λ_{2}} = \frac{1}{Δ2^{n}} \{(t + Δ)^{n} − (t − Δ)^{n}\} = \frac{1}{Δ2^{n}} ∑_{k=0}^{n} \binom{n}{k}t^{n−k}Δ^{k}(1^{k} − (−1)^{k})
= \frac{1}{2^{n−1}} ∑_{k=0,k odd}^{n} \binom{n}{k}t^{n−k}Δ^{k−1} = \frac{1}{2^{n−1}} ∑_{j=0}^{⌈ \frac{n}{2} ⌉−1} \binom{n}{2j + 1}t^{n−2j−1} (ρ + t^{2}(1 − ρ))^{j}
= \frac{1}{2^{n−1}} ∑_{j=0}^{⌈ \frac{n}{2} ⌉−1} \binom{n}{2j + 1}t^{n−2j−1} ∑_{k=0}^{j} \binom{j}{k}(\frac{ρ}{1 − ρ})^{k} (1 − ρ)^{j} t^{2j−2k}
= \frac{1}{2^{n−1}} ∑_{k=0}^{⌈ \frac{n}{2} ⌉−1} t^{n−2k−1} (\frac{ρ}{1 − ρ})^{k} ∑_{j=k}^{⌈ \frac{n}{2} ⌉−1} \binom{j}{k}\binom{n}{2j + 1} (1 − ρ)^{j}
= \frac{t^{[n even]}}{2^{n−1}} ∑_{k=0}^{⌈ \frac{n}{2} ⌉−1} t^{2k} (\frac{ρ}{1 − ρ})^{⌈ \frac{n}{2} ⌉−k−1} ∑_{j=⌈ \frac{n}{2} ⌉−k−1}^{⌈ \frac{n}{2} ⌉−1} \binom{j}{⌈\frac{n}{2}⌉ − k − 1}\binom{n}{2j + 1} (1 − ρ)^{j}
= \frac{t^{[n even]}}{2^{n−1}} ∑_{k} a_{n,k}(ρ) t^{2k}.  (17)

Making use of (14) and (17), we obtain for n odd

φ_{S_{n}}(t) = \{ \frac{1}{2^{n−1}} (∑_{k} a_{n,k}(ρ)t^{2k}) (\frac{ρ}{2} + t(1 − \frac{ρ}{2})\} + \{ \frac{1}{2^{n−2}} (∑_{k} a_{n−1,k}(ρ)t^{2k+1}) (\frac{ρ(1 − t^{2})}{4})\}
= \frac{1}{2^{n}} \{∑_{k} ρ a_{n,k}(ρ)t^{2k} + ∑_{k}(2 − ρ)a_{n,k}(ρ)t^{2k+1} + ∑_{k} ρ a_{n−1,k}(ρ)t^{2k+1} − ∑_{k} ρ a_{n−1,k−1}(ρ)t^{2k+1}\},

and the result follows by collecting terms in the representation φ_{S_{n}}(t) = ∑_{k} t^{2k}P (S_{n} = 2k) + ∑_{k} t^{2k+1}P (S_{n} = 2k + 1). Finally, a similar development leads to the stated result for n even. □

Remark 4 The probability functions given in Theorem 1 and Remark 3 form an interesting family on their own with parameter ρ, ρ ∈ (0, 1], with the case ρ = 1 corresponding to a Bin(n, 1/2) distribution. As seen below in Remark 5, all of these distributions may be described by a large n normal approximation. It is also instructive to consider some values of the probability function of S_{n} as prescribed by Theorem 1, such as the previously studied (Remark 2) probabilities of the events {S_{n} = 0} and {S_{n} = n}. As an illustration, consider P (S_{n} = n) for n even in which case (part (a) with k = n/2)

P (S_{n} = n) = \frac{1}{2^{n}} [ (2 − ρ) a_{n, \frac{n}{2} −1}(ρ) + ρ a_{n−1, \frac{n}{2}} (ρ) − ρ a_{n−1, \frac{n}{2} −1}(ρ) ]
= \frac{1}{2^{n}} [(2 − ρ) ∑_{j=0}^{\frac{n}{2} −1} \binom{n}{2j + 1}(1 − ρ)^{j} + 0 − ρ ∑_{j=0}^{\frac{n}{2} −1} \binom{n − 1}{2j + 1}(1 − ρ)^{j}]
= \frac{1}{2^{n+1}} [ (\sqrt{1 − ρ} + \frac{1}{\sqrt{1 − ρ}})\{(1 + \sqrt{1 − ρ})^{n} − (1 − \sqrt{1 − ρ})^{n}\}
+ (\sqrt{1 − ρ} − \frac{1}{\sqrt{1 − ρ}})\{(1 + \sqrt{1 − ρ})^{n−1} − (1 − \sqrt{1 − ρ})^{n−1}\}],

by virtue of the identity ∑_{j=0}^{\frac{s}{2} −1} \binom{s}{2j+1}w^{j} = \frac{1}{2\sqrt{w}} [(1 + \sqrt{w})^{s} − (1 − \sqrt{w})^{s}]; s an even positive integer, w > 0. Finally, with a little algebra, one obtains the equivalent form

P (S_{n} = n) = \frac{1}{2^{n+1}} [ (1 + \sqrt{1 − ρ})^{n+1} + (1 − \sqrt{1 − ρ})^{n+1} ] = p^{n+1} + (1 − p)^{n+1},

as in Remark 2.

We conclude this section with a large sample normal approximation for the distribution of S_{n}.

Remark 5 (Large sample normal approximation for S_{n}) In view of representation (16), the results of Stein (1972, Corollary 3.1) can be applied here to derive a large n normal approximation for the distribution of S_{n}. Indeed, the Bernoulli sequence Y_{1}, Y_{2}, … in (16) is stationary and 1-dependent (i.e., Y_{i} and Y_{j} are independent for all |i − j| > 1), and the results of Stein imply that

\frac{\frac{S_{n}}{n} − E(\frac{S_{n}}{n})}{\sqrt{V ar(\frac{S_{n}}{n})}} →^{d} N(0, 1).  (18)

Setting ρ = 4p(1 − p), we have Y_{k} ∼ Bernoulli(1 − ρ/2), E(\frac{S_{n}}{n}) = 1 − ρ/2 (as in Remark 3); V ar(Y_{1}) = \frac{ρ}{2}(1 − \frac{ρ}{2}); Cov(Y_{1}, Y_{2}) = P (X_{1} = X_{2} = X_{3}) − (p^{2} + (1 − p)^{2})^{2} = (p^{3} + (1 − p)^{3}) − (p^{2} + (1 − p)^{2})^{2} = ρ(1 − 2ρ)/4;

V ar(\frac{S_{n}}{n}) = \frac{1}{n^{2}} V ar(∑_{k=1}^{n} Y_{k}) = \frac{1}{n}\{V ar(Y_{1}) + 2(1 − 1/n)Cov(Y_{1}, Y_{2})\}
= \frac{1}{n}\{\frac{ρ}{2}(1 − \frac{ρ}{2}) + (1 − 1/n)\frac{ρ(1 − 2ρ)}{2}\}
= \frac{ρ − 3ρ^{2}/4}{n} + O(n^{−2}),

and finally from (18)

\frac{\frac{S_{n}}{n} − (1 − ρ/2)}{\sqrt{\frac{ρ−3ρ^{2}/4}{n}}} →^{d} N(0, 1).  (19)

Alternatively, the result is also available with an asymptotic expansion of (14).

3. Applications for Pólya urns

By virtue of de Finetti’s representation theorem for sequences of 0 − 1 exchangeable random variables, the results above under assumption (10) (Corollary 1 part b; Theorem 1) permit us to describe the distribution of S_{n} in (1) for r = 2 where the rows (X_{k,1}, X_{k,2}), k ≥ 1 are no longer independent, but arise in the context of a Pólya urn sampling scheme. In such schemes, an urn initially contains b black balls and w white balls. At step k, a ball is drawn randomly and uniformly from urn, and returned to the urn with s (s > 0) balls of the same colour. This generates the sequence of rows (X_{k,1}, X_{k,2}), k ≥ 1, where X_{k,1} = 1 − X_{k,2} is 1 or 0 according to whether the colour of the ball selected on the kth draw is black or white (respectively). Hence, S_{n} given in (1), and as described in Example 1, counts the number of consecutive pairs of draws with matching colours, among the first n + 1 draws. Now, in such a case, de Finetti’s representation theorem (see for instance Feller, 1971) implies the representation

X_{1,1}, …, X_{n+1,1} i.i.d. Bernouilli(θ), with θ ∼ Beta(\frac{b}{s}, \frac{w}{s}).  (20)

We thus obtain the following.

Corollary 2 Let c_{n,j,k} = \binom{j}{⌈ \frac{n}{2} ⌉−k−1} \binom{n}{2j+1} 1_{\{⌈ \frac{n}{2} ⌉−k−1≤j≤⌈ \frac{n}{2} ⌉−1\}}1_{\{0≤k≤⌈ \frac{n}{2} ⌉−1\}}, and

B_{n,k,m} = ∑_{j} c_{n,j,k} ∑_{i=0}^{j−(⌈ \frac{n}{2} ⌉−k−1)} \binom{j − (⌈\frac{n}{2}⌉ − k − 1)}{i}(−1)^{i} 4^{j+m−i} \frac{(\frac{b}{s})_{j+m−i}(\frac{w}{s})_{j+m−i}}{(\frac{b+w}{s})_{2(j+m−i)}} ,  (21)

for positive integers n, k, m = 0 or 1, and where (a)_{x} is the usual Pochhammer function defined as (a)_{0} = 1, and (a)_{x} = ∏_{i=0}^{x−1}(a + i) for x = 1, 2, … Then, for a Pólya urn as described above with parameters b, w, s, we have

(a) P (S_{n} = 2k) = \frac{B_{n,k,1}}{2^{n}}, and P (S_{n} = 2k + 1) = \frac{1}{2^{n}} [(2B_{n,k,0} − B_{n,k,1} + B_{n−1,k,1} − B_{n−1,k−1,1}], for n odd; and

(b) P (S_{n} = 2k) = \frac{1}{2^{n}} [(2B_{n,k−1,0} − B_{n,k−1,1} + B_{n−1,k,1} − B_{n−1,k−1,1}], and P (S_{n} = 2k + 1) = \frac{B_{n,k,1}}{2^{n}}, for n even.

Proof. It follows directly from representation (20) and Theorem 1 that the probability function of S_{n} in the context here of a Pólya urn is given by the above equations with B_{n,k,m} = E[Z^{m}a_{n,k}(Z)], with Z =^{d} 4θ(1 − θ), θ ∼ Beta(\frac{b}{s}, \frac{w}{s}). There remains to show that (21) is a valid expression for B_{n,k,m}. Indeed, we have

E[Z^{m}a_{n,k}(Z)] = ∑_{j} c_{n,j,k} E[Z^{m+⌈ \frac{n}{2} ⌉−k−1}(1 − Z)^{j−(⌈ \frac{n}{2} ⌉−k−1)}]  (22)
= ∑_{j} c_{n,j,k} ∑_{i=0}^{j−(⌈ \frac{n}{2} ⌉−k−1)} \binom{j − (⌈\frac{n}{2}⌉ − k − 1)}{i} (−1)^{i} E[(4θ(1 − θ))^{j+m−i}]
= B_{n,k,m},

by the evaluation

E(Z^{u}(1 − Z)^{v})] = \frac{(a_{1})_{u}(a_{2})_{v}}{(a_{1} + a_{2})_{u+v}} , for Z ∼ Beta(a_{1}, a_{2}); u, v ≥ 0.  (23)

Remark 6 (Case b = w) For cases where b = w (equal number of black and white balls initially in the Pólya urn), the expression of B_{n,k,m} in Corollary 2 is also equivalent to the simpler expression

B_{n,k,m} = (\frac{2b}{s} − 1)_{m+⌈ \frac{n}{2} ⌉−k−1} ∑_{j} c_{n,j,k} \frac{(\frac{1}{2})_{j−(⌈ \frac{n}{2} ⌉−k−1)}}{(\frac{2b}{s} − \frac{1}{2})_{j+m}} .

This is verified by establishing that: (i) Z = 4θ(1−θ) ∼ Beta(2b′ −1, \frac{1}{2}) whenever θ ∼ Beta(b′, b′), and (ii) by evaluating directly (22) via (23).

Acknowledgements

The research work of Éric Marchand is partially supported by NSERC of Canada.

References

[1] Ardakov, K. (1997). Powers and other functions of 2 × 2 matrices. The Mathematical Gazette, 4, 434-431.

[2] Feller, W. (1971). An Introduction to Probability theory and its Applications, volume II, Wiley, New York.

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

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

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

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

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

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

[9] Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Vol. II, pp. 583-602.