# Solving Poisson’s Equation: Existence, Uniqueness, Martingale Structure, and
CLT

Peter W. Glynn  Department of Management Science & Engineering, Stanford
University.  Institute for Computational & Mathematical Engineering, Stanford
University.  Alex Infanger  Institute for Computational & Mathematical
Engineering, Stanford University.

###### Abstract

The solution of Poisson’s equation plays a key role in constructing the
martingale through which sums of Markov correlated random variables can be
analyzed. In this paper, we study two different representations for the
solution in countable state space, one based on regenerative structure and the
other based on an infinite sum of expectations. We also consider integrability
and related uniqueness issues associated with solutions to Poisson’s equation,
and provide verifiable Lyapunov conditions to support our theory. Our key
results include a central limit theorem and law of the iterated logarithm for
Markov dependent sums, under Lyapunov conditions weaker than have previously
appeared in the literature.

##  1 Introduction

Let $X=(X_{n}:n\geq 0)$ be an irreducible positive recurrent Markov chain
taking values in a finite or countably infinite state space $S$. We let
$P=(P(x,y):x,y\in S)$ be the one-step transition matrix of $X$, and let
$\pi=(\pi(x):x\in S)$ be its associated (unique) stationary distribution
(encoded as a row vector). Given a function $f:S\rightarrow\mathbb{R}$
(encoded as a column vector), we say that a function $g$ is a solution of
_Poisson’s equation_ (for $f$) if

$\displaystyle(P-I)g=-f.$ (1.1)

Poisson’s equation is fundamental to the analysis of the additive functional
$S_{n}(f)\overset{\Delta}{=}\sum_{i=0}^{n-1}f(X_{i})$, since, in the presence
of integrability,

$\displaystyle g(X_{n})+\sum_{i=0}^{n-1}f(X_{i})$ (1.2)

should then be a martingale adapted to the filtration $(\mathcal{F}_{n}:n\geq
0)$, where $\mathcal{F}_{n}=\sigma(X_{j}:j\leq n)$. The martingale
representation (1.2) 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, and law of the iterated logarithm for $S_{n}(f)$; see,
for example, Maigret (1978) and Kurtz (1981). It is also fundamental to
obtaining bounds on the $k$’th moment $E_{x}|S_{n}(f)|^{k}$ (where
$E_{x}(\cdot)$ is the expectation corresponding to the probability
$P_{x}(\cdot)=P(\cdot|X_{0}=x)$) via the Burkholder-Davis-Gundy inequality;
see Hall and Heyde (1980). It is worth noting that (1.1) also arises
implicitly within the optimality equation for average reward/average case
stochastic control problems, since the value function under the optimal policy
must satisfy (1.1); see Ross (2014).

Given the central importance of (1.1) within applied probability, this paper
is intended to clarify the question of existence and uniqueness of solutions
to (1.1) when $|S|=\infty$. Assuming $g\in
L^{p}(\pi)\overset{\Delta}{=}\\{h:\sum_{x\in S}\pi(x)|h(x)|^{p}<\infty\\}$ for
$p\geq 1$, (1.1) implies that $f\in L^{1}(\pi)$ and $\pi f=0$. If $f\in
L_{0}^{1}(\pi)=\\{h:L^{1}(\pi):\pi h=0\\}$, $|S|<\infty$, and $X$ is
aperiodic, it turns out that a solution $g$ to (1.1) is given either by

$\displaystyle g_{1}(x)=E_{x}\sum_{n=0}^{\tau(z)-1}f(X_{n})$

or by

$\displaystyle g_{2}(x)=\sum_{n=0}^{\infty}E_{x}f(X_{n}),$

where $\tau(z)=\inf\\{n\geq 1:X_{n}=z\\}$ for $z\in S$. In this finite state
setting, both $g_{1}$ and $g_{2}$ are always finite-valued solutions to (1.1)
and $g_{1}(x)-g_{2}(x)$ is constant as a function of $x\in S$.

When $|S|=\infty$, both existence of solutions of (1.1) and the corresponding
uniqueness issues are more subtle. In particular, this paper shows that

  1. a)

While $g_{1}$ is always a solution to (1.1) when $f\in L^{1}(\pi)$, $g_{2}$
can sometimes fail to be well-defined (see Theorem 1 and Example 2);

  2. b)

The set of solutions to (1.1) can be infinite-dimensional (see Example 1);

  3. c)

When $g_{1}$ is used in (1.2), (1.2) is guaranteed to be integrable and hence
a martingale (Theorem 1);

  4. d)

The set of functions $g$ for which (1.2) is a martingale can be infinite-
dimensional (Example 1), but we show that it becomes one-dimensional when we
require a certain uniform integrability property (Theorem 6);

  5. e)

An approximation to $E_{x}S_{n}(f)$ can be developed when $g_{1}\in
L^{1}(\pi)$ (Theorem 3), and a Lyapunov criterion is provided (Theorem 5);

  6. f)

The function $g_{2}$ is well-defined under an extra condition (Theorem 4) that
can be verified through an associated Lyapunov criterion (Theorem 5);

  7. g)

Lyapunov criteria, weaker than those previously developed in the literature,
are provided that guarantee the central limit theorem (CLT) and law of the
iterated logarithm (LIL) for $S_{n}(f)$ (Theorems 7 and 8).

As we shall see in what follows, the conditions we will develop are close to
being minimal. Section 2 contains the key results on Poisson’s equation, while
Section 3 discusses two examples that illustrate mathematical subtleties
associated with (1.1). Section 4 describes the CLT and LIL for $S_{n}(f)$. As
an application of our theory, Glynn and Infanger (2022) uses the
characterization $g_{1}$ of the solution to establish that solutions of
Poisson’s equation are always monotone when the chain is stochastically
monotone and $f$ is monotone, without demanding the summability implicit in
$g_{2}$.

##  2 A Regenerative Representation for the Solution and Related Lyapunov
Conditions

As noted in the Introduction, we assume throughout this paper that $X$ is
irreducible and positive recurrent. This implies that

$\displaystyle E_{z}\tau(z)<\infty$ (2.1)

for each $z\in S$. This, in turn, implies that $E_{x}\tau(z)<\infty$ for
$x,z\in S$, since

$\displaystyle\infty>E_{z}\tau(z)$ $\displaystyle\geq
E_{z}\tau(z)I(\tau(x)<\tau(z))$ $\displaystyle\geq
P_{z}\left(\tau(x)<\tau(z)\right)E_{x}\tau(z).$ (2.2)

Of course, $P_{z}(\tau(x)<\tau(z))>0$ (because $x$ can not be reached from $z$
if $P_{x}(\tau(x)<\tau(z))=0$), thereby establishing that
$E_{x}\tau(z)<\infty$.

Similarly, if $f\in L^{1}(\pi)$, the regenerative structure of $X$ implies
that for each $z\in S$,

$\displaystyle\sum_{x\in
S}\pi(x)|f(x)|=\frac{E_{z}\sum_{j=0}^{\tau(z)-1}|f(X_{j})|}{E_{z}\tau(z)},$

and hence

$\displaystyle E_{z}\sum_{j=0}^{\tau(z)-1}|f(X_{j})|<\infty.$

Similarly as with $E_{x}\tau(z)<\infty$, this implies that

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}|f(X_{j})|<\infty$ (2.3)

for $x,z\in S$.

We conclude that if $f\in L^{1}(\pi)$, then for each $x,z\in S$,

$\displaystyle
g_{z}(x)\overset{\Delta}{=}E_{x}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})$

is finite-valued, where $f_{c}(x)=f(x)-\pi f$ for $x\in S$. Our first result
asserts that $g_{z}=(g_{z}(x):x\in S)$ is a solution of Poisson’s equation for
$f_{c}$, namely it satisfies

$\displaystyle(P-I)g=-f_{c}.$ (2.4)

It also establishes that for any $y,x\in S$, $g_{z}$ and $g_{y}$ differ only
by an additive constant. Let $e=(e(x):x\in S)$ be the (constant) function for
which $e(x)=1$ for $x\in S$, and put $a\land b\overset{\Delta}{=}\min(a,b)$
for $a,b\in\mathbb{R}$.

######  Theorem 1.

Suppose $f\in L^{1}(\pi)$. Then,

  1. a)

For each $z\in S$, $g_{z}$ is a finite-valued function that satisfies (2.4);

  2. b)

For each $y,z\in S$, $g_{z}-g_{y}=g_{z}(y)e$.

###### Proof.

We have already established that $g_{z}$ is finite-valued. For $x\in S$,
conditioning on $X_{1}$ shows that

$\displaystyle g_{z}(x)$
$\displaystyle=E_{x}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})$
$\displaystyle=f_{c}(x)+\sum_{y\neq z}P(x,y)g_{z}(y).$ (2.5)

But $\pi f_{c}=0$, and the regenerative structure of $X$ implies that

$\displaystyle\pi
f_{c}=\frac{E_{z}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})}{E_{z}\tau(z)},$

so that $g_{z}(z)=0$. Hence (2.5) yields the identity

$\displaystyle g_{z}(x)=f_{c}(x)+\sum_{y\in S}P(x,y)g_{z}(y),$

which is $a)$. As for $b)$, note that

$\displaystyle
g_{z}(x)=E_{x}\smashoperator[]{\sum_{j=0}^{(\tau(y)\land\tau(z))-1}}f_{c}(X_{j})+P_{x}(\tau(y)<\tau(z))g_{z}(y).$
(2.6)

Since the identity also holds for $g_{y}(x)$ (with $y$ playing the role of
$z$), we find that

$\displaystyle
g_{z}(x)-g_{y}(x)=g_{z}(y)-P_{x}(\tau(z)<\tau(y))(g_{y}(z)+g_{z}(y))$ (2.7)

for $x\in S$. If we set $x=y$ in (2.7) and note that irreducibility implies
that $P_{z}(\tau(z)<\tau(y))>0,$ we find that $g_{y}(z)-g_{z}(y)=0$, yielding
b). ∎

######  Remark 1.

Theorem 1 is a special case of Theorem 1 and 2 of Derman and Veinott (1967);
see also Schaufele (1967). Our proof is easier because we assume
irreducibility.

We say that $(M_{n}:n\geq 0)$ is a $P_{x}-$_martingale_ adapted to
$(\mathcal{F}_{n}:n\geq 0)$ if $(M_{n}:n\geq 0)$ is adapted to
$(\mathcal{F}_{n}:n\geq 0)$, $E_{x}|M_{n}|<\infty$, and
$E_{x}[M_{n+1}|\mathcal{F}_{n}]=M_{n}$ a.s. for $n\geq 0$.

######  Theorem 2.

Suppose $f\in L^{1}(\pi)$. Then, for all $x,z\in S$,

$\displaystyle g_{z}(X_{n})+\sum_{j=0}^{n-1}f_{c}(X_{j})$ (2.8)

is a $P_{x}$-martingale adapted to $(\mathcal{F}_{n}:n\geq 0)$.

###### Proof.

The only non-trivial issue that needs to be addressed is the
$P_{x}$-integrability of the martingale. Note that for $n\geq 0$, because
$f\in L^{1}(\pi)$,

$\displaystyle\pi(x)E_{x}|f_{c}(X_{n})|\leq\sum_{y\in
S}\pi(y)E_{y}|f_{c}(X_{n})|=\sum_{y\in S}\pi(y)|f_{c}(y)|<\infty$ (2.9)

due to stationarity, and hence $f_{c}(X_{n})$ is $P_{x}$-integrable for $n\geq
0$.

As for the integrability of $g_{z}(X_{n})$, we observe that for $x\neq z$,

$\displaystyle
a_{n}(x)\overset{\Delta}{=}E_{x}|g_{z}(X_{n})|=E_{x}|E_{x}\sum_{j=n}^{\tau(z)-1}f_{c}(X_{j})|I(\tau(z)>n)+\sum_{j=1}^{n}P_{x}(\tau(z)=j)a_{n-j}(z).$
(2.10)

As for $(a_{n}(z):n\geq 0)$, it satisfies the renewal equation

$\displaystyle
a_{n}(z)=E_{z}|E_{z}\sum_{j=n}^{\tau(z)-1}f_{c}(X_{j})|I(\tau(z)>n)+\sum_{j=1}^{n}P_{z}(\tau(z)=j)a_{n-j}(z)$

for $n\geq 0$, the solution of which is

$\displaystyle a_{n}(z)=\sum_{j=0}^{n}P_{z}(X_{j}=z)b_{n-j}(z),$ (2.11)

where

$\displaystyle b_{n}(x)$ $\displaystyle\leq
E_{x}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)$ $\displaystyle\leq
E_{x}\sum_{j=0}^{\tau(z)-1}|f_{c}(X_{j})|<\infty$

for each $x\in S$, on account of (2.3); see Chapter 13 of Feller (1968) for a
discussion of discrete-time renewal theory. Hence, $(b_{n}(x):n\geq 0)$ is a
finite-valued sequence for each $x\in S$, so that (2.10) and (2.11) imply the
finiteness of $(a_{n}(x):n\geq 0)$ for $x\in S$, yielding the
$P_{x}$-integrability of $g_{z}(X_{n})$. ∎

######  Remark 2.

Our result shows that whenever $f\in L^{1}(\pi)$, (2.8) is a
$P_{x}$-martingale. Discussion of the martingale (2.8) appears elsewhere (e.g.
in Kurtz (1981) and Makowski and Shwartz (2002)), but without a simple
sufficient condition for integrability.

######  Remark 3.

For $\mu=(\mu(x):x\in S)$ a probability on $S$, let
$P_{\mu}(\cdot)\overset{\Delta}{=}\sum_{x\in S}\mu(x)P_{x}(\cdot)$ be the
probability on the path-space of $X$ under which $X$ has initial distribution
$\mu$, and let $E_{\mu}(\cdot)$ be its corresponding expectation operator.
Then (2.8) is guaranteed to be a $P_{\mu}$-martingale provided that $\mu$ is
finitely supported. However (2.8) is, in general, not integrable for
infinitely supported $\mu$ (e.g. $\mu=\pi$).

As a consequence of Theorem 2,

$\displaystyle\sum_{j=0}^{n-1}E_{x}f(X_{j})=n\pi f+g_{z}(x)-E_{x}g_{z}(X_{n})$
(2.12)

for $x,z\in S$. To further simplify (2.12), we can apply the following result.

######  Theorem 3.

Suppose that $f\in L^{1}(\pi)$ and that there exists $z\in S$ for which

$\displaystyle E_{z}\sum_{j=0}^{\tau(z)-1}j|f_{c}(X_{j})|<\infty.$ (2.13)

Then, $g_{y}\in L^{1}(\pi)$ for all $y\in S$, and $\eqref{eq28}$ is a
$P_{\pi}$-martingale adapted to $(\mathcal{F}_{n}:n\geq 0)$. Furthermore, if
$X$ is aperiodic, then

$\displaystyle E_{x}g_{z}(X_{n})\rightarrow\pi
g_{z}=\frac{E_{z}\sum_{j=0}^{\tau(z)-1}(j+1)f_{c}(X_{j})}{E_{z}\tau(z)}$
(2.14)

as $n\rightarrow\infty$ for $x\in S$.

###### Proof.

As in the argument leading to (2.10) and (2.11), we find that

$\displaystyle\tilde{a}_{n}(x)=E_{x}g_{z}(X_{n})=\tilde{b}_{n}(x)+\sum_{k=1}^{n}P_{x}(\tau(z)=k)\sum_{j=0}^{n-k}\tilde{b}_{j}(z)P_{z}(X_{n-k-j}=z)$
(2.15)

where

$\displaystyle\tilde{b}_{n}(x)=E_{x}\sum_{j=n}^{\tau(z)-1}f_{c}(X_{j})I(\tau(z)>n).$

As a consequence of the aperiodicity, $P_{z}(X_{n}=z)\rightarrow\pi(z)$ as
$n\rightarrow\infty$. Also,

$\displaystyle\sum_{n=0}^{\infty}|\tilde{b}_{n}(z)|$ $\displaystyle\leq
E_{z}\sum_{n=0}^{\infty}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle=E_{z}\sum_{n=0}^{\tau(z)-1}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|$
$\displaystyle=E_{z}\sum_{j=0}^{\tau(z)-1}|f_{c}(X_{j})|\sum_{n=0}^{j}1$
$\displaystyle=E_{z}\sum_{j=0}^{\tau(z)-1}(j+1)|f_{c}(X_{j})|<\infty.$ (2.16)

With (2.16) in hand, we can apply the Dominated Convergence Theorem to (2.15),
thereby yielding (2.14).

Furthermore, the regenerative structure of $X$ implies that if
$\beta_{n}(z)=\inf\\{j>n:X_{j}=z\\}$, then

$\displaystyle E_{z}\tau(z)E_{\pi}|g_{z}(X_{0})|$
$\displaystyle=E_{z}\sum_{n=0}^{\tau(z)-1}|g_{z}(X_{n})|$
$\displaystyle=E_{z}\sum_{n=0}^{\infty}|E_{z}\sum_{j=n}^{\beta_{n}(z)-1}f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle\leq
E_{z}\sum_{n=0}^{\infty}\sum_{j=n}^{\beta_{n}(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle=E_{z}\sum_{n=0}^{\infty}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle=E_{z}\sum_{n=0}^{\tau(z)-1}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|,$
(2.17)

which equals the right-hand side of (2.16). It follows that $g_{z}\in
L^{1}(\pi)$. But $g_{y}$ is equal to $g_{z}$ (up to an additive constant), so
$g_{y}\in L^{1}(\pi)$ for $y\in S$. Obviously, if $g_{y}\in L^{1}(\pi)$, then
$g_{y}(X_{n})+\sum_{j=1}^{n-1}f_{c}(X_{j})$ is a $P_{\pi}$-martingale,
concluding the argument.

The expression for $\pi g_{z}$ follows from the same argument as that leading
to (2.17). ∎

Under the conditions of Theorem 3, we see that

$\displaystyle E_{x}\sum_{j=0}^{n-1}f(X_{j})=n\pi f+g_{z}(x)-\pi g_{z}+o(1)$
(2.18)

as $n\rightarrow\infty$, where $o(1)$ represents a sequence $(c_{n}:n\geq 0)$
with the property that $c_{n}\rightarrow 0$ as $n\rightarrow\infty$. Given the
expression for $\pi g_{z}$, it is evident that Theorem 3’s hypotheses are
close to necessary.

The next result shows that (2.13) is a “solidarity property”, in the sense
that if it holds for one $z\in S$, then it holds for each $y\in S$.

######  Proposition 1.

Suppose $f\in L^{1}(\pi)$ and (2.13) is valid for some $z\in S$. Then, (2.13)
holds for all $z\in S$.

###### Proof.

We note that the regenerative structure of $X$ implies that

$\displaystyle\infty>E_{z}\sum_{j=0}^{\tau(z)-1}(j+1)|f_{c}(X_{j})|$
$\displaystyle=E_{z}\sum_{k=0}^{\tau(z)-1}\sum_{j=k}^{\tau(z)-1}|f_{c}(X_{j})|$
$\displaystyle=E_{z}\sum_{\ell=0}^{\tau(z)-1}k_{z}(X_{\ell})=E_{z}\tau(z)\cdot\pi
k_{z}$

where $k_{z}(x)=E_{x}\sum_{j=0}^{\tau(z)-1}|f_{c}(X_{j})|$ for $x\in S$. If
$y\neq z$, relation (2.3) implies that
$E_{y}\sum_{\ell=0}^{\tau(y)-1}|k_{z}(X_{\ell})|<\infty$. Also,

$\displaystyle E_{y}\sum_{j=0}^{\tau(y)-1}(j+1)|f_{c}(X_{j})|$
$\displaystyle=E_{y}\sum_{j=0}^{\tau(y)-1}\sum_{k=j}^{\tau(y)-1}|f_{c}(X_{k})|$
$\displaystyle=E_{y}\sum_{j=0}^{\tau(y)-1}I(\beta_{j}(z)\geq\tau(y))\sum_{k=j}^{\tau(y)-1}|f_{c}(X_{k})|$
$\displaystyle\qquad+E_{y}\sum_{j=0}^{\tau(y)-1}I(\beta_{j}(z)<\tau(y))\sum_{k=j}^{\beta_{j}(z)-1}|f_{c}(X_{k})|$
$\displaystyle\qquad+E_{y}\sum_{j=0}^{\tau(y)-1}I(\beta_{j}(z)<\tau(y))\sum_{k=\beta_{j}(z)}^{\tau(y)-1}|f_{c}(X_{k})|$
$\displaystyle\leq
E_{y}\sum_{j=0}^{\tau(y)-1}\sum_{k=j}^{\beta_{j}(z)-1}|f_{c}(X_{k})|$
$\displaystyle\qquad+E_{y}\sum_{j=0}^{\tau(y)-1}I(\beta_{j}(z)<\tau(y))E_{y}[\sum_{k=\beta_{j}(z)}^{\tau(y)-1}|f_{c}(X_{k})|\
|X_{0},...,X_{\beta_{j}(z)}]$
$\displaystyle=E_{y}\sum_{j=0}^{\tau(y)-1}k_{z}(X_{j})+E_{y}\sum_{j=0}^{\tau(y)-1}I(\beta_{j}(z)<\tau(y))E_{z}\sum_{j=0}^{\tau(y)-1}|f_{c}(X_{k})|$
$\displaystyle\leq E_{y}\sum_{j=0}^{\tau(y)-1}k_{z}(X_{j})+E_{y}\tau(y)\cdot
E_{z}\sum_{j=0}^{\tau(y)-1}|f_{c}(X_{k})|<\infty,$

where we have used (2.3) in the last line, thereby proving the result. ∎

Our final result in this section on the behavior of
$\sum_{j=0}^{n}E_{x}f_{c}(X_{j})$ concerns the development of a regenerative
criterion that ensures the validity of

$\displaystyle\sum_{j=0}^{\infty}|E_{x}f_{c}(X_{j})|<\infty$ (2.19)

for $x\in S$.

######  Theorem 4.

Suppose that $f\in L^{1}(\pi)$ and that there exists $z\in S$ for which (2.13)
holds and $E_{z}\tau(z)^{2}<\infty$. If $X$ is aperiodic, then (2.19) holds
for all $x\in S$.

###### 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 $z\in S$; see
p.84 of Chung (1967). As a consequence of Proposition 1, we may assume (2.13)
and $E_{z}\tau(z)^{2}<\infty$ hold for $z=x$.

Then, if $a_{n}^{*}=E_{x}f_{c}(X_{n})$ it follows that it satisfies the
renewal equation

$\displaystyle a_{n}^{*}=\sum_{j=1}^{n}P_{x}(\tau(x)=j)a^{*}_{n-j}+b_{n}^{*},$

where $b_{n}^{*}=E_{x}f_{c}(X_{n})I(\tau(x)>n)$. So,

$\displaystyle a_{n}^{*}=\sum_{j=0}^{n}P_{x}(X_{j}=x)b_{n-j}^{*}.$

Recalling that $0=\pi f_{c}=\sum_{j=0}^{\infty}b_{j}^{*}$, we find that

$\displaystyle a_{n}^{*}$
$\displaystyle=\pi(x)\sum_{j=0}^{n}b_{n-j}^{*}+\sum_{j=0}^{n}(P_{x}(X_{j}=x)-\pi(x))b_{n-j}^{*}$
$\displaystyle=-\pi(x)\sum_{j=n+1}^{\infty}b_{j}^{*}+\sum_{j=0}^{n}(P_{x}(X_{j}=x)-\pi(x))b_{n-j}^{*}.$

Hence,

$\displaystyle\sum_{n=0}^{\infty}|a_{n}^{*}|$
$\displaystyle\leq\pi(x)\sum_{n=0}^{\infty}\sum_{j=n+1}^{\infty}|b_{j}^{*}|+\sum_{n=0}^{\infty}\sum_{j=0}^{n}|P_{x}(X_{n-j}=x)-\pi(x)||b_{j}^{*}|$
$\displaystyle\leq\pi(x)\sum_{j=0}^{\infty}(j+1)|E_{x}f_{c}(X_{j})I(\tau(x)>j)|+\sum_{j=0}^{\infty}|b_{j}^{*}|\sum_{n=j}^{\infty}|P_{z}(X_{n-j}=x)-\pi(x)|$
$\displaystyle\leq\pi(x)E_{x}\sum_{j=0}^{\infty}(j+1)|f_{c}(X_{j})|I(\tau(x)>j)$
$\displaystyle\qquad\qquad+E_{x}\sum_{j=0}^{\infty}(j+1)|f_{c}(X_{j})|I(\tau(x)>j)\cdot\sum_{n=0}^{\infty}|P_{x}(X_{n}=x)-\pi(x)|$
$\displaystyle=\pi(x)E_{x}\sum_{j=0}^{\tau(x)-1}(j+1)|f_{c}(X_{j})|+E_{x}\sum_{j=0}^{\tau(x)-1}|f_{c}(X_{j})|\cdot\sum_{n=0}^{\infty}|P_{x}(X_{n}=x)-\pi(x)|<\infty,$

provided that

$\displaystyle\sum_{n=0}^{\infty}|P_{x}(X_{n}=x)-\pi(x)|<\infty.$ (2.20)

The finiteness of (2.20) follows from Proposition 11.1.1 and Theorem 13.4.5 of
Meyn and Tweedie (2012). ∎

######  Remark 4.

Observe that when (2.19) holds for each $x\in S$, it is clear that

$\displaystyle
g^{*}(x)\overset{\Delta}{=}\sum_{j=0}^{\infty}E_{x}f_{c}(X_{j})$

is well-defined, finite-valued, and satisfies (2.4). So, when $\eqref{eq214}$
is valid and $E_{z}\tau(z)^{2}<\infty$ for some $z\in S$, the infinite sum
representation $g^{*}=(g^{*}(x):x\in S)$ is an alternative means of
representing the solution to Poisson’s equation (2.4).

We turn next to the development of Lyapunov criteria that characterize our
weakened sufficient conditions under which solutions of Poisson’s equation
exist, and exhibit the summability (Theorem 4) and limiting behaviors (Theorem
3) described above.

Our results are a simple consequence of the following special case of the
Comparison Theorem; see p.344 of Meyn and Tweedie (2012).

######  Proposition 2.

Suppose that $X=(X_{n}:n\geq 0)$ is an irreducible and recurrent Markov chain.
Assume that there exists $v:S\rightarrow\mathbb{R}_{+}$,
$w:S\rightarrow\mathbb{R}_{+}$, and a finite subset $K\subseteq S$ for which
$E_{x}v(X_{1})<\infty$ for $x\in K$ and

$\displaystyle E_{x}v(X_{1})\leq v(x)-w(x)$ (2.21)

for $x\in K^{c}$. Then, there exists $c<\infty$ such that

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}w(X_{j})\leq v(x)+c$ (2.22)

for $x\in S$ and $z\in K$.

###### Proof.

We first note that if we set

$\displaystyle d=\max_{x\in K}[E_{x}v(X_{1})-v(x)+w(x)],$

then (2.21) implies that

$\displaystyle E_{x}v(X_{1})\leq v(x)-w(x)+dI(x\in K)$

for $x\in S$. We then apply the Comparison Theorem to conclude that

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}w(X_{j})\leq
v(x)+dE_{x}\sum_{j=0}^{\tau(z)-1}I(X_{j}\in K)$

for $x\in S$. If $\Lambda_{0}=\inf\\{n\geq 0:X_{n}\in K\\}$, with
$\Lambda_{m}=\inf\\{n>\Lambda_{m-1}:X_{n}\in K\\}$ for $n\geq 1$, the
recurrence of $X$ implies that the $\Lambda_{m}$’s are finite-valued.
Furthermore, $(X_{\Lambda_{m}}:m\geq 0)$ is the Markov chain on $K$ that
records the successive visits of $X$ to $K$. Obviously, for $x\in S$,

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}I(X_{j}\in K)\leq E_{x}\gamma(z)$

where $\gamma(z)=\inf\\{m\geq 1:X_{\Lambda_{m}}=z\\}$. Since $X$ is
irreducible, the finite-state Markov chain $(X_{\Lambda_{m}}:m\geq 0)$ is
irreducible. The finiteness of $|K|$ implies that $E_{y}\gamma(z)<\infty$ for
$y,z\in K$. If we set $c=d\max\\{E_{y}\gamma(z):y,z\in K\\}$, we obtain
(2.22). ∎

######  Theorem 5.

Suppose that $X$ is an irreducible Markov chain, and let $K\subseteq S$ be a
finite subset. Consider the following conditions:

  1. a)

There exists $v_{1}:S\rightarrow\mathbb{R}_{+}$ such that $(Pv_{1})(x)<\infty$
for $x\in K$ and

$\displaystyle(Pv_{1})(x)\leq v_{1}(x)-1$

for $x\in K^{c}$;

  2. b)

There exists $v_{2}:S\rightarrow\mathbb{R}_{+}$ such that $(Pv_{2})(x)<\infty$
for $x\in K$ and

$\displaystyle(Pv_{2})(x)\leq v_{2}(x)-|f(x)|$

for $x\in K^{c}$;

  3. c)

There exist $v_{3}:S\rightarrow\mathbb{R}_{+}$ and
$v_{4}:S\rightarrow\mathbb{R}_{+}$ such that $(Pv_{3})(x)+(Pv_{4})(x)<\infty$
for $x\in K$,

$\displaystyle(Pv_{3})(x)\leq v_{3}(x)-v_{1}(x),$

and

$\displaystyle(Pv_{4})(x)\leq v_{4}(x)-v_{2}(x).$

Then:

  1. i)

If $a)$ holds, $X$ is positive recurrent and a unique stationary distribution
$\pi$ exists.

  2. ii)

If $a)$ and $b)$ hold, then Theorems 1 and 2 are valid.

  3. iii)

If $a)$, $b),$ and $c)$ hold, then Theorems 1 through 4 are valid.

###### Proof.

Condition $a)$ and Proposition 2 imply that $E_{x}\tau(z)\leq v_{1}(x)+c$ for
$x\in S$, whereas condition $b)$ implies that for $x\in S$,

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}|f(X_{j})|\leq v_{2}(x)+c$ (2.23)

for some $c\in K$, proving $i)$ and $ii)$ when we set $x=z$. (Of course, these
results are well known; see Meyn and Tweedie (2012).) If $c)$ is also in
force, then Proposition 2 implies that

$\displaystyle E_{z}\sum_{j=0}^{\tau(z)-1}v_{1}(X_{j})\leq v_{3}(z)+c$

and

$\displaystyle E_{z}\sum_{j=0}^{\tau(z)-1}v_{2}(X_{j})\leq v_{4}(z)+c.$

Consequently,

$\displaystyle\infty>E_{z}\sum_{j=0}^{\tau(z)-1}(\tau(z)-j)=E_{z}\frac{\tau(z)(\tau(z)+1)}{2}$

and

$\displaystyle\infty>E_{z}\sum_{j=0}^{\tau(z)-1}\sum_{k=j}^{\tau(z)-1}|f(X_{k})|=E_{z}\sum_{k=0}^{\tau(z)-1}(k+1)|f(X_{k})|,$

for $z\in K$, proving part $iii)$ for $z\in K$. These conditions imply
Theorems 3 and 4. ∎

######  Remark 5.

As usual, these Lyapunov conditions are also necessary conditions, in order
that the required moments of Theorems 1 through 4 be finite (for $f$ replacing
$f_{c}$). For example, in order that

$\displaystyle E_{z}\sum_{j=0}^{\tau(z)-1}(j+1)|f(X_{j})|<\infty,$ (2.24)

it must be that

$\displaystyle
q(x)\overset{\Delta}{=}E_{x}\sum_{j=0}^{T_{K}-1}(j+1)|f(X_{j})|<\infty$

for all $x\in S$, where $T_{K}=\inf\\{n\geq 0:X_{n}\in K\\}$ with
$K\supseteq\\{z\\}$. But the function $q=(q(x):x\in S)$ is then a finite-
valued solution of

$\displaystyle q(z)=(Pq)(x)+\tilde{q}(x)$

for $x\in S$, where $\tilde{q}=(\tilde{q}(x):x\in S)$ solves

$\displaystyle\tilde{q}(x)=(P\tilde{q})(x)+|f(x)|I(x\in K^{c})$

for $x\in S$. This, of course, implies that $q$ and $\tilde{q}$ satisfy the
Lyapunov inequalities for $v_{2}$ and $v_{4}$ with equality, so that if (2.24)
holds, there necessarily exist solutions of the associated Lyapunov
inequalities. Similarly, the Lyapunov inequalities for $v_{1}$ and $v_{3}$ are
necessary for the finiteness of $E_{z}\tau^{2}(z)$.

Theorem 5 therefore provides (weak) sufficient conditions under which Theorems
1 through 4 are valid. Assuming that one can find such suitable Lyapunov
conditions, one can then validate Theorems 1 through 4 under close to minimal
conditions.

##  3 Two Illustrative Examples

Our first example illustrates the fact that when $S$ is infinite, there can be
infinitely many solutions of Poisson’s equation; see, for example, Bhulai and
Spieksma (2003). However, the example below shows that when $X$ is
irreducible, there can even exist infinitely many linearly independent
solutions of Poisson’s equation. So, uniqueness can fail badly.

Given the form of (1.1), non-uniqueness emerges from consideration of
solutions $h$ to the linear system

$\displaystyle Ph=h.$ (3.1)

A function $h$ satisfying (3.1) is called a _harmonic function_. Of course,
the constant function $h$ always solves $\eqref{eq31}$, and this is the source
of the fact that even well-behaved solutions to Poisson’s equation are only
unique up to an additive constant.

######  Example 1.

Consider the Markov chain $X$ defined on the state space
$S=\\{0\\}\cup\\{(i,j):i\geq 1,j\geq 1\\}$ with transition probabilities
defined by

$\displaystyle P(x,y)=\begin{cases}p,&x=(i,j),y=(i+1,j),i,j\geq 1\\\
q,&x=(i,j),y=(i-1,j),i\geq 2,j\geq 1\\\ q,&x=(1,j),y=0,j\geq 1\\\
r_{j},&x=0,y=(1,j),j\geq 1\\\ 1-\sum_{j=1}^{\infty}r_{j},&x=y=0\\\
0,&\text{else},\end{cases}$

where $0<p<1/2,q=1-p,r_{j}>0$ for $j\geq 1$, and $\sum_{j=1}^{\infty}r_{j}<1$.
This Markov chain is irreducible, aperiodic, and positive recurrent (since
$p<q$). To compute its stationary distribution, we note that $\pi=(\pi(x):x\in
S)$ satisfies the linear system of equations

$\displaystyle\pi(i,j)=p\pi(i-1,j)+q\pi(i+1,j)$ (3.2)

for $i\geq 2,j\geq 1$ while

$\displaystyle\pi(1,j)=r_{j}\pi(0)+q\pi(2,j)$ (3.3)

and

$\displaystyle\pi(0)=(1-\sum_{j=1}^{\infty}r_{j})\pi(0)+q\sum_{j=1}^{\infty}\pi(1,j).$
(3.4)

The general solution of (3.2) is

$\displaystyle\pi(i,j)=a_{j}+b_{j}\left(\frac{p}{q}\right)^{i}$ (3.5)

for $i,j\geq 1$. Relation (3.3) implies that

$\displaystyle a_{j}+b_{j}=\frac{r_{j}}{p}\pi(0),$ (3.6)

while (3.4) requires that the $a_{j}$’s be summable and satisfy

$\displaystyle\sum_{j=1}^{\infty}a_{j}=0.$ (3.7)

Equations (3.5) and (3.7) imply that the solution space corresponding to the
stationary equations is infinite-dimensional. Of course, (3.5) implies that
$\pi(i,j)\rightarrow a_{j}$ as $i\rightarrow\infty$. In view of (3.7), any
solution for which $a_{j}\neq 0$ for some $j\geq 1$ must therefore have both
the property that the $\pi(x)$’s are non-summable and that the $\pi(x)$’s are
of mixed-sign. Hence, if $\pi$ is to be a probability distribution, we must
have $a_{j}=0$ for $j\geq 1$, in which case

$\displaystyle\pi(i,j)=\frac{r_{j}}{p}\left(\frac{p}{q}\right)^{i}\pi(0)$

for $i,j\geq 1$, with

$\displaystyle\pi(0)=(1+\frac{\sum_{j=1}^{\infty}r_{j}}{q-p})^{-1}.$

The solution space corresponding to the space of harmonic functions is
similarly infinite-dimensional. In particular, (3.1) is given by the linear
system

$\displaystyle ph(i+1,j)+qh(i-1,j)=h(i,j)$

for $i\geq 2,j\geq 1$, with

$\displaystyle ph(2,j)+qh(0)=h(1,j)$

for $j\geq 1$, and

$\displaystyle(1-\sum_{j=1}^{\infty}r_{j})h(0)+\sum_{j=1}^{\infty}r_{j}h(1,j)=h(0).$

The general solution of this linear system is given by

$\displaystyle h(i,j)=h(0)+\tilde{b}_{j}[(\frac{q}{p})^{i}-1]$ (3.8)

for $i,j\geq 1$, where the sequence $(\tilde{b}_{j}:j\geq 1)$ must be both
summable and satisfy

$\displaystyle\sum_{j=1}^{\infty}\tilde{b}_{j}=0.$ (3.9)

An interesting feature of Example 1 is that conditional on $X_{0}=x\in S$, the
birth-death structure of $X$ implies that the random variable (rv)
$X_{n}=(I_{n},J_{n})$ must be such that $I_{n}\leq i+n$. As a result,
$(h(X_{n}):n\geq 0)$ is $P_{x}$-integrable and hence is a $P_{x}$-martingale
for each $x\in S$. Consequently, whenever $f\in L^{1}(\pi)$,

$\displaystyle g_{z}(X_{n})+\sum_{i=0}^{n-1}f_{c}(X_{j})+h(X_{n})$

is a $P_{x}$-martingale for all the harmonic functions characterised by (3.8)
and (3.9), and $g_{z}+h$ is a solution of Poisson’s equation.

Note that any non-constant harmonic function fails to be $\pi$-integrable, so
$g_{z}+h$ is not $\pi$-integrable. Hence, this example establishes that even
when a solution to Poisson’s equation induces a martingale, that solution may
be badly behaved (e.g. it may not be $\pi$-integrable).

This raises the question of whether there is an alternative martingale
property that characterizes well-behaved solutions to Poisson’s equation (e.g.
solutions of the form $g_{z}+ce$ for $c\in\mathbb{R}$, where $e(x)=1$ for
$x\in S$). Our next result provides one such characterization; see part b.).

######  Theorem 6.

Assume that $f\in L^{1}(\pi)$.

  1. a)

For $x,y,z\in S$,

$\displaystyle(g_{y}(X_{\tau(z)\land
n})+\smashoperator[]{\sum_{j=0}^{(\tau(z)\land n)-1}}f_{c}(X_{j}):n\geq 0)$
(3.10)

is a $P_{x}$-uniformly integrable martingale adapted to
$(\mathcal{F}_{n}:n\geq 0)$.

  2. b)

Suppose that there exists $z\in S$ and $g:S\rightarrow\mathbb{R}$ such that
for each $x\in S$,

$\displaystyle(g(X_{\tau(z)\land
n})+\smashoperator[]{\sum_{j=0}^{(\tau(z)\land n)-1}}f_{c}(X_{j}):n\geq 0)$

is a $P_{x}$-uniformly integrable martingale adapted to
$(\mathcal{F}_{n}:n\geq 0)$. Then, for each $y\in S$,
$g(x)=g_{y}(x)+g(y)e(x)$.

###### Proof.

For part a), we first recognize that $g_{y}(\cdot)$ and $g_{z}(\cdot)$ differ
by an additive constant (by Theorem 1), so it is sufficient to prove the
result for $y=z$. We further note that Theorem 2 establishes (2.8) is a
$P_{x}$-martingale, and hence optional sampling implies that (3.10) is a
$P_{x}$-martingale. So, it remains only to prove that (3.10) is
$P_{x}$-uniformly integrable. Note that

$\displaystyle g_{z}(X_{\tau(z)\land n})+\sum_{j=0}^{(\tau(z)\land
n)-1}f_{c}(X_{j})\overset{a.s.}{\rightarrow}g_{z}(X(\tau(z)))+\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})=\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})$

as $n\rightarrow\infty$. In view of Theorem 4.6.3 of Durrett (2019), it
suffices to prove that

$\displaystyle E_{x}|g_{z}(X_{\tau(z)\land
n})+\smashoperator[]{\sum_{j=0}^{(\tau(z)\land n)-1}}|f_{c}(X_{j})|\rightarrow
E_{x}|\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})|$ (3.11)

as $n\rightarrow\infty$. But

$\displaystyle|g_{z}(X_{\tau(z)\land
n})+\smashoperator[]{\sum_{j=0}^{(\tau(z)\land n)-1}}f_{c}(X_{j})|$
$\displaystyle\leq|g_{z}(X_{n})|I(\tau(z)>n)+\sum_{j=0}^{\tau(z)-1}|f(X_{j})|+|\pi
f|\tau(z)$ (3.12)

and the latter two rv’s on the right-hand size of (3.12) have finite
$P_{x}$-expectation because $f\in L^{1}(\pi)$ and $X$ is positive recurrent.
For the first term, note that

$\displaystyle E_{x}(|g_{z}(X_{n})|I(\tau(z)>n))$
$\displaystyle=E_{x}|\sum_{j=n}^{\beta_{n}(z)-1}f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle\leq E_{x}\sum_{j=n}^{\beta_{n}(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)$
$\displaystyle=E_{z}\sum_{j=n}^{\tau(z)-1}|f_{c}(X_{j})|I(\tau(z)>n)\rightarrow
0$

as $n\rightarrow\infty$. As a consequence, (3.11) follows and we have
established the required uniform integrability.

For part $b)$, note that the uniform integrability and martingale property
imply that

$\displaystyle g(x)=E_{x}g(X_{\tau(z)\land
n})+\smashoperator[]{\sum_{j=0}^{(\tau(x)\land n)-1}}f_{c}(X_{j})\rightarrow
g(z)+E_{x}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})=g(z)+g_{z}(x)$

as $n\rightarrow\infty$, proving the result for $y=z$. The case of general $y$
is handled by just noting that $g_{z}(\cdot)$ and $g_{y}(\cdot)$ differ by an
additive constant; see Theorem 1.
∎

While our first example illustrates non-uniqueness issues related to Poisson’s
equation, our second example provides further insight into existence and
representation issues related to Poisson’s equation. Theorem 1 shows that
whenever $f\in L^{1}(\pi)$, $g_{z}$ solves Poisson’s equation. However, a
commonly used representation of the solution of Poisson’s equation is that
given by (2.21), namely

$\displaystyle g(x)=\sum_{j=0}^{\infty}E_{x}f_{c}(X_{j}).$ (3.13)

Our example below shows that there are Markov chains $X$ and functions $f\in
L^{1}(\pi)$ for which the solution $g_{z}$ is well-defined, while the
representation (3.13) is not well-defined (since the sum fails to be
summable). Hence, $g_{z}$ is a universal representation of the solution to
Poisson’s equation, while the “potential-theoretic” representation (3.13)
requires more regularity in order that it be valid.

######  Example 2.

Let $\beta_{1},\beta_{2},...$ be a sequence of independent and identically
distributed (iid) positive integer-valued rv’s, and put

$\displaystyle S_{n}=\beta_{1}+\beta_{2}+...+\beta_{n},$

with $S_{0}=0$. Let $\ell(n)=\max\\{j:S_{j}\leq n\\}$ and let

$\displaystyle X_{n}=n-S_{\ell(n)}$

be the “current age” Markov chain associated with the inter-renewal times
$\beta_{1},\beta_{2},...$ . Put $f(x)=\delta_{x0}$, so that $f(\cdot)$ is 1
when $x=0$ and 0 otherwise. Then,

$\displaystyle E_{0}f(X_{n})=P_{0}(X_{n}=0)\overset{\Delta}{=}u_{n},$

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

$\displaystyle P(\beta_{1}>n)\sim cn^{-\alpha}$

as $n\rightarrow\infty$ (where we write $a_{n}\sim b_{n}$ as
$n\rightarrow\infty$ when $a_{n}/b_{n}\rightarrow 1$ as $n\rightarrow\infty$).
Then, $E\beta_{1}<\infty$ and $X$ is positive recurrent with
$\pi(0)=\lambda\overset{\Delta}{=}1/E\beta_{1}$.

According to Lemma 4 of Frenk (1982),

$\displaystyle u_{n}-\lambda\sim\frac{\lambda^{2}nP(\beta_{1}>n)}{\alpha-1}$

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

$\displaystyle
P_{0}(X_{n}=0)-\pi(0)\sim\frac{\lambda^{2}cn^{1-\alpha}}{(\alpha-1)}$

as $n\rightarrow\infty$. As a consequence, if $\alpha\in(1,2]$, (3.13) fails
to be summable at $x=0$, providing the required example.

##  4 The CLT and LIL for Markov Chains

We finish this paper by developing a weakened Lyapunov criterion for the
validity of the central limit theorem and law of the iterated logarithm for
countable state Markov chains. It is well known that if there exists $z\in S$
such that

$\displaystyle
E_{z}\left(\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})\right)^{2}<\infty,$ (4.1)

then, regardless of the initial distribution for $X_{0}$,

$\displaystyle\frac{S_{n}(f)-n\pi f}{\sqrt{n}}\Rightarrow\sigma N(0,1)$ (4.2)

as $n\rightarrow\infty$, where $\Rightarrow$ denotes weak convergence,
$N(0,1)$ is a standard normal rv with mean 0 and variance 1, and

$\displaystyle\sigma^{2}\overset{\Delta}{=}\frac{E_{z}\left(\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})\right)^{2}}{E_{z}\tau(z)},$
(4.3)

see p.99 of Chung (1967) or Glynn and Whitt (1993). Furthermore, Theorem 14.4
of Chung (1967) proves that if $\eqref{eq41}$ is valid for one $z\in S$, then
it is valid for all $z\in S$, and the right-hand side of (4.3) does not depend
on $z$. In Glynn and Whitt (2002), it is shown that (4.2) implies (4.1), so
that (4.1) is a necessary and sufficient condition for the CLT (4.2), in the
presence of positive recurrence and $f\in L^{1}(\pi)$.

We now slightly strengthen (4.1) to the condition

$\displaystyle E_{z}(\sum_{j=0}^{\tau(z)-1}|f_{c}(X_{j})|)^{2}<\infty.$ (4.4)

######  Theorem 7.

Suppose that $X$ is irreducible, and let $K\subseteq S$ be a finite subset.
Suppose that there exists $v_{1}\in S\rightarrow\mathbb{R}_{+}$ and $v_{2}\in
S\rightarrow\mathbb{R}_{+}$ such that $(Pv_{i})(x)<\infty$ for $x\in K$ and
$i=1,2$ and

$\displaystyle(Pv_{1})(x)$ $\displaystyle\leq v_{1}(x)-(|f(x)|+1)$ (4.5)
$\displaystyle(Pv_{2})(x)$ $\displaystyle\leq v_{2}(x)-(|f(x)|+1)v_{1}(x)$
(4.6)

for $x\in K^{c}$. Then, $X$ is positive recurrent, $f\in L^{1}(\pi)$, and
$\eqref{eq44}$ is valid, so that the CLT (4.2) holds. Furthermore,
$\sigma^{2}$ can then be expressed as (4.3) or, equivalently, as

$\displaystyle\sigma^{2}=2E_{\pi}g_{z}(X_{0})f_{c}(X_{0})-E_{\pi}f_{c}(X_{0})^{2}.$
(4.7)

###### Proof.

Proposition 2 and (4.5) imply that $X$ is positive recurrent with $f\in
L^{1}(\pi)$, and

$\displaystyle E_{x}(\tau(z)+\sum_{j=0}^{\tau(z)-1}|f(X_{j})|)\leq
v_{1}(x)+c_{1}$

for $x\in S,z\in K,$ and some $c_{1}\in\mathbb{R}_{+}$. On the other hand,
Proposition 2 and (4.6) imply that there exists $c_{2}\in\mathbb{R}_{+}$ for
which

$\displaystyle E_{x}\sum_{j=0}^{\tau(z)-1}|f(X_{j})+1|v_{1}(X_{j})\leq
v_{2}(x)+c_{2}.$

Consequently,

$\displaystyle E_{x}(\sum_{j=0}^{\tau(z)-1}|f(X_{j})+1|)^{2}$
$\displaystyle\leq
2E_{x}\sum_{j=0}^{\tau(z)-1}|f(X_{j})+1|\sum_{k=j}^{\tau(z)-1}(|f(X_{k})|+1)$
$\displaystyle\leq
2E_{x}\sum_{j=0}^{\tau(z)-1}(|f(X_{j})+1|)(v_{1}(X_{j})+c_{1})$
$\displaystyle\leq 2(v_{2}(x)+c_{2})+c_{1}(v_{1}(x)+c_{1})<\infty$

for $x\in S$, proving (4.4).

To prove (4.7), note that in the presence of (4.4), we see that

$\displaystyle E_{z}(\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j}))^{2}$
$\displaystyle=2E_{z}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})\sum_{k=j}^{\tau(z)-1}f_{c}(X_{k})-E_{z}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})^{2}$
$\displaystyle=2E_{z}\sum_{j=0}^{\tau(z)-1}f_{c}(X_{j})g_{z}(X_{j})-E_{z}\sum_{j=0}^{\tau(z)-1}f_{c}^{2}(X_{j})$
$\displaystyle=E_{z}\tau(z)(2E_{\pi}f_{c}(X_{0})g_{z}(X_{0})-E_{\pi}f_{c}(X_{0})^{2}),$

establishing the result. ∎

######  Remark 6.

This Lyapunov criterion for Markov chain CLT weakens the existing criterion of
Glynn and Meyn (1996). In particular, when one writes $S_{n}(f)$ in terms of
the martingale (2.8), one is naturally led to consideration of the associated
martingale differences given by

$\displaystyle D_{i}=g_{z}(X_{i})-(Pg_{z})(X_{i-1})$

for $i\geq 1$. In order that $D_{i}\in L^{2}(\pi)$, it seems appropriate to
demand that $g_{z}\in L^{2}(\pi)$; see Theorem 4.1 of Glynn and Meyn (1996).
This is also the condition used in earlier work by Maigret (1978) on the
Markov chain CLT. However, the expression (4.7) makes clear that the key
requirement in the Markov chain CLT is $g_{z}f_{c}\in L^{1}(\pi)$. This is
effectively what (4.6) is verifying.

To see that use of (4.6) gives better conditions than does Glynn and Meyn
(1996), consider the Markov chain defined by

$\displaystyle X_{n+1}=[X_{n}+Z_{n+1}]^{+}$ (4.8)

where $[x]^{+}=\max(x,0)$ and the $Z_{i}$’s are independent and identically
distributed (iid) integer-valued rv’s with $-\infty<EZ_{1}<0$. As is well-
known, this Markov chain arises naturally in the modeling of queues. Use of
Theorem 4.1 in that paper for $f(x)=x$ leads to the requirement that
$E|Z_{1}|^{5}<\infty$. On the other hand, our Theorem 7 requires only that
$EZ_{1}^{4}<\infty$, thereby weakening the moment requirement on $Z_{1}$. (Use
$v_{1}(x)=ax^{2}$ and $v_{2}(x)=a^{\prime}x^{4}$ for suitably chosen $a$ and
$a^{\prime}$.)

We now argue that $EZ_{1}^{4}<\infty$ is the natural condition that arises in
connection to the CLT for the Markov chain defined by (4.8). We first note
that $X_{n}$ is a non-decreasing function of the independent rv’s
$X_{0},Z_{1},...,Z_{n}$. Consequently, the $X_{n}$’s are associated rv’s; see
Barlow and Proschan (1975), p.29-31. Hence,

$\displaystyle E_{\pi}(X_{0}\land r)(X_{n}\land r)\geq E_{\pi}X_{0}\land
r\cdot E_{\pi}X_{n}\land r$

for $r\geq 0$. Sending $r\rightarrow\infty$, we conclude that

$\displaystyle E_{\pi}X_{0}X_{n}\geq E_{\pi}X_{0}\cdot E_{\pi}X_{n}$

via the Monotone Convergence Theorem. If the CLT holds, this implies the
existence of a finite non-negative $\alpha\in\mathbb{R}$ such that
$n^{-1}\sum_{j=0}^{n-1}X_{j}\overset{p}{\rightarrow}\alpha$ as
$n\rightarrow\infty$. Because the $X_{j}$’s are non-negative, $\alpha$ must
equal $E_{\pi}X_{0}$. So, $E_{\pi}X_{0}<\infty$ and

$\displaystyle c_{n}\overset{\Delta}{=}E_{\pi}X_{0}X_{n}-E_{\pi}X_{0}\cdot
E_{\pi}X_{n}\geq 0$

for $n\geq 0$. Another truncation and monotone convergence argument
establishes that

$\displaystyle\frac{1}{n}E_{\pi}(\sum_{j=0}^{n-1}(X_{j}-E_{\pi}X_{0}))^{2}=c_{0}+2\sum_{j=1}^{n}\frac{(n-j)}{n}c_{j}.$
(4.9)

Since

$\displaystyle\frac{1}{2}\sum_{j=0}^{\lfloor n/2\rfloor}c_{j}\leq
c_{0}+2\sum_{j=1}^{n}\frac{(n-j)}{n}c_{j}\leq
c_{0}+2\sum_{j=1}^{\infty}c_{j},$

it is evident that the left-hand side of (4.9) has a finite limit if and only
if

$\displaystyle c_{0}+2\sum_{j=1}^{\infty}c_{j}<\infty.$ (4.10)

According to Daley (1968), (4.10) holds (in the presence of a blanket
assumption that $E|Z_{1}|^{3}<\infty$) if and only if $EZ_{1}^{4}<\infty$. Of
course, demanding that the left-hand side of (4.9) have a limit follows
whenever the CLT (4.2) is in force and the square of the left-hand side of
(4.2) is $P_{\pi}$-uniformly integrable.

######  Remark 7.

Another indication that $EZ_{1}^{4}$ is a necessary condition for the CLT in
this setting is that when one allows the $Z_{i}$’s to be continuous rv’s,
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
$EZ_{1}^{4}$ is necessary in order that $g_{z}f_{c}$ be $\pi$-integrable
(Asmussen (2008)), and hence that $\sigma^{2}$ as given by (4.7) be finite.

We now turn to the law of the iterated logarithm for $S_{n}(f)$. The following
is an immediate consequence of Theorem 7 above and Theorem 5, p.106 of Chung
(1967).

######  Theorem 8.

Under the same hypotheses as in Theorem 7,

$\displaystyle\varlimsup_{n\rightarrow\infty}\left|\frac{S_{n}(f)-n\pi
f}{\sqrt{n\log\log n}}\right|=|\sigma|\qquad P_{x}\ \text{a.s.}$

for each $x\in S$, where $\sigma^{2}$ is as given in Theorem 7.

Glynn and Whitt (1993) provide necessary and sufficient conditions for the LIL
when the process is regenerative. The condition is stronger than (4.1), but
slightly weaker than (4.2). So, Theorem 8 gives close to optimal conditions
for the LIL.

## References

  * Asmussen (2008) Asmussen, S. (2008).  Applied Probability and Queues.  New York: Springer Science & Business Media.
  * Barlow and Proschan (1975) Barlow, R. E. and Proschan, F. (1975).  Statistical Theory of Reliability and Life Testing: Probability Models.  New York: Holt, Rinehart and Winston.
  * Bhulai and Spieksma (2003) Bhulai, S. and Spieksma, F. M. (2003).  On the uniqueness of solutions to the Poisson equations for average cost Markov chains with unbounded cost functions.  Mathematical Methods of Operations Research, 58(2), 221–236.
  * Chung (1967) Chung, K. L. (1967).  Markov Chains (Second ed.).  Springer.
  * Daley (1968) Daley, D. J. (1968).  The serial correlation coefficients of waiting times in a stationary single server queue.  Journal of the Australian Mathematical Society, 8(4), 683–699.
  * Derman and Veinott (1967) Derman, C. and Veinott, A. F. (1967).  A solution to a countable system of equations arising in Markovian decision processes.  The Annals of Mathematical Statistics, 38(2), 582–584.
  * Durrett (2019) Durrett, R. (2019).  Probability: Theory and Examples.  Cambridge University Press.
  * Feller (1968) Feller, W. (1968).  An Introduction to Probability Theory and Its Applications., volume 1.  John Willey & Sons.
  * Frenk (1982) Frenk, J. B. (1982).  The behavior of the renewal sequence in case the tail of the waiting-time distribution is regularly varying with index- 1.  Advances in Applied Probability, 14(4), 870–884.
  * Glynn (1994) Glynn, P. W. (1994).  Poisson’s equation for the recurrent M/G/1 queue.  Advances in Applied Probability, 26(4), 1044–1062.
  * Glynn and Infanger (2022) Glynn, P. W. and Infanger, A. (2022).  Solutions of Poisson’s equation for stochastically monotone Markov chains.  Submitted for publication.
  * Glynn and Meyn (1996) Glynn, P. W. and Meyn, S. P. (1996).  A Liapounov bound for solutions of the Poisson equation.  The Annals of Probability, 916–931.
  * Glynn and Whitt (1993) Glynn, P. W. and Whitt, W. (1993).  Limit theorems for cumulative processes.  Stochastic Processes and their Applications, 47(2), 299–314.
  * Glynn and Whitt (2002) Glynn, P. W. and Whitt, W. (2002).  Necessary conditions in limit theorems for cumulative processes.  Stochastic Processes and their Applications, 98(2), 199–209.
  * Hall and Heyde (1980) Hall, P. and Heyde, C. C. (1980).  Martingale Limit Theory and Its Application.  Academic press.
  * Kurtz (1981) Kurtz, T. G. (1981).  The central limit theorem for Markov chains.  The Annals of Probability, 557–560.
  * Maigret (1978) Maigret, N. (1978).  Théorème de limite centrale fonctionnel pour une chaîne de Markov récurrente au sens de Harris et positive.  14, 425–440.
  * Makowski and Shwartz (2002) Makowski, A. M. and Shwartz, A. (2002).  The Poisson equation for countable Markov chains: Probabilistic methods and interpretations.  In Handbook of Markov Decision Processes (pp. 269–303). Springer.
  * Meyn and Tweedie (2012) Meyn, S. P. and Tweedie, R. L. (2012).  Markov Chains and Stochastic Stability.  Springer Science & Business Media.
  * Ross (2014) Ross, S. M. (2014).  Introduction to Stochastic Dynamic Programming.  Academic Press.
  * Schaufele (1967) Schaufele, R. A. (1967).  A potential theoretic proof of a theorem of Derman and Veinott.  The Annals of Mathematical Statistics, 585–587.