Stationary $1$-dependent Counting Processes:
from Runs to Bivariate Generating Functions

We give a formula for the bivariate generating function of a stationary $1$-dependent counting process in terms of its run probability generating function, with a probabilistic proof. The formula reduces to the well known bivariate generating function of the Eulerian distribution in the case of descents of a sequence of indepependent and identically distributed random variables. The formula is compared with alternative expressions from the theory of determinantal point processes and the combinatorics of sequences.

One-dependent process, bivariate generating function, run probability generating function, Eulerian numbers, dependence structures, determinantal point process.

Proof (of Theorem 2.1 and Corollary 2.2)

We will first prove the left equality in (2.1), rearranged as

by establishing the corresponding identity of coefficients of powers of $v$, that is,

Recall that $q_{j}:=[v^{j}]Q(v)$, whence

So (2.4) for each $n=1,2,\ldots$, with $j=k-1$, reduces to

which has the following interpretation. For $0\leq z\leq 1$, let $(Y_{n},n\geq 1)$ be a sequence of i.i.d. Bernoulli($z$) random variables, also independent of $(X_{n},n\geq 1)$. Employing van Dantzig’s method of marks [37], treat $Y_{n}$ as a mark on $X_{n}$: say the $n$-th item $X_{n}$ is $z$-marked if $Y_{n}=1$, and non-$z$-marked if $Y_{n}=0$. By construction, $Q_{S_{n}}(z)$ is the probability that every success among the first $n$ trials is $z$-marked. In particular, if $z=0$, every success in non-$z$-marked. Then the only way every success in the first $n$ trials is $z$-marked is if there are no successes. Hence $Q_{S_{n}}(0)=q_{n}$ is the probability of no successes in the first $n$ trials. The identity (2.6), decomposes the event that every success in the first $n$ trials is $z$-marked according to the value of $T_{z}:=\min\{n:Y_{n}=1\}$, the index of the first $z$-mark. So

• •

  $T_{z}$ has the geometric$(z)$ distribution ${\mathbb{P}}(T_{z}=k)=(1-z)^{k-1}z$ for $k=1,2,\ldots$;

• •

  On the event of probability $(1-z)^{n}$, that the first $z$-mark occurs at $T_{z}>n$, no trial among the first $n$ is allowed to be success, with probability $q_{n}$;

• •

  On the event of probability $(1-z)^{k-1}z$, that the first $z$-mark occurs at $T_{z}=k$ for some $1\leq k\leq n$, no trial among the first $k-1$ is allowed to be success, with probability $q_{k-1}$, and all success after the $k$-th (excluding the $k$-th) are $z$-marked, with probability $Q_{S_{n-k}}(z)$, with independence before and after the $k$-th trial by the assumption that $(X_{n},n\geq 1)$ is $1$-dependent.

This proves the left equality of (2.1). To prove the right, it is easiest to prove Corollary 2.2. Recall (1.9),

which yields the $P$ identity in (2.2). To see the $Q$ identity, simply replace $v$ with $-v$ in the last equation.

Lastly, the right equation of (2.1) is obtained from the left one and the involution

In this section, we present the example of Eulerian numbers. We were led to the general formula for the bivariate generating function of counts of a $1$-dependent indicator sequence by the algebraically simple form of the bivariate generating function of Eulerian numbers, whose probabilistic meaning is not immediately obvious, but nicely explained by the above proof of Theorem 2.1.

It is well known that a large class of stationary $1$-dependent indicator sequences (though not all, see [1, 3]) may be constructed from an independent and identically distributed background sequence $(Y_{1},Y_{2},\ldots)$, as two-block factors

for some product-measurable subset $B$ of the space of pairs of $Y$-values, say $[0,1]^{2}$ for $Y_{i}\sim$ Uniform$(0,1)$.

An important example is provided by the sequence of descents $X_{n}:=1(Y_{n}>Y_{n+1})$ for real-valued $Y_{i}$. In particular, for $Y_{i}\sim$ Uniform$(0,1)$ (or any continuous distribution) and $S_{n}:=D_{n+1}$ counting the number of descents $Y_{i}>Y_{i+1}$ with $1\leq i\leq n$:

So the run generating functions $Q(v)$ and $P(v)$ in this case are easily evaluated as

To simplify displays, we work in this section with the shifted run generating functions

and the shifted bivariate generating function

For reasons which do not seem obvious, the algebraic form of the generating functions associated with a $1$-dependent indicator sequence is typically simpler when they are shifted like this. The shifted generating functions of some selected models are shown in the table below, with detailed explanation later.

There are some benefits for using the shifted generating functions. Firstly, they are simpler, especially in the Eulerian case; secondly, for $2$-block factors, the shifted generating functions are actually ‘standard’ in combinatorics, since $n$ is set to be the length of background sequence; thirdly, the formulae in Theorem 2.1 and Corollary 2.2 are also slightly simplified: the involution formula (2.2) becomes (see, e.g. [32, 2] for earlier occurrences, and [18, 5] where this formula was first discovered in the study of $2$-block factors)

while our main theorem (2.1) is re-written as

We already discussed the Eulerian model in Section 3. The rest of Table $1$ will be briefed here row by row. Usually, we only say how one of the run probability generating functions is obtained, since the other one and the bivariate generating function can then be found easily through (4.1), (4.3) and (4.4).

Any indicator process can be treated as a point process by regarding the indicated events as points. It was shown in [2, Theorem 7.1] that any $1$-dependent point process on a segment of ${\mathbb{Z}}$ is a determinantal process, as discussed further in [8, 9, 2].

Given a finite set ${\mathcal{X}}$, a point process on ${\mathcal{X}}$ is a probability measure ${\mathbb{P}}$ on $2^{\mathcal{X}}$. Its correlation function is the function of subsets $A\subseteq{\mathcal{X}}$ defined by $\rho(A):={\mathbb{P}}(S:S\supseteq A)$. A point process is said to be determinantal with kernel $K(x,y)$ if

where the right hand side is the determinant of the $|A|\times|A|$ matrix with $K(x,y)$ on its $(x,y)$-th entry for $x,y\in A$. Now, we may state the following theorem from [2].

In the stationary case,

where $S_{n}$ and $p_{n}$ inherit the setup in Section 1. It is easy to see that then the kernel is also stationary, i.e.

To better describe the kernel, consider the kernel generating function

Borodin, Diaconis and Fulman[2, Corollary 7.3] give the following relationship between the kernel generating function $G_{k}$ and the $1$-run probability generating function $P$

One last interesting (but not hard) result [2, Theorem 4.1] is that we may write the probability of any string pattern as a determinant. Consider ${\mathcal{X}}=[n]:=\{1,2,\cdots,n\}$, then the string with exactly $k$ zeros at $0<w_{1}<w_{2}<\cdots<w_{k}\leq n$, which corresponds to the subset $A:=\{w_{1},w_{2},\cdots,w_{k}\}^{c}$, has probability

where $p_{n}=0,\forall n<-1,p_{0}=p_{-1}=1$ and $w_{0}=0,w_{k+1}=n+1$.

As shown in [2], this formula (5.7) is obtained by application of inclusion-exclusion formula on the correlation function. Hence, we may recover our bivariate generating function (2.1) as follows:

The proof to Corollary 5.2 is quite straightforward: just multiply (5.7) by $\prod_{i\in A}z_{i}$ and then sum it up over all subsets $A\subseteq[n]$. Corollary 5.3 is then obvious by considering the ordinary generating function of $S_{n}=\sum_{i\in[n]}I_{i}$, i.e. treat all $z_{i}$ in (5.8) as $z$. We are also aware of the following known determinantal generating function formula for any $1$-dependent process (not necessarily stationary)

where $I$ is the identity matrix and $K$ is the determinantal correlation kernel given by Theorem 5.1. This is not easy to simplify even for the stationary case. But from hindsight, one may check that this is essentially equivalent to (5.9). Lastly, one may also show Theorem 2.1 by the Laplace expansion of the last column of the determinant on the right of (5.9).

We have derived our main Theorem 2.1 from a probabilistic point of view, without assuming the sequences to be $2$-block factors. But its enumerative Corollary 6.1 on integer-valued $2$-block factors can be deduced from a combinatorial result in Goulden and Jackson [21, Section 4].

Recall (3.1), we defined $2$-block factors on $V$ based on the background sequence $(Y_{1},Y_{2},\ldots)$ as indicators of adjacent pairs $(Y_{i},Y_{i+1})$ falling in some subset $B\subseteq V^{2}$, which obviously is a $1$-dependent indicator process. For example, in section 3, we discussed the case where $V=[0,1]$ and $B=\{(x,y):0\leq y\leq x\leq 1\}$.

Say a string on ${\mathbb{Z}}_{+}$ is a $B$-string if each adjacent pair belongs to $B$. Suppose further that the background sequence $(Y_{1},Y_{2},\ldots)$ has i.i.d. uniform distribution on $[m]=\{1,2,\cdots,m\}$. Then, the $1$-run probability $p_{k}$ can be used to count the number $m_{k}$ of $B$-strings of length $k$, i.e.

and $m_{0}=1$ by convention. Define the $B$-string generating function as

where $P(v)$ is the $1$-run probability generating function. Now the following corollary follows from Theorem 2.1 by elementary algebra.

To see the connection between Corollary 6.1 and [21], we need the following definition from [21]. Let the $B$-string of length $k$ enumerator be

where the sum is over all $B$-string $\sigma$ of length $k$ and $\tau_{i}(\sigma)$ is the number of times that component $i\in{\mathbb{Z}}_{+}$ appears, with $v_{i}$ being the counting variable associated with $i$.

Using the $B$-string of length $k$ enumerator, the following result for enumerating sequences with a certain number of occurrences of $B$ is shown in [21]:

By setting $v_{1}=v_{2}=\cdots=v$, this becomes equivalent to (6.3) since $\gamma_{j}(v{\bf 1})=m_{j}v^{j}$. A more generalized version of Theorem 6.2, known as the Goulden-Jackson cluster theorem, allows enumeration of adjacent components of any length (not just pairs), see [20, 19].

In the case of descents, treated Section 3, the above discussion does not apply directly, as since the background sequence is continuously distributed. However, this can be circumvented by considering the ranks in the partial sequence instead of the absolute values, hence it can be treated combinatorially as in [21, Section 2.4.21] by considering only permutations of $\{1,2,\cdots,n\}$ instead of all possible sequences.

An application of Corollary 6.1 can be found in [17].

To check this from Corollary 6.1, note first that the $1$-run probability generating function is $P(v)=1+\frac{1}{a^{2}}v$, hence the $B$-string generating function is $G(v)=1+av+v^{2}$. (6.6) is then proved by substitutions $k\to m,n-k\to n,v\to y,zv\to x$.