An urn model for the Jacobi-Piñeiro polynomials

Urn models for the flow of two incompressible liquids between two containers or for the exchange of heat between two isolated bodies, which are nowadays given as examples of finite state Markov chains, predate any formal introduction of these probabilistic notions and even a rigorous set-up for probability theory as given by A. Kolmogorov around 1930. Two celebrated examples are the Bernoulli-Laplace (1769-1812) and the Ehrenfest (1907, see [7]) models discussed in W. Feller’s book (see [8], pages 121 and 378).

At a much later time it was noticed that these physically motivated Markov chains can be analyzed completely in terms of families of orthogonal polynomials that occupy important places in the Askey-Wilson tableaux, namely Hahn and Krawtchouk polynomials. For an exposition of this see [10] and its references, or more recently the monograph [6].

The situation described above was part of the motivation for [11] where an urn model (albeit an elaborate one) was proposed for the Markov chain with an infinite number of states going with the Jacobi polynomials. In this case one is dealing with a discrete-time birth-death chain stemming from a semi-infinite tridiagonal matrix. This approach was adapted to the case of matrix-valued Jacobi polynomials (see [13, 14]) where one is dealing with a quasi-birth-and-death process (see [16, 5]). This results in a stochastic matrix that is a semi-infinite block tridiagonal matrix. The importance of studying different walks by means of “spectral methods” has been exploited beyond classical walks. In the case of quantum walks, results such as recurrence are related to spectral properties of a measure on the unit circle, see [15, 4].

In [12] a new idea was introduced and exploited: by using a stochastic LU (or UL) factorization of the stochastic matrix going with the Jacobi polynomials a much simpler model than the one in [11] was put forward. This idea has been adapted to other situations such as multivariate orthogonal polynomials (see [9]).

The purpose of this paper is to use the approach in [12] to give an urn model associated to the Jacobi-Piñeiro polynomials. They originate in [18] and give a basic example of so-called multiple orthogonal polynomials. For references on this kind of polynomials the reader can consult [18, 17, 1, 2]. These are polynomials in one variable indexed by two non-negative indices $(n_{1},n_{2})$. They give rise to a family of polynomials indexed by one non-negative index $n$ (see Proposition 9 of [3]) and these polynomials satisfy a higher-order recursion relation. The fact that this gives rise to a stochastic matrix has been recently pointed out in [3].

Let $\{X_{t}:t=0,1,\ldots\}$ be the Markov chain on $\mathbb{Z}_{\geq 0}$ with transition probability matrix given by the stochastic matrix $P_{II}$ which appears in Corollary 7 of [3]. Here we will denote by $P$ this matrix, which is associated with the type II Jacobi-Piñeiro multiple orthogonal polynomials. We also denote by $a_{n},b_{n},c_{n+1},d_{n+2},n\geq 0,$ the corresponding transition probabilities given by

Therefore $P$ is the semi-infinite banded matrix given by

A diagram of the transitions between the states is given by

Following [3], $P$ depends on three parameters $\alpha,\beta$ and $\gamma$, and it is stochastic if and only if $\alpha,\beta,\gamma>-1,\alpha\neq\beta$ and $|\alpha-\beta|<1$ (although the case $\alpha=\beta$ is allowed too, as we will see below). The matrix $P$ (2.2) admits a stochastic LU factorization, as in [12], of the form

where, for $n\geq 0$, we have

and

Notice that all the coefficients are nonnegative, $x_{n}+y_{n}=1$ and $t_{n}+s_{n}+r_{n}=1$ for $n\geq 0$, i.e. the matrices $P_{L}$ and $P_{U}$ are stochastic. Observe that the factor $P_{U}$ is a pure-birth chain on $\mathbb{Z}_{\geq 0}$ with diagram

while $P_{L}$ is a pure-death chain on $\mathbb{Z}_{\geq 0}$ with absorbing state at 0 with diagram

The factorization (2.3) gives the following relations among all coefficients

which is an alternative way of writing the transition probabilities appearing in Corollary 7 of [3]. Now we can see from the coefficients in (2.4)–(2.6) that the case $\alpha=\beta$ can be allowed (although it may be exceptional in terms of the Jacobi-Piñeiro polynomials).

In [3] one finds a different matrix $P_{I}$ going with the type I Jacobi-Piñeiro polynomials. Its shape is given as that of the transpose of the one in (2.2). The methods and models used here for $P_{II}$ can be easily extended to the matrix $P_{I}$.

In this section we assume $\alpha=1/M,\beta=1/N,\gamma\geq 0,M,N,\gamma\in\mathbb{Z}_{>0}$. The condition $|\alpha-\beta|<1$ is now equivalent to $|M-N|<MN$. After this substitution we have that the coefficients in (2.4), (2.5) and (2.6) are given, for $n\geq 0$, by

and

Consider the LU factorization $P=P_{L}P_{U}$ (2.3) where the entries of $P_{L}$ and $P_{U}$ are given in (3.1), (3.2) and (3.3). Each one of these matrices $P_{L}$ and $P_{U}$ will give rise to an experiment in terms of an urn model, which we call Experiment 1 and Experiment 2, respectively. At times $t=0,1,2,\ldots$ an urn A contains $m$ blue balls and this determines the state of our Markov chain at that time. Additionally, for Experiment 1, we will have two other urns, one painted in blue, which we call B, and the other one painted in red, which we call R. These auxiliary urns are initially empty and will be emptied after their use in going from one time step to the next. All the urns sit in a bath consisting of an infinite number of blue and red balls. These urns are not used in Experiment 2.

Let us consider first the (slighty simpler) Experiment 2 (for $P_{U}$), and let us call this chain $\{X_{t}^{(2)},t=0,1,\ldots\}$. Assume that urn A contains $m$ blue balls ($m\geq 0$) at time 0 (i.e. $X_{0}^{(2)}=m$). Consider first the case where $m$ is even and write $m=2n,n\geq 0$. Remove all the balls from urn A and place in A $M(2n+\gamma+1)$ blue balls and $M(n+1)+1$ red balls from the bath. Draw one ball from urn A at random with the uniform distribution. We have two possibilities:

• •

  If we get a blue ball then we remove into the bath or add from the bath balls until we have $m+1=2n+1$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(2)}=2n+1\,|\,X_{0}^{(2)}=2n\right)=\frac{M(2n+\gamma+1)}{3Mn+M\gamma+2M+1}.$$

  Observe that this probability is given by $x_{2n}$ in (3.1).

• •

  If we get a red ball then we remove into the bath or add from the bath balls until we have $m=2n$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(2)}=2n\,|\,X_{0}^{(2)}=2n\right)=\frac{M(n+1)+1}{3Mn+M\gamma+2M+1}.$$

  Observe that this probability is given by $y_{2n}$ in (3.1).

Consider now the case where $m$ is odd and write $m=2n+1,n\geq 0$. Remove all the balls from urn A and place in A $N(2n+\gamma+2)$ blue balls and $N(n+1)+1$ red balls from the bath. Draw one ball from urn A at random with the uniform distribution. We have two possibilities:

• •

  If we get a blue ball then we remove into the bath or add from the bath balls until we have $m+1=2n+2$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(2)}=2n+2\,|\,X_{0}^{(2)}=2n+1\right)=\frac{N(2n+\gamma+2)}{3Nn+N\gamma+3N+1}.$$

  Observe that this probability is given by $x_{2n+1}$ in (3.1).

• •

  If we get a red ball then we remove into the bath or add from the bath balls until we have $m=2n+1$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(2)}=2n+1\,|\,X_{0}^{(2)}=2n+1\right)=\frac{N(n+1)+1}{3Nn+N\gamma+3N+1}.$$

  Observe that this probability is given by $y_{2n+1}$ in (3.1).

Now we describe Experiment 1 (for $P_{L}$), and let us call this chain $\{X_{t}^{(1)},t=0,1,\ldots\}$. Recall that now we will use two auxiliary urns B and R which are initially empty and will be emptied after their use in each time step. Assume that urn A contains $m$ blue balls ($m\geq 0$) at time $0$. Consider first the case where $m$ is even and write $m=2n,n\geq 1$ (the state 0 is absorbing). Remove all balls from urn A and place in A $Mn$ blue balls and $2Mn+M\gamma+M+1$ red balls from the bath. In urn B we place $MNn+N-M$ blue balls and $M(2Nn+N\gamma+1)$ red balls. In urn R we place $Nn$ blue balls and $2Nn+N\gamma+N+1$ red balls. Draw one ball from urn A at random with the uniform distribution. If we get a blue ball then we go to urn B and draw a ball, while if we get a red ball then we go urn R and draw a ball. We have three possibilities:

• •

  If we get two blue balls in a row, i.e. one from urn A and then one from urn B, then we remove into the bath or add from the bath balls until we have $m-2=2n-2$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(1)}=2n-2\,|\,X_{0}^{(1)}=2n\right)=\frac{Mn}{3Mn+M\gamma+M+1}\cdot\frac{MNn+N-M}{N(3Mn+M\gamma+1)}.$$

  Observe that this probability is given by $t_{2n}$ in (3.2).

• •

  If we get two red balls in a row, i.e. one from urn A and then one from urn R, then we remove into the bath or add from the bath balls until we have $m=2n$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(1)}=2n\,|\,X_{0}^{(1)}=2n\right)=\frac{2Mn+M\gamma+M+1}{3Mn+M\gamma+M+1}\cdot\frac{2Nn+N\gamma+N+1}{3Nn+N\gamma+N+1}.$$

  Observe that this probability is given by $s_{2n}$ in (3.2).

• •

  If we get either a blue and a red ball or a red and a blue ball then we remove into the bath or add from the bath balls until we have $m-1=2n-1$ blue balls in urn A and start over. Therefore

  	$\displaystyle\mathbb{P}\left(X_{1}^{(1)}=2n-1\,|\,X_{0}^{(1)}=2n\right)$	$\displaystyle=\frac{Mn}{3Mn+M\gamma+M+1}\cdot\frac{M(2Nn+N\gamma+1)}{N(3Mn+M\gamma+1)}$
  		$\displaystyle\qquad\qquad+\frac{2Mn+M\gamma+M+1}{3Mn+M\gamma+M+1}\cdot\frac{Nn}{3Nn+N\gamma+N+1}.$

  Observe that this probability is given by $r_{2n}$ in (3.3).

Consider now the case where $m$ is odd and write $m=2n+1,n\geq 1$ (the simpler case $m=1$ will be treated separately). Remove all balls from urn A and place in urn A $Nn$ blue balls and $2Nn+N\gamma+2N+1$ red balls from the bath. In urn B we place $MNn+M-N$ blue balls and $N(2Mn+M\gamma+M+1)$ red balls. In urn R we place $M(n+1)$ blue balls and $2Mn+M\gamma+2M+1$ red balls. Draw one ball from urn A at random with the uniform distribution. If we get a blue ball then we go to urn B and draw a ball, while if we get a red ball then we go urn R and draw a ball. Again, we have three possibilities:

• •

  If we get two blue balls in a row, i.e. one from urn A and then one from urn B, then we remove into the bath or add from the bath balls until we have $m-2=2n-1$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(1)}=2n-1\,|\,X_{0}^{(1)}=2n+1\right)=\frac{Nn}{3Nn+N\gamma+2N+1}\cdot\frac{MNn+M-N}{M(3Nn+N\gamma+N+1)}.$$

  Observe that this probability is given by $t_{2n+1}$ in (3.2).

• •

  If we get two red balls in a row, i.e. one from urn A and then one from urn R, then we remove into the bath or add from the bath balls until we have $m=2n+1$ blue balls in urn A and start over. Therefore

  $$\mathbb{P}\left(X_{1}^{(1)}=2n+1\,|\,X_{0}^{(1)}=2n+1\right)=\frac{2Nn+N\gamma+2N+1}{3Nn+N\gamma+2N+1}\cdot\frac{2Mn+M\gamma+2M+1}{3Mn+M\gamma+3M+1}.$$

  Observe that this probability is given by $s_{2n+1}$ in (3.2).

• •

  If we get either a blue and a red ball or a red and a blue ball then we remove into the bath or add from the bath balls until we have $m-1=2n$ blue balls in urn A and start over. Therefore

  	$\displaystyle\mathbb{P}\left(X_{1}^{(1)}=2n\,|\,X_{0}^{(1)}=2n+1\right)$	$\displaystyle=\frac{Nn}{3Nn+N\gamma+2N+1}\cdot\frac{N(2Mn+M\gamma+M+1)}{M(3Nn+N\gamma+N+1)}$
  		$\displaystyle\qquad\qquad+\frac{2Nn+N\gamma+2N+1}{3Nn+N\gamma+2N+1}\cdot\frac{M(n+1)}{3Mn+M\gamma+3M+1}.$

  Observe that this probability is given by $r_{2n+1}$ in (3.3).

For the case $m=1$ we only need to place in urn A $M$ blue balls and $M\gamma+2M+1$ red balls and draw one ball at random. If we get a blue ball (with probability $r_{1}$ in (3.3)) then we remove all balls from urn A and stop (since the state $0$ is absorbing). If we get a red ball (with probability $s_{1}$ in (3.2)) then we leave only $1$ blue ball in urn A and start over.

The urn model going with $P$ (on $\mathbb{Z}_{\geq 0}$) is obtained by repeatedly alternating Experiments 1 and 2 in that order (see Figures 1 and 2 below, included here for the benefit of the reader). If we first perform Experiment 1 (for $m=2n$) we will end up with an urn with $2n-2,2n-1$ or $2n$ blue balls. Now we perform Experiment 2 starting with $2n-2,2n-1$ or $2n$ blue balls, in which case we may end with either $2n-1$ or $2n-2$ blue balls in the first case, $2n$ or $2n-1$ blue balls in the second case and $2n+1$ or $2n$ blue balls in the final third case. The situation is similar if we start with $m=2n+1$. We first perform Experiment 1 and we will end up with an urn with $2n-1,2n$ or $2n+1$ blue balls. Now we perform Experiment 2 starting with $2n-1,2n$ or $2n+1$ blue balls, in which case we may end with either $2n$ or $2n-1$ blue balls in the first case, $2n+1$ or $2n$ blue balls in the second case and $2n+2$ or $2n+1$ blue balls in the final third case. The combination of possibilities of these six cases yields the transition probabilities in (2.1) (see also (2.7)).