Multivariate Krawtchouk Polynomials and Composition Birth and Death Processes

Griffiths [1] and Diaconis and Griffiths [2] construct multivariate Krawtchouk polynomials orthogonal on the multinomial distribution and study their properties. Recent representations and derivations of the orthogonality of these polynomials are in [3,4,5,6].

The authors emphasise different approaches to the multivariate orthogonal polynomials. The approach of Diaconis and Griffiths [2] is probabilistic and directed to Markov chain applications; the approach of Iliev [5] is via Lie groups; and the physics approach of Genest et al. [3] is as matrix elements of group representations on oscillator states. Xu [7] studies discrete multivariate orthogonal polynomials, which have a triangular construction of products of one-dimensional orthogonal polynomials. They are particular cases of the polynomials in this paper; see Diaconis and Griffiths [2]. These polynomials extend the Krawtchouk polynomials on the binomial distribution to a general class of multi-dimensional orthogonal polynomials on the multinomial distribution. They appear naturally in composition Markov chains as eigenfunctions in a diagonal expansion of the transition functions. There are many interesting examples of these Markov chains in Zhou and Lange [8]. Binomial and multinomial random variables can be constructed as a sum of independent and identically distributed random variables, which are indicator functions of the events that occur on each of N trials. The Krawtchouk and multivariate Krawtchouk polynomials are symmetric functions of orthogonal functions sets on each of the trials. The simplest case is the Krawtchouk polynomials where the representation is explained in Section 2. In the multivariate Krawtchouk polynomials, there is not a unique orthogonal function set on trials with multiple outcomes greater than two, so the polynomials depend on which orthogonal function set is taken for a basis on the trials.

A well-known spectral expansion by Karlin and McGregor [9,10,11] for the transition functions ${\left\{p_{ij}\left(t\right)\right\}}_{i,j=0}^{\infty }$ of a birth and death process with rates ${\lambda }_i,{\mu }_i$, $i=0,1,\dots$ is that: where ${\left\{Q_i\right\}}_{i=1}^{\infty }$ are orthogonal polynomials on the spectral measure ψ, which is a probability measure, and:

A number of classical birth and death processes have a spectral expansion where the orthogonal polynomials are constructed from the Meixner class. This class has a generating function of the form: where $h\left(v\right)$ is a power series in t with $h\left(0\right)=1$ and $u\left(v\right)$ is a power series with $u\left(0\right)=0$ and $u^{\prime }\left(0\right)\ne 0$. Meixner [12] characterizes the class of weight functions and orthogonal polynomials with the generating function Equation (3). They include the Krawtchouk polynomials, Poisson–Charlier polynomials, scaled Meixner polynomials and Laguerre polynomials (the Meixner orthogonal polynomials are a specific set belonging to the Meixner class with a name in common). A general reference to these orthogonal polynomials is Ismail [13].

In this paper, the spectral expansion is extended to composition birth and death processes, where there are N independent and identically distributed birth and death processes operating and ${\left\{X\left(t\right)\right\}}_{t\ge 0}$ is such that the i-th element ${\left\{X_i\left(t\right)\right\}}_{t\ge 0}$ counts the number of processes in state i at time t. In the analogue of Equation (1), the spectral polynomials are the dual multivariate Krawtchouk polynomials. The dual polynomial system is therefore very important, and attention is paid to describing it.

There are extensions of the multivariate Krawtchouk polynomials to multivariate orthogonal polynomials on the multivariate Meixner distribution and multivariate product Poisson distribution, where they occur as eigenfunctions of multi-type birth and death processes [14].

This paper defines the multivariate Krawtchouk polynomials, summarizes their properties, then considers how they are found in spectral expansions of composition birth and death processes. It is partly a review of these polynomials and is self-contained. For a fuller treatment, see Diaconis and Griffiths [15]. The polynomials are naturally defined by a generating function, and so, generating function techniques are used extensively in the paper. Probabilistic notation is used, particularly the expectation operator $\mathbb{E}$, which is a linear operator acting on functions of random variables, which take discrete values in this paper. If $X_1,\dots ,X_d$ are random variables, then:

Often, orthogonal polynomials are regarded as random variables. For example, ${\left\{K_n(X;N,p)\right\}}_{n=0}^N$ are the one-dimensional Krawtchouk polynomials as random variables and: where $q=1-p$. A convention of using capital letters for random variables and lower case for values that they take is used, except when the random variables are denoted by Greek letters, when they have to be considered in context.

Section 2, Theorem 1, shows how the Krawtchouk polynomials can be expressed as elementary symmetric functions of N Bernoulli trials, centred at their mean p. The Meixner orthogonal polynomials on the geometric distribution are also expressed as functions of an infinity of centred Bernoulli trials in Theorem 2. There is some, but not total symmetry in this expression. Krawtchouk polynomials occur naturally as eigenfunctions in Ehrenfest urn processes, and the eigenfunction expansion of their transition functions is explained in Section 2.3. Section 3 introduces the multivariate Krawtchouk polynomials, explaining how they are constructed in a symmetric way from a product set of orthogonal functions on N independent multinomial trials. The dual orthogonal system is described and a scaling found, so that they are multivariate Krawtchouk polynomials on a different multinomial distribution in Theorem 3. The polynomial structure of the multivariate Krawtchouk polynomials is described in Theorem 4 and the structure in the dual system in Theorem 5. Recurrence relationships are found for the system in Theorem 6 and for the dual system in Theorem 7. The dual recurrence relationship is used to identify the polynomials as eigenfunctions in a d-type Ehrenfest urn in Theorem 8. In Section 3.2, a new extension is made to multivariate Krawtchouk polynomials where there are an infinite number of possibilities in each multinomial trial. These polynomials occur naturally as eigenfunctions in composition birth and death processes in a Karlin and McGregor spectral expansion in Theorem 9. Theorem 10 considers the polynomial structure of the dual polynomials in the spectral expansion. Theorem 11 gives an interesting identity for these spectral polynomials in composition birth and death processes when the spectral polynomials in the individual processes belong to the Meixner class.

The paper begins with expressing the one-dimensional Krawtchouk polynomials as symmetric functions of Bernoulli trials. The multivariate Krawtchouk polynomials are extensions of this construction in higher dimensions.

The multivariate Krawtchouk polynomials with elementary basis u were first constructed by Griffiths [1]. A recent introduction to them is Diaconis and Griffiths [2]. They play an important role in the spectral expansion of transition functions of composition Markov processes. Zhou and Lange [8], Khare and Zhou [16] have many interesting examples of such Markov processes. Later in this paper, we consider the particular composition processes where there are N particles independently performing birth and death processes.

The multivariate Krawtchouk polynomials are orthogonal on the multinomial distribution: with $\mathit{p}={\left\{p_j\right\}}_{j=1}^d$ a probability distribution. Let $J_1,\dots ,J_N$ be independent and identically distributed random variables specifying outcomes on the N trials, such that:

Then:

Let $\mathit{u}={\left\{u^{\left(l\right)}\right\}}_{l=0}^{d-1}$ be an orthogonal set of functions on $\mathit{p}={\left\{p_k\right\}}_{k=1}^d$ with $u^{\left(0\right)}=1$ satisfying:

This notation for the orthogonal set of functions follows Lancaster [17]. There is an equivalence that: are elements of a $d\times d$ orthogonal matrix H. In this paper, ${\left\{u^{\left(l\right)}\right\}}_{l=0}^{d-1}$ are usually orthonormal functions with $a_l=1$, $l=0,1,\dots ,d-1$, unless stated otherwise. The one-dimensional Krawtchouk polynomials are constructed from a symmetrized product set of orthogonal functions $⨂{\{1,{\xi }_i-p\}}_{i=1}^N$, and the construction of the multivariate polynomials follows a similar, but more complicated procedure. Instead of having two unique elements in each orthogonal function set, there is a choice of orthogonal basis, and the construction is from the product set ${⨂}_{i=1}^N{\left\{u_{J_i}^{\left(l_i\right)}\right\}}_{l_i=0}^{d-1}$. The orthogonality Equation (25) is equivalent to: for $k=1,\dots ,N$. Define a collection of orthogonal polynomials $\left\{Q_{\mathit{n}}(\mathit{X};\mathit{u})\right\}$ with $\mathit{n}=(n_1,\dots n_{d-1})$ and $\left|\mathit{n}\right|\le N$ on the multinomial distribution as symmetrized elements from the product set, such that the sum is over products $u_{J_1}^{\left(l_1\right)}\cdots u_{J_N}^{\left(l_N\right)}$ with $n_k=\left|\{l_i:l_i=k,k=1,\dots ,N\}\right|$ for $k=1,\dots ,d-1$. $Q_{\mathit{n}}(\mathit{X};\mathit{u})$ is the coefficient of $w_1^{n_1}\cdots w_{d-1}^{n_{d-1}}$ in the generating function:

In the one-dimensional case $u_1^{\left(1\right)}=0-p_1=-p_1$, $u_2^{\left(1\right)}=1-p_1$, orthogonal on $1-p_1,p_1$, so the generating function is: which is, of course, the generating function of the Krawtchouk polynomials. $x_1,x_2$ are respectively the number of zero and one values in the N trials. It is straightforward to show, by using the generating function Equation (28), that: where ${\mathit{n}}^{+}=(n_0,\dots ,n_{d-1})$, with $n_0=N-{\sum }_{j=1}^{d-1}{n}_j$. Instead of indexing the polynomials by $\mathit{n}=(n_1,\dots ,n_{d-1})$, they could be indexed by ${\mathit{n}}^{+}$. This notation is sometimes convenient to use in the paper. The dual orthogonality relationship is, immediately from Equation (30),

Expanding the generating function Equation (28) shows that: where · indicates summation over an index and $a_{\left[b\right]}=a(a-1)\cdots (a-b+1)$ for non-negative integers b. The dual generating function is:

Expanding the generating function:

The two generating function Equations (28) and (33) are similar, and there is a form of self-duality for the polynomials. Let:

Then, because of Equation (25):

The right side of Equation (33) is equal to: which, apart from the different indexing and non-constant function ${\omega }^{\left(0\right)}$, generates multivariate Krawtchouk polynomials. Suppose that ${\omega }_i^{\left(0\right)}\ne 0$ for $i=1,\dots ,d$. Scale by letting ${\widehat{\omega }}_i^{\left(j\right)}={\omega }_i^{\left(j\right)}/{\omega }_i^{\left(0\right)}$, so that ${\widehat{\omega }}_i^{\left(0\right)}=1$. The orthogonality of these functions is:

Let $b={\left\{b_l\right\}}_{l=1}^d$ be the scaled probability distribution of ${\left\{a_{l-1}^{-1}{{\omega }_l^{\left(0\right)}}^2\right\}}_{l=1}^d$, so:

The following theorem is evident from Equations (33) and (37), once the indexing is sorted out.

There is an interesting identity when u is self-dual with an indexing of j beginning from zero instead of one. That is: Then indexing $\mathit{x}=(x_0,\dots ,x_n)$, where ${u_j^{\left(l\right)}}^{*}=u_l^{\left(j\right)}$. This duality occurs in the scaled Krawtchouk polynomial basis, orthogonal on a binomial $(n,p)$ distribution.

The emphasis in Theorem 3 is on considering the dual system, obtaining $\widehat{\mathit{\omega }}$ from u; however, sometimes, it is natural to construct u from an orthogonal set $\widehat{\mathit{\omega }}$, particularly when ${\omega }_i^{\left(0\right)}=1$, $i=1,\dots ,d$ and $\widehat{\mathit{\omega }}=\mathit{\omega }$. Then, the polynomials on the left of Equation (40) are defined by the dual polynomials on the right. Later in the paper, it will be seen that this is natural in composition birth and death Markov processes.

The polynomial structure of the multivariate Krawtchouk polynomials is detailed in the next theorem.

This transform is easily found by taking the transform of the generating function Equation (28). One can see directly that $Q_{\mathit{n}}(\mathit{X};\mathit{u})$ is an orthogonal polynomial by considering the transform:

From Equations (43) and (45), $Q_n\left(x\right)$ is a polynomial of degree $\left|n\right|$, whose only leading term is:

This is seen by noting that the leading term is found by replacing ${\varphi }_j{p}_j$ by $X_j$ in:

Since we can replace ${X_j}_{\left[k_j\right]}$ by $X^{k_j}$ in considering the leading term of Equation (43) and setting ${\varphi }_i=1$ for $i=1,\dots ,d$. ☐

The next theorem explains the polynomial structure in the dual system.

There are recurrence relationships for the multivariate Krawtchouk polynomials, which are found here from a generating function approach; for another different proof, see Theorem 6.1 in Iliev [5]. Note that his multivariate Krawtchouk polynomials are scaled differently as

In Theorems 6–8, u is taken to be orthonormal on p, so $a_l=1$, $l=0,1,\dots d-1$ in Equation (25).

Equating coefficients of ${\prod }_1^{d-1}{w}_j^{n_j}{\prod }_1^{d-1}{z}_j^{n_j^{\prime }}$;

The first recursive Equation (49) then follows by an expansion of $x_j{Q}_{\mathit{n}}(\mathit{x};\mathit{u})$ as a series in $Q_{{\mathit{n}}^{\prime }}(\mathit{x};\mathit{u})$ dividing the cases in Equation (52) to obtain the coefficients by:

The second recursion Equation (50) is found by summation, using the orthogonality of u. ☐

The dual orthogonal system when u is orthonormal is:

A dual generating function is:

The generating function Equation (55) arises from considering the coefficient of ${\prod }_{i=1}^{d-1}{w}_i^{n_i}$ in:

Therefore, non-zero terms with $\mathit{y}=\mathit{x}-{\mathit{e}}_j+{\mathit{e}}_l$ are:

The dual recurrence is therefore Equation (57). ☐

The reproducing kernel polynomials: are invariant under which set of orthonormal functions u is used. They have an explicit form; see Diaconis and Griffiths [2] and Xu [7] for details.