Title of the book!

Armand M. Makowski Department of Electrical and Computer Engineering,

and Institute for Systems Research

University of Maryland College Park, MD 20742, U.S.A.

Adam Shwartz

Electrical Engineering Department, Technion—Israel Institute of Technology

Technion City, Haifa 32000, Israel

May 28, 2000

Chapter 1

On the Poisson equation for countable Markov chains: Existence of solutions and parameter dependence by probabilistic methods

ch:Poisson

Abstract

This paper considers the Poisson equation associated with time-homogeneous Markov chains on a countable state space. The discussion emphasizes probabilistic arguments and focuses on three separate issues, namely (i) the existence and uniqueness of solutions to the Poisson equation, (ii) growth estimates and bounds on these solutions and (iii) their parametric dependence. Answers to these questions are obtained under a variety of recurrence conditions.

Motivating applications can be found in the theory of Markov decision processes in both its adaptive and non-adaptive formulations, and in the theory of Stochastic Approximations. The results complement available results from Potential Theory for Markov chains, and are therefore of independent interest.

1.1 Introduction

Let P ≡ (p_{xy}) be the one–step transition matrix for a time-homogeneous Markov chain {X_{t}, t = 0, 1, … } taking values in some countable space 𝕏. This paper is devoted to the corresponding Poisson equation with forcing function c : 𝕏 → ℝ, namely

h(x) + J = c(x) + ∑_{y}p_{xy}h(y), x ∈ 𝕏  (1.1) eq:(1.1)

for scalar J and mapping h : 𝕏 → ℝ. This equation arises naturally in a variety of problems associated with Markov chains as the following examples indicate.

1. As shown in Section ^{\underline{sec:3}} 1.3, solving the Poisson equation provides a means to evaluate the long-run average cost J associated with the cost function c ^{\underline{Rossc}} [30]: If (^{\underline{eq:(1.1)}} 1.1) has a solution (h, J) and some mild growth conditions are satisfied, then Lemma ^{\underline{l:Lemma 3.1}} 2 states that

J = lim_{t} 𝔼_{μ} [\frac{1}{t + 1} ∑_{s=0}^{t} c(X_{s})]  (1.2) eq:(1.2)

where μ is the initial distribution and 𝔼_{μ} is the corresponding expectation operator. The function h measures the sensitivity of the cost to the initial state, and represents a second-order effect ^{\underline{HSp}} [11] captured through the “deviation matrix.” The function h can also serve as a “Lyapunov function” in establishing ergodicity ^{\underline{Meyn}} [24], and plays a key role in proving the convergence of the policy improvement algorithm ^{\underline{Meyn}} [24].

2. In recent years, there has been widespread interest in stochastic approximation algorithms as a means to solve increasingly complex engineering problems ^{\underline{BMP,Chen,Kush,KY}} [1, 5, 14, 15]. As a result, focus has shifted from the original Robbins-Monro algorithm to (projected) stochastic approximations driven by Markovian “noise” or “state” processes. Properties of solutions to an appropriate Poisson equation play an essential role when establishing the a.s. convergence of such adaptive algorithms ^{\underline{BMP,MMS,MSsiam,MPa,MPb,SMant}} [1, 16, 20, 22, 23, 33].

3. In the context of Markov decision processes (MDPs), the need for adaptive policies can arise in response to both modeling uncertainties and computational limitations ^{\underline{SMman}} [34]. Several adaptive policies have been proposed as “implementations” to a Markov stationary policy, and shown to yield the same cost performance ^{\underline{BG,MMS,MSimp,Man,SMman}} [3, 16, 17, 21, 34]. Here too, the analysis requires precise information on the solution to the Poisson equation associated with the non-adaptive policy ^{\underline{SMman}} [34].

In many of these applications, it is natural to view the forcing function c and the transition matrix P as parametrized, say by some parameter θ (which may be loosely interpreted as a control variable). The requisite analysis then typically exploits smoothness properties (in θ) of the solution h together with various growth estimates (in x) for h. In addition, estimates on the moments of {h(X_{t}), t = 0, 1, 2, … } are required, with the added difficulty that the resulting process {X_{t}, t = 0, 1, 2, … } is not necessarily Markovian (say, under the given stochastic approximation scheme or adaptive policy).

Our main objective is to develop methods for addressing the concerns above in a systematic fashion. We emphasize a probabilistic viewpoint, whenever possible, and focus mostly on the following three issues:

1. Existence and uniqueness of solutions to the Poisson equation (^{\underline{eq:(1.1)}} 1.1);

2. Growth estimates and bounds on these solutions; and

3. Conditions for smoothness in the parameter of these solutions when dealing with the parametric case, as would arise when establishing the a.s. convergence of stochastic approximations and the self–tuning property of adaptive policies.

Answers to these questions are given under a variety of recurrence conditions. As we try to keep the exposition relatively self-contained, we have included some standard material on the Poisson equation. In addition to its tutorial merit, the discussion given here provides a unified treatment to many of the issues associated with the Poisson equation, e.g., existence, uniqueness and representation of solutions. This is achieved by manipulating a single martingale naturally induced by the Poisson equation.

Questions of existence and uniqueness of solutions to (^{\underline{eq:(1.1)}} 1.1) have obvious and natural points of contact with the Potential Theory for Markov chains ^{\underline{KSK,NumP}} [13, 27]. However, it is unfortunate that many situations of interest in applications, say in the context of MDPs, are not readily covered by classical Potential Theory. Indeed, the classical theory treats the purely transient and recurrent cases separately, with drastically different results for each situation. This approach is thus of limited use in the above-mentioned situations, where the recurrence structure of the Markov chain is typically far more complex in that it combines both transient and recurrent states. Here, in contrast with the analytical approach of classical Potential Theory, emphasis has been put on giving an explicit representation of the solution to (^{\underline{eq:(1.1)}} 1.1) with a clear probabilistic interpretation.

This probabilistic approach allows for a relatively elementary treatment of questions of existence and uniqueness, under a rather general recurrence structure. We accomplish this by focusing on the discrete space case, and by keeping the assumptions as transparent as possible. The intuition developed here applies to the general state-space case, under mild conditions on the existence of petite sets ^{\underline{GM,Meyn,MeynTwee}} [9, 24, 25]. Results are obtained in various degrees of completeness for both finite and countably infinite state spaces; recurrence structures include multiple positive recurrent classes, and transient classes. A representation for h is derived in detail in the case of a single positive recurrent class under integrability conditions involving the forcing function c. The derivation uses elementary methods, and provides intuition into more general situations. This representation is shown to also hold in the multiple class countable case, and readily lends itself to establishing natural bounds on the growth rate of h (as a function of the state), and to investigating smoothness properties in the parameterized problem.

Similar results are given in ^{\underline{GM}} [9] for the ergodic case on general state spaces. When the forcing function c is positive and “increasing” (i.e. when its sublevel sets are compact), there is an elegant theory that relates geometric ergodicity to the Poisson equation; details and references are available in Chapter ^{\underline{c:meyn}} 2.

The paper is organized as follows: The set-up is given in Section ^{\underline{sec:2}} 1.2 together with the basic martingale associated with (^{\underline{eq:(1.1)}} 1.1). Various uniqueness results on the the solution (J, h) are discussed in Section ^{\underline{sec:3}} 1.3. We give two decomposition results in Section ^{\underline{sec:4}} 1.4; the first is based on the decomposition of the state space 𝕏 into its recurrent and transient classes, while the second is an analog of the standard Green decomposition and relies on an expansion of the forcing function in terms of more “elementary” functions. To set the stage for the countably infinite case, we briefly recall an algebraic treatment of the finite-state case in Section ^{\underline{sec:5}} 1.5. In Section ^{\underline{sec:6}} 1.6 an explicit representation for the solution is developed in terms of some recurrence times, under a single positive recurrent class assumption. An example is developed in Section ^{\underline{sec:7}} 1.7 to illustrate the material of previous sections. Bounds and extensions to unbounded forcing functions and multichain structures are given in Section ^{\underline{sec:8}} 1.8. Equipped with this probabilistic representation of solutions, we can now investigate the smoothness properties of solutions to the parameterized problem; methods for proving continuity and Lipschitz continuity are developed in Sections ^{\underline{sec:9}} 1.9 and ^{\underline{sec:10}} 1.10, respectively.

To close, we note that most of the ideas which are discussed here in the context of countable Markov chains have extensions to fairly general state spaces. This is achieved by means of the so–called splitting technique \underline{GM,Meyn,MeynTwee,Num} [9, 24, 25, 26] which in essence guarantees the existence of an atom on an enlarged state space.

1.2 The Poisson equation and its associated mar-

tingale

sec:2

First, a few words on the notation used throughout the paper: The set of all real numbers is denoted by ℝ and 1[A] stands for the indicator function of a set A. Unless otherwise stated, lim_{t}, \underline{lim}_{t} and \overline{lim}_{t} are taken with t going to infinity. Moreover, the infimum over an empty set is taken to be ∞ by convention. The Kronecker mapping δ : 𝕏 × 𝕏 → ℝ is defined by δ(x, y) = 1 if x = y, and δ(x, y) = 0 otherwise. Finally, the notation ∑_{x∈𝕏} is often abbreviated as ∑_{x}.

1.2.1 The set-up

sec:Setup

The notion of a Markov chain we adopt in this paper is more general than the elementary one used in most applications. We do so with the view of broadening the applicability of the material developed here, especially to problems of adaptive control for Markov chains ^{\underline{MMS,MSimp,MSsiam,Man,SMant,SMman}} [16, 17, 20, 21, 33, 34].

The state space is a countable set 𝕏, and the one–step transition mechanism is given by the stochastic matrix P ≡ (p_{xy}), i.e., 0 ≤ p_{xy} ≤ 1 and ∑_{y}p_{xy} = 1 for all x and y in 𝕏. We assume the existence of a measurable space (Ω, F) large enough to carry all the probabilistic elements considered in this paper. In particular, let {F_{t}, t = 0, 1, … } denote a filtration of F, i.e., a monotone increasing sequence of σ–fields contained in F such that F_{t} ⊆ F_{t+1} for all t = 0, 1, …, and let {X_{t}, t = 0, 1, … } be a sequence of 𝕏–valued rvs which are F_{t}–adapted, i.e., the rv X_{t} is F_{t}–measurable for all t = 0, 1, . . ..

The Markovian structure of interest is defined by postulating the existence of a family {ℙ_{x}, x ∈ 𝕏} of probability measures on F such that for all x and y in 𝕏, we have

ℙ_{x}[X_{0} = y] = δ(x, y)  (1.3) eq:(2.1a)

and

ℙ_{x}[X_{t+1} = y | F_{t}] = p_{X_{t}y} ℙ_{x} − a.s. t = 0, 1, …  (1.4) eq:(2.1b)

With any probability distribution μ on 𝕏, we associate a probability measure ℙ_{μ} on F by setting

ℙ_{μ}[A] := ∑_{x}μ(x)ℙ_{x}[A], A ∈ F.  (1.5) eq:(2.2)

Obviously, when μ is the Dirac measure δ_{x} concentrated at some x in 𝕏, then ℙ_{μ} reduces to ℙ_{x}. Using (^{\underline{eq:(2.1a)}} 1.3)–(^{\underline{eq:(2.2)}} 1.5) we easily see that

ℙ_{μ}[X_{0} = x] = μ(x), x ∈ 𝕏  (1.6) eq:(2.3a)

and

ℙ_{μ}[X_{t+1} = y | F_{t}] = p_{X_{t}y}, x, y ∈ 𝕏 ℙ_{μ} − a.s. t = 0, 1, … (1.7) eq:(2.3b)

Hence, under the probability measure ℙ_{μ} the rvs {X_{t}, t = 0, 1, … } have the Markov property with respect to the filtration {F_{t}, t = 0, 1, … }, and are said to form a time-homogeneous F_{t}–Markov chain with one–step transition matrix P and initial probability distribution μ. In many instances, we take F_{t} to be the σ–field generated by the rvs X_{0}, …, X_{t} for all t = 0, 1, …, in which case the definition above coincides with the elementary definition of a Markov chain.

¿From (^{\underline{eq:(2.1a)}} 1.3–(^{\underline{eq:(2.2)}} 1.5) we readily conclude for μ–a.s. all x in 𝕏 that

ℙ_{μ}[A|X_{0} = x] = ℙ_{x}[A], A ∈ F  (1.8) eq:(2.4)

and ℙ_{x} has the useful interpretation of conditional probability (under ℙ_{μ} for any initial distribution measure μ).

Throughout it will be convenient to denote by 𝔼_{μ} and 𝔼_{x} the expectation operator associated with ℙ_{μ} and ℙ_{x}, respectively.

1.2.2 The Poisson equation

sec:PEqn

Let c be a given Borel mapping 𝕏 → ℝ. Throughout, it is understood that a constant J and a mapping h : 𝕏 → ℝ constitute a solution pair to the Poisson equation (^{\underline{eq:(1.1)}} 1.1) with forcing function c whenever h satisfies the integrability conditions

∑_{y}p_{xy}|h(y)| < ∞, x ∈ 𝕏  (1.9) eq:(2.5a)

and the relations

h(x) + J = c(x) + ∑_{y}p_{xy}h(y), x ∈ 𝕏  (1.10) eq:(2.5b)

hold. The Poisson equation is termed homogeneous if c ≡ 0.

For any initial distribution μ, we introduce several classes of ℝ–valued mappings defined on 𝕏. The mapping f : 𝕏 → ℝ is said to be an element of 1. I_{μ} if 𝔼_{μ}[|f(X_{t})|] < ∞ for all t = 0, 1, …;

2. B_{μ} if sup_{t} 𝔼_{μ}[|f(X_{t})|] < ∞;

3. S_{μ} if f belongs to I_{μ} with lim_{t} \frac{1}{t}𝔼_{μ}[f(X_{t})] = 0; and

4. U_{μ} if the rvs {f(X_{t}), t = 0, 1, … } are uniformly integrable under ℙ_{μ}.

When μ is the Dirac measure δ_{x} for some x in 𝕏, we substitute the simpler notation I_{x}, B_{x}, S_{x} and U_{x} to I_{δ_{x}}, B_{δ_{x}}, S_{δ_{x}} and U_{δ_{x}}, respectively.

For any initial distribution μ, it holds that

U_{μ} ⊂ B_{μ} ⊂ S_{μ} ⊂ I_{μ},  (1.11) eq:(2.6)

and for any x in 𝕏 such that μ(x) > 0, we have I_{μ} ⊂ I_{x}, B_{μ} ⊂ B_{x} and U_{μ} ⊂ U_{x}.

Since any mapping f : 𝕏 → ℝ can be viewed as a column vector (f(x)), the Poisson equation (^{\underline{eq:(1.1)}} 1.1) can be written in matrix notation as

h + Je = c + P h  (1.12) eq:(2.7)

where e denotes the column vector with all its entries equal to one, i.e., e(x) = 1 for all x in 𝕏. For any vector f = (f(x)) and any subset E of 𝕏, denote by f_{E} the restriction of f to E and similarly define P_{E} as the restriction of P to E. The identity matrix on 𝕏 is denoted by I.

1.2.3 A martingale property

sec:2.3

Many of the general results on solutions to the Poisson equation can be traced back to the following observation.

l:Lemma 2.1 Lemma 1 Let the pair (h, J) be a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)– (^{\underline{eq:(2.5b)}} 1.10) with forcing function c. If the mapping h belongs to I_{μ} for some probability measure μ on 𝕏, then the following statements hold:

1. The forcing function c is necessarily an element of I_{μ}; and

2. The rvs {M_{t}, t = 0, 1, … } defined by M_{0} := h(X_{0}) and

M_{t+1} := h(X_{t+1}) + ∑_{s=0}^{t} c(X_{s}) − (t + 1)J, t = 0, 1, …  (1.13) eq:(2.8)

form an integrable (ℙ_{μ}, F_{t})–martingale sequence.

Proof. Invoking the Markov property, we can reformulate the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) as

h(X_{t}) + J = c(X_{t}) + 𝔼_{μ}[h(X_{t+1})|F_{t}], t = 0, 1, …  (1.14) eq:(2.9)

and the ℙ_{μ}–integrability of the rvs {c(X_{t}), t = 0, 1, … } follows from the assumption on h. This proves Claim 1.

To establish Claim 2, we first conclude from the first part of the proof that the rvs {M_{t}, t = 0, 1, … } are well defined and indeed ℙ_{μ}–integrable. From (^{\underline{eq:(2.8)}} 1.13), we then get

𝔼_{μ}[M_{t+1}|F_{t}] = 𝔼_{μ}[h(X_{t+1})|F_{t}] + ∑_{s=0}^{t} c(X_{s}) − (t + 1)J, t = 0, 1, …

because the rvs X_{0}, …, X_{t} are all F_{t}–measurable, and the martingale property follows from (^{\underline{eq:(2.9)}} 1.14).

1.3 Uniqueness results

sec:3

In this section, we have collected several uniqueness results for the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). In that respect, we first note that if the pair (h, J) is a solution to the Poisson equation, so is the pair (h+αe, J) for any constant α. In other words, uniqueness can only be obtained up to an additive constant. We also observe that for c in I_{μ}, the definition

J(μ) := \overline{lim}_{t} 𝔼_{μ} [\frac{1}{t + 1} ∑_{s=0}^{t} c(X_{s})]  (1.15) eq:(3.1)

is well posed. The next lemma is a version of a standard result from the theory of MDPs under a long-run average criterion ^{\underline{HS,Rossc}} [10, 30], ^{\underline{SMman}} [34, Lemma 3.1].

l:Lemma 3.1 Lemma 2 Let the pair (h, J) be a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)– (^{\underline{eq:(2.5b)}} 1.10) with forcing function c. If the mapping h belongs to S_{μ} for some probability measure μ on 𝕏, then

J = J(μ) = lim_{t} 𝔼_{μ} [\frac{1}{t + 1} ∑_{s=0}^{t} c(X_{s})] .  (1.16) eq:(3.2)

Proof. Since h is an element of S_{μ}, it is also an element of I_{μ} by virtue of (^{\underline{eq:(2.6)}} 1.11). By Claim 2 of Lemma ^{\underline{l:Lemma 2.1}} 1 we readily obtain the equalities 𝔼_{μ}[M_{0}] = 𝔼_{μ}[M_{t+1}] for all t = 0, 1, … or, equivalently, in expanded form,

𝔼_{μ}[h(X_{0})] = 𝔼_{μ}[h(X_{t+1})] + 𝔼_{μ} [∑_{s=0}^{t} c(X_{s})] − (t + 1)J.  (1.17) eq:(3.3)

Simple rearrangements yield

𝔼_{μ} [\frac{1}{t + 1} ∑_{s=0}^{t} c(X_{s})] = J − \frac{1}{t + 1} \{𝔼_{μ}[h(X_{t+1})] − 𝔼_{μ}[h(X_{0})]\} , (1.18) eq:(3.4)

and the result (^{\underline{eq:(3.2)}} 1.16) is now immediate upon letting t ↑ ∞ in (^{\underline{eq:(3.4)}} 1.18) since h is an element of S_{μ}.

If the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) admits a solution (h, J) with h bounded, then c is necessarily bounded, so that both c and h belong to U_{μ} (thus S_{μ}) for any initial distribution μ. It then follows from Lemma ^{\underline{l:Lemma 3.1}} 2 that J(μ) is obtained as a limit which does not depend on the initial distribution μ.

The uniqueness of solutions to the Poisson equation is now briefly studied in the class of “uniformly L_{1}–bounded” solutions, i.e., solutions in B_{μ} for some initial state distribution μ. If the state space contains a set I of isolated states which are not reachable from 𝕏\I and if μ(I) = 0, then clearly the chain never visits the states in I. To simplify the exposition we find it convenient to reformulate the problem on the reduced state space 𝕏 − I.

The next lemma is preparatory in nature and will greatly simplify the presentation: For (h_{1}, J_{1}) and (h_{2}, J_{2}) solution pairs to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10), we define

ΔJ := J_{1} − J_{2} and Δh(x) := h_{1}(x) − h_{2}(x), x ∈ 𝕏.  (1.19) eq:(3.5)

l:Lemma 3.2 Lemma 3 Let (h_{1}, J_{1}) and (h_{2}, J_{2}) be two solutions of the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If Δh belongs to I_{μ} for some probability measure μ on 𝕏, then the rvs {Δh(X_{t}) − t · ΔJ, t = 0, 1, … } form a (ℙ_{μ}, F_{t})–martingale sequence with

ΔJ = \frac{1}{s}(𝔼_{μ}[Δh(X_{t+s})] − 𝔼_{μ}[Δh(X_{t})]), t = 0, 1, …; s = 1, 2, … (1.20) eq:(3.6)

Proof. Denoting by \{M_{t}^{i}, t = 0, 1, … \} the rvs (^{\underline{eq:(2.8)}} 1.13) associated with the solution pair (h_{i}, J_{i}), i = 1, 2, we define the rvs {ΔM_{t}, t = 0, 1, … } by

ΔM_{t} := M_{t}^{1} − M_{t}^{2} = Δh(X_{t}) − t · ΔJ, t = 0, 1, …

It is plain that (Δh, ΔJ) is a solution to the homogeneous Poisson equation Δh + ΔJe = P Δh. Applying Lemma ^{\underline{l:Lemma 2.1}} 1 to this Poisson equation, we conclude that the rvs {ΔM_{t}, t = 0, 1, … } indeed form an integrable (ℙ_{μ}, F_{t})– martingale sequence, whence 𝔼_{μ}[ΔM_{t+s}] = 𝔼_{μ}[ΔM_{t}] for all s, t = 0, 1, . . .. In expanded form, these equalities become

𝔼_{μ}[Δh(X_{t+s})] − (t + s)ΔJ = 𝔼_{μ}[Δh(X_{t})] − tΔJ, t = 0, 1, …

and we obtain (^{\underline{eq:(3.6)}} 1.20) after simple rearrangements.

The basic uniqueness result can now be developed.

t:Theorem 3.3 Theorem 4 Let (h_{1}, J_{1}) and (h_{2}, J_{2}) be two solutions of the Poisson equa-

tion (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10).

1. If Δh belongs to S_{μ} for some probability measure μ on 𝕏, then J_{1} = J_{2};

2. If in addition Δh is an element of B_{μ}, then Δh is constant on each recurrent class of the Markov chain ℙ_{μ}.

Proof. If Δh belongs to S_{μ}, then its is also an element of I_{μ}, and Claim 1 follows by letting s ↑ ∞ in (^{\underline{eq:(3.6)}} 1.20) and using the fact that Δh belongs to S_{μ}.

The proof of Claim 2 starts with the observation (^{\underline{eq:(2.6)}} 1.11) made earlier that since Δh is an element of B_{μ}, it it is also an element of S_{μ}. Therefore, J_{1} = J_{2} by Claim 1 and the rvs {Δh(X_{t}), t = 0, 1, … } form a (ℙ_{μ}, F_{t})– martingale sequence with sup_{t} 𝔼_{μ}[|Δh(X_{t})|] < ∞. By a standard martingale convergence theorem ^{\underline{Chb,KT}} [7, 12], the martingale sequence \{Δh(X_{t}), t = 0, 1, … \} converges ℙ_{μ}–a.s. to a proper rv.

If all the states in 𝕏 form a single recurrent class under P, then any two states in 𝕏, say x and y, are visited infinitely often ℙ_{μ}–a.s. It is now plain that h(x) = h(y) by virtue of the ℙ_{μ}–a.s. convergence of the martingale {Δh(X_{t}), t = 0, 1, … }, and Δh is therefore constant on 𝕏.

More generally, let R be a recurrence class under P, i.e., a closed irreducible set of recurrent states. Since p_{xy} = 0 for all x in R and y not in R, (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) implies

h_{i,R} + Je_{R} = c_{R} + P_{R}h_{i,R}, i = 1, 2.  (1.21) eq:(3.9)

The matrix P_{R} can be interpreted as the matrix of one–step transition probabilities for an irreducible Markov chain on R with all its states recurrent, and the problem is now reduced to the previously considered case. Therefore, h_{1,R} − h_{2,R} is constant on R and the proof is complete.

When h_{1} and h_{2} belong to U_{μ}, the Ergodic Theorem can be used to derive this result along the lines of ^{\underline{GM}} [9, Proposition 1.1]. Under conditions weaker than the ones assumed in Theorem ^{\underline{t:Theorem 3.3}} 4 we can obtain the following refinement of Claim 1 of Theorem ^{\underline{t:Theorem 3.3}} 4.

c:Corollary 3.4 Corollary 5 Let (h_{1}, J_{1}) and (h_{2}, J_{2}) be two solutions to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If for some probability measure μ on 𝕏, h_{1} belongs to S_{μ} and h_{2} belongs to I_{μ}, then

lim_{t} \frac{1}{t}𝔼_{μ} [h_{2}(X_{t})] = J_{2} − J_{1} .  (1.22) eq:(3.10)

Proof. First we note that if h_{1} is an element of S_{μ} and if h_{2} belongs to I_{μ}, then Δh belongs to I_{μ}. By Lemma ^{\underline{l:Lemma 3.2}} 3 we get

ΔJ = \frac{1}{t} \{𝔼_{μ}[Δh(X_{t})] − 𝔼_{μ}[Δh(X_{0})]\} , t = 1, 2, …  (1.23) eq:(3.11)

and (^{\underline{eq:(3.10)}} 1.22) follows upon letting t ↑ ∞ in (^{\underline{eq:(3.11)}} 1.23) and using the fact that h_{1} is an element of S_{μ}. The existence of the limit is a consequence of the equalities

(^{\underline{eq:(3.11)}} 1.23)

It is very easy to demonstrate the non-uniqueness of solutions to the Poisson equation: Consider the Markov chain P ≡ (p_{xy}) on the non–negative integers ℕ with p_{x,x+1} = 1, x = 0, 1, …, and let c ≡ 0. Then (h_{2}, J_{2}) ≡ (0, 0) is obviously a solution to the Poisson equation with h_{1}(0) = 0. However, the pair (h_{2}, J_{2}) ≡ (x, 1) is also a solution to the Poisson equation with h_{2}(0) = 0. For all t = 0, 1, …, we have X_{t} = X_{0} + t ℙ_{μ}–a.s, whence 𝔼_{μ}[h_{2}(X_{t})] = 𝔼_{μ}[X_{0}] + t, and under the condition 𝔼_{μ}[X_{0}] < ∞, h_{2} is an element of I_{μ}, but not of S_{μ}. In fact, (^{\underline{eq:(3.10)}} 1.22) holds as lim_{t} \frac{1}{t}𝔼_{μ} [h_{2}(X_{t})] = 1 ≠ 0. In Section ^{\underline{sec:7}} 1.7 we discuss the non-uniqueness issue for a more elaborate example of a positive recurrent system.

Although in practice it might be hard to verify the L_{1}–boundedness conditions of Theorem ^{\underline{t:Theorem 3.3}} 4, a simple characterization of the set B_{μ} is available in a special yet important case. Recall that a probability measure γ on B(𝕏) is an invariant measure for the one–step transition matrix P if

γ(x) = ∑_{y}γ(y)p_{yx}, x ∈ 𝕏.  (1.24) eq:(3.12)

Under ℙ_{γ} the Markov chain {X_{t}, t = 0, 1, … } forms a strictly stationary sequence with one-dimensional marginal distribution γ, so that the following characterization is immediate.

l:Lemma 3.5 Lemma 6 If γ is an invariant probability measure for the one–step transition matrix P, then I_{γ} = B_{γ} = U_{γ} = L_{1} (𝕏, B(𝕏), γ).

In ^{\underline{DV}} [8] Derman and Veinott consider the uniqueness issue for Markov chains with a single positive recurrent class (in which case the invariant measure γ is unique). They show uniqueness in the class DV of mappings f : 𝕏 → ℝ such that

𝔼_{x} [∑_{t=0}^{T −1} |f(X_{t})|] < ∞, x ∈ 𝕏  (1.25) eq:(3.13)

where T := inf{t > 0 : X_{t} = z} for some distinguished recurrent state z. Under these assumptions, for every mapping f : 𝕏 → ℝ, we conclude by standard results on Markov chains ^{\underline{Cha}} [6] that

𝔼_{γ}[|f(X_{t})|] = \frac{𝔼_{z} [∑_{t=0}^{T −1} |f(X_{t})|]}{𝔼_{z}[T]}, t = 0, 1, …  (1.26) eq:(3.14)

and DV is seen to coincide with B_{γ}.

1.4 Decomposition results

sec:4

1.4.1 A state decomposition results

sec:4.1

With the uniqueness result of Theorem ^{\underline{t:Theorem 3.3}} 4 in mind, we consider the decomposition of the countable set 𝕏 induced by the recurrence structure of P: Let T r denote the (possibly empty) set of transient states, and let {R_{α}, α ∈ A}, for some countable index set A, denote the recurrent components. The sets {T r, R_{α}, α ∈ A} form a partition of 𝕏. Moreover, for all α in A, p_{xy} = 0 for x in R_{α} and y not in R_{α}, and the restriction P_{α} of P to the recurrent class R_{α} is irreducible and recurrent on it. With the vector notation of Section \underline{sec:2} 1.2, the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) can now be partitioned as

h_{R_{α}} + Je_{R_{α}} = c_{R_{α}} + P_{α}h_{Rα}, α ∈ A  (1.27) eq:(4.1a)

and

h_{T r} + Je_{T r} = c_{T r} + ∑_{α∈A}T_{α}h_{R_{α}} + P_{T r}h_{T r}  (1.28) eq:(4.1b)

where the matrices {T_{α}, α ∈ A} and P_{T r} are determined from the decomposition of P associated with the sets {T r, R_{α}, α ∈ A}.

The decomposition (^{\underline{eq:(4.1a)}} 1.27)–(^{\underline{eq:(4.1b)}} 1.28) of the Poisson equation motivates introducing the following family of Poisson equations

h_{α} + J_{α}e_{R_{α}} = c_{R_{α}} + P_{α}h_{α}, α ∈ A  (1.29) eq:(4.2a)

and

h̃ + J̃e_{T r} = c̃ + P_{T r}h̃  (1.30) eq:(4.2b)

where for each α in A, c_{R_{α}} and h_{α} are mappings R_{α} → ℝ, while c̃ and h̃ are mappings T r → ℝ, with

c̃ = c_{T r} + ∑_{α∈A}T_{α}h_{α}.  (1.31) eq:(4.3)

The next result shows in what sense the solutions to the projected Poisson equations (^{\underline{eq:(4.2a)}} 1.29)–(^{\underline{eq:(4.2b)}} 1.30) determine the solution to the original equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). The proof is a simple consequence of (^{\underline{eq:(4.1a)}} 1.27)–(^{\underline{eq:(4.1b)}} 1.28) and of (^{\underline{eq:(4.2a)}} 1.29)–(^{\underline{eq:(4.2b)}} 1.30), and is omitted in the interest of brevity.

t:Theorem 4.1 Theorem 7 The Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) has a solution if and only if the following two conditions hold:

1. For each α in A, the Poisson equation (^{\underline{eq:(4.2a)}} 1.29) on R_{α} has a solution (h_{α}, J_{α}) such that J_{α} = J for some scalar J independent of α and

∑_{α∈A}T_{α}|h_{α}| < ∞;  (1.32) eq:(4.4)

2. The Poisson equation (^{\underline{eq:(4.2b)}} 1.30), with forcing function c̃ given by (^{\underline{eq:(4.3)}} 1.31) has a solution (h̃, J̃) such that J̃ = J.

A solution pair to (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) is necessarily of the form (h, J) with h determined by h_{R_{α}} = h_{α} for all α in A and h_{T r} = h̃.

Condition (^{\underline{eq:(4.4)}} 1.32), which is automatically satisfied when 𝕏 is finite, guarantees that c̃ (and therefore (^{\underline{eq:(4.2b)}} 1.30)) is well defined.

1.4.2 A Green-like decomposition

sec:4.2

Let (h_{1}, J_{1}) and (h_{2}, J_{2}) be two solutions of the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)– (^{\underline{eq:(2.5b)}} 1.10) with forcing functions c_{1} and c_{2}, respectively. Then for any β in ℝ, (h, J) := (βh_{1} + h_{2}, βJ_{1} + J_{2}) is a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)– (^{\underline{eq:(2.5b)}} 1.10) with forcing function βc_{1} + c_{2}. Indeed, by definition, for all x in 𝕏, we have

h(x) + J = β(h_{1}(x) + J_{1}) + (h_{2}(x) + J_{2})
= β (c_{1}(x) + ∑_{y}p_{xy}h_{1}(y)) + (c_{2}(x) + ∑_{y}p_{xy}h_{2}(y))
= (βc_{1}(x) + c_{2}(x)) + ∑_{y}p_{xy}(βh_{1}(y) + h_{2}(y)),  (1.33) eq:(4.5)

where the last sum is well defined owing to the definition (^{\underline{eq:(2.5b)}} 1.10) of a solution.

This simple fact can be used as follows: For each v in 𝕏, define the function c_{v} : 𝕏 → ℝ by c_{v}(x) := δ(v; x) for all x in 𝕏, and let (h_{v}, J_{v}) denote a solution to the Poisson equation with forcing function c_{v}. The obvious decomposition

c(x) = ∑_{v}c(v)c_{v}(x), x ∈ 𝕏  (1.34) eq:(4.6)

then leads naturally to the formal representation

J = ∑_{v}c(v)J_{v} and h(x) = ∑_{v}c(v)h_{v}(x), x ∈ 𝕏.  (1.35) eq:(4.7)

It remains then to check that (^{\underline{eq:(4.7)}} 1.35) indeed defines a legitimate solution. In view of (^{\underline{eq:(4.5)}} 1.33), this is the case whenever c is constant except at a finite number of points. In the more general case, this check can be done through the constructive arguments of Corollary ^{\underline{c:Corollary 6.2}} 10, or through the verification result of Theorem ^{\underline{t:Theorem 6.4}} 12. Such a calculation is performed directly in Section ^{\underline{sec:7}} 1.7.

1.5 Finite state spaces

sec:5

A complete picture of the solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) is available when 𝕏 is a finite set, and can be found in ^{\underline{Be,Whittle}} [2, 35]. In the finite space case any solution necessarily belongs to U_{μ} for every initial probability distribution μ. Let P^{⋆} denote the stochastic matrix defined by

P^{⋆} := lim_{t} \frac{1}{t + 1} ∑_{s=0}^{t} P^{s};  (1.36) eq:(5.1)

its existence is guaranteed by classical results from the theory of Markov chains ^{\underline{Be,Whittle}} [2, 35]. The matrix I − P + P^{⋆} being invertible, the definition

h := (I − P + P^{⋆})^{−1}(I − P^{⋆})c  (1.37) eq:(5.2)

is well posed, and the easy identities P^{⋆}P = P P^{⋆} = P^{⋆}P^{⋆} = P^{⋆} lead after some simple algebra to the relation

h + P^{⋆}c = c + P h.  (1.38) eq:(5.3)

A simple comparison of (^{\underline{eq:(5.3)}} 1.38) with (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) suggests that h defined by (^{\underline{eq:(5.2)}} 1.37) will solve the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) whenever the vector P^{⋆}c is proportional to e, i.e., all the components of the vector P^{⋆}c are identical.

To investigate the matter further, we introduce the canonical decomposition of 𝕏 into the recurrent and transient components induced by P, as already done in Section ^{\underline{sec:4}} 1.4. Here, it can be assumed that P induces m recurrent classes, say R_{1}, …, R_{m}, as well as a (possibly empty) set T r of transient states, with the sets {R_{1}, …, R_{m}, T r} forming a partition of 𝕏. For any vector f, let f_{k} denote the restriction of f to R_{k}, k = 1, …, m.

Recall that p_{xy} = 0 for x in R_{k} and y not in R_{k}, and the restriction P_{k} of P to the recurrent class R_{k} is irreducible and positive recurrent on it. Possibly upon rearranging P into a block lower triangular form, we see that the restriction (P^{⋆})_{k} of P^{⋆} to R_{k} coincides with (P_{k})^{⋆} given by

(P_{k})^{⋆} := lim_{t} \frac{1}{t + 1} ∑_{s=0}^{t} P_{k}^{s}, k = 1, …, m  (1.39) eq:(5.4)

with all its rows being identical to the long-run probability distribution associated with the irreducible chain P_{k}. Consequently, (P^{⋆}c)_{k} = J_{k}e_{k} where the scalar J_{k} depends on the class R_{k}. Therefore (^{\underline{eq:(5.3)}} 1.38) can be decomposed as

h_{k} + J_{k}e_{k} = c_{k} + P_{k}h_{k}, k = 1, …, m  (1.40) eq:(5.5a)

and

h_{T r} + (P^{⋆}c)_{T r} = c_{T r} + ∑_{k=1}^{m} T_{k}h_{k} + T rh_{T r}  (1.41) eq:(5.5b)

where the matrices T_{1}, …, T_{m} and T r are chosen appropriately from the decomposition of P associated with the sets {R_{1}, …, R_{m}, T r}.

t:Theorem 5.1 Theorem 8 The pair (h, J) is a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)– (^{\underline{eq:(2.5b)}} 1.10) if and only if the conditions

J_{1} = … = J_{m} = J and (P^{⋆}c)_{T r} = Je_{T r}  (1.42) eq:(5.6)

hold, in which case h is given—uniquely up to an additive constant on each recurrent class—by (^{\underline{eq:(5.2)}} 1.37), and J is the constant appearing in (^{\underline{eq:(5.6)}} 1.42). The conditions (^{\underline{eq:(5.6)}} 1.42) always hold when the Markov chain P has a single recurrent class.

Proof. The first part is immediate from the discussion given earlier since P^{⋆}c = Je under (^{\underline{eq:(5.6)}} 1.42). The uniqueness follows from Theorem ^{\underline{t:Theorem 3.3}} 4 and from the fact that I − T r is invertible. To conclude the last part, it suffices to observe that under the assumption of a single recurrent class R_{1} for the Markov chain P, the rows of P^{⋆} are all identical and of the form (ν, 0_{T r}) where ν coincides with the long-run probability distribution vector associated with the irreducible chain P_{1}

1.6 A probabilistic formula for solutions

sec:6

Consider now the situation where the state space 𝕏 is countably infinite. The matrix P^{⋆} is still well defined, but in general the invertibility of I − P + P^{⋆} cannot be guaranteed anymore owing to the intricate nature of the recurrence structures for Markov chains over countably infinite state spaces. As a result, the algebraic discussion of Section ^{\underline{sec:5}} 1.5 cannot be carried through.

In some situations however, probabilistic arguments can be used to prove the existence of a solution pair to the Poisson equation. Such a situation arises when there exists a distinguished state in 𝕏, say z, which is positive recurrent in a sense made precise below. In this more restricted set-up, a possible approach would mimic the arguments of ^{\underline{Rossc}} [30, Section 6.7], and would yield the solution as the limit of the discounted cost associated with c, when the discount factor tends to 1. This line of arguments was developed in ^{\underline{SMPoi}} [32] and does yield a probabilistic representation of the solution already obtained by Derman and Veinott ^{\underline{DV}} [8] through algebraic means.

Here, we take a different route for deriving this probabilistic representation of solutions to the Poisson equation. We do so in several steps by exploiting the martingale property of Lemma ^{\underline{l:Lemma 2.1}} 1. To precisely state the conditions, we define the first passage time to the state z as the F_{t}–stopping time T given by

T := inf{t > 0 : X_{t} = z}.  (1.43) eq:(6.1)

The recurrence condition (R) enforced thereafter is the finite mean condition

(R) T (x) := 𝔼_{x} [T] < ∞, x ∈ 𝕏.  (1.44) eq:(6.2)t

The condition (R) is automatically satisfied when the set 𝕏 is finite and the Markov chain P admits a single (positive) recurrent class decomposition 𝕏 = R∪T r into a set R of positive recurrent states and a (possibly empty) set T r of transient states. However, when the set 𝕏 is not finite, the condition (R) is far more stringent. Indeed, not only does it imply the single class decomposition 𝕏 = R ∪ T r, but it also prohibits the chain from wandering too long or exclusively amongst the transient states. We relax the first restriction in Section ^{\underline{sec:8}} 1.8.

We also find it convenient to consider the following integrability condition (I), where

(I) C_{⋆}(x) := 𝔼_{x} [∑_{t=0}^{T −1} |c(X_{t})|] < ∞, x ∈ 𝕏.  (1.45) eq:(6.2)i

Under (I) the quantities

C(x) := 𝔼_{x} [∑_{t=0}^{T −1} c(X_{t})] , x ∈ 𝕏  (1.46) eq:(6.3)

are well defined. Under the recurrence condition (R), any bounded mapping c will satisfy the integrability condition (I); in fact the conditions (R) and (I) coincide for c(x) = 1 for all x in 𝕏.

The next result is a consequence of the martingale property given in

Lemma ^{\underline{l:Lemma 2.1}} 1.

t:Theorem 6.1 Theorem 9 Assume the recurrence condition (R) to hold and let (h, J) be a solution pair to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If h is an element of I_{x} for some x in 𝕏, then

lim_{n} {𝔼_{x} [1[n < T]h(X_{n})] + 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c(X_{t})]}
= JT (x) + h(x) − h(z). (1.47) eq:(6.4)

Proof. By Lemma ^{\underline{l:Lemma 2.1}} 1, the rvs \{M_{t}, t = 0, 1, … \} given by (^{\underline{eq:(2.8)}} 1.13) form a (ℙ_{x}, F_{t})–martingale. By Doob’s Optional Sampling Theorem ^{\underline{Chb,KT}} [7, 12], the stopped process {M_{T ∧n}, n = 0, 1, … } is also a (ℙ_{x}, F_{T ∧n})–martingale, so that

𝔼_{x}[M_{T ∧n}] = 𝔼_{x}[M_{0}] = h(x), n = 0, 1, …  (1.48) eq:(6.5)

By Lemma ^{\underline{l:Lemma 2.1}} 1 we see that c is an element of I_{x} because h belongs to I_{x}, and therefore, for all n = 0, 1, …, the three rvs h(X_{T ∧n}), T ∧n and ∑_{t=0}^{T ∧n−1} c(X_{t}) are integrable under ℙ_{x}. From the definition of M_{T ∧n} we conclude by direct inspection of (^{\underline{eq:(6.5)}} 1.48) that

h(x) = 𝔼_{x} [h(X_{T ∧n}) − (T ∧ n)J + ∑_{t=0}^{T ∧n−1} c(X_{t})]
= h(z)ℙ_{x}[T ≤ n] + 𝔼_{x} [1[T > n]h(X_{n})]
− J𝔼_{x}[T ∧ n] + 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c(X_{t})] .  (1.49) eq:(6.6)

Under (R), we have lim_{n} ℙ_{x}[T ≤ n] = 1, whereas lim_{n} 𝔼_{x}[T ∧ n] = T (x) by monotone convergence, and the result (^{\underline{eq:(6.4)}} 1.47) follows upon letting n ↑ ∞ in (^{\underline{eq:(6.6)}} 1.49).

As we impose additional conditions, we see the form of the probabilistic representation emerge from the relation (^{\underline{eq:(6.4)}} 1.47).

c:Corollary 6.2 Corollary 10 Assume the recurrence condition (R) to hold, and let (h, J) be a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If h belongs to U_{x} for some x in 𝕏, then the relation

h(x) = lim_{n} 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c(X_{t})] − JT (x) + h(z)  (1.50) eq:(6.7)

holds. If in addition, the integrability condition (I) holds, then

h(x) = C(x) − T (x)J + h(z).  (1.51) eq:(6.8)

Proof. Under (R), we have lim_{n} ℙ_{x}[T > n] = 0. The uniform integrability under ℙ_{x} of the rvs {h(X_{t}), t = 0, 1, … } yields lim_{n} 𝔼_{x} [1[T > n]h(X_{n})] = 0, so that (^{\underline{eq:(6.7)}} 1.50) follows from (^{\underline{eq:(6.4)}} 1.47). Under (I) we get

lim_{n} 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c(X_{t})] = 𝔼_{x} [∑_{t=0}^{T −1} c(X_{t})] = C(x)  (1.52) eq:(6.9)

by dominated convergence, and (^{\underline{eq:(6.8)}} 1.51) is an immediate consequence of (^{\underline{eq:(6.7)}} 1.50) and (^{\underline{eq:(6.9)}} 1.52).

By carefully inspecting this last proof, we can extract additional information on the interaction between the uniform integrability of solutions and the integrability condition (^{\underline{eq:(6.2)i}} 1.45): We define the positive and negative parts of the forcing function c by c_{±}(x) := max{0, ±c(x)} for all x in 𝕏, so that c(x) = c_{+}(x) − c_{−}(x) and |c(x)| = c_{+}(x) + c_{−}(x). In analogy with (^{\underline{eq:(6.3)}} 1.46), we introduce the quantities

C_{±}(x) := 𝔼_{x} [∑_{t=0}^{T −1} c_{±}(X_{t})] , x ∈ 𝕏  (1.53) eq:(6.10)

which are both well defined, although possibly infinite. The relation C(x) = C_{+}(x)−C_{−}(x) holds provided at least one of the quantities C_{+}(x) and C_{−}(x) is finite, while the equality C_{⋆}(x) = C_{+}(x) + C_{−}(x) is always valid.

c:Corollary 6.3 Corollary 11 Assume the recurrence condition (R) to hold, and let (h, J) be a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If h belongs to U_{x} for some x in 𝕏, then the relation

h(x) + C_{−}(x) = C_{+}(x) − JT (x) + h(z)  (1.54) eq:(6.11)

holds. If in addition, c is either bounded above or below, then C_{⋆}(x) is finite and the relation (^{\underline{eq:(6.8)}} 1.51) holds.

Proof. The fact that h is an element of U_{x} (thus of I_{x}) implies that c belongs to I_{x}, and membership of c_{±} in I_{x} follows. Therefore, for each n = 0, 1 …, the rvs ∑_{t=0}^{T ∧n−1} c_{±}(X_{t}) are integrable under ℙ_{x}. The relation (^{\underline{eq:(6.6)}} 1.49), derived in the proof of Theorem ^{\underline{t:Theorem 6.1}} 9, still holds and can be rewritten as

\begin{aligned}h(x) + 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c_{−}(X_{t})] & = h(z)ℙ_{x}[T ≤ n] + 𝔼_{x} [1[T > n]h(X_{n})] \\ & − J𝔼_{x}[T ∧ n] + 𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c_{+}(X_{t})] . \end{aligned} (1.55) eq:(6.12)

Under (R), we have lim_{n} ℙ_{x}[T ≤ n] = 1, and lim_{n} E_{x}[T ∧ n] = T (x) by monotone convergence. Moreover, the uniform integrability of the rvs {h(X_{t}), t = 0, 1, … } under ℙ_{x} implies lim_{n} 𝔼_{x} [1[T > n]h(X_{n})] = 0, and C_{±}(x) = lim_{n} 𝔼_{x} [∑_{t=0}^{T ∧n−1} c_{±}(X_{t})] by monotone convergence. The result (^{\underline{eq:(6.11)}} 1.54) follows from these facts upon letting n ↑ ∞ in (^{\underline{eq:(6.12)}} 1.55).

To establish the second statement, we note that c being either bounded above or below implies that at least one of the quantities C_{+}(x) and C_{−}(x) is finite, whence both are necessarily finite in view of the relation (^{\underline{eq:(6.11)}} 1.54).

Corollary ^{\underline{c:Corollary 6.2}} 10 states that under conditions (R) and (I), any “uniformly integrable” solution (h, J) of the Poisson equation is necessarily given by (^{\underline{eq:(6.8)}} 1.51) (up to an additive constant). In a sense, we can view (^{\underline{eq:(6.8)}} 1.51) as the “minimal” solution to (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). However, as we next show, (^{\underline{eq:(6.8)}} 1.51) does define a solution even when there may exist no uniformly integrable one.

t:Theorem 6.4 Theorem 12 Assume both the recurrence condition (R) and the integrability condition (I) to hold. Then the pair (h, J) given by

J = \frac{C(z)}{T (z)} and h(x) = C(x) − J · T (x), x ∈ 𝕏  (1.56) eq:(6.13)

is a solution to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) with h(z) = 0.

When the state space 𝕏 is finite and the chain has a single recurrent class, (^{\underline{eq:(6.13)}} 1.56) provides a probabilistic interpretation for the solution described through purely algebraic means in ^{\underline{Be,Whittle}} [2, 35].

Although condition (R) may seem quite restrictive, it is in some sense close to being necessary. Indeed, as shown by Cavazos–Cadena ^{\underline{CC}} [4, Cor. 2.1–2.2, p. 105] if the Poisson equation admits a bounded solution for every forcing function c which vanishes at infinity, then (i) P admits a single recurrent class, which is necessarily positive recurrent; and (ii) a condition stronger than (R) holds, namely sup_{x}T (x) < ∞.

Proof. The algebraic manipulations below are validated through the following summability conditions

∑_{y≠z}p_{xy}T (y) < ∞ and ∑_{y≠z}p_{xy}|C(y)| < ∞, x ∈ 𝕏.  (1.57) eq:(6.14)

In view of the comment following (^{\underline{eq:(6.3)}} 1.46), we only need to establish the second condition in (^{\underline{eq:(6.14)}} 1.57) as the first one reduces to it when c ≡ 1. By the Markov property, we get

C_{⋆}(x) = |c(x)| + ∑_{y≠z}p_{xy}C_{⋆}(y), x ∈ 𝕏  (1.58) eq:(6.15)

and the second summability condition in (^{\underline{eq:(6.14)}} 1.57) follows from the integrability condition (I) since |C(x)| ≤ C_{⋆}(x) for all x in 𝕏.

The arguments that lead to (^{\underline{eq:(6.15)}} 1.58) also show that

C(x) = c(x) + ∑_{y≠z}p_{xy}C(y), x ∈ 𝕏  (1.59) eq:(6.16)

and

T (x) = 1 + ∑_{y≠z}p_{xy}T (y), x ∈ 𝕏.  (1.60) eq:(6.17)

Fix x in 𝕏. For any scalar J, we use (^{\underline{eq:(6.16)}} 1.59)–(^{\underline{eq:(6.17)}} 1.60) to write

C(x) − J · T (x) = [c(x) + ∑_{y≠z}p_{xy}C(y)]
−J · [1 + ∑_{y≠z}p_{xy}T (y)] .  (1.61) eq:(6.18)

Now, with the choice J = C(z)/T (z), (^{\underline{eq:(6.18)}} 1.61) becomes

C(x) − J · T (x) + J = c(x) + ∑_{y≠z} p_{xy}[C(y) − J · T (y)]
= c(x) + ∑_{y}p_{xy} [C(y) − J · T (y)],

and (h, J) is indeed the postulated solution of the Poisson equation.

We conclude this section by showing in what sense uniform integrability comes close to being necessary to ensure uniqueness. This will follow from the next result which is a simple consequence of (^{\underline{eq:(6.4)}} 1.47) once we observe that

C(x) = lim_{n}𝔼_{x} [ ∑_{t=0}^{T ∧n−1} c(X_{t})]

whenever C_{⋆}(x) is finite.

c:Corollary 6.5 Corollary 13 Assume the recurrence condition (R) to hold and let (h, J) be a solution pair to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If h is an element of I_{x} for some x in 𝕏 and if C_{⋆}(x) is finite, then

lim_{n}𝔼_{x} [1[n < T]h(X_{n})] = h(x) − h(z) − [C(x) − JT (x)] .  (1.62) eq:(6.20)

We see from (^{\underline{eq:(6.20)}} 1.62) that this solution h in I_{x} coincides with that given by (^{\underline{eq:(6.13)}} 1.56) provided lim_{n} 𝔼_{x} [1[n < T]h(X_{n})] = 0, a condition reminiscent of uniform integrability (i.e., h in U_{x}) and indeed implied by it.

1.7 An example

sec:7

In this section we specialize the results obtained so far to a simple reflected random walk. The solution given by the probabilistic representation is computed explicitly, and shown to belong to B_{γ} (= U_{γ} where γ is the invariant distribution) whenever the forcing function c is an element of B_{γ}. In that case, we also identify a class of solutions which are not uniformly integrable; in fact, we calculate all solutions to the Poisson equation, thereby exhibiting non-uniqueness for a positive recurrent Markov chain. The calculations are carried out in Appendix ^{\underline{sec:A}} 1.12.1.

The situation considered here is that of a random walk on the non– negative integers with reflection, i.e., 𝕏 = ℕ and

p_{0,0} = p_{x+1,x} = 1 − p := q and p_{x,x+1} = p, x = 0, 1, …  (1.63) eq:(7.1)

for some 0 < p < 1. With a queueing–theoretic interpretation in mind, we define ρ := p/q, and note that this Markov chain is positive recurrent—and condition (R) holds—whenever ρ < 1 (or equivalently 0 < p < 1/2). In that case, making use of the defining relation (^{\underline{eq:(3.12)}} 1.24), we readily determine the invariant distribution γ to be

γ(x) = (1 − ρ) ρ^{x}, x = 0, 1, …  (1.64) eq:(7.2)

For any forcing function c, the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) takes the form

ph(0) + J = ph(1) + c(0)

and

h(x + 1) + J = qh(x) + ph(x + 2) + c(x + 1), x = 0, 1, …  (1.65) eq:(7.3)

Before addressing the existence of solutions to (^{\underline{eq:(7.3)}} 1.65), we show that such solutions are not unique. Indeed, if (h_{i}, J_{i}), i = 1, 2, are two solution pairs to (^{\underline{eq:(7.3)}} 1.65), then their difference (Δh, ΔJ) (in the notation (^{\underline{eq:(3.5)}} 1.19)) solves the homogeneous equation Δh + ΔJe = P Δh, which can be rewritten as

p [Δh(1) − Δh(0)] = ΔJ  (1.66) eq:(7.4a)

and

p [Δh(x + 2) − Δh(x + 1)] = ΔJ + q [Δh(x + 1) − Δh(x)]  (1.67) eq:(7.4b)

for all x = 0, 1, . . .. For any value of ΔJ it is a simple matter to show that all the solutions to (^{\underline{eq:(7.4a)}} 1.66)–(^{\underline{eq:(7.4b)}} 1.67) are given by

Δh(x) = Δh(0) + \frac{ΔJ}{p − q} [\frac{1 − ρ^{−x}}{1 − ρ} + x] , x ∈ 𝕏  (1.68) eq:(7.5)

and parameterized by the initial condition Δh(0). Therefore, if (h_{1}, J_{1}) is a solution to (^{\underline{eq:(7.3)}} 1.65), so is (h_{1} + Δh, J_{1} + ΔJ) for any choice of ΔJ (in ℝ) where Δh is given by (^{\underline{eq:(7.5)}} 1.68) with that value of ΔJ. In other words, even when all solutions to (^{\underline{eq:(7.3)}} 1.65) are required to have identical initial conditions— a normalizing condition which dictates Δh(0) = 0 in (^{\underline{eq:(7.5)}} 1.68)—we conclude that the solution set to (^{\underline{eq:(7.3)}} 1.65) must necessarily be non-countable provided it is not empty. This non-uniqueness is independent of the choice of c, and holds also when ρ ≥ 1, i.e., the chain is null recurrent or transient.

When 0 < ρ < 1, we observe that Δh given by (^{\underline{eq:(7.5)}} 1.68) can never belong to U_{γ} unless ΔJ = 0, thereby confirming the uniqueness of solutions in U_{γ}, a result that derives from Theorem ^{\underline{t:Theorem 3.3}} 4 (and independently from Corollary \underline{c:Corollary 6.2} 10). It now remains to determine conditions under which the solution in U_{γ} exists.

With the representation (^{\underline{eq:(6.13)}} 1.56) in mind, we take z = 0 and use (^{\underline{eq:(6.17)}} 1.60) to obtain

T (x) = \frac{qδ(0, x) + x}{q − p}, x = 0, 1, …  (1.69) eq:(7.6)

calculations are outlined in Appendix ^{\underline{sec:A}} 1.12.1.

Next, intent on using the Green decomposition technique of Section ^{\underline{sec:4.2}} 1.4.2, we compute for each v in 𝕏 the cost per cycle function C_{v} associated with the cost c_{v} : 𝕏 → ℝ : x → δ(v, x). Since J_{v} = γ(v), we invoke (^{\underline{eq:(3.14)}} 1.26) to get

C_{v}(0) = J_{v}T (0) = γ(v)\frac{1}{1 − ρ} = ρ^{v}.  (1.70) eq:(7.7)

In Appendix ^{\underline{sec:A}} 1.12.1 we also show that

v = 0, 1 C_{v}(x) = v/q, x = 1, 2, …  (1.71) eq:(7.8)
v = 2 C_{v}(1) = ρ^{2}/p, C_{v}(x) = 1/q^{2}, x = 2, 3, …  (1.72) eq:(7.9)
v = 3, 4, … C_{v}(x) = ρ^{v}/p^{x}, x = 1, 2, v − 1  (1.73) eq:(7.10a)
v = 3, 4, … C_{v}(x) = \frac{1}{p} ∑_{j=0}^{x∧v−1} ρ^{v−j}, x = 3, 4, … (1.74) eq:(7.10b)

Substituting (^{\underline{eq:(7.6)}} 1.69)–(^{\underline{eq:(7.10b)}} 1.74) into (^{\underline{eq:(6.13)}} 1.56), we obtain the solution h_{v} to the Poisson equation with forcing function c_{v} in the form

h_{v}(x) = C_{v}(x) − J_{v}T (x) = C_{v}(x) − \frac{x}{q}ρ^{v}, x = 1, 2, …  (1.75) eq:(7.11)

with h_{v}(0) = 0 by virtue of (^{\underline{eq:(7.7)}} 1.70). Inspection of (^{\underline{eq:(7.7)}} 1.70)–(^{\underline{eq:(7.10b)}} 1.74) reveals that C_{v}(x) is bounded in x, and the solution h_{v} thus grows linearly is x. Therefore, invoking Lemma ^{\underline{l:Lemma 3.5}} 6 (in conjunction with (^{\underline{eq:(7.2)}} 1.64)), we see that h_{v} is an element of U_{γ} and is therefore the unique solution in that class.

Using the Green decomposition technique of Section ^{\underline{sec:4.2}} 1.4.2, we can identify a large class of forcing functions for which (^{\underline{eq:(7.3)}} 1.65) will have a unique solution in U_{γ}; details of the derivation are available in Appendix ^{\underline{sec:A}} 1.12.1.

t:Theorem 7.1 Theorem 14 Consider the random walk with reflection at the origin defined through (^{\underline{eq:(7.1)}} 1.63) with 0 < ρ < 1. Let c be a forcing function 𝕏 → ℝ such that |c(x)| ≤ K(1 + r^{x}) for all x in 𝕏, for some positive constants r and K. If rρ < 1, then the decomposition (^{\underline{eq:(4.7)}} 1.35) (where (h_{v}, J_{v}) is given by (^{\underline{eq:(7.11)}} 1.75) for all v in 𝕏) provides a solution (h, J) to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10), and this solution is (unique) in U_{γ}.

1.8 Bounds and extensions

sec:8

In this section, we explore some of the advantages afforded by the probabilistic representation (^{\underline{eq:(6.13)}} 1.56). We use it to develop various bounds on the solution to the Poisson equation and to obtain an existence result for unbounded costs under a multichain structure.

1.8.1 Bounds

sec:8.1

The following growth estimate is an easy consequence of the probabilistic representation (^{\underline{eq:(6.13)}} 1.56).

t:Theorem 8.1 Theorem 15 Assume the recurrence condition (R) to hold. If c is bounded, i.e., A := sup_{x} |c(x)| < ∞, then the solution pair (h, J) given by (^{\underline{eq:(6.13)}} 1.56) satisfies the growth estimate

|h(x)| ≤ (A + J)T (x), x ∈ 𝕏.  (1.76) eq:(8.1)

In general Theorem ^{\underline{t:Theorem 8.1}} 15 does not hold when c is not bounded. However, in many situations of interest, the underlying Markov chain is “skip-free to the left” with respect to z. For example, in discrete–time queueing systems it is often the case that the decrease per unit time in the total number of customers is bounded above by the maximal number of available servers, say K. As a result, with z representing the empty state, we obtain the relation |X_{t}| ≤ KT, 0 ≤ t ≤ T, where |X_{t}| denotes the total number of customers at time t, and T is here the time until the system empties. With this in mind, we introduce the following condition: There exists a positive constant K such that

ℙ_{x}[d(z, X_{t}) ≤ KT, 0 ≤ t ≤ T] = 1, x ∈ 𝕏  (1.77) eq:(8.2)

for some metric d on 𝕏. Under such a condition, the representation (^{\underline{eq:(6.13)}} 1.56) implies the following bound.

t:Theorem 8.2 Theorem 16 Assume both the recurrence condition (R) and the integrability condition (I) to hold. If the Markov chain satisfies (^{\underline{eq:(8.2)}} 1.77), and if c exhibits the growth condition

|c(x)| ≤ A (1 + d(z, x)^{δ}), x ∈ 𝕏  (1.78) eq:(8.3)

for positive constants A and δ, then the solution h given by (^{\underline{eq:(6.13)}} 1.56) satisfies the growth estimate

|h(x)| ≤ B (T (x) + 𝔼_{x} [T^{δ+1}]) , x ∈ 𝕏  (1.79) eq:(8.4)

where

B = max{A + J, AK^{δ}}.

In other words, the growth rate of h is determined by the growth rate of moments of T. In particular, Theorem ^{\underline{t:Theorem 8.2}} 16 shows how moments of recurrence times can be used to check that the solution (^{\underline{eq:(6.13)}} 1.56) indeed belongs to B_{μ} or U_{μ} for some μ. Such information is of interest when studying the a.s. convergence of stochastic approximations schemes driven by Markov chains

\underline{BMP,MSsiam,MPb} [1, 20, 23].

Proof. Note that (^{\underline{eq:(8.4)}} 1.79) is automatically satisfied for x = z since then h(z) = 0. Now, fixing x ≠ z in 𝕏, we observe from the definition of C(x) that

|C(x)| ≤ 𝔼_{x} [∑_{t=0}^{T −1} |c(X_{t})|]

≤ A𝔼_{x} [∑_{t=0}^{T −1} (1 + d(z, X_{t})^{δ})]

≤ A (T (x) + 𝔼_{x} [∑_{t=0}^{T −1}(KT)^{δ}])

= A (T (x) + K^{δ}𝔼_{x} [T^{δ+1}])  (1.80) eq:(8.5)

where the second and the third inequalities were obtained by making use of (^{\underline{eq:(8.3)}} 1.78) and (^{\underline{eq:(8.2)}} 1.77), respectively. The form of (^{\underline{eq:(6.13)}} 1.56) now yields (^{\underline{eq:(8.4)}} 1.79).

Bounds were also developed by Glynn and Meyn ^{\underline{GM}} [9] in terms of Lyapunov functions. In ^{\underline{Meyn}} [24] Meyn provides quadratic estimates for the solutions to the the Poisson equation associated with a queueing network, when the forcing function is linear. Assuming the existence of Lyapunov functions, he obtains properties of solutions for general state spaces. In particular, if the forcing function is large outside a small set, then the solution can be bounded below as follows.

Theorem 17 Assume both the recurrence condition (R) and the integrability condition (I) to hold, and let (h, J) be a solution pair to the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10). If the forcing function c is bounded below, and has the property that for some ε in (0, 1), the set S given by

S := {x ∈ 𝕏 : (1 − ε)c(x) < J}  (1.81) e:lowerBd

is finite, then h is bounded below.

If c is “norm–like” in the sense that the set {x ∈ 𝕏 : c(x) ≤ M} is finite for each M, then S in (^{\underline{e:lowerBd}} 1.81) is finite. However, our condition is much weaker.

Proof. We first consider the case when c is non–negative. With S and ε as above, we see that J − c(x) ≤ −εc(x) for x not in S, whence

J − c(x) ≤ J1[x ∈ S] − εc(x), x ∈ 𝕏  (1.82)

by the non–negativity of c. The fact that (h, J) is a solution pair yields

∑_{y}p_{xy}h(y) = h(x) + J − c(x)
≤ h(x) + J1[x ∈ S] − εc(x), x ∈ 𝕏.  (1.83)

Consequently, fix x in 𝕏 and proceed as in the proof of Lemma ^{\underline{l:Lemma 2.1}} 1: The fact that h is in U_{x} implies membership of c in U_{x}. Hence, the rvs {M_{t}, t = 0, 1, … } defined by M_{0} := h(X_{0}) and

M_{t+1} := h(X_{t+1}) + ∑_{s=0}^{t} (εc(X_{s}) − J1[X_{s} ∈ S]) , t = 0, 1, …

are integrable under ℙ_{x} and form a (ℙ_{x}, F_{t})–supermartingale sequence. Applying Doob’s Optional Sampling Theorem ^{\underline{Chb,KT}} [7, 12], we conclude that the rvs {M_{T ∧n}, n = 0, 1, … } form a (ℙ_{x}, F_{t})–supermartingale sequence, whence h(x) = 𝔼_{x}[M_{0}] ≥ 𝔼_{x}[M_{T ∧n}] for all n = 0, 1, . . .. Letting n go to infinity in this last relation, we readily conclude that

h(x) ≥ h(z) + ε𝔼_{x} [∑_{s=0}^{T −1} c(X_{s})] − J𝔼_{x} [∑_{s=0}^{T −1} 1[X_{s} ∈ S]]

≥ h(z) − J𝔼_{x} [∑_{s=0}^{T −1} 1[X_{s} ∈ S]]  (1.84)

upon using the non–negativity of c, the integrability conditions (I) and (R), and the fact that h belongs to U_{x}. By the finiteness of S, we get

h(x) ≥ h(z) − J sup_{y∈S} T (y), x ∈ S.  (1.85) e:lowerBd2

On the other hand, for x not in S, we consider the first hitting time σ of S, i.e., σ := inf{t = 1, 2, …: X_{t} ∈ S} (with the usual convention). The definition of σ and the strong Markov property readily yield

𝔼_{x} [∑_{s=0}^{T −1} 1[X_{s} ∈ S]] ≤ 𝔼_{x}[T (X_{σ})], x ∉ S  (1.86)

by standard arguments. Consequently, (^{\underline{e:lowerBd2}} 1.85) holds throughout 𝕏, i.e.,

h(x) ≥ h(z) − J sup_{y∈S} T (y), x ∈ 𝕏

and h is bounded below as claimed.

In general, we note that if c is bounded below and satisfies (^{\underline{e:lowerBd}} 1.81), then so does the function x → c(x) − inf_{y} c(y) (with the same ε but with appropriately modified J), and the result follows from the first part of the proof.

1.8.2 Multiple classes

sec:8.2.

When the state space contains several positive recurrent classes, it is convenient to use a decomposition of the state space 𝕏 into its transient and recurrent components {T r, R_{α}, α ∈ A}, and to partition the Poisson equation accordingly. The treatment is similar to the one sketched briefly in

\underline{Whittle} [35].

With the decomposition and notation of Section ^{\underline{sec:4}} 1.4, the results of the previous section extend to the multiple class case. For every α in A, select a state z_{α} in R_{α} and write Z := {z_{α}, α ∈ A}. We define the first passage times to the states z_{α}, α in A, and to the set Z := {z_{α}, α ∈ A} by

T_{α} := inf{t > 0 : X_{t} = z_{α}}, α ∈ A  (1.87) eq:(8.6)

and

T := inf{t > 0 : X_{t} ∈ Z}.  (1.88) eq:(8.7)

Since each recurrent class is closed under P, at most one of the rvs {T_{α}, α ∈ A} is finite ℙ_{x}–a.s. for each x in X, so that

T = ∑_{α}T_{α}1[T_{α} < ∞] on [T < ∞] ℙ_{x} − a.s.  (1.89) eq:(8.8)

under the convention 0 · ∞ = 0. For future use, we also define

T_{α}(x) := 𝔼_{x}[T_{α}1[T_{α} < ∞]], α ∈ A, x ∈ 𝕏.  (1.90) eq:(8.9)

The appropriate version of condition (R) for the multiple class case is the finite mean condition

(Rm) T (x) := 𝔼_{x}[T] < ∞, x ∈ 𝕏.  (1.91) eq:(Rm)

Note that (Rm) is essentially (R) but with the first passage time T defined through (^{\underline{eq:(8.8)}} 1.89) rather than by (^{\underline{eq:(6.1)}} 1.43). Under (Rm), it is plain that for each x in 𝕏, we have T < ∞ ℙ_{x}–a.s. and that for each α in A, T_{α}(x) = 𝔼_{x}[T_{α}] < ∞ whenever x lies in R_{α} with the implication that all recurrent states are positive recurrent. Condition (Rm) also implies that starting at any state x in 𝕏, the process eventually reaches the recurrent classes and does so in finite expected time.

We now impose conditions (Rm) and (I) (with T defined through (^{\underline{eq:(8.8)}} 1.89)). For every α in A, the following expressions

C_{α}(x) = 𝔼_{x} [ ∑_{t=0}^{T_{α}−1} c(X_{t})] , x ∈ R_{α} and J_{α} := \frac{C_{α}(z_{α})}{T_{α}(z_{α})}  (1.92) eq:(8.10)

are then well defined.

t:Theorem 8.3 Theorem 18 Assume the recurrence condition (Rm) and the integrability conditions (I) to hold. If there exists a scalar J such that J_{α} = J for all α in A, then the pair (h, J) with h : 𝕏 → ℝ given by

h(x) = C(x) − J · T (x), x in 𝕏  (1.93) eq:(8.12)

is a solution to the Poisson equation with the property that h(z) = 0 for every z in Z.

Proof. The proof proceeds in two steps.

Step 1: First assume the set T r of transient states to be empty. In that case the result follows readily from Theorem ^{\underline{t:Theorem 6.4}} 12 if it can be shown that for each α in A, the pair (h_{R_{α}}, J_{α}) is indeed a solution pair to the projected Poisson equation (^{\underline{eq:(4.1a)}} 1.27) on R_{α}. That this is indeed the case can be seen as follows. The recurrence condition (Rm) implies that the restriction of the Markov chain P to the recurrence class R_{α} satisfies the condition (R) imposed in the single recurrent case. Therefore, by Theorem ^{\underline{t:Theorem 6.4}} 12 the projected Poisson equation (^{\underline{eq:(4.1a)}} 1.27) on R_{α} admits as solution the pair (h_{α}, J_{α}) given by

h_{α}(x) = C_{α}(x) − J_{α} · T_{α}(x), x ∈ R_{α}  (1.94) eq:(8.13)

with J_{α} given by (^{\underline{eq:(8.10)}} 1.92). However, under (Rm) note that for x in R_{α}, T = T_{α} < ∞ ℙ_{x}–a.s., whence T (x) = T_{α}(x) and C(x) = C_{α}(x). As a result, we find that

J = J_{α} = \frac{C_{α}(z_{α})}{T_{α}(z_{α})} = \frac{C(z_{α})}{T (z_{α})},

so that h(x) = h_{α}(x) for all x in R_{α}.

Step 2: When T r is not empty, the difficulty in obtaining a solution to the Poisson equation is related to the existence of transient states from which more than one recurrent class can be reached. First observe however that now (^{\underline{eq:(6.13)}} 1.56)–(^{\underline{eq:(6.14)}} 1.57) have to be replaced by

T (x) = 1 + ∑_{y∉Z}p_{xy}T (y), x ∈ 𝕏  (1.95) eq:(8.15)

and

C(x) = c(x) + ∑_{y∉Z}p_{xy}C(y), x ∈ 𝕏.  (1.96) eq:(8.16)

Therefore, in the same way that (^{\underline{eq:(6.13)}} 1.56)–(^{\underline{eq:(6.14)}} 1.57) lead to (^{\underline{eq:(6.16)}} 1.59), it is easy to see that (^{\underline{eq:(8.15)}} 1.95)–(^{\underline{eq:(8.16)}} 1.96) imply

[C(x) − J · T (x)] + J = c(x) + ∑_{y∉Z}p_{xy}[C(y) − JT (y)]
= c(x) + ∑_{y}p_{xy}[C(y) − J · T (y)]  (1.97) eq:(8.17)

for each x in 𝕏, where the last step follows from the fact that C(z) = J ·T (z) for every z in Z as was noted in the first part of the proof. This time algebraic manipulations are validated through the summability conditions

∑_{y∉Z}p_{xy}T (y) < ∞ and ∑_{y∉Z}p_{xy}|C(y)| < ∞, x ∈ 𝕏  (1.98) eq:(8.18)

which follow from (^{\underline{eq:(8.15)}} 1.95)–(^{\underline{eq:(8.16)}} 1.96) and the integrability condition (I).

In this case (^{\underline{eq:(4.2b)}} 1.30) also has a solution, as can easily be seen by using (^{\underline{eq:(4.2a)}} 1.29) and the fact that for all x in 𝕏 and y in R_{α}, the n–step transition probabilities p_{xy}^{(n)} each converge to ℙ_{x}[T_{α} < ∞] · ν_{y}^{(α)} where ν^{(α)} is the invariant distribution of the Markov chain P when restricted to R_{α}.

1.9 Parametric dependence: Continuity

sec:9

In several applications, including stochastic adaptive control and stochastic approximations ^{\underline{BMP,BG,MMS,MSsiam,MPa,MPb}} [1, 3, 16, 20, 22, 23], the analysis simultaneously deals with a parameterized family of Markov chains, rather than with a single Markov chain, and crucial to the arguments is the smoothness (in the parameter) of solutions to the associated Poisson equations. Of particular interest are conditions on the model data which guarantee that the solution to the Poisson equation is continuous, or even Lipschitz continuous in the parameter. In this and the next sections we show how the representation results of Sections \underline{sec:6} 1.6 and ^{\underline{sec:8}} 1.8 provide a natural vehicle to explore this question. Our intent is not to get the best possible results, but rather to suggest ways of attacking these parametric issues.

In order to simplify the notation, the discussion in Sections ^{\underline{sec:9}} 1.9 and ^{\underline{sec:10}} 1.10 is given in the following framework: Only the case of a scalar parameter set is discussed as similar arguments can be developed mutatis mutandis for more general situations. Let the parameter set Θ be an open subset of ℝ, and consider a family {P (θ), θ ∈ Θ} of one–step transition probability matrices on the countable set 𝕏, with P (θ) ≡ (p_{xy}(θ)). For each θ in Θ and x in 𝕏, let ℙ_{x}^{θ} and 𝔼_{x}^{θ} denote the probability measure and corresponding expectation operator induced on (Ω, F) by P (θ) given that X_{0} = x.

For every θ in Θ, a given mapping c(θ) : 𝕏 → ℝ : x → c(θ, x) drives the Poisson equation (^{\underline{eq:(2.5a)}} 1.9)–(^{\underline{eq:(2.5b)}} 1.10) associated with P (θ), i.e.,

h + J = c(θ)e + P (θ)h.  (1.99) eq:(9.2)

As was the case in Section ^{\underline{sec:6}} 1.6, we assume the existence of a distinguished state z in 𝕏, independent of θ, with respect to which the integrability conditions (R) and (I) both hold for the Markov chain induced by P (θ) for all θ in Θ. Hence, with the F_{t}–stopping time T still given by (^{\underline{eq:(6.1)}} 1.43), we assume the appropriate versions of (^{\underline{eq:(6.2)t}} 1.44) and (^{\underline{eq:(6.2)i}} 1.45) to hold for each θ in Θ, and set

T (θ, x) := 𝔼_{x}^{θ}[T], x ∈ 𝕏  (1.100) eq:(9.3T)

and

C(θ, x) := 𝔼_{x}^{θ} [∑_{t=0}^{T −1} c(X_{t})] , x ∈ 𝕏.  (1.101) eq:(9.3)

Under the enforced assumptions, we may invoke Theorem ^{\underline{t:Theorem 6.4}} 12 to conclude that (^{\underline{eq:(9.2)}} 1.99) admits at least one solution (h(θ), J(θ)) where J(θ) is a scalar and h(θ) is a mapping 𝕏 → ℝ : x → h(θ, x). With the requirement h(θ, z) = 0, this solution (h(θ), J(θ)) has the representation

J(θ) = \frac{C(θ, z)}{T (θ, z)} and h(θ, x) = C(θ, x) − J(θ) · T (θ, x), x ∈ 𝕏. (1.102)

The next result identifies a set of natural conditions for establishing continuity of solutions to (^{\underline{eq:(9.2)}} 1.99). Such a regularity property was required, for example, in ^{\underline{BG}} [3].

t:Theorem 9.1 Theorem 19 Under the foregoing conditions, suppose that for each x in 𝕏,

(i) the mapping θ → c(θ, x) is continuous on Θ;

(ii) the mapping θ → p_{xy}(θ) is continuous over Θ for all y in 𝕏;

(iii) the family of probability measures {p_{x·}(θ), θ ∈ Θ} on 𝕏 is tight;

(iv) the rvs {(T, ℙ_{x}^{θ}), θ ∈ Θ} are uniformly integrable; and

(v) the rvs {(∑_{t=0}^{T −1} |c(θ, X_{t})|, ℙ_{x}^{θ}), θ ∈ Θ} are uniformly integrable.

Then for every x in 𝕏, the mappings θ → T (θ, x) and θ → C(θ, x) are continuous over Θ.

In many applications, c(θ, x) = c(x) for all x in 𝕏 and θ in Θ so that (i) automatically holds, while (iii) is satisfied whenever one–step transitions have some uniform (in θ) nearest-neighbor properties. The conditions (iv)– (v) are usually checked by (stochastically) bounding the original system uniformly in θ by means of another system which is naturally suggested by the original system. This approach was taken by Rosberg and Makowski in \underline{RM} [29].

The next two lemmas are needed in the proof of Theorem ^{\underline{t:Theorem 9.1}} 19; their proof is elementary and is omitted in the interest of brevity. l:Lemma 9.2 Lemma 20 Assume (ii)–(iii) of Theorem ^{\underline{t:Theorem 9.1}} 19. For all x and y in 𝕏, and

k = 1, 2, …, the mappings θ → ℙ_{x}^{θ}[T = k] and θ → ℙ_{x}^{θ}[X_{t} = y, T = k], 1 ≤ t < k, are all continuous on Θ.

l:Lemma 9.3 Lemma 21 Assume (iii) of Theorem ^{\underline{t:Theorem 9.1}} 19. For each t = 1, 2, … and x in 𝕏, the family of distributions {(X_{t}, P_{x}^{θ}), θ ∈ Θ} is tight.

To prepare the proof of Theorem ^{\underline{t:Theorem 9.1}} 19, we set

C_{m}(θ, x) := 𝔼_{x}^{θ} [1[T ≤ m] ∑_{t=0}^{T ∧m−1} c(θ, X_{t})] , x ∈ 𝕏, m = 1, 2, … (1.103) eq:(9.6)

A proof of Theorem ^{\underline{t:Theorem 9.1}} 19. Let x be a fixed element in 𝕏. By a standard decomposition argument, there is no loss of generality in assuming c(θ, x) ≥ 0 for all x in 𝕏 and θ in Θ. Moreover the first claim follows from the second one upon using c(θ, x) ≡ 1.

In the general case, standard facts from analysis ^{\underline{Rud}} [31] imply the desired continuity result if it can be established that the mappings θ → C_{m}(θ, x), m = 1, 2, …, are continuous on Θ, and then that the convergence lim_{m}C_{m}(θ, x) = C(θ, x) is uniform in θ.

To establish the first step, it suffices to show that the mappings θ → 𝔼_{x}^{θ} [1[T = k]c(θ, X_{t})], 0 ≤ t < k, are continuous for (^{\underline{eq:(9.6)}} 1.103) can be written as

C_{m}(θ, x) = ∑_{k=1}^{m} ∑_{t=0}^{k−1} 𝔼_{x}^{θ} [1[T = k]c(θ, X_{t})] , m = 1, 2, …  (1.104) eq:(9.7)

Fix 0 ≤ t < k. Because the rvs \{(X_{t}, ℙ_{x}^{θ}), θ ∈ Θ\} are tight by Lemma ^{\underline{l:Lemma 9.3}} 21, for every δ > 0 there exists a finite subset G_{x}(δ) of 𝕏 such that sup_{θ∈Θ} ℙ_{x}^{θ}[X_{t} ∉ G_{x}(δ)] < δ. The easy bound

𝔼_{x}^{θ} [1[T = k]1[X_{t} ∉ G_{x}(δ)]c(θ, X_{t})] ≤ 𝔼_{x}^{θ} [1[X_{t} ∉ G_{x}(δ)] ∑_{s=0}^{T −1} c(θ, X_{s})]

and the uniform integrability condition (v) together imply that for every ε > 0 there exists some δ(ε) > 0 such that

sup_{θ} 𝔼_{x}^{θ} [1[T = k]1[X_{t} ∉ G_{x}(δ(ε))]c(θ, X_{t})] ≤ ε.  (1.105) eq:(9.9)

On the other hand, the mapping θ → 𝔼_{x}^{θ} [1[T = k]1[X_{t} ∈ G_{x}(δ(ε))]c(θ, X_{t})] is continuous by virtue of Lemma ^{\underline{l:Lemma 9.2}} 20 since G_{x}(δ(ε)) is finite. The desired continuity of the mapping θ → 𝔼_{x}^{θ}[1[T = k]c(θ, X_{t})] readily follows from this remark and from (^{\underline{eq:(9.9)}} 1.105) by using a standard decomposition argument. Details are left to the interested reader.

For the second step, start with the estimate

0 ≤ C(θ, x) − C_{m}(θ, x) = 𝔼_{x}^{θ} [1[m < T] ∑_{t=0}^{T −1} c(θ, X_{t})] , m = 1, 2, …

and observe that the uniform integrability of the rvs {(T, ℙ_{x}^{θ}), θ ∈ Θ} yields lim_{m}sup_{θ}ℙ_{x}^{θ}[T > m] = 0. This fact and the uniform integrability condition (v) immediately imply the uniform convergence

lim_{m} sup_{θ} 𝔼_{x}^{θ} [1[m < T] ∑_{t=0}^{T −1} c(θ, X_{t})] = 0,  (1.106) eq:(9.11)

and the proof is now complete

1.10 Parametric dependence: Lipschitz continuity

sec:10

Metivier and Priouret ^{\underline{MPb}} [23] have shown that the a.s. convergence of stochastic approximations passes through the Lipschitz continuity of the solutions (h(θ), J(θ)) to the parameterized Poisson equation (^{\underline{eq:(9.2)}} 1.99). Arguments for establishing this Lipschitz continuity are now outlined in a somewhat restricted set-up which nevertheless often occurs in applications ^{\underline{MMS,MSsiam}} [16, 20]. To that end, we postulate that for all x in 𝕏, the probability measures {p_{x·}(θ), θ ∈ Θ} on 𝕏 are mutually absolutely continuous, i.e., if p_{xy}(θ) = 0 for some y in 𝕏 and θ in Θ, then p_{xy}(θ′) = 0 for all θ′ in Θ. As a result, for each m = 1, 2, …, the probability measures {ℙ_{x}^{θ}, θ ∈ Θ} are mutually absolutely continuous on the σ–field F_{m}. If L_{m}^{x}(θ, θ′) denotes the Radon–Nikodym derivative of ℙ_{x}^{θ′} with respect to ℙ_{x}^{θ} (on F_{m}), then

L_{m}^{x}(θ, θ′) = ∏_{i=0}^{m−1} \frac{p_{X_{i}X_{i+1}}(θ′)}{p_{X_{i}X_{i+1}}(θ)}, m = 1, 2, …  (1.107) eq:(10.1)

where the convention \frac{0}{0} = 0 is adopted. With L_{0}^{x}(θ, θ′) ≡ 1, the rvs {L_{m}^{x}(θ, θ′), m = 0, 1, … } form a (ℙ_{x}^{θ}, F_{m})–martingale, and for any non– negative F_{T ∧m}–measurable rv X,

𝔼_{x}^{θ′} [X] = 𝔼_{x}^{θ} [L_{T ∧m}^{x}(θ, θ′) · X] , m = 1, 2, …  (1.108) eq:(10.2)

by standard results on absolutely continuous changes of measures ^{\underline{Chb}} [7]. t:Theorem 10.1 Theorem 22 Under the foregoing conditions, suppose there exist a constant

K > 0 and a mapping 𝕏 → (0, ∞) : x → K(x) such that for all θ and θ′ in Θ,

|p_{xy}(θ) − p_{xy}(θ′)| ≤ Kp_{xy}(θ) · |θ − θ′|, x, y ∈ 𝕏  (1.109) eq:(10.3)

and

|c(θ, x) − c(θ′, x)| ≤ K(x) · |θ − θ′|, x ∈ 𝕏.  (1.110) eq:(10.4)

If the moment conditions

K̃(x) := sup_{θ} 𝔼_{x}^{θ} [∑_{t=0}^{T −1} K(X_{t})] < ∞, x ∈ 𝕏  (1.111) eq:(10.5)

and

C̃(x) := sup_{θ} 𝔼_{x}^{θ} [T (1 + δ)^{T} ∑_{t=0}^{T −1} |c(θ, X_{t})|] < ∞, x ∈ 𝕏 (1.112) eq:(10.6)

are satisfied for some 0 < δ ≤ 1, then for every x in 𝕏, the mappings θ → C(θ, x) are locally Lipschitz continuous over Θ. In fact, whenever |θ − θ′| ≤ \frac{δ}{K}, the Lipschitz estimates

|C(θ, x) − C(θ′, x)| ≤ L(x)|θ − θ′|, x ∈ 𝕏  (1.113) eq:(10.7)

hold with L(x) := KC̃(x) + K̃(x) for all x in 𝕏.

A few observations are in order before proving Theorem ^{\underline{t:Theorem 10.1}} 22: A result on the Lipschitz continuity of the mappings θ → T (θ, x), x in 𝕏, is readily obtained from Theorem ^{\underline{t:Theorem 10.1}} 22 upon using c(θ, x) ≡ 1, in which case conditions (^{\underline{eq:(10.4)}} 1.110)–(^{\underline{eq:(10.6)}} 1.112) are automatically satisfied, and (^{\underline{eq:(10.6)}} 1.112) reduces to

T̃(x) := sup_{θ} 𝔼_{x}^{θ} [T^{2} (1 + δ)^{T} ] < ∞, x ∈ 𝕏.  (1.114) eq:(10.8)

In fact, (^{\underline{eq:(10.6)}} 1.112) also reduces to (^{\underline{eq:(10.8)}} 1.114) whenever the cost function is bounded, i.e., |c(θ, x)| ≤ B for all x in 𝕏 and θ in Θ.

When the Lipschitz constant in (^{\underline{eq:(10.4)}} 1.110) does not depend on x, i.e., K(x) = K for all x in 𝕏, then (^{\underline{eq:(10.5)}} 1.111) reduces to the condition sup_{θ} 𝔼_{x}^{θ} [T] < ∞ for all x in 𝕏.

The uniform bounds (^{\underline{eq:(10.8)}} 1.114) can be checked in a variety of ways. For instance, in ^{\underline{MSrec,MSreckli,MSsiam,SMant}} [18, 19, 20, 33] the authors considered a particular model where the distribution of the first passage time T under ℙ_{x}^{θ} is independent of θ – of course a rare occurrence – so that (^{\underline{eq:(10.8)}} 1.114) becomes a simple moment requirement. Some general methods are sketched in ^{\underline{MSsiam}} [20]. In other situations, specific arguments have to be developed, as we now do under the assumption that for some distinguished θ^{⋆} in Θ, there exists a constant B > 0 such that for all θ in Θ,

\frac{p_{xy}(θ)}{p_{xy}(θ^{⋆})} ≤ B whenever p_{xy}(θ^{⋆}) > 0, x, y ∈ 𝕏.  (1.115) eq:(10.9)

In that case, fixing θ in Θ and x in 𝕏, we observe from (^{\underline{eq:(10.2)}} 1.108) that

𝔼_{x}^{θ} [1[T ≤ m] (T ∧ m)] ≤ 𝔼_{x}^{θ^{⋆}} [1[T ≤ m](T ∧ m) · B^{T ∧m}] , m = 1, 2, …

because 0 ≤ L_{T ∧m}^{x}(θ^{⋆}, θ) ≤ B^{T ∧m} by virtue of (^{\underline{eq:(10.9)}} 1.115), whence 𝔼_{x}^{θ} [T] ≤ 𝔼_{x}^{θ^{⋆}} [T · B^{T} ] by a simple limiting argument. The same reasoning shows that 𝔼_{x}^{θ} [T^{2}(1 + δ)^{T} ] ≤ 𝔼_{x}^{θ^{⋆}} [T^{2}((1 + δ)B)^{T} ]. Consequently (^{\underline{eq:(10.8)}} 1.114) holds under the structural condition (^{\underline{eq:(10.9)}} 1.115) whenever the more compact conditions

𝔼_{x}^{θ^{⋆}} [T^{2}((1 + δ)B)^{T} ] < ∞

holds. A proof of Theorem ^{\underline{t:Theorem 10.1}} 22. Let x be a fixed element in 𝕏. As in the proof of Theorem ^{\underline{t:Theorem 9.1}} 19, there is no loss of generality in assuming c(θ, x) ≥ 0 for all x in 𝕏 and θ in Θ.

Fix θ and θ′ in Θ, and m = 1, 2, . . .. It is easily seen from (^{\underline{eq:(9.6)}} 1.103) and (^{\underline{eq:(10.2)}} 1.108) that

C_{m}(θ′, x) := 𝔼_{x}^{θ} [1[T ≤ m] · L_{T ∧m}^{x}(θ, θ′) ∑_{t=0}^{T ∧m−1} c(θ′, X_{t})] .

With this relation in mind, we define

A_{m}(θ, θ′) := 𝔼_{x}^{θ} [1[T ≤ m] [1 − L_{T ∧m}^{x}(θ, θ′)] · ∑_{t=0}^{T ∧m−1} c(θ, X_{t})]

and

B_{m}(θ, θ′) := 𝔼_{x}^{θ} [1[T ≤ m] · L_{T ∧m}^{x}(θ, θ′) · [ ∑_{t=0}^{T ∧m−1} c(θ, X_{t}) − ∑_{t=0}^{T ∧m−1} c(θ′, X_{t})]]

so that

C_{m}(θ, x) − C_{m}(θ′, x) = A_{m}(θ, θ′) + B_{m}(θ, θ′).

Condition (^{\underline{eq:(10.3)}} 1.109) implies

|1 − \frac{p_{xy}(θ′)}{p_{xy}(θ)}| ≤ K · |θ − θ′| whenever p_{xy}(θ) > 0, x, y ∈ 𝕏

so that on the event [L_{T ∧m}^{x}(θ, θ′) > 0], provided K|θ − θ′| < 1,

(1 − K|θ − θ′|)^{T ∧m} ≤ L_{T ∧m}^{x}(θ, θ′) ≤ (1 + K|θ − θ′|)^{T ∧m} .  (1.116) eq:(10.15)

Now the easy identities

(1 ± Kt)^{m} − 1 = ∫_{0}^{t} (±mK) · (1 ± Kτ)^{m−1}dτ, t > 0

yield

|(1 ± Kt)^{T ∧m} − 1| ≤ K(T ∧ m) · (1 + δ)^{T ∧m} · t,  (1.117) eq:(10.17)

whenever 0 < t ≤ \frac{δ}{K} (where 0 < δ ≤ 1). Therefore, upon combining (^{\underline{eq:(10.15)}} 1.116) and (^{\underline{eq:(10.17)}} 1.117), under the condition K|θ − θ′| < δ we find

|A_{m}(θ, θ′)|
≤ K · 𝔼_{x}^{θ} [1[T ≤ m] · (T ∧ m) · (1 + δ)^{(T ∧m)} · ∑_{t=0}^{T ∧m−1} c(θ, X_{t})] · |θ − θ′|

and a simple limiting argument gives

\overline{lim}_{m} |A_{m}(θ, θ′)| ≤ K · 𝔼_{x}^{θ} [T · (1 + δ)^{T} · ∑_{t=0}^{T −1} c(θ, X_{t})] · |θ − θ′|. (1.118) eq:(10.18)

On the other hand, for each m = 1, 2, …, we have

|B_{m}(θ, θ′)| ≤ 𝔼_{x}^{θ} [1[T ≤ m] · L_{T ∧m}^{x}(θ, θ′) · ∑_{t=0}^{T ∧m−1} |c(θ, X_{t}) − c(θ′, X_{t})|]

≤ 𝔼_{x}^{θ} [1[T ≤ m] · L_{T ∧m}^{x}(θ, θ′) · ∑_{t=0}^{T ∧m−1} K(X_{t})] · |θ − θ′|

= 𝔼_{x}^{θ′} [1[T ≤ m] ∑_{t=0}^{T ∧m−1} K(X_{t})] · |θ − θ′|,

where the second inequality is a consequence of (^{\underline{eq:(10.4)}} 1.110), and the final equality follows from (^{\underline{eq:(10.2)}} 1.108). In the limit, we conclude

\overline{lim}_{m} |B_{m}(θ, θ′)| ≤ 𝔼_{x}^{θ′} [∑_{t=0}^{T} K(X_{t})] · |θ − θ′|  (1.119) eq:(10.20)

and the result now readily follows from (^{\underline{eq:(10.18)}} 1.118) and (^{\underline{eq:(10.20)}} 1.119).

1.11 Acknowledgement

We are indebted to an anonymous referee for pointing out reference ^{\underline{DV}} [8].

1.12 Appendices

1.12.1 The example

sec:A

To obtain (^{\underline{eq:(7.6)}} 1.69) from (^{\underline{eq:(7.2)}} 1.64), we apply (^{\underline{eq:(6.17)}} 1.60) with z = 0 to get

T (x) = 1 + pT (x + 1), x = 0, 1  (1.120) eq:(A.1)

and

T (x) = 1 + pT (x + 1) + qT (x − 1), x = 2, 3, …  (1.121) eq:(A.2)

Since T (0) = 1/γ(0) by standard results on Markov chains, we can use (^{\underline{eq:(7.2)}} 1.64) to obtain (^{\underline{eq:(7.6)}} 1.69). Indeed, the validity of (^{\underline{eq:(7.6)}} 1.69) can be seen by substituting T (0) into (^{\underline{eq:(A.1)}} 1.120)–(^{\underline{eq:(A.2)}} 1.121), so that T (3) − T (2) = T (2) − T (1). By virtue of (^{\underline{eq:(A.2)}} 1.121), this last equality propagates by induction, i.e., T (x + 1) − T (x) = T (x) − T (x − 1) for all x = 2, … and (^{\underline{eq:(7.6)}} 1.69) readily follows.

Fixing v in 𝕏, we now set out to compute the cost per cycle C_{v} associated with c_{v}. To do so, we use the system of equations (^{\underline{eq:(6.16)}} 1.59) which here takes the form

C_{v}(x) = c_{v}(x) + pC_{v}(x + 1) + qC_{v}(x − 1), x = 0, 1  (1.122) eq:(A.4)

and

C_{v}(x) = c_{v}(x) + pC_{v}(x + 1) + qC_{v}(x − 1), x = 2, 3, …  (1.123) eq:(A.5)

For v = 0, 1 or v = 2, we use (^{\underline{eq:(A.4)}} 1.122)–(^{\underline{eq:(A.5)}} 1.123) to get (^{\underline{eq:(7.8)}} 1.71)–(^{\underline{eq:(7.9)}} 1.72) by straightforward calculations. The case v ≥ 3 is more involved: We observe that C_{v}(x) = C_{v}(x + 1), x = v, …, which is readily derived from the definition of C_{v} (which holds for v ≥ 1). Moreover, as the relation (^{\underline{eq:(A.5)}} 1.123) implies

p(C_{v}(x + 1) − C_{v}(x)) = q(C_{v}(x) − C_{v}(x − 1)), x = 2, …, v − 1

we conclude that

C_{v}(x + 1) = (C_{v}(x + 1) − C_{v}(x)) + (C_{v}(x) − C_{v}(x − 1)) + …
… + (C_{v}(2) − C_{v}(1)) + C_{v}(1)
= ∑_{j=0}^{x−1} ρ^{−j}(C_{v}(2) − C_{v}(1)) + C_{v}(1)  (1.124) eq:(A.7)

for all x = 2, …, v − 1. Because c_{v}(0) = c_{v}(1) = 0, we obtain (^{\underline{eq:(7.10a)}} 1.73) from (^{\underline{eq:(7.7)}} 1.70) and (^{\underline{eq:(A.4)}} 1.122), and combining this last relationship with (^{\underline{eq:(A.7)}} 1.124), we finally get (^{\underline{eq:(7.10b)}} 1.74) after some algebra.

A proof of Theorem ^{\underline{t:Theorem 7.1}} 14. First, under the enforced assumptions, we conclude from (^{\underline{eq:(7.2)}} 1.64) that

∑_{v=0}^{∞} |c(v)|J_{v} ≤ K ∑_{v=0}^{∞}(1 + r^{v})(1 − ρ)ρ^{v} < ∞  (1.125) eq:(A.8)

because ρ < 1 and rρ < 1, and the quantity J given by (^{\underline{eq:(4.7)}} 1.35) is therefore well defined. Next, using (^{\underline{eq:(7.6)}} 1.69), and the fact ρ < 1, we see that

∑_{x=0}^{∞} γ(x)T (x) = 1 + \frac{ρ}{q(1 − ρ)^{2}} < ∞.  (1.126) eq:(A.9)

Finally, we claim that

∑_{x=0}^{∞} γ(x) ∑_{v=0}^{∞} |c(v)|C_{v}(x) < ∞.  (1.127) eq:(A.10)

Before giving a proof, we combine (^{\underline{eq:(A.10)}} 1.127) with (^{\underline{eq:(4.7)}} 1.35) and (^{\underline{eq:(A.9)}} 1.126) to conclude that for each x in X, the quantity h(x) given by

h(x) := ∑_{v=0}^{∞} c(v)h_{v}(x) = ∑_{v=0}^{∞} c(v)[C_{v}(x) − J_{v}T (x)]

= ∑_{v=0}^{∞} c(v)C_{v}(x) − JT (x)  (1.128) eq:(A.11)

is well defined since all infinite series are absolutely convergent.

To establish (^{\underline{eq:(A.10)}} 1.127), we interchange the order of summation (by a simple application of Tonelli’s Theorem), and note that

∑_{x=0}^{∞} γ(x) ∑_{v=0}^{∞} |c(v)|C_{v}(x) ≤ K ∑_{v=0}^{∞}(1 + r^{v}) ∑_{x=0}^{∞} γ(x)C_{v}(x)

= K(1 − ρ) ∑_{v=0}^{∞}(1 + r^{v}) ∑_{x=0}^{∞} ρ^{x}C_{v}(x).

The desired conclusion (^{\underline{eq:(A.10)}} 1.127) now follows from (^{\underline{eq:(7.8)}} 1.71)–(^{\underline{eq:(7.10b)}} 1.74) once we observe that for v = 3, 4, …, the bounds

C_{v}(x) = \{ \begin{matrix}ρ^{v} & x = 0 \\ Cρ^{v−x}(1 − ρ^{x}) & x = 1, …, v \\ C(1 − ρ^{v}) & x = v, v + 1, … \end{matrix}  (1.129) eq:(A.13)

hold for some positive constant C which depends only on p. The calculations are tedious and are omitted; the finiteness of the various infinite series follows from the fact that ρ < 1 and rρ < 1.

Combining (^{\underline{eq:(A.9)}} 1.126) and (^{\underline{eq:(A.10)}} 1.127) with (^{\underline{eq:(A.11)}} 1.128) we see that h defined by (^{\underline{eq:(A.11)}} 1.128) belongs to B_{γ} = U_{γ}. As the Poisson equation (^{\underline{eq:(3.1)}} 1.15) involves here only a finite sum, it is immediate by substitution that under the stated conditions, the pair (h, J) defined above is indeed a solution to (^{\underline{eq:(3.1)}} 1.15) since for each v in 𝕏, the pair (h_{v}, J_{v}) is a solution to the Poisson equation.

Chapter 2

Generic chapter for in-volume reference

c:meyn

Bibliography

BMP [1] A. Benveniste, M. Metivier and P. Priouret, Adaptive Algorithms and Stochastic Approximations, Springer-Verlag, NY (1990).

Be [2] D.P. Bertsekas, Dynamic Programming and Stochastic Control, Academic Press, NY (1976).

BG [3] V. Borkar and M.K. Ghosh, “Ergodic and adaptive control of nearestneighbor motions,” Math. Control, Signals & Systems 4 (1991), pp. 81–98.

CC [4] R. Cavazos-Cadena, “Necessary conditions for the optimality equation in average reward Markov decision processes,” Appl. Math. and Opt. 19 (1989), pp. 97–112.

Chen [5] H.F. Chen, “Stochastic Approximation and its new applications,” Proc. 1994 Hong Kong Intl. Workshop on New Directions in Control and Manufacturing, (1994), pp. 2-12.

Cha [6] K.L. Chung, Markov Chains with Stationary Transition Probabilities, Second Edition, Springer Verlag, NY (1967).

Chb [7] K.L. Chung, A Course in Probability Theory, Second Edition, Academic Press, NY (1974).

DV [8] C. Derman and A.F. Veinott, Jr., “A solution to a countable system of equations arising in Markovian decision processes,” Ann. Math. Stat. 38 (1967), pp. 582–584.

GM [9] P.W. Glynn and S.P. Meyn, “A Lyapunov bound for solutions of the Poisson equation,” Annals of Probability 24 (1996), pp. 916–931.

HS [10] D. Heyman and M. Sobel, Stochastic Models in Operations Research, Volume II: Stochastic Optimization, McGraw-Hill, NY (1984).

HSp [11] A. Hordijk and F.M. Spieksma, “A new formula for the deviation matrix,” Technical Report TW-93-08, Leiden University (1994).

KT [12] S. Karlin and H. Taylor, A First Course in Stochastic Processes, Academic Press, NY (1974).

KSK [13] J.G. Kemeny, J.L. Snell and A.W. Knapp, Denumerable Markov Chains, Second Edition, Springer-Verlag, NY (1976).

Kush [14] H.J. Kushner, Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory, MIT Press, Cambridge, MA (1984).

KY [15] H.J. Kushner and G. G. Yin, Stochastic Approximation Algorithms and Applications, Springer-Verlag, New York (1997).

MMS [16] D.-J. Ma, A.M. Makowski and A. Shwartz, “Stochastic approximations for finite state Markov chains,” Stochastic Processes and Their Applications 35 (1990), pp. 27–45.

MSimp [17] A.M. Makowski and A. Shwartz, “Implementation issues for Markov decision processes,” pp. 323–337 in Stochastic Differential Systems, Stochastic Control Theory and Applications, Eds. W. Fleming and P.-L. Lions, IMA Volume 10, Springer-Verlag, NY (1988).

MSrec [18] A.M. Makowski and A. Shwartz, “Recurrence properties of a system of competing queues, with applications,” EE Pub. 627, Technion, Israel (1987).

MSreckli [19] A.M. Makowski and A. Shwartz, “Recurrence properties of a discretetime single-server network with random routing,” EE Pub. 718, Technion, Israel (1989).

MSsiam [20] A.M. Makowski and A. Shwartz, “Stochastic approximations and adaptive control of a discrete-time single-server network with random routing,” SIAM J. Control and Optimization 30 (1992), pp. 1476– 1506.

Man [21] P. Mandl, “Estimation and control in Markov chains,” Adv. Appl. Prob. 6 (1974), pp. 40–60.

MPa [22] M. Metivier and P. Priouret, “Applications of a Kushner and Clark lemma to general classes of stochastic algorithms,” IEEE Transactions on Information Theory IT-30 (1984), pp. 140–150.

MPb [23] M. Metivier and P. Priouret, “Théorèmes de convergence presque sûre pour une classe d’algo rithmes stochastiques à pas décroissants,” Prob. Theory Related Fields 74 (1987), pp. 403–428.

Meyn [24] S.P. Meyn, “The policy improvement algorithm for Markov decision processes with general state space,” IEEE Transactions on Automatic Control AC-42 (1997), pp. 191-196.

MeynTwee [25] S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability, Springer-Verlag, Series in Control and Communication in Engineering, London (U.K.) (1993).

Num [26] E. Nummelin, General Irreducible Markov Chains and Non-negative Operators, Cambridge University Press, Cambridge, (U.K.) (1984).

NumP [27] E. Nummelin, “On the Poisson equation in the potential theory of a single kernel,” Math. Scand. 68 (1991), pp. 59–82.

Orey [28] S. Orey, Limit Theorems for Markov Chain Transition Probabilities, Van Nostrand Reinhold, London (U.K.) (1971).

RM [29] Z. Rosberg and A.M. Makowski, “Optimal dispatching to parallel heterogeneous servers—Small arrival rates,” IEEE Transactions on Automatic Control AC–35 (1990), pp. 789–796.

Rossc [30] S.M. Ross, Introduction to Stochastic Dynamic Programming, Academic Press, NY (1984).

Rud [31] W. Rudin, Real and Complex Analysis, Second Edition, McGraw-Hill, NY (1974).

SMPoi [32] A. Shwartz and A.M. Makowski, “On the Poisson equation for Markov chains,” EE Pub. 646, Technion, Israel, September 1987.

SMant [33] A. Shwartz and A.M. Makowski, “An optimal adaptive scheme for two competing queues with constraints,” pp. 515–532 in Analysis and Optimization of Systems, Eds. A. Bensoussan and J.-L. Lions, Lecture Notes in Control and Info. Sci. 83, Springer-Verlag, NY (1987).

SMman [34] A. Shwartz and A.M. Makowski, “Comparing policies in Markov decision processes: Mandl’s lemma revisited,” Mathematics of Operations Research 15 (1990), pp. 155–174.

Whittle [35] P. Whittle, Optimization Over Time (Volume II): Dynamic Programming and Stochastic Control, Wiley & Sons, NY (1983).