Solution Representations for Poisson’s Equation, Martingale Structure, and the Markov Chain Central Limit Theorem

1. Introduction

Let $X=(X_n:n\ge 0)$ be an irreducible Markov chain taking values in a finite or countably infinite state space S, and let $P=(P(x,y):x,y\in S)$ be the one-step transition matrix of X. Given a function $f:S\to \mathbb{R}$ (encoded as a column vector), we say that a function g is a solution of Poisson’s equation associated with charge (or forcing function) f if

for $x\in S$ and

Poisson’s equation is fundamental to the analysis of the additive functional $S_n(f)\triangleq {\sum }_{i=0}^{n-1}f(X_i)$ because, in the presence of integrability,

should then be a martingale adapted to the filtration $({\mathcal{F}}_n:n\ge 0)$, where ${\mathcal{F}}_n=\sigma (X_j:j\le n)$. The martingale representation (1.3) can then be used to advantage in computing expected values (e.g., via optional sampling), and in deriving the law of large numbers, central limit theorem (CLT), and law of the iterated logarithm for $S_n(f)$; see, for example, Maigret (1978) and Kurtz (1981). It is also fundamental to computing joint “area moments” of the form $E_x{S}_n(k_1)S_n(k_2)$, where $E_x(·)$ is the expectation corresponding to the probability $P_x(·)=P(·|X_0=x)$; see Glynn et al. (2023). The solution to Poisson’s equation also arises in obtaining bounds on such moments via the Burkholder–Davis–Gundy inequality (see Hall and Heyde 2014) and in concentration inequalities for Markov additive sums (see Glynn and Ormoneit 2002). Furthermore, recent work of Rhee and Glynn (2022) shows that Poisson’s equation also plays a fundamental role in computing gradients of steady-state Markov chain performance measures; see also Glynn and Meyn (1996). Finally, it is worth nothing that (1.2) arises implicitly within the optimality equation for average reward/average cost stochastic control problems, because the value function under the optimal policy must satisfy (1.2); see Ross (2014).

Given the central importance of (1.2) within applied probability, this paper fully develops the uniqueness and existence theory for solutions to (1.2) when $|S|=\infty$. We note that uniqueness of solutions to (1.2) is equivalent to studying the class of harmonic functions h satisfying (1.1) and (1.2) with charge $f\equiv 0$ (i.e., Ph = h). Of course, constant functions are always harmonic, so solutions to (1.2) can (at best) only be unique up to an additive constant.

Our framework provides a unified perspective on Poisson’s equation that covers transient chains, null recurrent chains, and positive recurrent chains. The existing literature focuses on positive recurrent chains; see Nummelin (1991), Glynn and Meyn (1996), Hernández-Lerma and Lasserre (1999), Makowski and Shwartz (2002), Bhulai and Spieksma (2003), Meyn and Tweedie (2009), and Veretennikov (2017). As noted in Section 2, the extension to null recurrent processes is needed in order to develop a discrete time theory for Poisson’s equation that fully covers positive recurrent Markov jump processes as a special case. The ability to fully cover nonexplosive jump processes via our discrete time theory is useful both theoretically and numerically. In particular, any algorithm (e.g., algorithms that require state space truncation) that can compute solutions to Poisson’s equation for recurrent discrete-time chains automatically also covers positive recurrent Markov jump processes.

In addition to the new results for transient and null recurrent chains, this paper identifies a new representation for the solution to Poisson’s equation, namely, the final state entry time solution $\underset{˜}{g_z}$; see Sections 3 and 4. This representation complements the existing representations studied in the literature, namely, the initial state entry solution ${\tilde{g}}_z$ and the potential kernel representation $g^{*}$, and may be useful computationally; see Remark 3. This paper also focuses on studying minimal conditions under which these representations hold. Our theory establishes for the first time that the entry representations hold more generally than does the potential kernel representation; see Theorem 2 and Example 5.

In addition, we study the martingales induced by solutions to Poisson’s equation. When f is integrable and integrates to zero against the invariant measure η of X, the entry representations always make (1.3) a martingale; see Theorem 2. This weakens existing conditions in the literature under which $(M_n:n\ge 0)$ is a P_x-martingale; see Remark 5. Furthermore, we introduce a new “stopping property” characterization (Section 4) of solutions to Poisson’s equation under which our entry time solutions are unique. Finally, we study close to minimal conditions under which the central limit theorem for $S_n(f)$ is valid; see Section 6. Whereas existing CLT theory for Markov chains requires square integrability of the solution g, we weaken the condition and show that the martingale differences that arise in the Markov chain setting are always square integrable under our condition, regardless of the square integrability of g; see Theorem 5. We then develop a new Lyapunov condition (Condition (7.8)) that provides a weaker CLT sufficient condition than in the existing literature, thereby allowing us to weaken the condition required for the $GI/G/1$ queue delay sequence CLT to what is likely the best possible; see Section 7. The CLT is then extended to Markov jump processes in Section 8, thereby providing close to minimal conditions under which the CLT holds for jump processes.

This paper is organized as follows. Section 2 connects Poisson’s equation for jump processes to that for discrete-time chains, whereas Section 3 discusses different representations for the solution to Poisson’s equation when X is transient. Sections 4 and 5 extend this theory to the recurrent setting, whereas Section 6 discusses the CLT for Markov chains. Finally, Section 7 provides new Lyapunov conditions related to our theory, whereas Section 8 finishes the paper by extending the theory to the jump process setting.

2. Reduction of Poisson’s Equation for Markov Jump Processes to the Discrete-Time Setting

Let $Y=(Y(t):t\ge 0)$ be an S-valued irreducible nonexplosive Markov jump process with rate matrix $Q=(Q(x,y):x,y\in S)$. Given a function $\widehat{f}:S\to \mathbb{R}$, we say that g is a solution of Poisson’s equation (for Y) associated with the charge (or forcing function) $\widehat{f}$ if

for $x\in S$ and

Recall that the embedded discrete-time Markov chain $X=(X_n:n\ge 0)$ associated with Y describes the sequence of states visited by Y. The transition matrix of X is given by $R=(R(x,y):x,y\in S)$, where

and in which $\lambda (x)\triangleq -Q(x,x)$ for $x\in S$.

We observe that g is a solution to Poisson’s equation (for Y) associated with charge $\widehat{f}$ if and only if g is a solution to Poisson’s equation (for X) associated with charge f, where $f(x)=\widehat{f}(x)/\lambda (x)$ for $x\in S$, so that

In both discrete and continuous time, most applications of Poisson’s equations involve positive recurrent systems. Note that Y is recurrent if and only if X is recurrent. However, if Y is positive recurrent, X may be either positive or null recurrent. Hence, in reducing the analysis of Poisson’s equation for Y to the associated equation for X, we must allow for the possibility that X is null recurrent.

As a consequence, we will wish to develop a discrete-time theory for Poisson’s equation that goes beyond the existing theory that covers only positive recurrent chains.

3. Poisson’s Equation for Transient Chains

The literature that discusses the martingale structure of solutions to Poisson’s equation focuses on positive recurrent chains. In this section, we provide new theory that addresses transient Markov chains.

In particular, suppose that X is an irreducible transient Markov chain on countable state space S. (Irreducible chains are always positive recurrent when $|S|<\infty$.) We start by noting that when $f(X_n)$ is P_x-integrable for $n\ge 0,(M_n:n\ge 0)$ need not be a martingale, even in the presence of the integrability condition (1.1). We illustrate this point by providing a new example of a harmonic function h for which $(h(X_n):n\ge 0)$ is not a P_x-martingale.

Example 1.

Suppose $I=(I_n:n\ge 1),\hspace{0.17em}Z=(Z_n:n\ge 1)$, and $\beta =({\beta }_n:n\ge 1)$ are independent sequences of independent and identically distributed (i.i.d.) random variables (RVs) in which I₁ is Bernoulli(1/2), β₁ takes on the values $\{-1,1\}$ with equal probability 1/2, and Z₁ is integer valued with $E{Z}_1=0$ and $E{Z}_1^2=\infty$. If X satisfies the recursion

$$X_{n+1}=X_n+I_{n+1}{X}_n^2{Z}_{n+1}+(1-I_{n+1}){\beta }_{n+1}$$

for $n\ge 0$, then X is irreducible on $S=\mathbb{Z}$, h(x) = x is harmonic, and $h(X_1)$ is P_x-integrable for $x\in S$.

But observe that if $X_0=x$, then

$$X_2=x+I_1{x}^2{Z}_1+(1-I_1){\beta }_1+I_2{(x+I_1{x}^2{Z}_1+(I-I_1){\beta }_1)}^2{Z}_2+(1-I_2){\beta }_2.$$

Everything on the right-hand side is P_x-integrable except the term $x^4{I}_1{I}_2{Z}_1^2{Z}_2$, which is nonintegrable. Consequently, $h(X_2)$ fails to be P_x-integrable, and $(h(X_n):n\ge 0)$ is not a P_x-martingale.

Remark 1.

This is a counterexample to the lemma stated in Chung (1974, p. 345). The argument given there implicitly assumes h is nonnegative.

Assume now that the forcing function f is such that there exists some $z\in S$ for which

$${\displaystyle \sum _{n=0}^{\infty }{E}_z}|f(X_n)|<\infty .$$(3.1)

For $x\in S$, let $\tau (x)=\inf \{n\ge 1:X_n=x\}$ be the first entry time to x, and let

$$\begin{array}{ll}{g}^{*}(x)\hfill & ={\displaystyle \sum _{n=0}^{\infty }{E}_x}f(X_n),\hfill \\ {\tilde{g}}_z(x)\hfill & =E_x{\displaystyle \sum _{j=0}^{\tau (z)-1}f}(X_j)-E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}f}(X_j)\frac{P_x(\tau (z)=\infty )}{P_z(\tau (z)=\infty )},\hfill \\ \underset{\sim }{g_z}(x)\hfill & =-\frac{E_z{\sum }_{j=0}^{\tau (x)-1}f(X_j)}{P_z(\tau (x)<\infty )}+\frac{P_z(\tau (x)=\infty )}{P_z(\tau (x)<\infty )}\frac{E_z{\sum }_{j=0}^{\tau (z)-1}f(X_j)}{P_z(\tau (z)=\infty )}\hfill \end{array}$$

for $x\in S$. Our next theorem establishes that $g^{*}=(g^{*}(x):x\in S),\hspace{0.17em}{\tilde{g}}_z=({\tilde{g}}_z(x):x\in S),\hspace{0.17em}\text{and}\hspace{0.17em}\underset{\sim }{g_z}=(\underset{\sim }{g_z}(x):x\in S)$ are all solutions of Poisson’s equation for forcing function f and differ from one another by (at most) an additive constant.

We will call $g^{*}$ the potential kernel representation, ${\tilde{g}}_z$ the initial state entry time representation, and $\underset{\sim }{g_z}$ the final state entry time representation of the solution of Poisson’s equation. (We adopt the term “potential kernel representation” because ${\sum }_{n=0}^{\infty }{P}^n$ is a so-called potential kernel; see Revuz (1975, p. 41).) The representations ${\tilde{g}}_z$ and $\underset{\sim }{g_z}$ are completely new in this transient setting.

Theorem 1.

Suppose that X is an irreducible transient Markov chain for which (3.1) holds for some $z\in S$. Then,

1. (3.1) holds everywhere (i.e., ${\sum }_{n=0}^{\infty }{E}_x|f(X_n)|<\infty$ for each $x\in S$);

2. $g^{*}$ is a solution of Poisson’s equation for forcing function f;

3. for each $x\in S$,

   $$M_n^{*}\triangleq g^{*}(X_n)+{\displaystyle \sum _{j=0}^{n-1}f}(X_j)\to {\displaystyle \sum _{j=0}^{\infty }f}(X_j)\triangleq M_{\infty }^{*}\hspace{1em}\hspace{1em}{P}_x\text{-}a.s.$$
   as $n\to \infty$, and $(M_n^{*}:0\le n\le \infty )$ is a P_x-uniformly integrable martingale;

4. for each $y\in S,\hspace{0.17em}{\tilde{g}}_y$ and $\underset{\sim }{g_y}$ satisfy Poisson’s equation for the forcing function f, and

   $${\tilde{g}}_y(·)=\underset{\sim }{g_y}(·)=g^{*}(·)-g^{*}(y).$$

Proof.

Observe that

$$\infty >E_z{\displaystyle \sum _{j=0}^{\infty }|}f(X_j)|=E_z{\displaystyle \sum _{j=0}^{\tau (x)-1}|}f(X_j)|+P_z(\tau (x)<\infty )E_x{\displaystyle \sum _{j=0}^{\infty }|}f(X_j)|.$$

Because X is irreducible, $P_z(\tau (x)<\infty )>0$, establishing part i. As for part ii,

$$g^{*}(x)=f(x)+E_x{\displaystyle \sum _{j=1}^{\infty }f}(X_j)=f(x)+{\displaystyle \sum _{y\in S}^{}P}(x,y)g^{*}(y),$$

so that $g^{*}$ is a solution of Poisson’s equation for f. For part iii, we note that part i implies that $E_x|M_{\infty }^{*}|<\infty$, and

$$\begin{array}{ll}{E}_x[M_{\infty }^{*}|{\mathcal{F}}_n]\hfill & ={\displaystyle \sum _{j=0}^{n-1}}f(X_j)+E_x\left[{\displaystyle \sum _{j=n}^{\infty }f}(X_j)|{\mathcal{F}}_n\right]\hfill \\ \hfill & ={\displaystyle \sum _{j=0}^{n-1}f}(X_j)+E_x{g}^{*}(X_n)\hfill \\ \hfill & =M_n^{*},\hfill \end{array}$$

proving part iii, in view of theorem 9.4.5 of Chung (1974).

For part iv, we apply the optional sampling theorem to the martingale $(M_n^{*}:0\le n\le \infty )$, thereby obtaining

$$E_x{g}^{*}(X_{\tau (y)\wedge n})+E_x{\displaystyle \sum _{j=0}^{(\tau (y)\wedge n)-1}f}(X_j)=g^{*}(x)$$

for each $x,y\in S$ and $n\ge 0$, where $a\wedge b\triangleq \min (a,b)$. The uniform integrability of $(M_n^{*}:n\ge 0)$ ensures that when $n\to \infty$, we get

$$g^{*}(y)P_x(\tau (y)<\infty )+E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}f}(X_j)=g^{*}(x).$$(3.2)

Hence,

$$g^{*}(x)-g^{*}(y)=E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}f}(X_j)-g^{*}(y)P_x(\tau (y)=\infty ).$$(3.3)

Transience implies that $P_y(\tau (y)=\infty )>0$. So, setting x = y in (3.3) yields

$$g^{*}(y)=\frac{E_y{\sum }_{j=0}^{\tau (y)-1}f(X_j)}{P_y(\tau (y)=\infty )}.$$(3.4)

Substituting (3.4) in (3.3) shows that ${\tilde{g}}_y(·)=g^{*}(·)-g^{*}(y)$, so that ${\tilde{g}}_y$ agrees with $g^{*}$ up to an additive constant, and hence satisfies Poisson’s equation.

On the other hand, irreducibility implies that $P_x(\tau (y)<\infty )>0$, so (3.2) can be written as

$$g^{*}(y)=-\frac{E_x{\sum }_{j=0}^{\tau (y)-1}f(X_j)}{P_x(\tau (y)<\infty )}+\frac{g^{*}(x)}{P_x(\tau (y)<\infty )}.$$

Consequently,

$$g^{*}(y)-g^{*}(x)=-\frac{E_x{\sum }_{j=0}^{\tau (y)-1}f(X_j)}{P_x(\tau (y)<\infty )}+\frac{g^{*}(x)P_x(\tau (y)=\infty )}{P_x(\tau (y)<\infty )}.$$(3.5)

Using (3.4) to represent $g^{*}(x)$ and substituting this expression into the right-hand side of (3.5) establishes that $\underset{\sim }{g_x}(·)=g^{*}(·)-g^{*}(x)$, thereby proving that $\underset{\sim }{g_x}$ agrees with $g^{*}$ up to an additive constant. □

We have shown that under (3.1), all three representations yield solutions g to Poisson’s equation for which the martingale $(M_n:0\le n\le \infty )$ is P_x-uniformly integrable for $x\in S$. If g is an arbitrary solution to Poisson’s equation for which $(M_n:0\le n\le \infty )$ is P_x-uniformly integrable for $x\in S$, then the identical argument as followed in (3.2) and (3.4) establishes that ${\tilde{g}}_y(·)=g(·)-g(y)$. Hence, g must agree with all three representations, up to an additive constant. So, under (3.1), Poisson’s equation has solutions that are unique (up to additive constants) within the class of solutions g for which $(M_n:0\le n\le \infty )$ is a P_x-uniformly integrable martingale for $x\in S$.

In general, the class of harmonic functions can include nonconstant functions, so care must be taken in studying the uniqueness of solutions of Poisson’s equation.

Example 2.

Suppose that X is an irreducible birth–death chain on $S={\mathbb{Z}}_{+}$, where $P(i,i+1)=p_i=1-P(i,i-1)$ for $i\ge 1$, where $P(0,1)=p_0=1-P(0,0)$. Poisson’s equation for the forcing function f takes the form

$$p_0(g(1)-g(0))=-f(0)$$(3.6)

with

$$p_i{g}_i(i+1)+(1-p_i)g(i-1)-g(i)=-f(i)$$(3.7)

for $i\ge 1$. Note that g(1) can be solved in terms of f(0) and g(0) from (3.6), after which g(2), g(3), … can be recursively computed from (3.7). So, subject to the additive constant g(0), such birth–death chains always have unique solutions to Poisson’s equation for any forcing function f, regardless of whether X is transient, null recurrent, or positive recurrent. (This analysis corrects the example of section 9.7 of Makowski and Shwartz (2002), in which it is asserted that a reflecting birth–death random walk on ${\mathbb{Z}}_{+}$ possesses nonconstant harmonic functions.)

Example 3.

When we consider birth–death chains on $S=\mathbb{Z}$, nonuniqueness occurs. Poisson’s equation then takes the form

$$p_{i}g(i+1)+(1-p_i)g(i-1)-g(i)=-f(i)$$(3.8)

for $i\in \mathbb{Z}$. If $(\mathrm{\Delta }g)(i)\triangleq g(i)-g(i-1)$, then (3.8) asserts that

$$p_i(\mathrm{\Delta }g)(i+1)-(1-p_i)(\mathrm{\Delta }g)(i)=-f(i).$$(3.9)

Hence, we may arbitrarily choose g(0) and $(\mathrm{\Delta }g)(0)$, from which we can recursively solve for $(\mathrm{\Delta }g)(i+1)$ in terms of $\mathrm{\Delta }g(i)$ and f(i) for $i\ge 0$ (and for $(\mathrm{\Delta }g)(i-1)$ in terms of $(\mathrm{\Delta }g)(i)$ and $f(i-1)$ for $i\le 0$). So, Poisson’s equation again always has a solution. However, the space of harmonic functions is now always two-dimensional (rather than one-dimensional as in Example 2). So, this class of Markov chains always possesses nonconstant harmonic functions. When the birth–death chain is transient, the chain will then possess solutions to Poisson’s equation for f (even in the presence of (3.1)) that do not agree with $g^{*},{\tilde{g}}_y$, or $\underset{\sim }{g_y}$ (up to an additive constant). However, as noted earlier, these solutions will induce martingales $(M_n:n\ge 0)$ that do not exhibit the uniform integrability property discussed earlier.

Remark 2.

When X is irreducible and transient, (3.1) is guaranteed when f is finitely supported, because ${\sum }_{n=0}^{\infty }{P}_x(X_n=y)<\infty$ for each $x,y\in S$ when X is transient. In addition, (3.1) holds if and only if there exists a nonnegative (Lyapunov) function $v:S\to {\mathbb{R}}_{+}$ such that $(Pv)(x)\le v(x)-|f(x)|$ for $x\in S$. The sufficiency of the Lyapunov function follows from the fact that ${\sum }_{j=0}^{n-1}f(X_j)+v(X_n)$ is then a nonnegative P_x-supermartingale for each $x\in S$. For the necessity, let $v(x)={\sum }_{n=0}^{\infty }{E}_x|f(X_n)|$ for $x\in S$.

4. Poisson’s Equation for Recurrent Chains: Entry Representations

In this section, we extend the initial state entry representation ${\tilde{g}}_z$ and final state entry representation $\underset{\sim }{g_z}$ for solutions to Poisson’s equation when X is an irreducible recurrent Markov chain. The initial state entry representation for positive recurrent chains has a long history; see Derman and Veinott (1967, theorems 1 and 2) and also Schaufele (1967). However, the extension to null recurrent chains given here is new, as is the final state entry representation that we shall introduce (and that extends that given in Section 3).

Recall that an irreducible recurrent Markov chain has a nontrivial nonnegative invariant measure $\eta =(\eta (x):x\in S)$ (which we encode as a row vector) that is unique up to a multiplicative constant. The measure η satisfies

Furthermore, the recurrence implies that for each $x\in S,\hspace{0.17em}{P}_x(\tau (x)<\infty )=1$. If we fix any $z\in S$, then η can be defined via

for $x\in S$; see, for example, Meyn and Tweedie (2009). When X is positive recurrent, we denote the multiple of η that has been normalized to be a probability as π. Let $L^1(\eta )\triangleq \{k:\eta (x)|k(x)|<\infty \}$, and observe that $k\in L^1(\eta )$ is equivalent to requiring that

If g is a solution of Poisson’s equation associated with forcing function f and $g\in L^1(\eta )$, then (4.1) implies that $|Pg|\le P|g|\in L^1(\eta )$, which implies, in turn, that $f\in L^1(\eta )$.

Because g satisfies Poisson’s equation for f, it follows that

So, when $g\in L^1(\eta )$, it is necessary that $f\in L_0^1(\eta )\triangleq \{k\in L^1(\eta ):\eta k=0\}$ in order that Poisson’s equation be solvable. This is the standard solvability condition imposed on Poisson’s equation when X is positive recurrent. We shall also impose this condition when X is null recurrent. Of course, Examples 2 and 3 make clear that Poisson’s equation can have solutions for $f\notin L_0^1(\eta )$, even when X is recurrent. However, we shall not pursue such forcing functions f in this paper. (But there are also irreducible recurrent chains for which Poisson’s equation only has a solution for $f\in L_0^1(\eta )$, as for finite chains.)

If $f\in L_0^1(\eta )$, we note that (4.3) implies that for each $x,y\in S$,

Because irreducibility implies that $P_y(\tau (x)<\tau (y))>0$, we may conclude that

We now define the initial state entry representation $\underset{\sim }{g_z}$ and final state entry representation in the recurrent setting via

andfor $x\in S$. Then (4.2) implies that ${\tilde{g}}_z(z)=0=\underset{\sim }{g_z}(z)$, because

Given a solution g to Poisson’s equation for the forcing function f, we say that g has the stopping property if $(M_n:n\ge 0)$ is a P_x-martingale for each $x\in S$, and if for each $x\in S$ and nonempty $B\subseteq S$,

where $T(B)=\inf \{n\ge 0:X_n\in B\}$ is the hitting time of B. In other words, g has the stopping property if the martingale can be “stopped” at all hitting times of S while preserving the optional sampling identity.

Theorem 2.

Let X be an irreducible recurrent Markov chain and assume that $f\in L_0^1(\eta )$. Then ${\tilde{g}}_z$ is a solution to Poisson’s equation with forcing function f. Furthermore,

1. $({\tilde{g}}_z(X_n)+{\sum }_{j=0}^{n-1}f(X_j):n\ge 0)$ is a P_x-martingale for each $n\ge 0$;

2. ${\tilde{g}}_z$ has the stopping property;

3. if g is a solution to Poisson’s equation for f having the stopping property, then $g(·)={\tilde{g}}_z(·)+g(z)$;

4. ${\tilde{g}}_z(·)=\underset{\sim }{g_z}(·)$ and ${\tilde{g}}_y(·)={\tilde{g}}_z(·)-{\tilde{g}}_z(y)$ for $y\in S$.

Proof.

The fact that ${\tilde{g}}_z(·)$ is a solution of Poisson’s equation in the positive recurrent case can be found in Derman and Veinott (1967). We give a short self-contained proof in the general case.

Let ${\beta }_z(n)=\inf \{j>n:X_j=z\}$ be the time of the first visit to z after time n, let $T_n(z)$ be the time of the nth return to z, and let

$$q_z(x)\triangleq E_x{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|$$

for $x,z\in S$. Note that

$$\begin{array}{ll}{\displaystyle \sum _y^{}P}(x,y)|{\tilde{g}}_z(y)|\hfill & \le {\displaystyle \sum _y^{}P}(x,y)q_z(y)\hfill \\ \hfill & ={\displaystyle \sum _y^{}P}(x,y)E_y{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|\hfill \\ \hfill & =E_x{\displaystyle \sum _{j=1}^{{\beta }_z(1)-1}|}f(X_j)|\hfill \\ \hfill & \le E_x{\displaystyle \sum _{j=0}^{T_2(z)-1}|}f(X_j)|\hfill \\ \hfill & =q_z(x)+q_z(z)<\infty ,\hfill \end{array}$$

proving (1.1) for ${\tilde{g}}_z(·)$. Also, by conditioning on X₁ and noting that ${\tilde{g}}_z(z)=0$, we find that

$${\tilde{g}}_z(x)=f(x)+{\displaystyle \sum _{y\ne z}^{}P}(x,y){\tilde{g}}_z(y)=f(x)+{\displaystyle \sum _y^{}P}(x,y){\tilde{g}}_z(y),$$

proving (1.2), so ${\tilde{g}}_z$ is a solution of Poisson’s equation for f.

To prove part i, the only nontrivial property needing verification is the P_x-integrability of the martingale associated with ${\tilde{g}}_z(·)$. First,

$$E_x{\displaystyle \sum _{j=0}^{n-1}|}f(X_j)|\le E_x{\displaystyle \sum _{j=0}^{T_n(z)-1}|}f(X_j)|=q_z(x)+(n-1)q_z(z)<\infty .$$

Also, because ${\beta }_z(n)\le T_{n+1}(z)$,

$$\begin{array}{ll}{E}_x|{\tilde{g}}_z(X_n)|\hfill & \le E_x{q}_z(X_n)\hfill \\ \hfill & =E_x{\displaystyle \sum _{j=n}^{{\beta }_z(n)-1}|}f(X_j)|\hfill \\ \hfill & \le E_x{\displaystyle \sum _{j=0}^{T_{n+1}(z)-1}|}f(X_j)|=q_z(x)+n{q}_z(z)<\infty ,\hfill \end{array}$$

verifying the P_x-integrability.

As for part ii, choose $y\in B$ and note that $T(B)\le \tau (y)$. Applying the optional sampling theorem, we find that

$$E_x{\tilde{g}}_z(X_{T(B)})I(T(B)\le n)+E_x{\tilde{g}}_z(X_n)I(T(B)>n)+E_x{\displaystyle \sum }_{j=0}^{(T(B)\wedge n)-1}f(X_j)={\tilde{g}}_z(z)$$(4.6)

for $x\in S$ and $n\ge 0$. Note that

$$|{\displaystyle \sum }_{j=0}^{(T(B)\wedge n)-1}f(X_j)|\le {\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|$$

and

$$|{\tilde{g}}_z(X_{T(B)})|I(T(B)\le n)\le q_z(X_{T(B)}).$$

But $E_x{\sum }_{j=0}^{\tau (y)-1}|f(X_j)|=q_y(x)<\infty$, and

$$E_x{q}_z(X_{T(B)})=E_x{\displaystyle \sum }_{j=T(B)}^{{\beta }_z(T(B))-1}|f(X_j)|\le E_x{\displaystyle \sum }_{j=0}^{{\beta }_z(\tau (y))-1}|f(X_j)|=q_y(x)+q_z(y)<\infty ,$$(4.7)

so the dominated convergence theorem can be applied to the first and third terms on the left-hand side of (4.6). Finally, for the second term, observe that

$$\begin{array}{ll}|E_x{\tilde{g}}_z(X_n)|I(T(B)>n)\hfill & \le E_x{q}_z(X_n)I(\tau (y)>n)\hfill \\ \hfill & =E_x{\displaystyle \sum _{j=n}^{{\beta }_z(n)-1}|}f(X_j)|I(\tau (y)>n),\hfill \end{array}$$

where

$${\displaystyle \sum _{j=n}^{{\beta }_z(n)-1}|}f(X_j)|I(\tau (y)>n)\le {\displaystyle \sum _{j=0}^{{\beta }_z(\tau (y))-1}|}f(X_j)|,$$

which has finite P_x-expectation; see (4.7). Consequently, the second term converges to zero as $n\to \infty$ by the dominated convergence theorem, proving the stopping property.

For part iii, suppose that g has the stopping property. If $B=\{z\}$, the stopping property implies that

$$g(z)+E_x{\displaystyle \sum _{j=0}^{\tau (z)-1}f}(X_j)=g(x)$$

for $x\in S$, so that $g(·)-g(z)={\tilde{g}}_z(·)$.

Finally, for part iv, we use the fact that ${\tilde{g}}_z(·)$ has the stopping property to conclude that

$${\tilde{g}}_z(y)+E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}f}(X_j)={\tilde{g}}_z(x)$$(4.8)

for $y\in S$. Consequently, ${\tilde{g}}_y(x)={\tilde{g}}_z(x)-{\tilde{g}}_z(y)$. Also, setting x = z in (4.8) shows that $\underset{\sim }{g_z}(·)={\tilde{g}}_z(·)$, proving part iv. □

Remark 3.

Theorem 2 is new when X is null recurrent, as are parts i–iv in the positive recurrent setting. This paper introduces the final state entry representation in both the transient and recurrent settings. This representation presents the possibility that one can use simulation to estimate solutions to Poisson’s equation by running independent paths initialized at a single state $z\in S$, whereas the initial state entry representation suggests a simulation algorithm that requires running independent paths from each state $x\in S$ at which one wishes to estimate the solution. We leave the pursuit of this possibility to future research.

Remark 4.

The use of the stopping property to characterize the uniqueness of solutions (up to an additive constant) is new to this paper. Much of the existing literature studies uniqueness within the class of solutions $g\in L^1(\eta )$ when X is positive recurrent; see, for example, Makowski and Shwartz (2002, p. 278) and Meyn and Tweedie (2009, p. 443). Suppose, however, that X is only irreducible and recurrent. Then, if $g_1,g_2\in L^1(\eta )$ are two solutions of Poisson’s equation, $h=g_1-g_2\in L^1(\eta )$ is harmonic. Hence, for $x\in S$,

$$h(x)=\frac{1}{n}{\displaystyle \sum _{j=0}^{n-1}{E}_x}h(X_j)\to \frac{E_z{\sum }_{j=0}^{\tau (z)-1}h(X_j)}{E_z\tau (z)}=\frac{\eta h}{E_z\tau (z)}$$

as $n\to \infty$; see Chung (1967). So h must be constant (and in fact must be zero when X is null recurrent).

Remark 5.

An alternative uniqueness characterization for positive recurrent chains can be found in theorem 17.7.2 of Meyn and Tweedie (2009). The martingale property (Theorem 2) appears as theorem 17.4.3 in Meyn and Tweedie (2009), but with the stronger requirement that ${\tilde{g}}_z\in L^1(\eta )$.

In view of Remarks 4 and 5, we now turn to the question of when ${\tilde{g}}_z$ (and hence $\underset{\sim }{g_z}$) lies in $L^1(\eta )$.

Theorem 3.

Let X be irreducible and recurrent with $f\in L_0^1(\eta )$. Then, ${\tilde{g}}_z\in L^1(\eta )$ if

$$\eta q_z=E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}(j+1)}|f(X_j)|<\infty$$(4.9)

and

$$\eta {\tilde{g}}_z=E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}(j+1)}f(X_j).$$(4.10)

Furthermore, if X is positive recurrent and (4.9) holds for one $z\in S$, then it holds for all $z\in S$. Also, when X is positive recurrent, ${\tilde{g}}_z\in L^1(\eta )$ if and only if ${\tilde{g}}_y\in L^1(\eta )$ for each $y\in S$.

Proof.

Note that

$$\begin{array}{ll}{\displaystyle \sum _x^{}\eta }(x)|{\tilde{g}}_z(x)|\hfill & \le {\displaystyle \sum _x^{}\eta }(x)q_z(x)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\infty }{q}_z}(X_j)I(\tau (z)>j)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{k=j}^{{\beta }_z(j)-1}|}}f(X_k)|I(\tau (z)>j)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{k=j}^{\tau (z)-1}|}}f(X_k)|I(\tau (z)>j)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}{\displaystyle \sum _{k=j}^{\tau (z)-1}|}}f(X_k)|\hfill \\ \hfill & =E_z{\displaystyle \sum _{k=0}^{\tau (z)-1}|}f(X_k)|{\displaystyle \sum _{j=0}^{k}1}\hfill \\ \hfill & =E_z{\displaystyle \sum _{k=0}^{\tau (z)-1}(k+1)}|f(X_k)|<\infty ,\hfill \end{array}$$(4.11)

so ${\tilde{g}}_z\in L^1(\eta )$. A similar argument establishes that

$${\displaystyle \sum _x^{}\eta }(x){\tilde{g}}_z(x)=E_z{\displaystyle \sum _{k=0}^{\tau (z)-1}(k+1)}f(X_k).$$

We note that (4.11) implies that (4.9) is equivalent to $q_z\in L^1(\eta )$. If X is positive recurrent and $y\in S$,

$$\begin{array}{ll}\eta q_y\hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}{q}_y}(X_j)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}{\displaystyle \sum _{k=j}^{{\beta }_y(k)}|}}f(X_k)|\hfill \\ \hfill & \le E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}{\displaystyle \sum _{k=j}^{{\beta }_y(\tau (z))-1}|}}f(X_k)|\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}\left({\displaystyle \sum _{k=j}^{\tau (z)-1}|}f(X_k)|+{\displaystyle \sum _{k=\tau (z)}^{{\beta }_y(\tau (z))-1}|}f(X_k)|\right)}\hfill \\ \hfill & =\eta q_z+E_z\tau (z)q_y(z),\hfill \end{array}$$

so $q_y\in L^1(\eta )$, thereby proving that (4.9) holds for $y\in S$. Finally, if ${\tilde{g}}_z\in L^1(\eta )$, then ${\tilde{g}}_y\in L^1(\eta )$ for $y\in S$, because ${\tilde{g}}_y-{\tilde{g}}_z$ is a constant (integrable) function. □

Remark 6.

Suppose that $|f(x)|\ge 1$ for $x\in S$. Then, $\eta q_z<\infty$ is equivalent to asserting that η is an $|f|$-regular measure; see Meyn and Tweedie (2009, p. 339). (Note that $f\ge 1$ is required within the definition of f-regularity.)

When ${\tilde{g}}_z\in L^1(\eta )$ and X is irreducible, aperiodic, and recurrent, it is known that for each $x\in S$,

$$E_x{\tilde{g}}_z(X_n)\to \frac{E_z{\sum }_{j=0}^{\tau (z)-1}{\tilde{g}}_z(X_j)}{E_z\tau (z)}$$

as $n\to \infty$. Hence, under these conditions, part i of Theorem 2 and (4.10) imply that

$${\displaystyle \sum _{j=0}^{n-1}{E}_x}f(X_j)\to {\tilde{g}}_z(x)-\frac{E_z{\sum }_{j=0}^{\tau (z)-1}(j+1)f(X_j)}{E_z\tau (z)}$$(4.12)

as $n\to \infty$.

Remark 7.

The limit (4.12) has the following simulation interpretation. In particular, the time-average estimator $n^{-1}{\sum }_{i=0}^{n-1}r(X_i)$ has a bias in estimating the stationary reward per unit time πr for a positive recurrent irreducible Markov chain that is given by

$$E_x\frac{1}{n}{\displaystyle \sum _{i=0}^{n-1}r}(X_i)-\pi r=\frac{1}{n}\left({\tilde{g}}_z(x)-\frac{E_z{\sum }_{j=0}^{\tau (z)-1}(j+1)f(X_j)}{E_z\tau (z)}\right)+o\left(\frac{1}{n}\right)$$

as $n\to \infty$, where we have set $f(x)=r(x)-\pi r$; see also Awad and Glynn (2007, theorem 3.1).

Remark 8.

Recall that ${\tilde{g}}_y(·)={\tilde{g}}_z(·)-{\tilde{g}}_z(y)$. Consequently, if ${\tilde{g}}_z\in L^1(\eta )$ and ${\tilde{g}}_z(y)\ne 0,\hspace{0.17em}{\tilde{g}}_y\notin L^1(\eta )$ if X is null recurrent (because nonzero constant functions are not η-integrable). So, (4.10) may only be well defined at some $z\in S$ when X is a null recurrent chain. This raises the question of whether there exist null recurrent chains for which $q_z\in L^1(\eta )$ for some $z\in S$, but not for others (thereby establishing that the final part of Theorem 3 fails when X is null recurrent).

Example 4.

Suppose that $S={\mathbb{Z}}^{+}$ and that X is a Markov chain with $P(i,i+1)=1/2=P(i+1,i)$ for $i\ge 3,P(3,1)=1/2,\hspace{0.17em}P(0,1)=1=P(2,3)$, and $P(1,2)=P(1,0)=1/2$. Then, η is a multiple of $(1/2,1,1/2,1,1,\dots )$. If $f(0)=-2,f(1)=1,$ and f(x) = 0 for $x\ge 2$, then $f\in L_0^1(\eta )$ and

$$\begin{array}{l}{E}_1{\displaystyle \sum _{j=0}^{\tau (1)-1}(j+1)}|f(X_j)|=E_1{\displaystyle \sum _{j=0}^{\tau (1)-1}(j+1)}|f(X_j)|I(X_1=0)\\ =1+4=5,\end{array}$$

whereas

$$\begin{array}{ll}{E}_2{\displaystyle \sum _{j=0}^{\tau (2)-1}(j+1)}|f(X_j)|\hfill & =E_2{\displaystyle \sum _{j=0}^{\tau (2)-1}(j+1)}|f(X_j)|I(X_1=3)\hfill \\ \hfill & \ge E_2(\tau (1)+1)I(X_1=3)\hfill \\ \hfill & =E_3\tau (1)P_2(X_1=3)=\infty ,\hfill \end{array}$$

so $q_1\in L^1(\eta )$, whereas $q_2\notin L^1(\eta )$.

5. Poisson’s Equation for Recurrent Chains: Potential Kernel Representations

As discussed in Section 3, the potential kernel representation takes the form

In order that the right-hand side of (5.1) be well defined, we require that

exists and is finite valued for $x\in S$.

In order that (5.2) be valid, we must have that $E_{x}f(X_n)\to 0$ as $n\to \infty$. This typically fails when X is a periodic positive recurrent chain with $f\in L_0^1(\eta )$. However, this problem can be fixed when X is periodic with period p by modifying (5.2).

Theorem 4.

Let $X=(X_n:n\ge 0)$ be irreducible and recurrent, with period $p\ge 1$. Suppose $f\in L_0^1(\eta )$ and ${\tilde{g}}_z\in L^1(\eta )$ for some $z\in S$. Then,

$$\underset{n\to \infty }{\lim }{\displaystyle \sum _{j=0}^n{E}_x}f(X_j)+\frac{1}{p}{\displaystyle \sum _{i=1}^{p-1}(p-i)}{E}_{x}f(X_{n+i})$$(5.3)

exists and is finite valued. Let $g^{*}(x)$ be the limit defined by (5.3). Then, $g^{*}$ is a solution to Poisson’s equation, and

$$g^{*}(x)=\{\begin{array}{ll}{\tilde{g}}_z(x)-\pi {\tilde{g}}_z\hfill & if X is \mathit{\text{positive}} \mathit{\text{recurrent}},\hfill \\ {\tilde{g}}_z(x)\hfill & if X is \mathit{\text{null}} \mathit{\text{recurrent}}.\hfill \end{array}$$

Proof.

Note that Theorem 2, part i, implies that for $0\le i<p$,

$${\displaystyle \sum _{j=0}^{n+i}{E}_x}f(X_j)={\tilde{g}}_z(x)-E_x{\tilde{g}}_z(X_{n+i+1}).$$

It follows that

$$\begin{array}{ll}\frac{1}{p}{\displaystyle \sum _{i=0}^{p-1}{\displaystyle \sum _{j=0}^{n+i}{E}_x}}f(X_j)\hfill & ={\displaystyle \sum _{j=0}^n{E}_x}f(X_j)+\frac{1}{p}{\displaystyle \sum _{i=1}^{p-1}(p-i)}{E}_{x}f(X_{n+i})\hfill \\ \hfill & ={\tilde{g}}_z(x)-\frac{1}{p}{\displaystyle \sum _{i=0}^{p-1}{E}_x}{\tilde{g}}_z(X_{n+i+1}).\hfill \end{array}$$

If X is positive recurrent and ${\tilde{g}}_z\in L^1(\eta )$, then

$$\frac{1}{p}{\displaystyle \sum _{i=0}^{p-1}{E}_x}{\tilde{g}}_z(X_{n+i+1})\to \pi {\tilde{g}}_z$$

as $n\to \infty$, whereas if X is null recurrent and ${\tilde{g}}_z\in L^1(\eta )$,

$$\frac{1}{p}{\displaystyle \sum _{i=0}^{p-1}{E}_x}{\tilde{g}}_z(X_{n+i+1})\to 0$$

as $n\to \infty$; see Chung (1967). In both cases, the limit (5.3) exists and is finite-valued. Furthermore, $g^{*}-{\tilde{g}}_z$ is a constant function when X is positive recurrent, and is zero when X is null recurrent. This implies that $g^{*}$ is a solution of Poisson’s equation. □

Note that Theorem 2 establishes that the initial state and final state entry representations are well-behaved solutions to Poisson’s equation whenever $f\in L_0^1(\eta )$. On the other hand, Theorem 4 requires the extra condition that ${\tilde{g}}_z\in L^1(\eta )$ in order that $g^{*}$ be well defined. Our next example shows that the limit (5.2) (and (5.3)) can fail to be finite-valued without the extra assumption ${\tilde{g}}_z\in L^1(\eta )$. This example establishes that the two entry representations ${\tilde{g}}_z$ and $\underset{\sim }{g_z}$ hold more generally than does the potential kernel representation $g^{*}$.

Example 5.

Let ${\beta }_1,{\beta }_2,\dots$ be a sequence of i.i.d. positive integer-valued RVs, and let

$$S_n={\beta }_1+{\beta }_2+\cdots +{\beta }_n,$$

with $S_0=0$. Let $\mathcal{\ell }(n)=\max \{j:S_j\le n\}$, and let

$$X_n=n-S_{\mathcal{\ell }(n)}$$

be the “current age” Markov chain associated with the interrenewal times ${\beta }_1,{\beta }_2,\dots$. Let $\tilde{f}(x)={\delta }_{x0}$, so that $\tilde{f}(·)$ is one when x = 0 and zero otherwise. Then,

$$E_0\tilde{f}(X_n)=P_0(X_n=0)\triangleq u_n,$$

where $(u_n:n\ge 0)$ is the renewal sequence associated with the increment probability mass function $(p_j:j\ge 1)$ given by $p_j=P({\beta }_1=j)$ for $j\ge 1$. Assume that $(p_j:j\ge 1)$ is a positive sequence for which there exists c > 0 and $\alpha >1$ for which

$$P({\beta }_1>n)\sim c{n}^{-\alpha }$$

as $n\to \infty$ (where we write $a_n\sim b_n$ as $n\to \infty$ when $a_n/b_n\to 1$ as $n\to \infty$). Then, $E{\beta }_1<\infty$, and X is positive recurrent with $\pi (0)=\lambda \triangleq 1/E{\beta }_1$. Let $f(x)=\tilde{f}(x)-\lambda$.

According to Frenk (1982, lemma 4),

$$E_{0}f(X_n)=u_n-\lambda \sim \frac{{\lambda }^{2}nP({\beta }_1>n)}{\alpha -1}$$

as $n\to \infty$, from which it follows that

$$E_{0}f(X_n)\sim \frac{{\lambda }^{2}c{n}^{1-\alpha }}{(\alpha -1)}$$

as $n\to \infty$. As a consequence, if $\alpha \in (1,2]$, the limit (5.2) fails to be finite valued.

We conclude this section by studying when (5.2) can be strengthened to

$${\displaystyle \sum _{n=0}^{\infty }|}{E}_{x}f(X_n)|<\infty$$(5.4)

for $x\in S$. The absolute summability (5.4) can be mathematically useful in some settings, so we provide a criterion for (5.4).

Proposition 1.

Suppose that X is an irreducible aperiodic positive recurrent Markov chain, and assume that $f\in L_0^1(\eta )$. If there exists $z\in S$ for which $q_z\in L^1(\eta )$ and $E_z{\tau }^2(z)<\infty$, then (5.4) holds.

Proof.

We first note that $E_z\tau {(z)}^2<\infty$ is a solidarity property, in the sense that if it holds for one $z\in S$, then it holds for all $x\in S$; see Chung (1967, p. 84). As a consequence of Theorem 3, we may assume $q_x\in L^1(\eta )$ and $E_x{\tau }^2(x)<\infty$. This implies that $E_x{\sum }_{j=0}^{\tau (x)-1}(j+1)(|f(X_j)|\vee 1)<\infty$, where $a\vee b=\max (a,b)$. Hence, η is $|f|\vee 1$ regular, so theorem 14.3.5 of Meyn and Tweedie (2009) applies, proving (5.4). □

6. The CLT for Markov Chains

The most common means of proving the CLT for positive recurrent Markov chains is to apply the martingale CLT to the martingale of Section 4. In particular, for $f\in L_0^1(\eta )$, we write

as a sum of martingale differences, namely, ${\tilde{M}}_z(n)={\sum }_{j=1}^n{\tilde{D}}_z(j)$, wherefor $j\ge 1$. To guarantee the square integrability of the ${\tilde{D}}_z(j)$’s, the natural sufficient condition is to require that ${\tilde{g}}_z\in L^2(\pi )\triangleq \{k:{\sum }_x{k}^2(x)\pi (x)<\infty \}$. This is the approach followed by Gordin and Lifšic (1978), Maigret (1978), Kurtz (1981), Bhattacharya (1982), Glynn and Meyn (1996), and Meyn and Tweedie (2009); see also the survey by Jones (2004).

However, this approach does not lead to minimal conditions under which the Markov chain CLT holds. Suppose that X is irreducible and positive recurrent. For $f\in L_0^1(\eta )$, the necessary and sufficient condition under which there exists ${\sigma }^2<\infty$ for which

as $n\to \infty$ is that there exists $z\in S$ for which

The sufficiency of (6.2) for (6.1) can be found in Chung (1967), whereas the necessity is due to Glynn and Whitt (2002); see also Glynn and Whitt (1993). The key to establishing these results is to rely on the regenerative structure of X, thereby allowing for the exploitation of known necessary and sufficient conditions that have been developed for CLT’s governing sums of i.i.d. random variables.

This raises the question of the connection between (6.2), ${\tilde{g}}_z\in L^2(\pi )$, and $E_{\pi }{\tilde{D}}_z{(1)}^2<\infty$.

Theorem 5.

Suppose that X is irreducible and recurrent. Then,

$$E_z{\left({\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|\right)}^2<\infty$$(6.3)

is equivalent to $f{q}_z\in L^1(\eta )$. Furthermore, if X is positive recurrent and (6.3) holds, then

1. ${\sigma }^2=2E_{\pi }f(X_0){\tilde{g}}_z(X_0)-E_{\pi }f{(X_0)}^2$;

2. $E_{\pi }{\tilde{D}}_z{(1)}^2<\infty$ and ${\sigma }^2=E_{\pi }{\tilde{D}}_z{(1)}^2$.

Whereas (6.2) is difficult to translate into a condition involving a Lyapunov function, the stronger (6.3) is well suited to the development of a Lyapunov function criterion. Furthermore, (6.3) can hold even when ${\tilde{g}}_z\notin L^2(\pi )$. In fact, this phenomenon can arise even within the delay sequence for the single-server queue; see Section 7. Finally, in the presence of (6.3), $E_{\pi }{\tilde{D}}_z{(1)}^2<\infty$ (so that the martingale CLT can be applied), even without ${\tilde{g}}_z\in L^2(\pi )$.

Proof of Theorem 5.

We note that

$$\begin{array}{ll}{\displaystyle \sum _x^{}\eta }(x)|f(x)|q_z(x)\hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|q_z(X_j)\hfill \\ \hfill & =E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|{\displaystyle \sum _{k=j}^{\tau (z)-1}|}f(X_k)|\hfill \\ \hfill & \le E_z{\left({\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|\right)}^2\hfill \end{array}$$

and

$${\displaystyle \sum _x^{}\eta }(x)|f(x)|q_z(x)\ge \frac{1}{2}{E}_z{\left({\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|\right)}^2,$$

so $f{q}_z\in L^1(\eta )$ is equivalent to (6.3).

When (6.2) holds and X is positive recurrent, theorem 1 of Chung (1967, p. 99) establishes that

$${\sigma }^2=\frac{E_z{\left({\sum }_{j=0}^{\tau (z)-1}f(X_j)\right)}^2}{E_z\tau (z)}.$$(6.4)

In the presence of (6.3),

$$\begin{array}{ll}{\sigma }^2\hfill & =\frac{2E_z{\sum }_{j=0}^{\tau (z)-1}f(X_j){\sum }_{k=j}^{\tau (z)-1}f(X_k)}{E_z\tau (z)}-\frac{E_z{\sum }_{j=0}^{\tau (x)-1}{f}^2(X_j)}{E_z\tau (z)}\hfill \\ \hfill & =2\frac{E_z{\sum }_{j=0}^{\tau (z)-1}f(X_j){\tilde{g}}_z(X_j)}{E_z\tau (z)}-\frac{E_z{\sum }_{j=0}^{\tau (z)-1}{f}^2(X_j)}{E_z\tau (z)}\hfill \\ \hfill & =2E_{\pi }f(X_0){\tilde{g}}_z(X_0)-E_{\pi }{f}^2(X_0),\hfill \end{array}$$

proving part i. For part ii, note that for each $x\in S$,

$$\begin{array}{ll}4E_z{\left({\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|\right)}^2\hfill & \ge E_z{\left({\displaystyle \sum _{j=0}^{T_2(z)-1}|}f(X_j)|\right)}^2\hfill \\ \hfill & \ge E_z{\left({\displaystyle \sum _{j=\tau (x)+1}^{T_2(z)-1}|}f(X_j)|\right)}^{2}I(\tau (x)<\tau (z))\hfill \\ \hfill & =P_z(\tau (x)<\tau (z))E_x{\left({\displaystyle \sum _{j=1}^{{\beta }_z(1)-1}|}f(X_j)|\right)}^2\hfill \\ \hfill & =P_z(\tau (x)<\tau (z))E_x{q}_z{(X_1)}^2.\hfill \end{array}$$

Because X is irreducible, $P_z(\tau (x)<\tau (z))>0$, and hence $d(x)\triangleq E_x{q}_z{(X_1)}^2<\infty$ for $x\in S$. Let $T_m=\inf \{n\ge 0:d(X_n)>m\}$. Note that $E_x{\tilde{D}}_z{(1)}^2\le E_x{\tilde{g}}_z{(X_1)}^2\le E_x{q}_z{(X_1)}^2$. Because $d(X_j)\le m$ for $j<T_m,\hspace{0.17em}E[{\tilde{D}}_z{(j)}^2|X_{j-1}]\le m$ on $\{T_m\ge j\}$. Hence, we find that for j < k,

$$\begin{array}{l}E{\tilde{D}}_z(j){\tilde{D}}_z(k)I(T_m\wedge \tau (z)\ge k)=E{\tilde{D}}_z(j)I(T_m\wedge \tau (z)\ge k)E[{\tilde{D}}_z(k)|X_0,\dots ,X_{k-1}]\\ =0,\end{array}$$

so that

$$E_z{\left({\displaystyle \sum _{j=1}^{T_m\wedge \tau (z)}{\tilde{D}}_z}(j)\right)}^2=E_z{\displaystyle \sum _{j=1}^{T_m\wedge \tau (z)}{\tilde{D}}_z}{(j)}^2.$$(6.5)

The monotone convergence theorem implies that

$$E_z{\displaystyle \sum _{j=1}^{T_m\wedge \tau (z)}{\tilde{D}}_z}{(j)}^2\nearrow E_z{\displaystyle \sum _{j=1}^{\tau (z)}{\tilde{D}}_z}{(j)}^2$$

as $m\to \infty$. For the left-hand side of (6.5), we note the conditional Jensen inequality implies that when $X_0=z$,

$$\begin{array}{ll}|{\displaystyle \sum _{j=1}^{T_m\wedge \tau (z)}{\tilde{D}}_z}(j){|}^2\hfill & \le {(q_z(X_{T_m})I(T_m<\tau (z))+{\displaystyle \sum _{k=0}^{(T_m\wedge \tau (z))-1}|}f(X_k)|)}^2\hfill \\ \hfill & ={\left(E_z\right[{\displaystyle \sum _{k=0}^{\tau (z)-1}|}f(X_k)|\hspace{0.17em}|\hspace{0.17em}{X}_j:0\le j\le T_m\left]\right)}^2\hfill \\ \hfill & \le E_z[{\left({\displaystyle \sum _{k=0}^{\tau (z)-1}|}f(X_k)|\right)}^2|\hspace{0.17em}{X}_j:0\le j\le T_m].\hfill \end{array}$$(6.6)

Theorem 9.4.5 of Chung (1974) implies that the final sequence of RVs appearing on the right-hand side of (6.6) is uniformly integrable in m. Consequently, the left-hand side of (6.6) is uniformly integrable, so

$$E_z{\left({\displaystyle \sum _{j=1}^{T_m\wedge \tau (z)}{\tilde{D}}_z}(j)\right)}^2\to E_z{\left({\displaystyle \sum _{j=1}^{\tau (z)}{\tilde{D}}_z}(j)\right)}^2=E_z{\left({\displaystyle \sum _{j=0}^{\tau (z)-1}f}(X_j)\right)}^2.$$

In view of (6.4), we conclude that

$$\begin{array}{ll}{\sigma }^2=\frac{E_z{\sum }_{j=1}^{\tau (z)}{\tilde{D}}_z{(j)}^2}{E_z\tau (z)}\hfill & =\frac{E_z{\sum }_{j=0}^{\tau (z)-1}{E}_z[{\tilde{D}}_z{(j)}^2\hspace{0.17em}|X_{j-1}]}{E_z\tau (z)}\hfill \\ \hfill & =E_{\pi }E[{\tilde{D}}_z{(1)}^2|X_0]\hfill \\ \hfill & =E_{\pi }{\tilde{D}}_z{(1)}^2,\hfill \end{array}$$

proving part ii. □

Hence, for irreducible positive recurrent Markov chains on discrete state space S, the martingale differences ${\tilde{D}}_z(1),{\tilde{D}}_z(2),\dots$ are square integrable under $P_{\pi }$ even when ${\tilde{g}}_z$ may not be $P_{\pi }$ square integrable, provided that (6.2) is in force.

In the presence of (6.3), the CLT for ${\sum }_{j=0}^{n-1}f(X_j)$ can be justified either on the basis of a regenerative argument or on the basis of the martingale CLT. For more general additive functionals, the martingale CLT is often more convenient.

Suppose, for example, that we desire a CLT for

where ${\sum }_{x,y}^{}k(x,y)\eta (x)P(x,y)=0$. Letfor $x\in S$. Then, $f\in L_0^1(\eta )$ andso that the right-hand side is a sum of martingale differences. Hence, under suitable moment conditions, the martingale CLT can be immediately applied.

We conclude this section with an example that illustrates the “within-cycle” cancellation of variability that can occur in settings where (6.2) holds but (6.3) fails. In fact, $f{\tilde{g}}_z\notin L^1(\pi )$ in the example, so the formula of Theorem 5, part i, fails to be valid.

Example 6.

Let $S=\{0\}\cup {\cup }_{k=2}^{\infty }\{(k,i):0\le i\le k\}$, and suppose $P(0,0)=p_0>0$, with $P(0,(k,0))=p_k$ for $k\ge 2$, where $(p_k:k\ge 0)$ is a mass function with $p_1=0,\hspace{0.17em}{\sum }_{k=1}^{\infty }k{p}_k<\infty$, and ${\sum }_{k=1}^{\infty }{k}^2{p}_k=\infty$. We assume that $P((k,i),(k,i+1))=1$ for $0\le i<k$, and $P((k,k),0)=1$ for $k\ge 2$. Let $f(0)=0,f(k,0)=k,$ and $f(k,i)=-1$ for $1\le i\le k$. Then, X is irreducible, aperiodic, and positive recurrent. If z = 0, then ${\sum }_{j=0}^{\tau (z)-1}f(X_j)=0,\hspace{0.17em}{\tilde{g}}_z(0)=0={\tilde{g}}_z(k,0)$, and ${\tilde{g}}_z(k,i)=-k+i-1$ for $1\le i\le k$. Finally,

$$E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}f}(X_j){\tilde{g}}_z(X_j)=-{\displaystyle \sum _{k=2}^{\infty }{p}_k}(1+2+\cdots +k)=\infty ,$$

so $f{\tilde{g}}_z\notin L^1(\eta )$ (and hence (6.3) must fail).

Remark 9.

Under (6.3), the functional central limit theorem and the law of the iterated logarithm also hold for $S_n(f)$; see Glynn and Whitt (1993).

7. Lyapunov Conditions

In this section, we develop new Lyapunov conditions that guarantee the finiteness of

and

As noted in Section 6, “within-z-cycle” cancellation can arise in computing (7.1) and (7.2). Without such fortuitous cancellation, the finiteness of the moments (7.1) and (7.2) is contingent upon the finiteness of

and

Theorem 6.

Suppose that X is irreducible, and let K be a finite subset of S. Suppose that f is such that there exist nonnegative functions v₀and v₁and finite constants b₀and b₁such that

$$E_x{v}_0(X_1)\le v_0(x)-1+b_{0}I(x\in K)$$(7.5)

and

$$E_x{v}_1(X_1)\le v_1(x)-|f(x)|+b_{1}I(x\in K)$$(7.6)

for $x\in S$. Then, X is positive recurrent and $f\in L^1(\eta )$. Furthermore, (7.3) is finite if there exists a nonnegative function v₂and a finite constant b₂such that

$$E_x{v}_2(X_1)\le v_2(x)-v_1(x)+b_{2}I(x\in K)$$(7.7)

for $x\in S$. Also, (7.4) is finite if there exists a nonnegative function v₃and a finite constant b₃such that

$$E_x{v}_3(X_1)\le v_3(x)-|f(x)|v_1(x)+b_{3}I(x\in K)$$(7.8)

for $x\in S$.

Proof.

The positive recurrence and fact that $f\in L^1(\eta )$ are standard; see Meyn and Tweedie (2009). We outline the proof in order to leverage the same argument in the remainder of the proof. Fix $y\in K$, and note that the comparison theorem (see Meyn and Tweedie 2009, p. 344) implies that when (7.5) holds,

$$E_x\tau (y)\le v_0(x)+b_0{E}_x{\displaystyle \sum _{j=0}^{\tau (y)-1}I}(X_j\in K)$$

for $x\in S$. If V_i is the ith time at which X enters K and $\mathrm{\Gamma }=\inf \{j\ge 1:X_{V_j}=y\}$,

$${\displaystyle \sum _{j=0}^{\tau (y)-1}I}(X_j\in K)=\mathrm{\Gamma }.$$

Because $(X_{V_j}:j\ge 1)$ is an irreducible finite state Markov chain taking values in K, it follows that $\gamma \triangleq \max \{E_y\mathrm{\Gamma }:y\in K\}<\infty$. So,

$$E_x\tau (y)\le v_0(x)+b_0\gamma$$

for $x\in S$. Similarly, (7.6) implies that

$$E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|\le v_1(x)+b_1\gamma .$$

So, X is positive recurrent, and $f\in L^1(\eta )$.

In the presence of (7.7), we similarly obtain the bound

$$E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}{v}_1}(X_j)\le v_2(x)+b_2\gamma$$

for $x\in S$. So,

$$\begin{array}{ll}{E}_x{\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|(j+1)\hfill & =E_x{\displaystyle \sum _{k=0}^{\tau (y)-1}{\displaystyle \sum _{j=k}^{\tau (y)-1}|}}f(X_j)|\hfill \\ \hfill & \le E_x{\displaystyle \sum _{k=0}^{\tau (y)-1}(v_1(}{X}_k)+b_1\gamma )\hfill \\ \hfill & \le v_2(x)+b_2\gamma +b_1\gamma (v_0(x)+b_0\gamma )\hfill \end{array}$$

for $x\in S$, so $E_y{\sum }_{j=0}^{\tau (y)-1}|f(X_j)|(j+1)<\infty$. Because finiteness of (7.3) is a solidarity property (see Theorem 3; the proof requires only that $f\in L^1(\eta )$), it follows that (7.3) holds for y = z.

When (7.8) holds, we get the bound

$$\begin{array}{ll}{E}_x{\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|{\displaystyle \sum _{k=j}^{\tau (y)-1}|}f(X_k)|\hfill & =E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|E_x[{\displaystyle \sum _{k=j}^{\tau (y)-1}|}f(X_k)|\hspace{0.17em}|X_j]\hfill \\ \hfill & \le E_x{\displaystyle \sum _{j=0}^{\tau (y)-1}|}f(X_j)|(v_1(X_j)+b_1\gamma )\hfill \\ \hfill & \le v_3(x)+b_3\gamma +(v_1(x)+b_1\gamma )b_1\gamma \hfill \end{array}$$

for $x\in S$, yielding the finiteness of (7.4). Finally, (7.4) is a solidarity property of X, so that (7.4) holds for y = z; see Chung (1967). □

Remark 10.

Note that when X is positive recurrent and $f\in L^1(\eta )$, then there must exist nonnegative functions $v_0,v_1,\hspace{0.17em}\text{and}\hspace{0.17em}{v}_2$ and finite constants b₀, b₁, and b₂ satisfying (7.5), (7.6), and (7.7) whenever (7.3) is finite. In particular, let

$$v_0(x)=E_{x}T(K),v_1(x)=E_x{\displaystyle \sum _{j=0}^{T(K)-1}|}f(X_j)|,v_2(x)=E_x{\displaystyle \sum _{j=0}^{T(K)-1}(j+1)}|f(X_j)|$$

and

$$\begin{array}{ll}{b}_0\hfill & =\max \{E_x(1+v_0(X_1)I(X_1\in K^c)):x\in K\},\hfill \\ b_1\hfill & =\max \{E_x(|f(X_0)|+v_1(X_1)I(X_1\in K^c)):x\in K\},\hfill \\ b_2\hfill & =\max \{E_x{v}_2(X_1)I(X_1\in K^c):x\in K\}.\hfill \end{array}$$

Similarly, there must exist nonnegative functions v₁ and v₃ satisfying (7.6) and (7.8) whenever (7.4) is finite (because finiteness of (7.4) implies that $f\in L^1(\eta )$). Hence, our Lyapunov conditions are necessary and sufficient for (7.3) and (7.4).

Remark 11.

Suppose we desire a CLT for ${\sum }_{j=0}^{n-1}r(X_j)$ where $r(·)\in L^1(\eta )$ is a reward function and X is an irreducible positive recurrent Markov chain. Note that Theorem 5 must be applied to $r(x)-\pi r$. In view of the fact that $|r(x)-\pi r|\le (|\pi r|+1)(|r(x)\vee 1)$, Condition (6.3) can be validated by applying Theorem 6 to $f(x)=|r(x)|\vee 1$.

Remark 12.

Glynn and Meyn (1996) provides a general state space bound on the analog of ${\tilde{g}}_z$ and applies this bound to obtaining the Markov chain CLT under the hypothesis that ${\tilde{g}}_z\in L^2(\pi )$. In our setting, the square integrability of ${\tilde{g}}_z$ can be validated from a Lyapunov condition of the form

$$E_x{v}_4(X_1)\le v_4(x)-v_1{(x)}^2+b_{4}I(X\in K)$$(7.9)

for $x\in S$. Our current paper weakens the Markov chain CLT hypothesis to (6.3) (or, equivalently, $f{q}_z\in L^1(\pi )$), which can be verified from the Lyapunov condition (7.8).

We now provide an example in which the weaker (7.8) yields better CLT conditions than does (7.9). Suppose that $X=(X_n:n\ge 0)$ is the Markov chain on ${\mathbb{Z}}_{+}$ for which

$$X_{n+1}={[X_n+Z_{n+1}]}^{+},$$

where $(Z_n:n\ge 1)$ is an i.i.d. sequence of integer-valued RVs with $E|Z_1|<\infty$ and $E{Z}_1<0$. This, of course, is the Markov chain associated with the delay sequence of the single-server $GI/G/1$ queue. If B_n is the integer-valued service time of customer n and $A_{n+1}$ is the independent integer-valued $(n+1)$st interarrival time, then $Z_{n+1}=B_n-A_{n+1}$. Then, $X_n\Rightarrow X_{\infty }$ as $n\to \infty$ and $E{X}_{\infty }^2<\infty$ if and only if $E{B}_1^3<\infty$; see Kiefer and Wolfowitz (1956).

If $E{B}_1^4<\infty$, we can set $v_i(x)=a_i{x}^{i+1}$ for $0\le i\le 3$ for suitable constants $a_0,\dots ,a_3$ and utilize Theorem 6 to verify (6.3) for $f(x)=x-E{X}_{\infty }$. Hence, when $E{B}_1^4<\infty$,

$$n^{-1/2}\left({\displaystyle \sum _{i=0}^{n-1}{X}_i}-{\mathit{\text{nEX}}}_{\infty }\right)\Rightarrow \sigma N(0,1)$$(7.10)

as $n\to \infty$. If the square of the left-hand side of (7.10) is uniformly integrable when X is initialized under the stationary distribution, then

$$n^{-1}\hspace{0.17em}\text{var}\left({\displaystyle \sum _{i=0}^{n-1}{X}_i^{*}}\right)\to {\sigma }^2<\infty$$(7.11)

as $n\to \infty$, where $(X_n^{*}:n\ge 0)$ is the stationary version of X. Because $(X_n^{*}:n\ge 0)$ is an associated sequence of RVs, $\text{cov}(X_0^{*},X_i^{*})\ge 0$ for $i\ge 0$ (see, e.g., Barlow and Proschan 1975). So,

$$\begin{array}{ll}\text{var}\hspace{0.17em}{X}_0^{*}+{\displaystyle \sum _{i=0}^{\lfloor n/2\rfloor }}\text{cov}(X_0^{*},X_i^{*})\hfill & \le \text{var}\hspace{0.17em}{X}_0^{*}+2{\displaystyle \sum _{i=1}^{n-1}\left(1-\frac{i}{n}\right)\hspace{0.17em}}\text{cov}(X_0^{*},X_i^{*})\hfill \\ \hfill & =\frac{1}{n}\text{var}\left({\displaystyle \sum _{i=0}^{n-1}{X}_i^{*}}\right),\hfill \end{array}$$

from which it follows from (7.11) that

$${\text{var}\hspace{0.17em}\mathit{\text{X}}}_0^{*}+2{\displaystyle \sum _{i=1}^{\infty }}\text{cov}(X_0^{*},X_i^{*})<\infty .$$

Hence,

$${\text{var X}}_0^{*}+2{\displaystyle \sum _{i=1}^{\infty }}\text{cov}(X_0^{*},X_i^{*})=\underset{n\to \infty }{\lim }\frac{1}{n}\text{var}\left({\displaystyle \sum _{i=0}^{n-1}{X}_i^{*}}\right)={\sigma }^2.$$(7.12)

Daley (1968) proved that the left-hand side of (7.11) is finite if and only if $E{B}_1^4<\infty$. So $E{B}_1^4<\infty$ is necessary in order that (7.10) holds with the additional uniform integrability present in (7.11). Hence, $E{B}_1^4<\infty$ is likely the minimal condition under which the CLT (7.10) holds, and our new improved sufficient condition covers this setting.

Remark 13.

Another indication that $E{Z}_1^4$ is a necessary condition for the CLT in this setting is that when one allows the Z_i’s to be continuous RVs, Glynn (1994) explicitly solves the associated Poisson’s equation for the $M/G/1$ queue. In that setting, the solution to Poisson’s equation for f is quadratic, so that $g_z{f}_c$ is cubic. As a result, it is well known that $E{Z}_1^4$ is necessary in order that $g_z{f}_c$ be π-integrable (Asmussen 2008), and hence that ${\sigma }^2$ as given by Theorem 5 be finite.

On the other hand, verifying that ${\tilde{g}}_z\in L^2(\pi )$ for this model leads to the requirement $E{B}_1^5<\infty$; see Glynn and Meyn (1996). Hence, use of (7.8) (rather than (7.9)) improves the CLT condition for this model to what is likely the minimal moment requirement on the distribution of B₁.

8. Extensions to the Markov Jump Process Setting

In this section, we briefly discuss the extensions of the theory developed in this paper to the Markov jump process setting. Our discussion builds on the notation of Section 2, so that Y corresponds to the jump process, and X to its embedded discrete-time Markov chain. We note that Section 2 already makes clear that, for example, numerical computation of Poisson’s equation for positive recurrent jump processes can be reduced to that for discrete-time (possibly null recurrent) chains. This can simplify the development of algorithms that seek to leverage the nonnegativity of the coefficient matrices that arise in discrete time.

Assume henceforth that Y is an irreducible positive recurrent jump process with (continuous-time) stationary distribution $\nu =(\nu (x):x\in S)$. For $z\in S$, let $\kappa (z)=\inf \{t\ge 0:Y(t)=z,Y(t-)\ne z\}$ be the time at which Y enters z for the first time, and let ${\beta }_z(t)$ be the first time subsequent to t at which Y enters z.

Suppose $\widehat{f}\in L_0^1(\nu )$. Then $f\in L_0^1(\eta )$ and

and

The following is the continuous-time analog of Theorem 2.

Theorem 7.

Let Y be an irreducible nonexplosive positive recurrent jump process with $\widehat{f}\in L_0^1(\nu )$. Then

1. $({\tilde{g}}_z(Y(t))+{\int }_0^t\widehat{f}(Y(s))ds:t\ge 0)$ is a martingale adapted to the filtration $({\mathcal{G}}_t:t\ge 0)$, where ${\mathcal{G}}_t=\sigma (Y(s):0\le s\le t)$ for $t\ge 0$;

2. the martingale ofi has the stopping property in the sense that for each nonempty subset $B\subseteq S$ and $x\in S$,

   $$E_x{\tilde{g}}_z(Y(\widehat{T}(B)))+{\displaystyle {\int }_0^{\widehat{T}(B)}\widehat{f}}(Y(s))ds={\tilde{g}}_z(x),$$
   where $\widehat{T}(B)=\inf \{t\ge 0:Y(t)\in B\}$;

3. if g is a solution to Poisson’s equation for $\widehat{f}$ for which its associated martingale has the stopping property, then $g(·)={\tilde{g}}_z(·)+g(z)$.

Proof.

The proof mirrors that of Theorem 2, excepting the integrability of the martingale i. Let $N_z(t)$ be the number of times Y visits z over $[0,t]$. Then, Wald’s identity implies that

$$\begin{array}{ll}{E}_x{\displaystyle {\int }_0^t|}\widehat{f}(Y(s))|ds\hfill & \le E_x{\displaystyle {\int }_0^{{\beta }_z(t)}|}\widehat{f}(Y(s))|ds\hfill \\ \hfill & \le E_x{\displaystyle {\int }_0^{\kappa (z)}|}\widehat{f}(Y(s))|ds+E_z(N_z(t)+1)E_z{\displaystyle {\int }_0^{\kappa (z)}|}\widehat{f}(Y(s))|ds\hfill \\ \hfill & =E_x{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|+E_z(N_z(t)+1)E_z{\displaystyle \sum _{j=0}^{\tau (z)-1}|}f(X_j)|,\hfill \end{array}$$(8.3)

where $E_z{N}_z(t)<\infty$ for each $t\ge 0$ (as a consequence of the fact that $N_z(·)$ is a renewal counting process). Also,

$$\begin{array}{ll}{E}_x|{\tilde{g}}_z(Y(t))|\hfill & \le E_x{\displaystyle {\int }_t^{{\beta }_z(t)}|}\widehat{f}(Y(s))|\hfill \\ \hfill & \le E_x{\displaystyle {\int }_0^{{\beta }_z(t)}|}\widehat{f}(Y(s))|ds<\infty ,\hfill \end{array}$$

as just established in (8.3). □

We turn next to the extension of the CLT to the jump process setting. Suppose $\widehat{f}\in L_0^1(\nu )$. Then, there exists a (deterministic) finite σ for which

as $t\to \infty$ if and only if there exists some $z\in S$ for whichin which case ${\sigma }^2=E_z{({\int }_0^{\kappa (z)}\widehat{f}(Y(s))ds)}^2/E_z\kappa (z)$.

This follows from the fact that Y is a regenerative process; see Glynn and Whitt (1993, 2002). A sufficient condition for (8.5) is

But

wherefor $x\in S$. As a consequence, (8.6) holds if and only if $\widehat{f}{q}_z\in L^1(\nu )$. But this is equivalent to $f{q}_z\in L^1(\eta )$. Furthermore,

Alternatively, when expressed in terms of X,

We have arrived at the following CLT for Markov jump processes.

Theorem 8.

Suppose that Y is an irreducible nonexplosive positive recurrent Markov jump process. If $\widehat{f}\in L_0^1(\nu )$ (or, equivalently, $f\in L_0^1(\eta )$) and $\widehat{f}{q}_z\in L^1(\nu )$ (or, equivalently, $f{q}_z\in L^1(\eta )$), then

$$t^{-1/2}{\displaystyle {\int }_0^t\widehat{f}}(Y(s))ds\Rightarrow \sigma N(0,1)$$

as $t\to \infty$ where ${\sigma }^2=2E_{\nu }\widehat{f}(Y(0)){\tilde{g}}_z(Y(0))$ (or, equivalently, ${\sigma }^2=2\eta (f{\tilde{g}}_z)/\eta {\lambda }^{-1}$).

We conclude this section by briefly discussing the continuous-time Lyapunov condition for the CLT (8.4). As discussed above, we must verify that $f{q}_z\in L^1(\eta ),\hspace{0.17em}f\in L^1(\eta )$, and ${\lambda }^{-1}\in L^1(\eta )$. The corresponding Lyapunov conditions (when verified in terms of X) are

for $x\in S$ (to verify ${\lambda }^{-1}\in L^1(\eta )$),for $x\in S$ (to verify $f\in L^1(\eta )$), andfor $x\in S$ (to verify $f{q}_z\in L^1(\eta )$).

Of course, a more natural (and equivalent) formulation of (8.7) through (8.9) in continuous time is to write these inequalities in terms of Q, namely,

andfor $x\in S$ and finite constants $b_0^{\prime },b_1^{\prime }$, and $b_3^{\prime }$.

As noted in Section 7, the CLT (8.4) must often be validated for an (uncentered) reward function $\widehat{r}$, in which case the CLT takes the form

as $t\to \infty$. We then need to verifyandfor $x\in S$.