PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 83(97) (2008), 27–35 DOI: 10.2298/PIM0897027O

SINGLES IN A MARKOV CHAIN

Edward Omey and Stefan Van Gulck

Communicated by Slobodabka Janković

Abstract. Let {X_{i}, i ⩾ 1} denote a sequence of variables that take values in {0, 1} and suppose that the sequence forms a Markov chain with transition matrix P and with initial distribution (q, p) = (P (X_{1} = 0), P (X_{1} = 1)). Several authors have studied the quantities S_{n}, Y (r) and AR(n), where S_{n} = ∑_{i=1}^{n} X_{i} denotes the number of successes, where Y (r) denotes the number of experiments up to the r-th success and where AR(n) denotes the number of runs. In the present paper we study the number of singles AS(n) in the vector (X_{1}, X_{2}, …, X_{n}). A single in a sequence is an isolated value of 0 or 1, i.e., a run of length 1. Among others we prove a central limit theorem for AS(n).

1. Introduction

Many papers are devoted to sequences of Bernoulli trials and they form the basis of many (known) distributions and scientific activities. Applications are numerous. To mention only a few:

– the one-sample runs test can be used to test the hypothesis that the order in a sample is random;

– the number of successes can be used for testing for trends in the weather or in the stock market;

– Bernoulli-trials are important in matching DNA-sequences;

– the number of (consecutive) failures can be used in quality control.

In the case where the trials are i.i.d. many results are known concerning e.g. the quantities S_{n}, Y (r) and AR(n), where S_{n} = ∑_{i=1}^{n} X_{i} denotes the number of successes, where Y (r) denotes the number of experiments up to the r-th success and where AR(n) denotes the number of runs. A Markovian binomial distribution and other generalizations of the binomial distribution was studied e.g. by Altham [1], Madsen [7], Omey et al. [8]. In the present paper we study the number of singles AS(n) in the vector (X_{1}, X_{2}, …, X_{n}).

Suppose that each X_{i} takes values in the set {0, 1} and for n ⩾ 1, let AS(n) denote the number of singles in the sequence (X_{1}, X_{2}, …, X_{n}). With AS(n) we count the number of isolated values of 0 or 1 in (X_{1}, X_{2}, …, X_{n}). Mathematically we can study AS(n) as follows. For fixed n ⩾ 1 we construct a new sequence of t{0, 1}-valued r.v. t_{i} where t_{i} = 1 if and only if X_{i} is a single. More precisely we define the t_{i} as follows:

2000 Mathematics Subject Classification: Primary 60J10; Secondary 60F05, 60K99, 60J20.

t_{1} = (X_{2} − X_{1})^{2}, t_{n} = (X_{n} − X_{n−1})^{2};
t_{i} = (X_{i+1} − X_{i})^{2}(X_{i} − X_{i−1})^{2}, 2 ⩽ i ⩽ n − 1.

Clearly we have AS(n) = ∑_{i=1}^{n} t_{i}. Note that for simplicity we use the notation t_{i} and not the notation t_{i}^{(n)}. In studying t_{i} and AS(n) we assume that the sequence X_{1}, X_{2}, …, X_{n}, … is a Markov chain taking values in {0, 1}. As special cases we recover the i.i.d. case. We also briefly consider the the number of 0-singles AS_{n}^{(0)} and the number of 1-singles AS_{n}^{(1)}, i.e., AS_{n}^{(0)} counts the number of isolated zeros in the sequence and AS_{n}^{(1)} counts the number of isolated ”1” in the sequence.

Before starting our analysis we briefly discuss the Markov chain we use. We assume that {X_{i}, i ⩾ 1} is a {0, 1}-Markov chain with initial distribution

(P (X_{1} = 0), P (X_{1} = 1)) = (q, p), where 0 < p = 1 − q < 1.

The transition matrix P is given by

P = (\begin{matrix}p_{0,0} & p_{0,1} \\ p_{1,0} & p_{1,1} \end{matrix})

where for i, j = 0, 1, p_{i,j} = P (X_{2} = j | X_{1} = i). To avoid trivialities we suppose that 0 < p_{i,j} < 1. Note that the Markov chain has the unique stationary vector given by (x, y) = (p_{1,0}, p_{0,1})/(p_{0,1} + p_{1,0}). The eigenvalues of P are given by λ_{1} = 1 and λ = 1 − p_{0,1} − p_{1,0} = p_{0,0} − p_{1,0}. Note that |λ| < 1. By induction it is easy to show that the n-step transition matrix is given by

(1.1)  P^{n} = A + λ^{n}B, where A = (\begin{matrix}x & y \\ x & y \end{matrix}) and B = (\begin{matrix}y & −y \\ −x & x \end{matrix}) .

Using these relations we find that

(P (X_{n} = 0), P (X_{n} = 1)) = (q, p)P^{n−1} = (x + λ^{n−1}(y − p), y − λ^{n−1}(y − p)).

Among others this implies (see Omey et al. [8]) that for n ⩾ 1 we have

E(X_{n}) = y − λ^{n−1}(y − p),
Var(X_{n}) = (y − λ^{n−1}(y − p))(x + λ^{n−1}(y − p)),
Cov(X_{m}, X_{n}) = λ^{n−m} Var(X_{m}), m ⩽ n.

As a special case we consider the case where the transition matrix P = P (p, ρ) is given by

P (p, ρ) = (\begin{matrix}q + ρp & p(1 − ρ) \\ q(1 − ρ) & p + ρq \end{matrix}) .

In this case we have (x, y) = (q, p) and λ = ρ. Since we also have P (X_{n} = 1) = p, for all n, the X_{i} have the same distribution. If ρ ≠ 0, the X_{i} are correlated with ρ = ρ(X_{n}, X_{n+1}). From this it follows that Cov(X_{n}, X_{m}) = ρ^{n−m}pq (m ⩽ n). This type of correlated Bernoulli trials has been studied among others by Dimitrov and Kolev [3]. See also Kupper and Haseman [5] or Lai et al. [6]. If ρ = 0, we find back the case where the X_{i} are i.i.d. Bernoulli variables. In Fu and Lou [4], the authors use a finite Markov imbedding approach to study runs and patterns.

2. Moments

Now we focus our attention on the number of singles. We use the sequence of r.v. t_{i} as in the introduction. In Propositions 2.1 and 2.2 below we study distributional properties of the random variables t_{i}.

Proposition 2.1. For n ⩾ 3 we have: • P (t_{1} = 1) = pp_{1,0} + qp_{0,1};

• P (t_{i} = 1) = p_{0,1}p_{1,0}, for 2 ⩽ i ⩽ n − 1;

• P (t_{n} = 1) = P (X_{n−1} = 1)p_{1,0} + P (X_{n−1} = 0)p_{0,1} = (q, p)P^{n−2}(\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}).

Proof. For t_{1} we have

P (t_{1} = 1) = P ((X_{1}, X_{2}) ∈ {(1, 0), (0, 1)}) = pp_{1,0} + qp_{0,1}.

For 2 ⩽ i ⩽ n − 1, we have

P (t_{i} = 1) = P ((X_{i−1}, X_{i}, X_{i+1}) ∈ {(0, 1, 0), (1, 0, 1)})

and it follows that

P (t_{i} = 1) = (P (X_{i−1} = 0) + P (X_{i−1} = 1))p_{0,1}p_{1,0} = p_{0,1}p_{1,0}.

Finally, we have P (t_{n} = 1) = P ((X_{n−1}, X_{n}) ∈ {(1, 0), (0, 1)}) so that

P (t_{n} = 1) = P (X_{n−1} = 1)p_{1,0} + P (X_{n−1} = 0)p_{0,1}.  □

Proposition 2.2. For n ⩾ 4, the joint distributions are given by:

(a) For i = 1 or i = n − 1, P (t_{i} = t_{i+1} = 1) = p_{0,1}p_{1,0}.

(b) For 2 ⩽ i ⩽ n − 2, P (t_{i} = t_{i+1} = 1) = p_{0,1}p_{1,0}(q, p)P^{i−2} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}).

(c) P (t_{1} = t_{n} = 1) = (pp_{1,0}, qp_{0,1})P^{n−3} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}).

(d) For 2 ⩽ i ⩽ n − 2, P (t_{i} = t_{n} = 1) = p_{0,1}p_{1,0}(q, p)P^{n−4} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}).

(e) In all other cases t_{i} and t_{j} are independent.

Proof. (a) For (t_{1}, t_{2}) we have

P (t_{1} = t_{2} = 1) = P ((X_{1}, X_{2}, X_{3}) ∈ {(1, 0, 1), (0, 1, 0)})

so that P (t_{1} = t_{2} = 1) = pp_{1,0}p_{0,1} + qp_{0,1}p_{1,0} = p_{1,0}p_{0,1}. The result for i = n − 1 follows in a similar way.

(b) For i = 2, 3, …, n − 2 we have

P (t_{i} = t_{i+1} = 1) = P ((X_{i−1}, X_{i}, X_{i+1}, X_{i+2}) ∈ {(1, 0, 1, 0), (0, 1, 0, 1)})

so that

P (t_{i} = t_{i+1} = 1) = P (X_{i−1} = 1)p_{1,0}p_{0,1}p_{1,0} + P (X_{i−1} = 0)p_{0,1}p_{1,0}p_{0,1}.

Using (P (X_{i−1} = 0), P (X_{i−1} = 1)) = (q, p)P^{i−2} we find that

P (t_{i} = 1, t_{i+1} = 1) = p_{0,1}p_{1,0}(q, p)P^{i−2} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) .

(c) For (t_{1}, t_{n}) we have P (t_{1} = t_{n} = 1) = P ((X_{1}, X_{2}, X_{n−1}, X_{n}) ∈ S) where S = {(1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1)}. Considering the first case, we have

P ((X_{1}, X_{2}, X_{n−1}, X_{n}) = (1, 0, 1, 0)) = pp_{1,0}p_{0,1}^{(n−3)}p_{1,0}.

In a similar way we calculate the other 3 cases. Using matrices, it follows that

P (t_{1} = t_{n} = 1) = (pp_{1,0}, qp_{0,1})P^{n−3} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) .

(d) For 2 ⩽ i ⩽ n − 2 we have

P (t_{i} = t_{n} = 1) = P ((X_{i−1}, X_{i}, X_{i+1}, X_{n−1}, X_{n}) ∈ S)

where S = {(1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (0, 1, 0, 0, 1), (0, 1, 0, 1, 0)}. Considering the first case, we have

P ((X_{i−1}, X_{i}, X_{i+1}, X_{n−1}, X_{n}) = (1, 0, 1, 0, 1)) = P (X_{i−1} = 1)p_{1,0}p_{0,1}p_{1,0}^{(n−i−2)}p_{0,1}.

In a similar way we treat the other cases and using matrices we find that

P (t_{i} = t_{n} = 1) = p_{0,1}p_{1,0}(P (X_{i−1} = 0), P (X_{i−1} = 1))P^{n−i−2} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix})

so that

P (t_{i} = t_{n} = 1) = p_{0,1}p_{1,0}(q, p)P^{n−4} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) .

(e) To prove independence, consider for example (t_{1}, t_{3}). We have

P (t_{1} = t_{3} = 1) = P ((X_{1}, X_{2}, X_{3}, X_{4}) ∈ {(1, 0, 1, 0), (0, 1, 0, 1)})

so that

P (t_{1} = t_{3} = 1) = pp_{1,0}p_{0,1}p_{1,0} + qp_{0,1}p_{1,0}p_{0,1} = P (t_{1} = 1) P (t_{3} = 1).

It follows that t_{1} and t_{3} are independent. In a similar way it follows that (t_{1}, t_{i}) for i = 3, 4, …, n−1 are independent r.v. and that the other (t_{i}, t_{j}) are independent r.v.

□

In the i.i.d. case, we obtain the following corollary.

Corollary 2.1. Suppose n ⩾ 4 and X_{1}, X_{2}, …, X_{n} i.i.d. with P (X_{1} = 1) = p; then

(a) P (t_{1} = 1) = P (t_{n} = 1) = 2pq and for 2 ⩽ i ⩽ n − 1, P (t_{i} = 1) = pq.

(b) P (t_{1} = t_{2} = 1) = P (t_{n−1} = t_{n} = 1) = pq and for 2 ⩽ i ⩽ n − 2, P (t_{i} = t_{i+1}) = 2p^{2}q^{2}.

(c) P (t_{1} = t_{n} = 1) = 4p^{2}q^{2}.

(d) For 2 ⩽ i ⩽ n − 2, P (t_{i} = t_{n} = 1) = 2p^{2}q^{2}.

(e) In the other cases t_{i} and t_{j} are independent.

In the next result we discuss the mean and the variance of AS(n).

SINGLES IN A MARKOV CHAIN 31

Proposition 2.3. (a) As n → ∞, we have \frac{1}{n}E(AS(n)) → p_{0,1}p_{1,0}.

(b) As n → ∞, we have \frac{1}{n} Var(AS(n)) → p_{0,1}p_{1,0}(1 − 3p_{0,1}p_{1,0} + \frac{4p_{0,1}p_{1,0}}{p_{0,1} + p_{1,0}} ).

Proof. (a) Using Proposition 2.1, for 2 ⩽ i ⩽ n − 1 we have E(t_{i}) = p_{0,1}p_{1,0} It follows that E(AS(n)) = (n − 2)p_{0,1}p_{1,0} + E(t_{1}) + E(t_{n}) and the result follows.

(b) Using Proposition 2.2 we have

Var(AS(n)) = ∑_{1=1}^{n} Var(t_{i}) + 2 ∑_{i=1}^{n−2} Cov(t_{i}, t_{i+1}) + 2 ∑_{i=1}^{n−1} Cov(t_{i}, t_{n}) = I + II + III.

We consider these three terms separately.

Term I. For i = 2, 3, , …, n − 1 we have Var(t_{i}) = p_{0,1}p_{1,0}(1 − p_{0,1}p_{1,0}). For i = 1, n, we have Var(t_{1})+Var(t_{n}) ⩽ 2. It follows that I/n → p_{0,1}p_{1,0}(1−p_{0,1}p_{1,0}).

Term II. For i = 2, 3, …, n − 2 it follows from Propositions 2.1 and 2.2 that

Cov(t_{i}, t_{i+1}) = p_{0,1}p_{1,0}(q, p)P^{i−2} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) − (p_{0,1}p_{1,0})^{2}.

It follows that

∑_{i=2}^{n−2} Cov(t_{i}, t_{i+1}) = p_{0,1}p_{1,0}(q, p) ∑_{i=2}^{n−2} P^{i−2} (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) − (n − 3)(p_{0,1}p_{1,0})^{2}.

Using P^{k} = A + λ^{k}B, cf (1.1), we obtain that

\frac{1}{n} ∑_{i=2}^{n−2} P^{i−2} = \frac{1}{n} ∑_{j=0}^{n−4}(A + λ^{j}B) → A.

We conclude that

\frac{II}{n} → 2p_{0,1}p_{1,0}(q, p)A (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) − 2(p_{0,1}p_{1,0})^{2} = 2p_{0,1}p_{1,0}(xp_{0,1} + yp_{1,0} − p_{1,0}p_{0,1}).

Term III. For 2 ⩽ i ⩽ n − 1, we have

Cov(t_{i}, t_{n}) = p_{0,1}p_{1,0}(q, p) (P^{n−4} − P^{n−2}) (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix})

so that

Cov(t_{i}, t_{n}) = p_{0,1}p_{1,0}(q, p) (λ^{n−4} − λ^{n−2}) B (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) ,
∑_{i=2}^{n−1} Cov(t_{i}, t_{n}) = (n − 3)p_{0,1}p_{1,0}(q, p) (λ^{n−4} − λ^{n−2}) B (\begin{matrix}p_{0,1} \\ p_{1,0} \end{matrix}) .

It follows that III/n → 0. We conclude that

\frac{1}{n} Var(AS(n)) → p_{0,1}p_{1,0}(1 − p_{1,0}p_{0,1}) + 2p_{0,1}p_{1,0}(xp_{0,1} + yp_{1,0} − p_{1,0}p_{0,1}).

Using x = p_{1,0}/(p_{1,0} + p_{0,1}) and y = 1 − x, it follows that

\frac{1}{n} Var(AS(n)) → p_{0,1}p_{1,0}(1 − 3p_{0,1}p_{1,0} + \frac{4p_{0,1}p_{1,0}}{p_{0,1} + p_{1,0}} ).  □

Remark 2.1. A more detailed analysis shows that E(AS(n)) = (p + y)p_{1,0} + (q + x)p_{0,1} + (n − 2)p_{0,1}p_{1,0} + λ^{n−2}(y − p)(p_{0,1} − p_{1,0}).

In the next corollary we formulate two special cases. Corollary 2.2. (i) If P = P (p, ρ) then

E(AS(n)) = (n − 2)pq(1 − ρ)^{2} + 4pq(1 − ρ),

\frac{1}{n} Var(AS(n)) → pq(1 − ρ)^{2}(1 + pq(1 − ρ) + 3pqρ(1 − ρ)).

(ii) (the i.i.d. case) If ρ = 0, then

E(AS(n)) = (n + 2)pq, and \frac{1}{n} Var(AS(n)) → pq(1 + pq).

3. The distribution of AS(n)

In the next proposition we show how to calculate p_{n}(k) = P (AS(n) = k) recursively.

For n ⩾ 2 and for i, j = 0, 1 we write

p_{n}(k) = ∑_{i=0}^{1} ∑_{j=0}^{1} p_{n}^{(i,j)}(k), where p_{n}^{(i,j)}(k) = P (AS(n) = k, X_{n−1} = i, X_{n} = j)

For n = 2 we clearly have p_{2}^{(0,0)}(0) = qp_{0,0} and 0 otherwise; also p_{2}^{(0,1)}(2) = qp_{0,1} and 0 otherwise; p_{2}^{(1,0)}(2) = pp_{1,0} and 0 otherwise and p_{2}^{(1,1)}(0) = pp_{1,1} and 0 otherwise. We have the following relations.

Proposition 3.1. For n ⩾ 2 we have • p_{n+1}^{(0,0)}(k) = p_{0,0}p_{n}^{(1,0)}(k + 1) + p_{0,0}p_{n}^{(0,0)}(k);

• p_{n+1}^{(0,1)}(k) = p_{0,1}p_{n}^{(0,0)}(k − 1) + p_{0,1}p_{n}^{(1,0)}(k − 1);

• p_{n+1}^{(1,0)}(k) = p_{1,0}p_{n}^{(0,1)}(k − 1) + p_{1,0}p_{n}^{(1,1)}(k − 1);

• p_{n+1}^{(1,1)}(k) = p_{1,1}p_{n}^{(0,1)}(k + 1) + p_{1,1}p_{n}^{(1,1)}(k).

Proof. We only prove the first relation. We have p_{n+1}^{(0,0)}(k) = I + II where

I = P (AS(n + 1) = k, X(n − 1) = 0, X(n) = 0, X(n + 1) = 0)
II = P (AS(n + 1) = k, X(n − 1) = 1, X(n) = 0, X(n + 1) = 0).

It follows that

I = P (AS(n) = k, X(n − 1) = 0, X(n) = 0, X(n + 1) = 0)
= P (X(n + 1) = 0 | X(n) = 0, X(n − 1) = 0, AS(n) = k)p_{n}^{0,0}(k)

so that I = p_{0,0}p_{n}^{(0,0)}(k).

In a similar way we have II = p_{0,0}p_{n}^{(1,0)}(k + 1). □

Proposition 3.1 can be used to calculate the p.d. of AS(n) explicitly for small values of n. A straightforward analysis shows that the complexity effort is of order n^{2} and exact calculations can be carried out for moderate values of n. For large values of n we prove the following central limit theorem.

Theorem 3.1. As n → ∞, we have

\frac{AS(n) − np_{0,1}p_{1,0}}{\sqrt{n}} ⇒^{d} Z,

where Z ∼ N(0, β) with β = p_{0,1}p_{1,0} (1 − 3p_{0,1}p_{1,0} + 4\frac{p_{0,1}p_{1,0}}{p_{1,0} + p_{0,1}} ) .

Proof. To prove the result we use Proposition 3.1 and generating functions. Let Ψ_{n}^{(i,j)}(z) denote the generating function of p_{n}^{(i,j)}(k) and let Ψ_{n}(z) denote the generating function of p_{n}(k). Also, let

Λ_{n}(z) = (Ψ_{n}^{(0,0)}(z), Ψ_{n}^{(0,1)}(z), Ψ_{n}^{(1,0)}(z), Ψ_{n}^{(1,1)}(z)).

Clearly we have

Λ_{2}(z) = (qp_{0,0}, qp_{0,1}z^{2}, pp_{1,0}z^{2}, pp_{1,1}) and Ψ_{n}(z) = Λ_{n}(z)(1, 1, 1, 1)^{t}.

For n ⩾ 2 we use Proposition 3.1 to see that • Ψ_{n+1}^{(0,0)}(z) = (p_{0,0}/z)Ψ_{n}^{(1,0)}(z) + p_{0,0}Ψ_{n}^{(0,0)}(z);

• Ψ_{n+1}^{(0,1)}(z) = p_{0,1}zΨ_{n}^{(0,0)}(z) + p_{0,1}zΨ_{n}^{(1,0)}(z);
• Ψ_{n+1}^{(1,0)}(z) = p_{1,0}zΨ_{n}^{(0,1)}(z) + p_{1,0}zΨ_{n}^{(1,1)}(z);
• Ψ_{n+1}^{(1,1)}(z) = (p_{1,1}/z)Ψ_{n}^{(0,1)}(z) + p_{1,1}Ψ_{n}^{(1,1)}(z).

For n ⩾ 2 we obtain that Λ_{n+1}(z) = Λ_{n}(z)A(z) = Λ_{2}(z)A^{n−1}(z), where the matrix A(z) is given by

A(z) = (\begin{matrix}p_{0,0} & p_{0,1}z & 0 & 0 \\ 0 & 0 & p_{1,0}z & p_{1,1}/z \\ p_{0,0}/z & p_{0,1}z & 0 & 0 \\ 0 & 0 & p_{1,0}z & p_{1,1} \end{matrix}) .

The eigenvalue equation of A(z) leads to

(3.1)  λ^{4} − λ^{3}(p_{0,0} + p_{1,1}) + λ^{2}(p_{0,0}p_{1,1} − z^{2}p_{0,1}p_{1,0}) − λa(z) − b(z) = 0,

where

a(z) = z(1 − z)(p_{0,0} + p_{1,1})p_{0,1}p_{1,0}, and b(z) = p_{0,0}p_{0,1}p_{1,0}p_{1,1}(1 − z)^{2}.

In the case where z = 1 the eigenvalues are λ_{1} = 1, λ_{2} = 1 − p_{0,1} − p_{1,0} and λ_{3} = λ_{4} = 0. In the general case, a continuity argument shows that for z < 1, the matrix A(z) has a unique largest eigenvalue λ(z) = λ_{1}(z) such that λ(z) → 1 as z → 1. The other eigenvalues are dominated by λ(z). It follows that

A^{n}(z_{n})/(λ(z_{n}))^{n} → U(1)

where z_{n} → 1 and where each row of U(1) equals (xp_{0,0}, xp_{0,1}, yp_{1,0}, yp_{1,1}).

Now we consider the largest eigenvalue λ(z) of A(z). Starting from (3.1) we calculate the first derivative, then the second derivative and then take z = 1. Some lengthy but straighforward calculations show that

λ′(1) = p_{1,0}p_{0,1} and λ′′(1) = \frac{2p_{0,1}^{2}p_{1,0}^{2}(p_{0,0} + p_{1,1})}{p_{0,1} + p_{1,0}}.

Using Taylor’s expansion for log(z) and for log(λ(z)) around z = 1, we find that

\frac{log(λ(z)) − p_{1,0}p_{0,1} log(z)}{(1 − z)^{2}} → \frac{1}{2}β

where

β = p_{0,1}p_{1,0} (1 − 3p_{0,1}p_{1,0} + 4\frac{p_{0,1}p_{1,0}}{p_{1,0} + p_{0,1}} ) .

Now we replace z by u_{n} = z^{1/\sqrt{n}} to see that

\frac{λ^{n}(u_{n})}{u_{n}^{np_{0,1}p_{1,0}}} → exp(\frac{1}{2}β(log(z))^{2}).

Turning to Ψ_{n+1}(z) we find that Ψ_{n+1}(u_{n}) ∼ Λ_{2}(u_{n})λ^{n}(u_{n})U(1)(1, 1, 1, 1)^{t} and hence

Ψ_{n+1}(u_{n})u_{n}^{−np_{0,1}p_{1,0}} → (exp\{\frac{1}{2}β(log(z))^{2}\})Λ_{2}(1) U(1) (1, 1, 1, 1)^{t}.

It follows that

Ψ_{n+1}(u_{n})u_{n}^{−np_{0,1}p_{1,0}} → exp\{\frac{1}{2}β(log(z))^{2}\}.

Since Ψ_{n+1}(u_{n}) = E(z^{AS(n+1)/\sqrt{n}}) the desired result follows. □

In the i.i.d. case we find back the following result of Bloom [2].

Corollary 3.1. In the i.i.d. case we have

\frac{AS(n) − npq}{\sqrt{n}} ⇒^{d} Z,

where Z ∼ N(0, β = pq(1 + pq)).

4. Singles “0” and singles “1”

In this section we briefly discuss the number AS_{n}^{(0)} of isolated values 0 and the number AS_{n}^{(1)} of isolated values 1. First we look at isolated values of 0. Starting from the sequence X_{1}, X_{2}, …, X_{n} we define t_{i}^{(0)} = 1 if X_{i} = 0 is a single. Clearly we have

t_{1}^{(0)} = X_{2}(1 − X_{1}), t_{n}^{(0)} = X_{n−1}(1 − X_{n}), t_{i}^{(0)} = X_{i−1}(1 − X_{i})X_{i+1}

and AS_{n}^{(0)} = ∑_{i=1}^{n} t_{i}^{(0)}. Using the methods of the previous sections one can prove the following result.

Theorem 4.1. (a) As n → ∞ we have \frac{1}{n}E(AS_{n}^{(0)}) → yp_{0,1}p_{1,0} and

\frac{1}{n} Var(AS_{n}^{(0)}) → θ_{0} = yp_{0,1}p_{1,0}(1 − 3yp_{0,1}p_{1,0} + 2xyp_{1,0}).

(b) As n → ∞ we have

\frac{AS_{n}^{(0)} − nyp_{0,1}p_{1,0}}{\sqrt{n}} ⇒^{d} Z^{(0)}

where Z^{(0)} ∼ N(0, θ_{0}).

An entirely similar result holds for AS_{n}^{(1)}. Now we find

\frac{AS_{n}^{(1)} − nxp_{0,1}p_{1,0}}{\sqrt{n}} ⇒^{d} Z^{(1)}

where Z^{(1)} ∼ N(0, θ_{1}) with θ_{1} = xp_{0,1}p_{1,0}(1 − 3xp_{0,1}p_{1,0} + 2xyp_{0,1}). Using

Var(AS(n)) = Var(AS_{n}^{(0)}) + Var(AS_{n}^{(1)}) + 2 Cov(AS_{n}^{(0)}, AS_{n}^{(1)}),

we obtain the following asymptotic expression for the covariance.

Corollary 4.1. As n → ∞ we have

\frac{1}{n} Cov(AS_{n}^{(0)}, AS_{n}^{(1)}) → −3xyp_{0,1}^{2}p_{1,0}^{2} + \frac{2p_{0,1}^{2}p_{1,0}^{2}}{p_{1,0} + p_{0,1}} (1 − xy).

References

[1] P. Altham, Two generalizations of the binomial distribution, J. R. Stat. Soc., Ser. C 27 (1978), 162–167.

[2] D. M. Bloom, Singles in a sequence of coin tosses, Coll. Math. J. 29(2) (1998), 120–127.

[3] B. Dimitrov, B. and N. Kolev, Extended in time correlated Bernoulli trials in modeling waiting times under periodic environmental conditions, Technical paper, Universidade de Sao Paulo, Brasil, 1999.

[4] J. C. Fu and W. Y. W. Lou, Distribution theory of runs and patterns and its applications. A finite Markov chain imbedding approach, World Scientific, Singapore, 2003.

[5] L. L. Kupper and J. K. Haseman, The use of the correlated binomial model for the analysis of certain toxicological experiments, Biometrics 34 (1978), 69–76.

[6] C. D. Lai, K. Govindaraju, and M. Xie, Effects of correlation on fraction non-conforming statistical process control procedures, J. Appl. Stat. 25(4) (1998), 535–543.

[7] R. W. Madsen, Generalized binomial distributions, Commun. Stat., Theory Methods 22(11) (1993), 3065–3086.

[8] E. Omey, J. Santos, and S. Van Gulck, A Markov binomial distribution, Appl. Anal. Discrete Math. 2(1) (2008), 38–50. (available electronically at: http://pefmath.etf.bg.ac.yu)

Department of Mathematics and Statistics (Received 06 05 2008) HUB, Stormstraat 2, 1000 Brussels, Belgium and Affiliated Researcher K. U. Leuven – ORSTAT Naamsestraat 69, 3000 Leuven, Belgium

edward.omey@hubrussel.be

Department of Mathematics and Statistics HUB, Stormstraat 2, 1000 Brussels, Belgium

stefan.vangulck@hubrussel.be