数理解析研究所講究録
1193 巻 2001 年 79-103

79

ASYMPTOTIC BEHAVIOR OF
CONTINUOUS-TIME MARKOV CHAINS OF
THE EHRENFEST TYPE WITH APPLICATIONS*
神奈川大学 工学部 成田清正 (Kiyomasa Narita)

Faculty of Engineering, Kanagawa Univ.
Abstract

Kac [6] considers the discrete-time Markov chain for the original Ehrenfest urn model andgives the expression of the -step transition probabilities in terms of the Krawtchouk polynomials; moreover, Kac’s formulas for transition laws show that the model yields Newton’s law ofcooling at the level of the evolution of the averages. Here we first give a version of Newton’s lawof cooling for Dette’s [4] Ehrenfest urn model. We next discuss the continuous-time formulationof Markov chain for Krafft and Schaefer’s [9] Ehrenfest urn model and calculate probability lawof transitions and first-passage times in both the reduced description with states counting thenumber of balls in the specified urn and the full description with states enumerating the verticesof the $N$ -cube. Our results correspond to a generalization of the work of Bingham [3]. We also
treat several applications of urn models to queueing network and reliability theory.
$n$

1. Introduction

Let and be two parameters such that $0<s=<1$ and $0<t=<1$ , and consider the
homogeneous Markov chain with state $\{0,1, \ldots , N\}$ and transition probabilities
.
$s$

$t$

$(1- \frac{i}{N})s$$\frac{i}{N}t$

if $j=i+1.$ ’,

if $j=i-1$ ,

,

(1.1)

$p_{ij}=\{$$1-(1- \frac{i}{N})s-\frac{i}{N}t$$0$,, if $j=i$ ,$0<<=^{j}=^{N}$’

otherwise,

which is proposed by Krafft and Schaefer [9]. In case $s=t=1$ , the Markov chain is
the same as P. and T. Ehrenfest [5] use for illustration of the process of heat exchange
between two bodies that are in contact and insulated from the outside. The temperatures
are assumed to change in steps of one unit and are represented by the numbers of balls$N$in two urns. The two urns are marked I and II and there are $N$ balls labeled 1, 2, . . . ,and distributed in two urns. The chain is in state when there are balls in I. At eachpoint of time one ball is chosen at random (i.e. with equal probabilities $1/N$ among ball
$i$

$i$

$n$

*This research was supported in part by$\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{t}_{-}\mathrm{i}\mathrm{n}_{-\mathrm{A}\mathrm{i}}\mathrm{d}$The Ministry of Education, Science, Sports and Culture.

for General Scientific Research (No. 10640138),

80
numbers 1, 2, . . . , $N$ ) and moved from its urn to other urn by the following way. If it isin urn I, it is placed in II with probability and returned to I with probability l-t. If it
is in , it is placed in I with probability and returned to II with probability l-s. The
case where $s+t=1$ is the one-parameter Ehrenfest urn model as investigated by Karlinand. The case where $s=t$ is the thinning of the Ehrenfest urn model as
proposed by Vincze [14] and Tak\’acs [13].
Remark 1.1. The process of the Markov chain in the model (1.1) corresponds to a$N$‘reduced description’ with $N+1$ states, $0,1,$
counting the number of balls in urn
I. If we use a ‘full description’ withstates, representing the possible configurations by$N$-tuples $i=$
, where $i_{k}=1,0$ if ball is in urn I, II, respectively, one
may identify the states with the vertices of the N-cube.
Let and denote real numbers such that $b>-1$ or $b<-N$ , and consider
the following homogeneous Morkov chain with state space $\{0,1, \ldots , N\}$ and transition
probabilities
$t$

$\Pi$

$s$

$\mathrm{M}\mathrm{c}\mathrm{G}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{o}\mathrm{r}[7]$$\cdots,$$2^{N}$$(i_{1}, \ldots, i_{k}, \ldots , i_{N})$

$k$

$b$

$a$

$a,$

,

if $j=i+1$ ,$(1- \frac{i}{N})(\frac{a+1+i}{N+a+b+2})l\text{ノ}$$\frac{i}{N}(\frac{N+b+1-i}{N+a+b+2})\nu$

$a,$

,

if $j=i-1$ ,(1.2)$p_{ij}=\{$, if $j=i$ ,$1-(1- \frac{i}{N})(\frac{a+1+i}{N+a+b+2})$ $l \text{ノ}-\frac{i}{N}(\frac{N+b+1-i}{N+a+b+2})l^{\text{ノ}}$$0$,otherwise,$N$ .
where $\nu>0$ is arbitrary such that $0=^{pij=^{1}}<<$ for all $i,j=0,1,$
Remark 1.2. The two-parameter Ehrenfest urn model (1.1) is obtained by putting$a=su/(s+t),$ $b=tu/(s+t)$ and $\nu=s+t$ and taking the limit as.
For the model (1.2), Dette [4] obtains the more general integral representations for the-step transition probabilities and the (unique) stationary probability distribution withrespect to the spectral measure of random walk and shows the following remark.
Remark 1.3.
(i) The -step transition probabilities
in the model (1.1) are given by$\ldots,$$uarrow\infty$

$n$

$n$

$p_{ik}^{(n)}$$p_{ik}^{(n)}=( \frac{p}{q})^{k}\sum_{=x\mathrm{o}}^{N}p^{x}q^{N\prime}-x_{I\iota(X}i,p,$ $N)I\mathrm{i}_{k}(’)x,p,$$N(1- \frac{s+t}{N}X)^{n}$,where $p=s/(s+t)$ and $q=t/(s+t)$ . Here $\{K_{n}(x,p, N) : n=0,1, \ldots, N\}$ is the familyof Krawtchouk polynomials, which will appear in Remark 1.4 below. This result is also
found by Krafft and Schaefer [9].
(ii) The (unique) stationary probability distribution
in the model (1.2)
is given by$\pi=(\pi_{0}, \ldots , \pi_{N})$$\pi_{j}=\frac{\beta(a+1+j,N+b+1-j)}{\beta(a+1,b+1)}$

where$\beta(x, y)$,denotes the beta function, that is,$\beta(x, y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}=\int_{0}^{1}u^{x-1}(1-u)^{y-}1du$

for

$x,$

$y>0$ .

81
For the model (1.1) with $s=t=1$ , Kac [6] finds the same form with (i) of Remark 1.3
and shows Newton’s law of cooling that concerns the estimate of the excess of the numbersof balls in urn I over the mean of the stationary probability distribution.
Our purpose is the following:
For the model (1.2), we will show the same result with Newton’s law of cooling[Theorem 2.1].
For the model (1.1), we will give the continuous-time formulation and obtain thelaw of transition probabilities and first-passage times in both the ‘reduced’ and the ‘full’descriptions, using the method of Bingham [3] [Theorems 2.2-2.3].
Remark 1.4. With $0<p=1-q<1$ and integer $N>=0$ the Krawtchouk polynomials
are defined by the hypergeometric series:$\bullet$$\bullet$$K_{n}(x,p, N)$$=$$2F1(-n, -x;-N;1/p)$$=$$\sum_{\nu=0}^{n}(-1)^{\nu}\frac{(\begin{array}{l}n\nu\end{array})(\begin{array}{l}x\nu\end{array})}{(\begin{array}{l}N\nu\end{array})}(\frac{1}{p})^{\nu}$,$n=0,1,$$\ldots,$$N$.

When the meaning is clear, we write simply $K_{n}(x)$ instead of $K_{n}(x,p, N)$ . From Karlin
and
we cite the properties for, which will be used in after sections.
$\mathrm{M}_{\mathrm{C}}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{g}_{\mathrm{o}\mathrm{r}}[7]$$I_{\mathrm{L}_{n}}’(X)$(i)$\sum_{n=0}^{N}I\mathrm{i}_{n}’(X)_{Z}n=(1+z)N-x(1-\frac{q}{p}Z)^{x}$(ii)$I\mathrm{i}_{n}^{r}(0)=1$(iii)$I\mathrm{i}_{n}^{\Gamma}(x, p, N)=I\mathrm{i}_{x}^{r}(n,p, N)$

(iv)

,

$I\mathrm{i}_{0}^{r}(x)=1$,$x=0,1,$$\ldots,$

$N$

.

.

,

$n,$

$x=0,1,$$N$$\ldots,$$I \mathrm{i}_{n}^{r}(N-x, p, N)=(-1)^{n}(\frac{q}{p})^{n}I\iota_{n}’(x, q, N)$.

.

2. Theorems

We first concern ourselves with evaluation of the excess of the number of balls in urn I
over the value averaged by the stationary probability distribution for the model (1.2).
Theorem 2.1. Let $\{X_{n} : n=0,1, \ldots\}$ be the Markov chain with transition probabilities(1.2) with $a>-1$ and $b>-1$ . Let $\pi=(\pi_{0}, \ldots , \pi_{N})$ be the stationary probabilitity
distribution given by (ii) of Remark 1.3, and denote $by<\pi>the$ mean of , that is,$< \pi>=\sum_{j0}^{N}=j\pi_{j}$ . Set $Y_{n}=X_{n}-<\pi>and$
put $e_{n}=E_{i}(Y_{n})$ , that is, the expected valueof given $X_{0}=i$ . Then we have the following:$\pi$$Y_{n}$(i)$< \pi>=N(\frac{a+1}{a+b+2})$

.

82

(ii)

$e_{n}=(i-< \pi>)[1-\nu(\frac{a+b+2}{N(N+a+b+2)})]^{n}$Remark 2.1. Suppose that the frequency of transitions isthere are $n=T\tau$ transitions. Write$\tau$.

per second. Then in time$T$$c=- \log[1-\nu(\frac{a+b+2}{N(N+a+b+2)})]^{\mathcal{T}}$Then (ii) of the above theorem yields$e_{n}=(i-<\pi>)\exp[-cT]$ .

Let

$a,$

$b$

and

$\nu$

be taken as in Remark 1.2. Then$< \pi>arrow N(\frac{s}{s+t})$in the limit as(2.1)$uarrow\infty$

andl–v $( \frac{a+b+2}{N(N+a+b+2)})arrow 1-\frac{s+t}{N}$, which showswith$e_{n}= \{i-N(\frac{s}{s+t})\}\exp[-C\tau]$$c=- \log[1-\frac{s+t}{N}]^{\tau}$(2.2)

Newton’s law of cooling in Kac [6] is the special case of (2.2) where $s=t=1$ .
Remark 2.2. Consider the Markov chain $\{X_{n} : n=0,1, \ldots\}$ for the model (1.2) with
$a=-N-1-l$ and $b=-N-1-k$ , where and are nonnegative integers. Then,as follows from Dette [4], the stationary probability distribution is the hypergeometric
distribution:$k$$\pi_{j}=\frac{(\begin{array}{l}N+lj\end{array})(\begin{array}{l}N+kN-j\end{array})}{(\begin{array}{l}2N+\iota_{+}kN\end{array})}$,$l$$j=0,1,$$\ldots,$$N$,by the same way as, define
having its mean $< \pi>=\sum_{j=0}^{N}j\pi_{j}=N(\frac{N+l}{2N+l+k})$ . For
that in Theorem 2.1. Then a straightforward calculation as taken in the proofs of (i) of
Theorem 2.1 and Remark 2.1 leads us to the following result:$X_{n}$$e_{n}$$e_{n}=E_{i}[x_{n}-< \pi>]=(i-<\pi>)[1-\nu(\frac{2N+l+k}{N(N+\iota+k)})]^{n}$$e_{n}=(i--<\pi>)\exp[-cT]$with$c=- \log[1-\nu(\frac{2N+l+k}{N(N+l+k)})]^{\tau}$

Namely, Theorem 2.1 and Remark 2.1 hold for the model (1.2) with the choice$a=-N-1-^{\iota}$
and $b=-N-1-k$ .
In the following, let us consider the two-parameter Ehrenfest urn model (1.1). Thenwe will give the continuous-time formulation for this model.
We first consider the reduced description in continuous-time. Let $X(u)$ be the number

83
of balls in urn I at time . We shall sometimes speak of this number as the state of thesystem. Then $X(u)$ is a random function which can take integer values from to $N$ .
Associate with theball a random function $X_{i}(u)$ defined as follows:
$u$

$0$

$i\mathrm{t}\mathrm{h}$$X_{i}(u)=1$$X_{i}(u)=0$

if the th ball is in urn I at the time ,otherwise.
$i$

$u$

(2.3)

Assumption 2.1. The family $\{X_{i}(u) : i=1,2, \ldots , N\}$ of random functions are independent. Each $X_{i}(u)$ is a Markov process with continuous-time parameter $u_{=}>0$ on thestate space $\{0,1\}$ and governed by the following -matrix (infinitesimal generator):
$Q$

$Q=$

.

Remark 2.3. Under Assumption 2.1, the transition probability matrix $\exp[uQ]$ is given
by

where
$p_{00}(u)=q+p\exp[-(S+t)u/N]$ ,$p_{10}(u)=q-q\exp[-(s+t)u/N]$ ,$p_{01}(u)=p-p\exp[-(s+t)u/N]$ ,$p_{11}(u)=p+q\exp[-(S+t)u/N]$ ,with parameters $0<s,$ $t<1=’ p=s/(s+t)$ and $q=t/(s+t)$ .
Since $X(u)$ is the number of balls in urn I, we note that $X(u)= \sum_{i=1}^{N}x_{i}(u)$ .
Suppose that initially there areballs in urn I and the trials are independent.
Then {X $(u)$ : $u_{=}>0$ } is a homogeneous Markov chain with state space $\{0,1, \ldots, N\}$ andtransition probabilities$X(\mathrm{O})$$P_{ik}(u)=P(X(u)=k|X(\mathrm{O})=i)$ ,$i,$$k=0,1,$$\ldots$

, N.

(2.4)

Secondly we consider the continuous-time Markov chain in the full description. For
this process write$\overline{X}(u)=(X_{1}(u), x_{2}(u),$$\ldots$, $X_{N}(u))$ ,where $X_{i}(u)$ is given by (2.3), and put$\overline{P}_{ij}(u)=P(\tilde{X}(u)=j|\overline{X}(0)=i)$,$i,j\in V$,(2.5)

where is the vertex-set. Then we obtain the next theorem.
Theorem 2.2. Under Assumption 2.1, we have the following:(i) In the full
the transition probabilities (2.5) are given by$V$$d_{eSC}\dot{n}pti_{\mathit{0}}nf$$\overline{P}_{ij}(u)=\frac{1}{2^{N}}[p_{0}\mathrm{o}(u)+p_{11}(u)]^{N-m}$$[$

pol $(u)+p_{1}\mathrm{o}(u)]^{m}$ ,$m=|i-j|$ ,84$p_{0}1(u),$whereand $p_{11}(u)$ are the functions as given in Remark 2.3, and for-tuples $i=(i_{1}, \ldots, i_{k}, \ldots, i_{N})$ and $j=(j_{1}, \ldots,j_{k}, \ldots , j_{N})$ , the distance $|i-j|ofj$ fromis defined by $|i-j|= \sum_{k=1}^{N}|i_{k}-j_{k}|$ .
(ii) In the reduced
the transition probabilities (2.4) are given by$p\mathrm{o}0(u),$$p1\mathrm{o}(u)$

$N$
$i$

$d_{esC}ripti_{on_{J}}$$P_{ik}(u)=( \frac{p}{q})^{k}\sum_{=x0}^{N}p^{x}q^{N\prime}-x_{Ic_{i}}(x,p, N)\mathrm{A}_{k}(x,p, N)\exp[-X(S+t)u/N]$,

where $K_{n}(x,p, N)|$ are the Krawtchouk polynomials as given in Remark 1.4.
Remark 2.4. Bingham [3] shows Theorem 2.2 for the particular case where $s=t=1$(i.e. $p=q= \frac{1}{2}$ ). The form (i) of Remark 1.3 in the discrete-time parameter is a corollaryof Theorem 2.2. Indeed, we condition on the total number of transitions in $[0, u]$ , which
is Poisson with parameter :$u$$P_{ik}(u)= \sum_{=n0}\overline{p}ik(n)e-u\frac{u^{n}}{n!}\infty$

,

where
stand for the -step transition probabilities in the discrete-time chain. Then,by (ii) of Theorem 2.2 we see$\overline{p}_{ik}(n)$$n$$\sum_{n=0}^{\infty}\overline{p}_{ik}(n)\frac{u^{n}}{n!}=P_{ik}(u)eu$$=( \frac{p}{q})^{k}\sum_{x=0}^{N}p^{x}q^{N-x_{K_{i}(x,N}}p,)Kk(x,p, N)\exp[\{1-X(S+t)/N\}u]$ .

Equating the coefficients of, we get the form ofwhich is just the same
expression with (i) of Remark 1.3.
Lastly, consider the Markov chain with transition probabilities (1.1) in the reduced
description of the random walk on the $N$ -cube in discrete-time, starting at the origin(state ). By
denote the first-passage time to the opposite vertex (state $N$ ), and let$F_{0N}(Z)$ andbe the probability generating function and the mean of, respectively:$0$$u^{n}/n!$$\overline{p}_{ik}(n)$$\tau_{0N}$$\tau_{0N}$$\mu_{0N}$$F_{\mathit{0}N}(Z)=E[z^{T_{0N}}]$and $\mu 0N=E[T_{0N}]$ .

Let
be the continuous-time analogue of. By
Stieltjes transform and mean of, repectively:$\overline{\tau}_{0N}$$\tau_{0N}$$\overline{F}_{\mathit{0}N}(Z)$and$\overline{\mu}_{0N}$

denote the Laplace-$\overline{\tau}_{0N}$$\overline{F}_{\mathit{0}N}(z)=E[\exp(-Z\tilde{\tau}_{0}N)]$and$\tilde{\mu}0N=E[\overline{T}_{0N}]$.

Then we will investigate the asymptotics of the first passage to the opposite vertex as $N$
increases, extending the theorem of Bingham [3].
Theorem 2.3. Consider the model (1.1). Put$p= \frac{s}{s+t}$,$q= \frac{t}{s+t}$

and$\lambda=\frac{s+t}{N}$.

In (iv), (v) and (vi) below, suppose that $s_{=}<t$ . Then we have the following:

85

(i)

$F_{0N}(_{Z)}=[ \sum_{x=0}^{N}(-1)^{x}\{\frac{1}{1-z(1-\lambda X)}\}]$$\cross[\sum_{x=0}^{N}(\frac{q}{p})^{x}\{\frac{1}{1-z(1-\lambda_{X})}\}]^{-1}$(ii)$\overline{F}_{0N}(z)=F_{0}N(\frac{1}{1+z})=[\sum_{x=^{0}}^{N}(-1)^{x}\{\frac{1}{z+\lambda x}\}]$$\mathrm{x}[\sum_{x=0}^{N}(\frac{q}{p})^{x}\{\frac{1}{z+\lambda x}\}]^{-1}$(iii)$\mu \mathit{0}N=\overline{\mu}0N$(iv)$\mu_{\mathit{0}N}=\frac{1}{\lambda}\sum_{=x1}^{N}[(\frac{q}{p})^{x}-(-1)^{x}]\frac{1}{x}$.

(v)

For large $N,$(vi)$(tp^{N})\tau_{0}N$$\mu_{0N}\sim\frac{1}{tp^{N}}$.

.

converges in distribution to the exponential distribution withparameter 1 as $Narrow\infty$ .

3. Proof of Theorem 2.1(i) Write
bution $\pi=$$\square (z)$for the probability generating function of the stationary probability distrithat is given in (ii) of Remark 1.3:$(\pi_{0}, \ldots , \pi_{N})$$\square (z)=\sum_{j=0}^{N}\pi_{j^{Z}}j=\frac{1}{\beta(a+1,b\dagger 1)}\int_{0}^{1}u^{a}(1-u)b\{zu+(1-u)\}^{N}du$with constants$a,$$b>-1$ , where $\beta(x, y)=\Gamma(x)\Gamma(y)/\Gamma(x+y)$ .

From this we calculate the differential coefficient $\Pi’(1)$ and obtain the result.
(ii) First of all we rewrite (1.2) as follows:$p_{i,i+1}= \frac{\nu}{N(N+a+b+2)}\{N(a+1)+(N-a-1)i-i^{2}\}$ ,$p_{i,i-1}= \frac{\iota \text{ノ}{N(N+a+b+2)}}\{(N+b+1)i-i^{2}\}$,$p_{i,i}=1- \frac{\nu}{N(N+a+b+2\mathrm{I}}\{N(a+1)+(2N-a+b)i-2i^{2}\}$ .

86
So, a straightforward calculation yields$(i+1)\cdot pi,i+1+(i-1)\cdot pi,i-1+i\cdot p_{i,i}$$=i+ \frac{\nu}{N(N+a+b+2)}\{N(a+1)-(a+b+2)i\}$ .

(3.1)

For the Markov chain with transition probabilities (1.2), let $E(X_{n}|X_{n-1})$ be the conditional expectation of. Then (3.1) implies
given$X_{n}$$X_{n-1}$$E(X_{n}|X_{n-1})=X_{n-1}+ \frac{\nu}{N(N+a+b+2)}\{N(a+1)-(a+b+2)X_{n-1}\}$ ,and so(3.2)$E(X_{n}|X_{n-1})-x_{n-1}=- \nu(\frac{a+b+2}{N(N+a+b+2)})\{X_{n-1}-<\pi>\}$with $< \pi>=N(\frac{a+1}{a+b+2})$ . For $Y_{n}=X_{n}-<\pi>$ , set, that is, the expectedvalue of given $X_{0}=i$ . Then, taking note of that $E_{i}(X_{n}-X_{n}-1)=E_{i}[E(X_{n}|X_{n-1})-$$X_{n-1}]$ , by (3.2) we can calculate as follows:$e_{n}=E_{i}(\mathrm{Y}_{n})$$Y_{n}$$e_{n}=E_{i}(x_{n}-<\pi>)=E_{i}[(X_{n-1}-<\pi>)+(X_{n}-X_{n}-1)]$$=E_{i}(X_{n-1}-<\pi>)+E_{i}(X-nxn-1)$$=e_{n-1^{-\mathcal{U}}}( \frac{a+b+2}{N(N+a+b+2)})E_{i}(x_{n}-1-<\pi>)$$=[1- \nu(\frac{a+b+2}{N(N+a+b+2)})]e_{n-1}$ .

Thus, by successive applications of the above relation, we get$e_{n}=[1- \nu(\frac{a+b+2}{N(N+a+b+2)})]^{n}e_{0}$,where $e_{0}=E_{i}(X_{0^{-}}<\pi>)=i-<\pi>_{\alpha}$Hence the proof is complete.
4. Proof of Theorem 2.2(i) Consider the matrix
withgiven by (2.5). Then we must verify
thatis a stochastic matrix, satisfying, where is the identity
asmatrix. By (2.3) and Remark 2.3 it is easy to see that the transition probabilities
can be expressed by the form of (i). Since for each there are
we have$\overline{P}(u)=(\overline{P}_{ij}(u))$$\overline{P}(u)$$\overline{P}_{ij}(u)$$\overline{P}(u)arrow I$$I$$uarrow \mathrm{O}$$\overline{P}_{ij}(u)$$i$$\sum_{j}\overline{P}_{ij}(u)=\frac{1}{2^{N}}\sum_{m=0}^{N}[p\mathrm{o}\mathrm{o}(u)+p_{11}(u)]^{N-m}$[pol $(u)+p_{1}0(u)$ ]$= \frac{1}{2^{N}}[\{p_{0}0(u)+p11(u)\}+\{p01(u)+p10(u)\}]N$$= \frac{1}{2^{N}}[\{p\mathrm{o}\mathrm{o}(u)+p01(u)\}+\{p1\mathrm{o}(u)+p11(u)\}]N$$= \frac{1}{2^{N}}[\{q+p\}+\{q+p\}]^{N}=‘\frac{1}{2^{N}}[1+1]^{N}=1$

.

$m$

87
Namely,$\overline{P}(u)$is stochastic. On the other hand, by Remark 2.3, since$p_{0}\mathrm{o}(\mathrm{o})+p_{11}(0)=(q+p)+(p+q)=1+1=2$

and since$p_{01}(\mathrm{o})+p_{1}\mathrm{o}(\mathrm{o})=(p-p)+(q-q)=0$

we have thatas
. Further we note that each
derivative at $u=0$ , associating with the -matrix$\overline{P}(u)arrow I$$uarrow \mathrm{O}$

if $m=0$ ,$\frac{s+t}{2N}$if$m=1$ ,

has the right-handsuch that$\overline{P}_{ij}(u)$$Q=(\overline{P}_{ij}’(0))$$Q$$\tilde{P}_{ij}’(0)=-\frac{s+t}{2}$,$0$if $m>1$ .

(ii) Consider the coordinate process $X_{i}(u)$ given by (2.3). Then we may define the probability generating function of $X_{i}(u)$ by$P( X_{i}(u)=0)+zP( X_{i}(u)=1)$ ,which is from Remark 2.3,
$p_{00}(u)+zp_{01}(u)=(q+pz)[1+( \frac{1-z}{q+pz})p\exp[-(S+t)u/N]]$ ,or$p_{10}(u)+zp_{11}(u)=(q+pz)[1-( \frac{1-z}{q+pz})q\exp[-(s+t)u/N]]$ ,is or 1. Remember that $X(u)= \sum_{i=1}^{N}X_{i}(u)$ and $P_{ik}(u)=P(X(u)=$$k|X(\mathrm{O})=i)$ . Now, suppose that there are initiallyballs in urn I and $N-i$ in urn II.
$N$$X_{i}(u)$Then, since the quantities, where $i=1,2,$, are independent, the probability
generating function of $X(u)$ is calculated as follows:

according as$X_{\mathrm{i}}(0)$

$0$

$i$

$\ldots,$$(E_{i}(\cdot)=E(\cdot|X(\mathrm{O})=i))$$\sum_{k=0}^{N}Pik(u)z^{k}=E_{i}[z^{X(u})]=\Pi_{j=1}^{N}E_{i}[z^{X_{\mathrm{J}}()}u]$$=[p_{1}\mathrm{o}(u)+zp11(u)]^{i}[p_{0}\mathrm{o}(u)+Zp_{01}(u)]^{N-i}$$=(q+pz)^{N}[1- \frac{q}{p}\xi]lN[1+\xi]-i$$=(q+pz)N \sum_{x=0}^{N}K_{x}(i)\xi^{x}$$( \xi=(\frac{1-z}{q+pz})p\exp[-(s+t)u/N])$$= \sum_{x=0}^{N}K_{x}(i)pxqN-x\{[1+\eta]^{N-x}[1-\frac{q}{p}\eta]^{x}\}\exp[-x(S+t)u/N]$$( \eta=\frac{p}{q}z)$$= \sum_{x=0}^{N}I\mathrm{i}_{x}^{r}(i)pqxN-x\{\sum_{k=0}^{N}K_{k}(X)\eta^{k}\}\exp[-x(s+t)u/N]$.

$= \sum_{k=0}^{N}(\frac{p}{q})^{k}[\sum_{x=0}^{N}p^{x}q^{N-x_{I}}\iota’(i)I\mathrm{i}_{k}^{\Gamma}(Xx)\exp[-X(s+t)u/N]]z^{k}$88
Here $K_{n}(x)$ with $n,$ $x=0,1,$, $N$ are the Krawtchouk polynomials appearing in Remark
1.4, and in the above equalities the property of the generating function ofis usedat twice. Note the symmetry relation such that
. Then, equating thecoefficients of , we obtain the expression of $P_{ik}(u)$ . Hence the proof is complete.
$\ldots$$I\mathrm{i}_{n}’(X)$$\mathrm{A}_{x}^{\nearrow}(i)=I1_{i}^{r}(x)$$z^{k}$

5. Proof of Theorem 2.3(i) Consider the Markov chain with transition probabilities (1.1). Denote by
andthe -step transition probabilities and the first-passage times to the state for this chain
starting at the state , respectively. Set$p_{ij}^{(n)}$$n$$T_{ij}$$j$$i$$P_{ij}(z)= \sum_{n=0}^{\infty}p^{()}ijz^{n}n$and$F_{ij}(z)= \sum_{n=0}^{\infty}P(T_{ij}=n)z^{n}$.

Then, since $P_{ij}(z)=P_{jj}(z)F_{ij}(\mathcal{Z})$ for $i\neq j$ , we see that $F_{0N}(Z)=P0N(Z)/P_{NN}(Z)$ . By
Remark 1.3,
is expressed in terms of the Krawtchouk polynomials, which implies$p_{ij}^{(n)}$$P_{0N}(z)= \sum_{=n0}^{\infty}p^{()}\mathrm{o}^{n}Nzn$$= \sum_{n=0}^{\infty}(\frac{p}{q})^{N}\sum_{=x0}^{N}p^{x}q^{N-x}I\iota \mathrm{o}(x’)KN(X)[(1-\lambda x)z]^{n}$$=( \frac{p}{q})^{N}\sum_{=x0}^{N}p^{x}q^{N-x}K0(X)I\{’N(x)[\frac{1}{1-z(1-\lambda x)}]$By Remark 1.4, since $K_{0}(x)=1$ and$I \mathrm{t}^{r_{N}}(x)=I\mathrm{i}_{x}’(N)=(-1)^{x}(\frac{q}{p})^{x}$$P_{0N}(z)=p \sum_{x}^{N}N(-1=0)^{x}[\frac{1}{1-z(1-\lambda X)}]$.

, we get.

By the same way, we get$P_{NN(Z)}= \sum_{=n0}^{\infty}p^{()}Nz^{n}=p^{N}\sum^{N}n_{N}x=0(\frac{q}{p})^{x}[\frac{1}{1-z(1-\lambda x)}]$,from which follows (i).
(ii) The time reversibility shows that $\overline{F}_{0N}(Z)=E(\exp[-z\overline{T}_{0}N])=F_{0N}(\frac{1}{1+z})$ . So, theabove formula (i) with replaced by $1/(1+z)$ yields (ii).
(iii) Evidently,$z$.

$\overline{\mu}0N=E(\overline{T}_{0N})=-\overline{F}_{0N}’(0)=-[\frac{d}{dz}F_{0N}(\frac{1}{1+z})]_{z=0}=F_{0N}’(1)=E(T_{0N})=\mu 0N$

89(iv) The above result (ii) can be rewritten by the form$\overline{F}_{0N}(_{\mathcal{Z})}=(\frac{1}{z}+f_{1}(z))(\frac{1}{z}+f_{2}(_{Z}))-1$

where
Since

and
exist at $z=0$ , and since$f_{2}(z)= \sum_{x=1}^{N}(\frac{q}{p})^{x}[\frac{1}{z+\lambda x}]$$f_{1}(z)= \sum_{x=1}^{N}(-1)^{x(\begin{array}{l}Nx\end{array})}[\frac{1}{z+\lambda x}]$$f_{1}’(z)$and$f_{2}’(z)$,.

$- \overline{F}_{0N}’(\mathcal{Z})=-[\frac{g(z)-h(Z)}{(1+zf2(z))^{2}}]$

with functions$g(z)=-f_{2}(z)+zf_{1}’(\mathcal{Z})+z^{2}f_{1}’(\mathcal{Z})f_{2(Z})$

we have that

and$h(z)=-f_{1}(z)+zf_{2}’(z)+z^{2}f_{1}(z)f’2(z)$ ,$\mu_{oN}=\overline{\mu}_{0N}=-\overline{F}_{0N}’(0)=f_{2}(0)-f_{1}(0)=\sum_{x=1}^{N}[(\frac{q}{p})^{x}-(-1)^{x}]\frac{1}{\lambda x}$

Here, the assumption on

$s$

and

$t$

.

such that $s<t=$ implies$( \frac{q}{p})^{x}-(-1)^{x}=(\frac{t}{s})^{x}-(-1)^{x}=^{0}>$for$x=1,2,$$\ldots$, $N$ ,

which guarantees that $\mu_{0N=}0>$ , giving (iv).
(v) Put$a_{N}= \frac{1}{\lambda}\sum_{x=1}^{N}(\frac{q}{p})^{x}\frac{1}{x}$and$b_{N}= \frac{1}{\lambda}\sum_{x=1}^{N}(-1)^{x}\frac{1}{x}$

.

(5.1)

Then we evaluate $a_{N}-b_{N}$ for large $N$ . Set$p(x)=( \frac{p^{N}}{1-p^{N}})(\frac{q}{p})^{x}$,$x=1,2,$$\ldots,$$N$,

so that$\sum_{x=1}^{N}p(x)=(\frac{p^{N}}{1-p^{N}})[(1+\frac{q}{p})N-1]=1$.

Namely, $\{p(x) : x=1,2, \ldots, N\}$ is a probability distribution, having the probability
generating function$( \frac{p^{N}}{1-p^{N}})[(1+\frac{q}{p}Z)^{N}-1]$

and mean $Nq/(1-p^{N})$ . For large $N$ , the binomial distribution can be approximated by
the standard normal distribution, and so the mass of $p(x)$ concentrates on the intervals of

90
the form $(Nq/(1-p^{N})-C\sqrt{N}, Nq/(1-p^{N})+C\sqrt{N})$ with a constant $C>0$ . Namely,on such intervals, $1/x\sim(1-p^{N})/Nq$ . Hence$(Narrow\infty)$$\sum_{x=1}^{N}p(x)(\frac{Nq}{1-p^{N}})\frac{1}{x}\sim 1$,

which implies$\frac{1}{\lambda}\sum_{x=1}^{N}(\frac{q}{p})^{x}\frac{1}{x}\sim\frac{1}{\lambda}(\frac{1-p^{N}}{Nq})(\frac{1-p^{N}}{p^{N}})$$=( \frac{N}{s+t})(\frac{s+t}{Nt})\frac{(1-p^{N})^{2}}{p^{N}}$Here, $0<p=s/(s+t)<1$ , and so $(1-p^{N})^{2}\sim 1$$a_{N}\sim\underline{1}$$(Narrow\infty)$$tp^{N}$$(Narrow\infty)$$(Narrow\infty)$.

. Thus(5.2).

On the other hand, as Bingham [3, p.604] shows, we have$\frac{N}{2}\sum_{x=1}^{N}(-1)^{x}\frac{1}{x}=o(2^{N})$$(Narrow\infty)$.

Notice that$(tp^{N})b_{N}=(tp^{N})( \frac{2}{s+t})\{\frac{N}{2}\sum_{x=1}^{N}(-1)^{x}\frac{1}{x}\}$$=(2p)^{N}( \frac{2t}{s+t})\frac{1}{2^{N}}\{\frac{N}{2}\sum_{x=1}^{N}(-1)^{x}\frac{1}{x}\}$and consider that for $s_{=}<t,$ $0<(2p)^{N}=[2s/(s+t)]^{N}=<1$ . Then$b_{N}=o( \frac{1}{tp^{N}})$$(Narrow\infty)$

(5.3)

.

Therefore, (5.2) and (5.3) yield$a_{N}-b_{N} \sim\frac{1}{tp^{N}}$$(Narrow\infty)$,

giving (v).
(vi) The above result (ii) shows$E[ \exp\{-(tp^{N})\overline{T}_{0N^{Z}}\}]=\overline{F}_{0N}((tp^{N})_{Z})=\frac{B_{N}}{A_{N}}$

,

(5.4)

91
where
$A_{N}= \frac{1}{(tp^{N})z}+\sum_{x=1}^{N}(\frac{q}{p})^{x}[\frac{1}{(tp^{N})_{\mathcal{Z}+\lambda X}}]\sim\frac{1}{(tp^{N})z}+a_{N}$$(Narrow\infty)$

and$B_{N}= \frac{1}{(tp^{N})z}+\sum_{x=1}^{N}(-1)^{x}[\frac{1}{(tp^{N})z+\lambda x}]\sim\frac{1}{(tp^{N})z}+b_{N}$

with
and
we have$a_{N}$$b_{N}$$(Narrow\infty)$

as defined by (5.1). Accordingly, combining (5.4) with (5.3) and (5.2),$E[\exp\{-(tp)N\overline{\tau}0Nz\}]$$=$$\frac{\frac{1}{(tp^{N})z}+o(\frac{1}{tp^{N}})}{\frac{1}{(tp^{N})z}+\frac{1}{tp^{N}}+o(\frac{1}{tp^{N}})}$$arrow$$(Narrow\infty)$$\frac{\frac{1}{z}}{\frac{1}{z}+1}=\frac{1}{1+z}$.

Since a random variable $X$ having the exponential distribution with parameter 1 satisfies
that $E[\exp\{-zx\}]=1/(1+z)$ , the above relation implies thatconverges in
distribution to the exponential distribution with parameter 1 as $Narrow\infty$ , and (vi) follows
similarly or by (ii). Hence the proof is complete.
$(tp^{N})\tilde{\tau}_{0}N$

5. Complements
In Theorem 2.2 there is a limit distribution in each case:
Since $\lim_{uarrow\infty}p_{\mathrm{o}0}(u)=\lim_{uarrow\infty}p_{1}0(u)=q=t/(s+t)$ and $\lim_{uarrow\infty}p_{01}(u)=\lim_{uarrow\infty^{p_{11}}}(u)=$$p=s/(s+t)$ , we have$\lim_{uarrow\infty}\overline{P_{ij}}(u)=\frac{1}{2^{N}}[q+p]N-m[p+q]^{m}=\frac{1}{2^{N}}$,so that the limit law is uniform for the ‘full description’.
On the other hand, by Remark 1.4, since $K_{i}(0)=I1_{k}^{r}(0)=1$ , we have$\lim_{uarrow\infty}P_{ik}(u)=(\frac{p}{q})^{k}p^{0}q^{N0}-=p^{k}qN-k$

,

where

$i,$

$k=0,1,$$\ldots,$$N$.

Namely, the limit law is binomial for thedescription’.
By contrast, in Kac’s theorem [6] for the -step transition probability of the discretetime Markov chain that is the Ehrenfest model (1.1) with $s=t=1,$ $\pi_{k}=2^{-N}$ gives
an invariant (stationary) probability distribution, but there is no limit distribution:
Indeed, let
be the transition probability matrix for the model (1.1) with
$s=t=1$ . Then it is easy to see that$\zeta \mathrm{r}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}\mathrm{d}$$n$$\overline{\mathrm{p}}=(\overline{p_{ik}})$$\lim_{narrow\infty}\overline{\mathrm{p}}^{2n}\neq\lim\overline{\mathrm{p}}^{2n+1}narrow\infty$.

92
If we start at any vertex that we relabel as the ‘origin’ $(0, \ldots, 0)$ , the vertex it takes
longest to hit is $(1, \ldots, 1)$ . Now if we apply a unit voltage between these two vertices
so that the voltage at $(0, \ldots, 0)$ is 1 and the voltage at $(1, \ldots, 1)$ is , then all vertices
having the same number of l’s share the same voltage and can be shorted. In general
what we obtain is a new graph with $N+1$ vertices, where the th new vertex consistsof the shorting of all vertices in the unit cube with. Thus, as follows from Palacios$N$[10] and [11], the -cube yields the platonic graphs in electric networks.
The well-known Ornstein-Uhlenbeck process is obtained in the diffusion limit of the
Ehrenfest model (1.1) with $s=t=1$ , where we centre at $N/2$ , scale space and time andlet $Narrow\infty$ .
The Ehrenfest urn models are applicable to the field of neuron firing and have a complementary aspect which is the study of the time taken to approach stationarity-measured
in terms of variation distance-and the ‘cut-off phenomenon’ typically exhibited.
Our work for a generalization is inspired by the above point of view.
$0$

$k$

$k1’ \mathrm{s}$6. Discrete-time Ehrenfest urn models with applications

The transition matrix $P=(p_{ij})$ as defined in (1.1) or (1.2) is a special cae of tridiagonal
matrix$P=$

satisfying$\lambda_{i}=pi,i+1$,$\mu_{i}=pi,i-1$,$\nu_{i}=p_{i,i}$$(i=0,1, \ldots, N)$ ,$\lambda_{N}=0$

(6.1)

,

$\mu_{0}=0$.

This chain is a random walk on $\{0,1, \ldots, N\}$ . The model (1.2) is a generalization ofandare allowed to be
the model (1.1) such that the transition probabilities
quadratic functions of the current state . In this section, for simplicity of the notationand the calculation, we take the discrete-time Ehrenfest model (1.1), that is, the model(6.1) satisfying$p_{i,i+1}$$p_{i,i-1}$$i$$\lambda_{i}=(1-\frac{i}{N})s$,$\mu_{i}=\frac{i}{N}t$,$\nu_{i}=1-(\lambda_{i}+\mu_{i})$

,

(6.2)

$N$ .
where $0<s,$ $t<1=$ and $i=0,1,$$(\mu_{N},\nu_{N})=(1,0)$ , and such a model is a birth-death
If $s=t=1$ , thenandchain with reflecting boundaries at and $N$ . For the case $s+t=1$ , which we call a
one-parameter Ehrenfest model, we interpret and $t(=1-s)$ as probabilities of choosing
urns I and II, respectively. If $s\neq 1$ and $t\neq 1$ , then the chain is a randam walk with sticky
boundaries at and $N$ .
$\ldots,$$(\nu_{0}, \lambda_{0})=(0,1)$

$0$

$s$

$0$

93
6.1 Steady state and time reversibility

The Ehrenfest model (6.1) with rates (6.2) satisfies the global balance equations
for $i=0,1,$$\pi_{i}=\sum_{j=0}^{N}\pi jp_{ji}$$\ldots,$$N$

and also satisfies the detailed balance equationsfor$\pi_{i}p_{i}j=\pi_{j}pji$$i,j=0,1,$$\ldots,$$N$.

Hence the chain is time reversible, having (unique) stationary probability distribution$\pi_{j}=(\frac{s}{s+t})^{j}(\frac{t}{s+t})^{N-j}$

6.2 Convergence$\mathrm{v}\mathrm{s}$,$j=0,1,$, $N$ ,$\ldots$

where$0<s,$ $t<1=$ .

. recurrence

Here we discusss the Ehrenfest model (6.1) satisfying (6.2) with $s=t=1$ . Then we
can show that recurrence is not observable for states far from the steady state $M=N/2$ ,assuming that $N$ is even. For instance, the average time to reach from state $M$ , where$M$ is the mean for thebinomial distribution (stationary probability distribution), is$0$$\frac{1}{2M}2^{2M}(1+O(\frac{1}{M}))$

whereas the average time to reach state $M$ from state$0$is less than

$M+M\log M+o(1)$ .

With $M=10^{4}$ balls and rate of transition one ball per second, the return time to equilibrium from state is on the order of 102103 seconds, which is less than 29 hours (onlyabout a day), whereas it would take on the order ofyears to go from $M$ to , which
is an astronomical time (see Bhattacharya and Waymire [2, pp.250-251]).
Newton’s law of cooling (Theorem 2.1) is another manifestation of thermodynamic
irreversibility in the Ehrenfest model. On the other hand, in much more general settings,
several authors investigate ‘relaxation time’, measuring the time taken for the random
walk to approximate the limit law in variation norm (see Aldous [1] and Kijima [8]).
Example 6.1 (Finite Buffer). A discrete-time communication channel with a finite bufferof size $N$ behaves as follows: During theslot, either a new message arrives (if there isroom for it), with positive probability, or one of the messages in the buffer (if any) is transmitted, with positive probability, or there is no change. This system can be modelled by aMarkov chain which is in state when there are messages in the buffer $(i=0,1, \ldots, N)$ .
From state , there are transitions to states $i-1$ (except when $i=0$ ), and $i+1$ (except
when $i=N$ ), with probabilities$0$$10^{6}000$$0$$i\mathrm{t}\mathrm{h}$

$i$

$i$

$i$

$i$

$\mu_{i}=_{Pi,i}-1$,$\nu_{i}=p_{i,i}=1-(\lambda_{i}+\mu_{i})$and$\lambda_{i}=p_{i,i+1}$,94respectively. The chain with rates of the form (6.2) is an example of such a transmission.
Example $6.2(Portfoli_{\mathit{0})}$ . There will be one risky investment opportunity (such as acommon stock) whose market price changes with time in probabilistic way. This risky
asset will form a Markov chain called a random walk with sticky boundaries. Prices
and $N$ are (certainly or uncertainly) reflecting states. If the price now is , then at thenext time instant the price will be 1 with certainty or uncertainty. Similarly, if the price
is $N$ now, the price at the next instant of time will be $N-1$ or $N$ . Otherwise, for states
between and $N$ , the price will increase by 1 with probability, or decreaseby 1 with probability $\mu_{i}=p_{i,i-1}$ , or remain with probability $\nu_{i}=p_{i,i}=1-(\lambda_{i}+\mu_{i})$ .
The chain with rates of the form (6.2) is an example of such a market. We follow the
progress of an investor who owns shares in this asset, and who also owns shares in a riskfree asset (such as a government bond) whose value is multiplied by a constant $\gamma>1$ ,at each discrete instant of time. The investor can allocate his wealth between the risky
and the risk-free asset at each instant, and also, if he chooses, consume some of his
wealth. The investor is to decide how to change his porfolio and how to consume moneyas time progresses, in order to maximize his expected total consumption. In a finite time
horizon investment-consumption problem, all wealth is consumed at the terminal time.
In an infinite-horizon discounted problem, the invester will maximize the expected total
discounted consumption. The optimal-value function for the control problem contains
two parameters and such that $0<s,$ $t<=1$ . We may be concerned with asymptotic
analysis as
.
$0$

$0$

$0$

$\lambda_{i}=p_{i,i+1}$

$s$

$t$

$s\uparrow 1\dot{\mathrm{a}}\mathrm{n}\mathrm{d}t\uparrow 1$

7. Continuou-time Ehrenfest urn models with applications
Here we treat the Markov process which is the continuous-time formulation of the Markov
chain with transition matrix (6.1) satisfying (6.2). First of all, we note that the Krawtchouk
polynomials $K_{n}(x,p, N)$ as described in Remark 1.4, which play an essential role in thecontinuous-time formulation, have the following equivalent formula:$Ii_{n}^{r}(x,p, N)=C^{-1} \sum_{\nu=0}(-1)n\nu(\frac{q}{p})^{\nu}$,$n=0,1,$$\ldots$

?

$N$

,

where

$C=$

and

$0<p=1-q<1$ .

The Krawtchouk polynomials are orthogonal with respect to the binomial distribution$N$ .
with masses $p^{x}q^{N-x}$ at the $N+1$ points $x=0,1,$;$N$ , define
For $i=0,1,$by$\ldots$$\ldots,$$k_{ij}$$k_{ij}=I\mathrm{i}_{i}(\prime j,p, N)$

Then, as follows from Karlin andrecurrence relation:$\mathrm{M}\mathrm{c}\mathrm{G}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{o}\mathrm{r}[7]$.

, the polynomials$k_{ij}$satisfy the following$-jk_{ij}=iqk_{i-1,j}-[iq+(N-i)p]k_{ij}+(N-i)pk_{i}+1,j$ .

95
7.1 Expression of the Krawtchouk polynomials
The above-mentioned formula and Remark 1.4 yield the following explicit expression of
the polynomials:$k_{ij}$$k_{0j}=1$,$k_{1j}=\underline{1}$$pN$$k_{Nj}=(-1)^{j}( \frac{q}{p})^{j}$$k_{ij}=k_{ji}$

Let

$s$

and

$t$

,

(Np-j),$k_{N-1,j}=(-1)j \frac{q^{j-1}}{p’ N}$,$i,j=0,1,$$\ldots,$$N$(Nq-j),.

be the parameters such that $0<s,$ $t=<1$ , and put$q= \frac{t}{s+t}$$p= \frac{s}{s+t’}$$K=(pk_{i}j)_{0}\leqq i,j\leqq N$’,$\lambda_{j}=1-\frac{j}{N}(_{S}+t)$,$0<=^{j<N}=$ ’$\Lambda=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\lambda 0, \lambda_{1}, \ldots, \lambda_{N})$.

Let
be the transition matrix as given by (6.1) and (6.2). Then, it follows from Krafft
and Schaefer [9] that $PK=K$ A. Namely, the Krawtchouk polynomials provide righteigenvectors of corresponding to the eigenvalues .
$P$

$P$

$\lambda_{j}$7.2 Q-matrix
Let $X(u)$ andbe the Markov processes with continuos parameter $u\geq 0$ , which
are the continuou-time formulation of the Ehrenfest urn model (1.1) in the ‘reduced
description’ and the ‘full description’ as described in Remark 1.1, respectively. Then, thetransition probabilities of $X(u)$ andare denoted by$\overline{X}(u)$$\overline{X}(u)$$P_{ik}(u)$, where$i,$$k=0,1,$$\ldots,$$N$

and$\overline{P}_{ij}(u)$, where and
$i$

$j$

vary in the vertex-set ,$V$

respectively (see (2.4) and (2.5)). By Theorem 2.2 and the expression of the Krawtchouk
polynomials
in the preceding subsection, we can calculate the right-hand derivatives
$u=0$
at
for
and
, associating the -matrices
and $Q=(P_{ik}’(0))$
with the following results:$\underline{k}ij$$P_{ij}(u)$$P_{ik}(u)$$Q$$- \frac{1}{2}(s+t)$(i)$Q=(\overline{P}_{ij(0}’))$,$\overline{P}_{ij}’(\mathrm{o})=\{$$\frac{1}{2N}(s+t)$$0$$Q=(\overline{P}_{ij}^{J}(0))$

if $m=|i-j|=0$ ,if $m=|i-j|=1$ ,if $m=|i-j|>1$ ,where $i=(i_{1}, \ldots, i_{k}, \ldots, i_{N})$ and $j=(j_{1}, \ldots,j_{k}, \ldots,j_{N})$ are in the vertex-set$m=|i-j|= \sum_{k=1}^{N}|i_{k}-j_{k}|$ , and moreover $0<s,$ $t<=1$ .
$\lambda_{i}$(ii)$Q=(P_{ik}’(0))$,$\mu_{i}$$P_{ik}’(\mathrm{o})=\{$$-(\lambda_{i}+\mu_{i})$$0$

if $k=i+1$ ,if $k=i-1$ ,if $k=i$ ,otherwise,

(7.1)
$V$

, and

(7.2)

96
where
$\lambda_{i}=(1-\frac{i}{N})s$,$\mu_{i}=\frac{i}{N}t$,$i=0,1,$$0<s,$ $t<1=$ ’, $N$ .

$\ldots$

The -matrices (7.1) and (7.2) are called the (formal) infinitesimal generator associatedwithand $X(u)$ , respectively, which represent the instantaneous transition rates.
The Markov proxess $X(u)$ as governed by (7.2) is a finite birth-death process withstate space $\{0,1, \ldots, N\}$ , satisfying the following Kolmogorov’s backward equation:$Q$$\tilde{X}(u)$$\frac{d}{du}P_{i,k}(u)=(\frac{i}{N}t)Pi-1,k(u)-(\frac{i}{N}t+(1-\frac{i}{N})S)Pi,k(u)$$+((1- \frac{i}{N})S)Pi+1,k(u)$ ,$i,$$k=0,1,$$\ldots,$$N$,$P_{N+1,k}(u)\equiv 0$,$P_{-1,k}(u)\equiv 0$

(7.3)

,

and the initial conditionsif$P_{i,k}(0)=1$$i=k$ ,

$P_{i,k}(0)=0$

if$i\neq k$.

7.3 Models in 3-cube(i) The Markov process$\overline{X}(u)$in the full description. Define the vertex-set

$V$

by

$V=\{\overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4}, \overline{5}, \overline{6}, \overline{7}\}$

where,$\overline{4}=(1,0,0)$ ,,$\overline{5}=(1,0,1)$ ,$\overline{0}=(0,0,0)$,$\overline{6}=(1,1,0)$ ,$\overline{1}=(0,0,1)$$\overline{2}=(0,1,0)$$\overline{3}=(0,1,1)$$\overline{7}=(1,1,1)$.

Set$c= \frac{1}{2}(s+t)$

Then, by (7.1), theexpression:

$Q$

and

-matrix associated with$Q=($$-cd000dd0$$d= \frac{1}{6}(s+t)$$\overline{X}(u)$.

on the vertex set$-cd00d0d0-cd00d0d0-cd0d00d0-cdd00d00-cd0d0d00-cddd0000$$-cddd0000$

).

$V$

has the following

97(ii) The Markov process $X(u)$ in the reduced description. By (7.2), thewith $X(u)$ on $\{0,1,2,3\}$ has the following expression:$\frac{1}{3}t$$Q=$$\backslash \text{ノ}-s00$$- \frac{1}{3}(2s+t)$$\frac{1}{3}2s$$- \frac{1}{3}(_{S}+2t0t)$$\frac{1}{3}2t0s$$\frac{1}{-3}0_{S}0t)$$Q$-matrix associated.

Example 7.1(Mean First-Passage Time). Let us consider the Markov process $X(u)$ on). Letthe 3-cube in the reduced description, starting at the origin (state$X(u)$),
and(statetovertexbe the first-passage time ofthe opposite
set. Then, by (iii) and (iv) of Theorem 2.3, we obtain$0\Leftrightarrow\overline{0}=(0,0,0)$$3\Leftrightarrow\overline{3}=(1,1,1)$$\overline{T}_{03}$$\overline{\mu}_{03}=E[\overline{T}_{03}]$$\overline{\mu}_{03}=\frac{1}{s}\{9+(\frac{t}{s}-1)\frac{7}{2}+(\frac{t}{s})^{2}\}$,and hence$\overline{\mu}_{03}=10$

if $s=t=1$ .

7.4 Reliability theory, $N$ , be the one-particle process as defined in (2.3), satisfying
Let $X_{i}(u)$ , where $i=0,1,$
Assumption 2.1. Then we can interpret as follows: Each $X_{i}(u)$ sojourns in urn I (state
1) and urn II (state ) with exponentiol holding time of parameter $1/N$ , and at the next
instant of the end of its sojourn time, $X_{i}(u)$ remains in urn I and urn II repeatedly withprobabilities $1-t$ and l-s, respectively, or moves to the opposite urn with probabilities
and , respectively. The Markov process $X(u)$ in the reduced description is defined by$\ldots$

$0$

$t$

$s$

$X(u)= \sum^{N}X_{i}(ui=1)$,

with transition probabilities $P_{ik}(u)$ as given in (2.4). The probability law of $X(u)$ is
obtained by the convolution of probability laws of i.i.d. random functions $X_{i}(u)$ . So, therate of occurrence that $X(u)$ terminates its sojourn is estimated at $1=N*(1/N)$ . Namely,$X(u)$ is a kind of Markov renewal process such that the discrete-time Markov chain withtransition probabilities (1.1) moves from state to state with exponential holding time ofparameter 1. From this poin,of view, the results (ii) and (iii) of Theorem 2.3 are regarded
as trivial properties.
Example 7.2(Parallel System). Let us consider a machine with $N$ components, eachalternately functioning (up) and defective (down). Suppose that $X_{i}(u)$ denote the states’
and $1=$of thecomponent, that is, the process with state space $\{0,1\}$ , where‘down’, and suppose that Assumption 2.1 holds for the family $\{X_{i}(u) : i=1, \ldots , N\}$ . Set$X(u)= \sum_{i=1}^{N}x_{i}(u)$ , and consider $X(u)$ on the $N$ -cube. For $X(u)$ , starting at the origin
the first-passage time of $X(u)$ to the opposite vertex (state $N$ ).
(state ), denote by, so that the machine functions if and only if at least one
If the components areisthetime to first failure of the machine. The results (iii),
component does, thenof Theorem 2.3 show the asymptotc behavior of the mean first-failure time(iv) andfor large $N$ , if $s=t=1$ .
as $Narrow\infty$ :$0=‘ \mathrm{u}\mathrm{p}$$i\mathrm{t}\mathrm{h}$$\overline{\tau}_{0N}$$0$$\mathrm{i}\mathrm{n}_{-}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}1$$\tau_{0N}$$(\underline{\mathrm{v}})$$\overline{\mu}_{0N}=E[T_{0N}]$$\overline{\mu}0N\sim 2^{N}$

98$7.5_{\mathrm{i}}$Queueing network

Let $X(u)$ be the Markove process in the reduced description with transition probabilities
as given in (2.4) in the reduced description. Then $X(u)$ represents a model of a closed
queueing network of the Jackson type with two nodes (urn I and urn II), each of whichcontains $N$ servers whose service times are independent exponentials of parameter $1/N$ ,satisfying the following:
The total number of customers is $N$ . Each customer, after completion of his service in urn
I (resp. urn II), moves to urn II (resp. urn I) with probability (resp. ) and remains in
urn I (resp. urn II) with probability $1-t$ (resp. l-s) in order to be served, repeatedly.
The results as obtained in the previous section 2 may be extended to the ‘multi-urn’versions of the classical Ehrenfest model in order that the continuous-time formulation
can be applied to closed networks with multi-node.
$t$

$s$

7.6 Infinite system of queue processes
In the finite system of differential equations (7.3), let $N$ tend to infinity. Then we obtainthe (formal) infinite system:$\frac{d}{du}P_{i,k}^{*}(u)=-sP_{i^{*}k},(u)+sP_{i^{*}+1,k}(u)$$P_{i,k}^{*}(0)=1$

if,$i=k$ ,$i,$$k=0,1,2,$$P_{i,k}^{*}(0)=0$$\ldots$

if,$i\neq k$,which are the differential equations associated with the pure birth process with state space.
We can obtain another infinite system under suitable scale change.
which is large enough,Example 7.3(Infinitely Many Servers). Fix a positive integer
and choose $N$ so that $N>N_{0}$ . Set $s=a/N$ and $t=1-b/N$ . Here and are positive
real numbers, which are chosen so that $0<s,$ $t<=1$ , and fixed. Multiply the equations. Then we see(7.3) by$\{0,1,2, \ldots\}$$N_{0}$$b$$a$$N_{0}$$N_{0} \frac{d}{du}P_{i,k}(u)$$=$$( \frac{N_{0}}{N})i(1-\frac{b}{N})P_{i-1,k}(u)$$- \{(\frac{N_{0}}{N})i(1-\frac{b}{N})+(\frac{N_{0}}{N})(1-\frac{i}{N})a\}Pi,k(u)$$+( \frac{N_{0}}{N})(1-\frac{i}{N})$a $P_{i+1,k}(u)$ .

Let $N$ tend to infinity in the avove equations, assuming that $N_{0}/N\approx 1$ as $Narrow\infty$ . Then,
we obtain the following (formal) infinite system:$N_{0} \frac{d}{du}P_{i}^{*},(ku)$$=$$iP_{i-1,k}^{*}(u)-(i+a)P_{i,k}^{*}(u)+aP_{i+1,k}^{*}(u)$$i,$ $k$$=$$0,1,2,$$P_{i,k}^{*}(0)$$=$1$\ldots$,,

if $i=k$ ,$P_{i,k}^{*}(0)=0$

if$i\neq k$,which are the differential equations associated with a birth-death queueing process with
infinitely many servers.

99
7.7 Manufacturing system
We consider the stochastic manufacturing system with the surplus level $x(u)\in R^{1}$ andthe production rate $y(u)\in R^{1}$ satisfying$\frac{d}{du}x(u)=y(u)-z$,$x(0)=x$ ,where $z\in R^{1}$ is the constant demand rate and is the initial value of $x(u)$ .
Let $S=\{0,1,2, \ldots , N\}$ denote the set of capacity states, and let $K(\epsilon, u)\in S,$ $u_{=}>0$ ,denote the total production capacity process of the parallel machines in the system, which
is given by a finite state Markov process parameterized by a small number. Thenthe production rate $y(u)$ must satisfy $0_{=}<_{y}(u)=<K(\epsilon, u)$ for
O. We consider the costfunctionwithdefined by$x$$\epsilon>0$$u_{=}>$$J^{\epsilon}(x, k, y(\cdot))$$K(\epsilon, \mathrm{O})=k$$J^{\epsilon}(X, k, y( \cdot))=E[\int_{0}^{\infty}\exp(-\rho u)G(X(u), y(u))du]$,

where $G(x, y)$ is the running cost of having surplus and production rate and $\rho>0$ is
the discount rate. The problem is to find an admissible control $0\leqq y(u)=<K(6, u),$ $u>0=$ ’
as a function of the past
, that minimizes.
According to Sethi [12], we make the following assumptions on and:(i) The cost function satisfies suitable smoothness condition and growth restriction.
(ii) The capacity process $0=<K(\epsilon, u)\in S,$ $u>0=$ ’ is a finite Markov process governed by
the infinitesimal generatorof the form$x$$K(\epsilon, u)$$y$$J^{\epsilon}(x, k, y(\cdot))$$G$$K(\epsilon, u)$$G$$Q^{\epsilon}$$Q^{\in}=Q^{()(}1+ \frac{1}{\epsilon}Q2)$

,

where
is a $(N+1)\cross(N+1)$ matrix such that $Q^{(l)}=(q_{ij}^{()}l)$ with
if $i\neq j$
andis weakly irreducible, that is, it has a’ for $l=1,2$ . The matrix
unique stationary probability distribution.
Under these assumtions, Sethi [12] investigates the limiting control problem as.
Sethi [12] also considers
which is modelled by a birth-death process such thatthe second -matrix $Q^{(2)}=(q_{i}^{(2)}j)$ in the infinitesimal generator
has the following
expresslon:$Q^{(l)}$$q_{ij}^{(l)}=>0$$q_{ii}^{(l)}=- \sum i\neq jq_{i}^{(l)}j$$Q^{(2)}$$\epsilonarrow 0$$K(\epsilon, u)$$Q$$q_{ij}^{(2)}=\lambda_{i}$$Q^{\epsilon}$

if $j=i+1$ ,$q_{ij}^{(2)}=-(\lambda_{i}+\mu_{i})$,$q_{ij}^{(2)}=\mu_{i}$if $j=i$ ,$q_{ij}^{(2)}=0$

if $j=i-1$ ,otherwise,with nonnegative constants and . In the case where the second -matrix
is givenby the Ehrenfest model (7.2), the value function for the above problem contains several
parameters, such as $0<\epsilon\ll 1,0<s,$ $t<=1$ and $N>=1$ . We may be concerned with theasymptotic analysis as
and
.
$Q$

$\lambda_{i}$$\mu_{i}$$\epsilon\downarrow 0,$$s\uparrow 1,$$t\uparrow 1$$N\uparrow\infty$$Q^{(2)}$

100
8. Limiting distribution and diffusion approximation

Let $P_{ik}(u)$ be the transition probabilities of the continuous-time Markov chain in the
reduced description as given in Theorem 2.2. Then we have the following results for thelimiting distribution and diffusion approximation.
8.1 The rate of convergence to the limiting binomial distribution

Theorem 2.2 implies the explicit formula:$P_{ik}(u)=( \frac{p}{q})^{k}\sum_{x=0}^{N}p^{x}q-x_{I}\mathrm{i}_{i}’(N)x\Lambda’k(x)\exp[-\lambda xu]$

where$\mathrm{A}_{i}’(x)=\mathrm{A}_{i}’(x,p, N)$,

and $\lambda=(s+t)/N$ . Using$K_{n}(0)=1$,$I\iota_{0}’(X)=1$,

which appear in (ii) of Remark 1.4, we have$P_{ik}(u)$$=$$( \frac{p}{q})^{k}\{q^{N}I\mathrm{t}_{i}^{\nearrow}(0)I\zeta_{k}(0)+\sum_{=x1}p^{x}q^{N-}K_{i(x)\iota_{k}}xI’(X)\exp[-\lambda Xu]\}N$$=$$p^{k}qN-k+ \exp[-\lambda u]\overline{\pi}_{k}\sum_{x=1}^{N}p^{x}q^{N-x_{I}}\mathrm{i}’i(x)I\mathrm{i}_{k}’(x)\exp[-\lambda(X-1)u]$

,

where
$\overline{\pi}_{k}=(\frac{p}{q})^{k}$,that is,$P_{ik}(u)=p^{k}q-k+ON(e^{-})\lambda u$as$uarrow\infty$.

In other words the rate of convergence to the limiting (binomial) distribution is expoThe constant in the -symbol is easily expressed in terms of thenential of orderparameters, in fact$e^{-\lambda u}$$O$$P_{ik}(u)=p^{k}q^{N-k} \{1+\sum_{x=1}^{N}px-qix_{I\mathrm{i}(}\prime x)I\mathrm{i}_{k}’(X)\exp[-\lambda xu]\}$(Np–i)(Np–k) $\exp[-\lambda u]+O(\exp[-2\lambda u])\}$$=$$p^{k}q^{Nk}- \{1+Npq^{-1}\frac{1}{pN}$$=$$p^{k}q^{N-k} \{1+\frac{(Np-i)(Np-k)}{Npq}e^{-\lambda u}+O(e^{-})2\lambda u\}$$\frac{1}{pN}$,

since $I\mathrm{i}_{j}’(1)=k_{j1}=k_{1j}=(Np-j)/(pN)$ as given in subsection 7.1.

101
8.2 Convergence to the Ornstein-Uhlenbeck process

The Ehrenfest chain of the model (1.1) is given on the state space $\{0,.1, \ldots, N\}$ withtransition probabilities:$p(i,i-1)= \frac{i}{N}t$$p(i, i+1)=(1- \frac{i}{N})s$ ,,$p(i, i)=1-(1- \frac{i}{N})s-\frac{i}{N}t$,where $0<s,$ $t\leqq 1$ . Assume that $N$ is an even number. Set $a=N/2$ and let $\{X_{n}\}$ bethe discrete-time Ehrenfest chain on the state space$\{-a, -a+1, \ldots , -1,0,1, \ldots, a-1, a\}$with the following transition probabilities :,$p(k, k-1)$$=$$( \frac{k+a}{2a})t=\frac{1}{2}(1+\frac{k}{a})t$$p(k, k+1)$$=$$( \frac{a-k}{2a})s=\frac{1}{2}(1-\frac{k}{a})s$$p(k, k)$$=$$1- \frac{1}{2}(1-\frac{k}{a})s-\frac{1}{2}(1+\frac{k}{a})t$,.

Let $p(n;k, m)$ be the -step transition probabilities such that$n$$p(n;k, m)=P(X_{n}=m|X_{0}=k)$ .

Then it is clear that$p(n+1;k, m)$$=$$p(n;k, m-1)p(m-1, m)+p(n;k, m+1)p(m+1, m)+p(n;k, m)p(m, m)$$=$$\frac{1}{2}(1-\frac{m-1}{a})Sp(n;k, m-1)+\frac{1}{2}(1+\frac{m+1}{a})tp(n;k, m+1)$$+ \{1-\frac{1}{2}(1-\frac{m}{a})S-\frac{1}{2}(1+\frac{m}{a})t\}p(n;k, m)$.

Let us speed up this nonhomogeneous random walk. Let $a(=N/2)arrow\infty$ such that$\frac{(\triangle x)^{2}}{\triangle u}=\sigma^{2}$and$a(\triangle u)arrow\nu^{-1}$with constants $\sigma>0$ and.
Let us pass from the -step transition probability to the transition density$l\text{ノ}>0$$n$$f(u, y)=f(x;u, y)$by taking $n(\triangle u)=u$ ,$f(u+\triangle u, y)$$=$$m(\triangle x)=x$:$\frac{1}{2}(1-\frac{\gamma\gamma l-1}{a})sf(u, y-\triangle y)+\frac{1}{2}(1+\frac{m+1}{a})tf(u, y+\triangle y)$$+ \{1-\frac{1}{2}(1-\frac{m}{a})s-\frac{1}{2}(1+\frac{m}{a}\mathrm{I}t\}f(u, y)$

.

102
Then
$f(u, y)+( \triangle u)\frac{\partial f}{\partial u}+o(\triangle u)$$=$$\frac{1}{2}(1-\frac{m-1}{a})s\{f(u, y)-(\triangle y)\frac{\partial f}{\partial y}+\frac{1}{2}(\triangle y)^{2}\frac{\partial^{2}f}{\partial y^{2}}\}$$+ \frac{1}{2}(1+\frac{m+1}{a})t\{f(u, y)+(\triangle y)\frac{\partial f}{\partial y}+\frac{1}{2}(\triangle y)2_{\frac{\partial^{2}f}{\partial y^{2}}}\}$$+ \{1-\frac{1}{2}(1-\frac{m}{a})S-\frac{1}{2}(1+\frac{m}{a})t\}f(u, y)+o((\triangle y)^{2})$$=$$\{1+\frac{t+s}{2a}\}f(u, y)+\{\frac{t-s}{2}+\frac{m}{2a}(t+s)+\frac{t-s}{2a}\}(\triangle y)\frac{\partial f}{\partial y}$$+ \{\frac{t+s}{2}+\frac{m}{2a}(t-S)+\frac{t+s}{2a}\}\frac{1}{2}(\triangle y)2\frac{\partial 2f}{\partial y^{2}}+o((\triangle y)^{2})$.

Observe that $m=y/(\triangle y)$ , so that$\frac{\partial f}{\partial u}+\frac{o(\triangle u)}{\triangle u}$$=$$( \frac{t+s}{2})(\frac{1}{a(\triangle u)})f(u, y)$$+ \{(\frac{t-s}{2})(\frac{1}{\triangle u})(\triangle y)\frac{\partial f}{\partial y}+(\frac{t+s}{2})(\frac{1}{a(\triangle u)})y\frac{\partial f}{\partial y}$$+( \frac{t-s}{2})(\frac{1}{a(\triangle u)})(\triangle y)\frac{\partial f}{\partial y}\}$$+ \{(\frac{t+s}{2})\frac{1}{2}(\frac{(\triangle y)^{2}}{\triangle u})\frac{\partial^{2}f}{\partial y^{2}}+(\frac{t-s}{2})(\frac{1}{a(\triangle u)})y(\triangle y)\frac{\partial^{2}f}{\partial y^{2}}$$+( \frac{t+s}{2})(\frac{1}{a(\triangle u)})(\triangle y)^{2}\frac{\partial^{2}f}{\partial y^{2}}\}+\frac{o((\triangle y)^{2})}{\triangle u}$Assume that $t=s$ and choose$\frac{1}{a(\triangle u)}arrow\nu$$\triangle u$$(\triangle uarrow \mathrm{O})$

and
and

$\triangle y$.

so that$\frac{(\triangle y)^{2}}{\triangle u}arrow\sigma^{2}$$(\triangle uarrow \mathrm{O}, \triangle yarrow 0)$.

Then, we can obtain the following Kolmogorov’s forward equation for the OrnsteinUhlenbeck process :$\frac{\partial f}{\partial u}=t\{\nu\frac{\partial}{\partial y}(yf)+\frac{1}{2}\sigma\frac{\partial^{2}f}{\partial y^{2}}2\}$

.

103

References[1] D. Aldous: Finite-time implications of relaxation times for stochastically monotone
processes. Probab. Th. Rel. Fields, 77 (1988) 137-145.

[2] R.N. Bhattacharya and E.C. Waymire: Stochastic Processes with Applications (Wiley,
New York, 1990).
[3] N. H. Bingham: Fluctuation theory for the Ehrenfest urn. Adv. Appl. Prob. 23(1991) 598-611.
[4] H. Dette: On a generalization of the Ehrenfest urn model. J. Appl. Prob. 31 (1994)

930-939.
[5] P. and T. Ehrenfest: Uber zwei bekannte Einw\"ande gegen das Boltzmannsche HTheorem. Physik. Zeit. 8 (1907) 311-314.
[6] M. Kac: Random walk and the theory of Brownian motion. Amer. Math. Mon.. thly
54 (1947) 369-391.

[7] S. Karlin and J. McGregor: Ehrenfest urn models. J. Appl. Prob. 2 (1965) 352-376.
[8] M. Kijima: Upper bounds of a measure of dependence and the relaxation time for
finite state Markov chains. J. Operations Research Soc. Japan, 32 (1989) 93-102.

[9] O. Krafft and M. Schaefer: Mean passage times for tridiagonal transition matrices
and a two-parameter Ehrenfest urn model. J. Appl. Prob. 30 (1993) 964-970.
[10] J. L. Palacios: Fluctuation theory for the Ehrenfest urn via electric networks. Adv.
Appl. Prob. 25 (1993) 472-476.

[11] J. L. Palacios: Another look at t,he Ehrenfest urn via electric networks. Adv. Appl.
Prob. 26 (1994) 820-824.
[12] S.P. Sethi: Some insights into near-optional plans for stochastic manufacturing sys: Mathematics of Stochastic Manufacturingtems. In G.G. Yin and Q. Zhang
Lectures in Appl. Math. 33 (AMS, Providence, 1997), 287-315.
$(\mathrm{e}\mathrm{d}_{\mathrm{S}}.)$$s_{y_{S}}tems_{f}$[13] L. Tak\’acs: On an urn problem of Paul and Tatiana Ehrenfest. Math. Proc. Camb.
Phil. Soc. 86 (1979) 127-130.

[14] I. Vincze: \"Uber das Ehrenfestsche Modell der W\"arme\"ubertragung. Arch. Math. 15(1964) 394-400.
Kiyomasa Narita
Engineering and Management
Department of
Faculty of Engineering, Kanagawa University
Rokkakubashi Kanagawa-ku Yokohama 221-8686, Japan
Email: narita@math.ie.kanagawa-u.ac.jp$\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{u}\mathrm{s}\dot{\mathrm{t}}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}$