Local Poisson equations associated with the Varadhan functional

Abstract

This work concerns Markov chains evolving on a denumerable sate space, which is endowed with a non-negative reward function with finite support. In this context, the problem of determining the Varadhan function, given by the exponential growth rate of the aggregated rewards, is studied. The main results in this direction are expressed in terms of the idea of a system of local Poisson equations, and can be summarized as follows: (i) the Varadhan function is determined by one of such systems, and (ii) if a finite set is accessible form any state, then a system of local Poisson equations exits.

Keywords

discounted approximation fixed points stopping time accessibility to a finite set weak Doeblin condition risk-sensitive average reward

1. Introduction

Let ${X_{n}}$ be a Markov chain with transition matrix $P = [p_{x, y}]$ on a denumerable state space S. Given a running reward function $R : S \to [0, \infty)$ , this work is concerned with the characterization of the exponential grow rate of the aggregated rewards $\sum_{t = 0}^{n - 1} R (X_{n})$ , which determine the following Varadhan function $J : S \to R$ : $\begin{matrix} (1.1) & J (x) : = \underset{n \to \infty}{lim sup} \frac{1}{n} J_{n} (x), x \in S, \end{matrix}$ where $\begin{matrix} (1.2) & J_{n} (x) : = log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}]), x \in S, n = 1, 2, 3, \dots, \end{matrix}$ and $E_{x} [\cdot]$ stands for the expectation operator given that the initial state is $X_{0} = x \in S$ . Within the theory of large deviations, this function plays a crucial role to analyze the rate of convergence of the empirical measure of the Markov chain ${X_{n}}$ ; see, for instance, [7] or [11–13]. In the context of stochastic optimal control, this functional has been the fundamental instrument to formulate the class of risk-sensitive average control problems; see, for instance, [8–10,19], or [18] where discrete-time Markov decision chains are studied, or [2,14] or [3], which concern continuous-time models.

When the state space S is finite and communicating, i.e., for all $x, y \in S$ there exists a positive integer $n = n (x, y)$ such that $P_{x} [X_{n} = y] > 0$ , the Perron–Frobenious theory of positive matrices [22] yields that $J (\cdot)$ is constant, say g, and that $e^{g}$ is the largest eigenvalue of the matrix ${[e^{R (x)} p_{x, y}]}_{x, y \in S}$ . Moreover, g is characterized as the unique real number for which there exists a function $h : S \to R$ satisfying the following Poisson equation: $\begin{matrix} (1.3) & e^{g + h (x)} = E_{x} [e^{R (X_{0}) + h (X_{1})}], x \in S, \end{matrix}$ a result that can be traced back to the seminal paper by Howard and Matheson [17], where it was also shown that, if the above equation is satisfied, then the superior limit in (1.1) can be replaced by limit. Under appropriate ergodicity conditions, this result was extended in [21] to Markov chains with general states space and continuous or discrete time parameter, whereas a formulation of the corresponding eigenvalue problem for differential operators associated with diffusions was given in [15]. The analysis of the risk sensitive ergodic problem for diffusions was analyzed by Kaise and Nagai [20].

The communication condition described above is essential to characterize the Varadhan’s function in terms of the Poisson equation (1.3). Indeed, under the unichain assumption that ${X_{n}}$ has only one recurrent class but the set of transient states is non-empty, it is possible to have that $J (\cdot)$ is not constant, and then it cannot be characterized by a single Poisson equation; moreover, even if $J (\cdot)$ takes only a single value, it is not generally determined via Eq. (1.3) [5]. On the other hand, still within the context of a finite state space, it was shown in [6] that $J (\cdot)$ is generally characterized by a system of local Poisson equations, a result that can be roughly described as follows: There exists a partition $S_{1}, S_{2}, \dots, S_{k}$ of the state space such that, on $S_{k}$ , $J (\cdot)$ is constant, say $g_{k}$ , this value depends only on the rewards earned while the chain stays in $S_{k}$ , and is characterized by an equation similar to (1.3). This notion is extended in Definition 2.1 to the presented context of a denumerable state space, and the main problem studied in this note is the following:

To determine conditions on the reward and transition structures so that the Varadhan function can be characterized in terms of a system of local Poisson equations.

This problem will be analyzed under the assumption that the reward function is non-negative and has finite support. Within this framework, the main conclusions of the paper, which are formally stated in Section 2, can be described as follows:

the Varadhan function can be obtained from a system of local Poisson equations, and

if some finite subset F of the state space is accessible from any initial state, then a system of local Poisson equations exists.

The approach used below to establish these results relies on the discounted method, which is based on contractive operators on the space of bounded functions on S, and the corresponding fixed points are used to construct the components of a system of local Poisson equations. The discounted technique is the fundamental tool used in [8–10,16,19], where controlled Markov chains endowed with the average index were studied under risk-aversion. The particular usage of the discounted procedure in this note is motivated by the results in [1], where a general characterization of the optimal risk-sensitive average cost was established for controlled models with finite sate space.

The organization of the paper is as follows: In Section 2 the basic structural conditions of the paper are formally expounded as Assumption 2.1, the idea of a system of local Poisson equations is introduced in Definition 2.1, and the main conclusions of this work are stated as Theorems 2.1 and 2.2. The first of these results is the verification theorem, stating that the Varadhan function can be obtained form a system of local Poisson equations, whereas the second one establishes that, under Assumption 2.1, such a system certainly exists. Also, and example illustrating the fundamental idea in Definition 2.1 is presented. Next, Section 3 is dedicated to establish the verification theorem, whereas in Section 4 the family of discounted operators ${T_{α}}_{α \in (0, 1)}$ is introduced, and the corresponding fixed points ${V_{α}}_{α \in (0, 1)}$ are used in Sections 5 and 6 to construct the components of a system of local Poisson equations. Finally, the exposition concludes in Section 7 with a proof of the existence result in Theorem 2.2.

Notation. For integers a and b, $a \land b$ is an infix notation for $min {a, b}$ . If f is a real valued function, the corresponding supremum norm is denoted by $∥ f ∥$ , that is, $\begin{matrix} ∥ f ∥ : = sup {| f (x) | ∣ x belongs to the domain of f}, \end{matrix}$ whereas the class of all real valued and bounded functions defined on a set $\tilde{S}$ is denoted by $B (\tilde{S})$ , so that $f : \tilde{S} \to R$ belongs to $B (\tilde{S})$ if and only $∥ f ∥ < \infty$ . The indicator function associated to an event A is denoted by $I [A]$ and, without explicit reference, a relation involving random variables holds almost surely with respect to the underlying probability measure.

2. Local Poisson equations and main results

In this section the main conclusions on the determination of the Varadhan function will be stated. The subsequent analysis will be performed under the following assumption, whose formulation involves the idea of first return time $T_{B}$ to a non-empty subset B of the state space: $\begin{matrix} (2.1) & T_{B} : = min {n ⩾ 1 ∣ X_{n} \in B}, \end{matrix}$ where by convention, the minimum of the empty set is ∞; when $B = {r}$ is a singleton, the simpler notation $T_{r}$ is used in place of $T_{{r}}$ .

Assumption 2.1.

The reward function R is non-negative and has finite support, i.e., $\begin{matrix} R (x) ⩾ 0, x \in S, and supp (R) : = {y \in S ∣ R (y) > 0} is finite . \end{matrix}$

There exists a finite set $F \subset S$ such that, with probability 1, F is accessible from every initial state, that is, $\begin{matrix} (2.2) & P_{x} [T_{F} < \infty] = 1, x \in S . \end{matrix}$

Remark 2.1.

The accessibility property in Assumption 2.1(ii) is a weak form of the Doeblin condition, which prescribes the existence of a finite set F such that ${sup}_{x \in S} E_{x} [T_{F}] < \infty$ ; a generalized version of that requirement, which is referred to as the simultaneous Doeblin condition, has been intensively used to analyze the risk-neutral average criterion in controlled Markov chains [23].

Under Assumption 2.1 the chain $(X_{t})$ may be transient but, even in that case, the Varadhan function may be positive [4].

The results of this note on the characterization of the Varadhan function involve the idea of system of local Poisson equations, which is now introduced.
Definition 2.1.
A vector of triplets $\begin{matrix} (2.3) & P = ((S_{1}, g_{1}, h_{1}), (S_{2}, g_{2}, h_{2}), \dots, (S_{k}, g_{k}, h_{k})), \end{matrix}$ is a system of local Poisson equations for the reward function R and the transition matrix P if, and only if, the following requirements (i)–(v) are satisfied:
$S_{1}, S_{2}, \dots, S_{k}$ is a partition of S.

For each $i = 1, 2, \dots, k$ , $g_{i} \in R$ , and $h_{i} : S_{i} \to R$ satisfy that $\begin{matrix} (2.4) & g_{1} ⩽ g_{2} ⩽ \dots ⩽ g_{k}, \end{matrix}$ and $\begin{matrix} (2.5) & sup_{x \in S_{i}} h_{i} (x) = : M_{i} < \infty, 1 ⩽ i ⩽ k . \end{matrix}$

For each $i = 1, 2, \dots, k$ , the set $S_{1} \cup S_{2} \cup \dots \cup S_{i}$ is closed with respect to the transition matrix P, that is, $\begin{matrix} \sum_{y \in S_{1} \cup S_{2} \cup \dots \cup S_{i}} p_{x, y} = 1, x \in S_{i}, i = 1, 2, \dots, k . \end{matrix}$

For each $i = 1, 2, \dots, k$ , the pair $(g_{i}, h_{i} (\cdot))$ satisfies the following local Poisson equation: $\begin{matrix} (2.6) & e^{g_{i} + h_{i} (x)} = e^{R (x)} \sum_{y \in S_{i}} p_{x, y} e^{h_{i} (y)}, x \in S_{i} . \end{matrix}$

For each $i = 1, 2, \dots, k$ , $\begin{matrix} (2.7) & \underset{n \to \infty}{lim inf} E_{ν_{i, x, n}} {[e^{h_{i} (X_{n})}]}^{1 / n} ⩾ 1, x \in S_{i}, \end{matrix}$ where for each positive integer n, $E_{ν_{i, x, n}} [\cdot]$ is the expectation operator with respect to the measure $ν_{i, x, n}$ on $S_{i}^{n}$ defined by $\begin{matrix} (2.8) & ν_{i, x, n} (A) = \frac{E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [(X_{1}, X_{2}, \dots, X_{n}) \in A]]}{E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, 1 ⩽ t < n]]}, A \subset S_{i}^{n}, x \in S_{i} . \end{matrix}$

Observe that the left-hand side of (2.6) is positive, so that $\begin{matrix} (2.9) & \sum_{y \in S_{i}} p_{x, y} > 0, x \in S_{i} . \end{matrix}$ From this point, an induction argument using the Markov property yields that, for every positive integer n, $P_{x} [X_{t} \in S_{i}, 1 ⩽ t < n] > 0$ when $x \in S_{i}$ , so that the denominator in (2.8) is always positive, and then the measure $ν_{i, x, n}$ is well defined.
Remark 2.2.

The idea in Definition 2.1 is an extension of the corresponding notion formulated in [6]. In this last paper Markov chains with finite state space were considered, and just conditions (i)–(iv) were required for a system of local Poisson equations. Indeed, when the state space is finite, the fifth part in Definition 2.1 follows from the conditions (i)–(iv). To verify this assertion, assume that S is finite and note that, for each $x \in S_{i}$ , (2.9) yields that the set ${y \in S_{i} ∣ p_{x, y} > 0}$ is non-empty (and finite), so that $\begin{matrix} m_{i} = min_{x \in S_{i}} min {p_{x, y} ∣ y \in S_{i}, p_{x, y} > 0} > 0; \end{matrix}$ setting $b_{i} = {min}_{x \in S_{i}} h_{i} (x) \in R$ , it is not difficult to verify that the above display and (2.8) together lead to $E_{ν_{i, x, n}} [e^{h_{i} (X_{n})}] ⩾ m_{i} e^{b_{i}}$ , and then (2.7) holds.

Assume that condition (iv) in Definition 2.1 is satisfied by the vector of triplets $P$ in (2.3). In that case, it will be shown in Lemma 3.1 below that, for every positive integer n and $x \in S_{i}$ , $\begin{matrix} (2.10) & e^{n g_{i} + h_{i} (x)} = E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + h_{i} (X_{n})} I [X_{t} \in S_{i}, t ⩽ n]] . \end{matrix}$ Using this fact, it will be now verified that the requirement (2.7) is equivalent to $\begin{matrix} (2.11) & e^{g_{i}} ⩾ \underset{n \to \infty}{lim sup} E_{x} {[e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]}^{1 / n}, x \in S_{i} . \end{matrix}$ To achieve this goal, note (2.10) and the definition of the measure $ν_{i, x, n}$ in (2.8) together yield that, for every $x \in S_{i}$ and $n = 1, 2, 3, \dots$ , $\begin{matrix} \begin{matrix} E_{ν_{i, x, n}} [e^{h_{i} (X_{n})}] & = \frac{E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + h_{i} (X_{n})} I [X_{t} \in S_{i}, t ⩽ n]]}{E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]} \\ = \frac{e^{n g_{i} + h_{i} (x)}}{E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]} . \end{matrix} \end{matrix}$ Therefore, $\begin{matrix} \underset{n \to \infty}{lim inf} E_{ν_{i, x, n}} {[e^{h_{i} (X_{n})}]}^{1 / n} = \frac{e^{g_{i}}}{{lim sup}_{n \to \infty} E_{x} {[e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}^{*}, t ⩽ n - 1]]}^{1 / n}}, \end{matrix}$ and it follows that (2.7) is equivalent to (2.11).

The main results of this note are stated in the following two theorems. The first one establishes that the Varadhan function can be determined from a system of local Poisson equations.
Theorem 2.1 (Verification).

Let ${X_{n}}$ be a Markov chain with transition matrix $P = [p_{x, y}]$ on a denumerable state space S, and let $R \in B (S)$ be such that Assumption 2.1(i) holds. If $P = ((S_{1}, g_{1}, h_{1}), (S_{2}, g_{2}, h_{2}), \dots, (S_{k}, g_{k}, h_{k}))$ is a system of local Poisson equations in the sense of Definition 2.1, then $\begin{matrix} J (x) = g_{i}, x \in S_{i}, i = 1, 2, \dots, k . \end{matrix}$ Moreover, for each $x \in S$ , $\begin{matrix} J (x) = lim_{n \to \infty} \frac{1}{n} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}]) . \end{matrix}$

A complement to this theorem is the following existence result.

Theorem 2.2.
If the reward function $R \in B (S)$ and the transition law $P = {[p_{x, y}]}_{x, y \in S}$ satisfy Assumption 2.1, then a system of local Poisson equations for R and P exists.

Before proceeding with the proof of the above theorems, an example illustrating the idea of a system of local Poisson equations will be analyzed.
Example 2.1.
On the state space $S : = {0, 1, 2, 3, \dots}$ , consider the Markov chain with transition matrix determined by $\begin{matrix} (2.12) & p_{0, 0} = 1, p_{x, x} = 1 / 2 = p_{x, 0}, x = 1, 2, \end{matrix}$ whereas for each positive integer k, $\begin{matrix} (2.13) & \begin{matrix} p_{3 k, 3 (k - 1)} = \frac{1}{2} = p_{3 k, 3 (k + 1)}, \\ p_{3 k + 1, 3 (k - 1) + 1} = p_{3 k + 1, 3 (k - 1)} = \frac{1}{4} and p_{3 k + 1, 3 (k + 1) + 1} = \frac{1}{2}, \\ p_{3 k + 2, 3 (k - 1) + 2} = p_{3 k + 2, 3 (k - 1) + 1} = p_{3 k + 2, 3 (k - 1)} = \frac{1}{6} and p_{3 k + 2, 3 (k + 1) + 2} = \frac{1}{2} . \end{matrix} \end{matrix}$ Now, define the reward function $R : S \to R$ by $\begin{matrix} (2.14) & R (x) = x, x = 1, 2, R (x) = 0, x \in S ∖ {1, 2} . \end{matrix}$

First, it will be verified that Assumption 2.1 is satisfied in this example.
Proposition 2.1.
In Example 2.1 Assumption 2.1 holds with $F = {0}$ .
Proof.
Since the reward function is non-negative and has finite support, it is sufficient to show that (2.2) occurs with $F = {0}$ . To achieve this goal, have a glance at (2.12) and note that $P_{0} [T_{0} = 1] = 1$ whereas $\begin{matrix} (2.15) & P_{x} [T_{0} = n] = 1 / 2^{n}, x = 1, 2, \end{matrix}$ so that $\begin{matrix} (2.16) & P_{x} [T_{0} < \infty] = 1, x = 0, 1, 2 . \end{matrix}$ To conclude, let ${X_{n}}$ the Markov chain associated to the transition law $[p_{x, y}]$ , and for each non-negative integer n, set $\begin{matrix} Y_{n} = integer part of X_{n} / 3 . \end{matrix}$ It follows from (2.12) and (2.13) that, for each non-negative integer n, conditional on $X_{t}$ , $t ⩽ n$ , $Y_{n + 1}$ takes the values $Y_{n} - 1$ and $Y_{n} + 1$ with probability $1 / 2$ when $Y_{n} > 0$ , whereas $Y_{n + 1} = 0$ with probability 1 if $Y_{n} = 0$ . Therefore, ${Y_{n}}$ is a symmetric random walk on S with absorbing barrier ${0}$ , so that $P_{x} [Y_{n} = 0 for some n > 0] = 1$ for every $x \in S$ . Since $Y_{n} = 0$ is equivalent to $X_{n} \in {0, 1, 2}$ , it follows that $\begin{matrix} P_{x} [X_{n} \in {0, 1, 2} for some n > 0] = 1, x \in S, \end{matrix}$ a property that via (2.16) leads to (2.2). □

Combining the above proposition with Theorem 2.2, it follows that there exists a system of local Poisson equations for the model in Example 2.1. To provide an explicit instance of such a system, first note that, since 0 is an absorbing state and $R (0) = 0$ , $\begin{matrix} (2.17) & g_{0} : = J (0) = 0 . \end{matrix}$ On the other hand, (2.12), (2.14) and (2.15) together yield that $e^{J_{n} (1)} = E_{1} [e^{\sum_{k = 0}^{n - 1} R (X_{t})}] = \sum_{r = 0}^{n - 1} e^{r} P_{1} [T_{0} = r] + e^{n} P_{1} [T_{0} ⩾ n] = \sum_{r = 0}^{n} {(e / 2)}^{r}$ , so that ${(e / 2)}^{n} ⩽ e^{J_{n} (1)} ⩽ n {(e / 2)}^{n}$ , and then $\begin{matrix} (2.18) & g_{1} : = J (1) = lim_{n \to \infty} \frac{1}{n} J_{n} (1) = log (e / 2) . \end{matrix}$ Similarly, $\begin{matrix} (2.19) & g_{2} : = J (2) = lim_{n \to \infty} \frac{1}{n} J_{n} (2) = log (e^{2} / 2) . \end{matrix}$ Next, define the partition $S_{0}$ , $S_{1}$ , $S_{2}$ of the state space $S = {0, 1, 2, \dots}$ by $\begin{matrix} (2.20) & S_{r} = {3 k + r ∣ k = 0, 1, 2, 3, \dots}, r = 0, 1, 2, \end{matrix}$ and, for each $r = 0, 1, 2$ , define the function $h_{r}$ on the set $S_{r}$ by $\begin{matrix} (2.21) & h_{0} (x) : = 0, x \in S_{0}, \end{matrix}$ and $\begin{matrix} (2.22) & h_{r} (r) = 0, h_{r} (x) : = log (E_{x} [e^{- g_{r} T_{r}} I [T_{r} < \infty]]), x \in S_{r} ∖ {r}, r = 1, 2 . \end{matrix}$ Consider now a fixed state $x = 3 k + r \in S_{r} ∖ {r}$ , where $r = 1$ or $r = 2$ . In this case $x ⩾ 3 + r$ and $p_{x, x - 3} = 1 / [2 (r + 1)]$ , by (2.13), and then $P_{x} [X_{t} = 3 (k - t) + r, 0 ⩽ t ⩽ k] = 1 / {[2 (r + 1)]}^{k}$ , a relation that immediately leads to $P [T_{r} = k] ⩾ 1 / {[2 (r + 1)]}^{k}$ , so that $\begin{matrix} E_{x} [e^{- \sum_{k = 1}^{T_{r} - 1} g_{r}}] ⩾ e^{- k g_{r}} P_{x} [T_{r} = k] ⩾ e^{- k g_{r}} / {(1 + r)}^{k}, x = 3 k + r \in S_{r} ∖ {r} . \end{matrix}$ This last relation and (2.17)–(2.22) together imply that $\begin{matrix} (2.23) & h_{r} (x) \in (- \infty, 0], x \in S_{r}, r = 0, 1, 2 . \end{matrix}$
Proposition 2.2.
With the notation in (2.17)–(2.22 ) , $\begin{matrix} \tilde{P} = ((S_{0}, g_{0}, h_{0}), (S_{1}, g_{1}, h_{1}), (S_{2}, g_{2}, h_{2})) \end{matrix}$ is a system of local Poisson equations for the model in Example 2.1 .
Proof.
It will be shown that the five conditions in Definition 2.1 are satisfied by $\tilde{P}$ :
$S_{0}$ , $S_{2}$ , $S_{2}$ is a partition of $S = {0, 1, 2, 3, \dots}$ , by (2.20).

By (2.17)–(2.19) the relation $g_{0} < g_{1} < g_{2}$ occurs, whereas condition (2.5) holds in the present case with $M_{i} = 0$ , by (2.23).

Combining (2.20) with the specification of the transition law in (2.12) and (2.13), it follows that $S_{0}$ and $S_{0} \cup S_{1}$ are closed with respect to the transition law $[p_{x, y}]$ ; of course $S = S_{0} \cup S_{1} \cup S_{2}$ is also closed.

It will be verified that, for each $r = 0, 1, 2$ , $\begin{matrix} (2.24) & e^{g_{r} + h_{r} (x)} = e^{R (x)} \sum_{y \in S_{r}} p_{x, y} e^{h_{r} (y)}, x \in S_{r} . \end{matrix}$
Case $r = 0$ .
In this context, the left-hand side of the above equation is 1, by (2.17) and (2.21). On the other hand, using that $R (x) = 0 = h_{0} (y)$ for $x, y \in S_{0}$ , by (2.14) and (2.21), note that $e^{R (x)} \sum_{y \in S_{0}} p_{x, y} e^{h_{r} (y)} = \sum_{y \in S_{0}} p_{x, y} = 1$ , where the second equality is due to the fact that $S_{0}$ is closed with respect to $[p_{x, y}]$ . Consequently, (2.24) holds when $r = 0$ .
Case $r = 1$ .
Note that $e^{g_{1} + h_{1} (1)} = e^{g_{1}}$ , since $h_{1} (1) = 0$ , whereas (2.12) and (2.14) yield that $e^{R (1)} \sum_{y \in S_{1}} p_{1, y} e^{h_{1} (y)} = e^{R (1)} p_{11} e^{h_{1} (1)} = e / 2$ . Therefore, by (2.18), $\begin{matrix} (2.25) & e^{g_{1} + h_{1} (1)} = e^{R (1)} \sum_{y \in S_{1}} p_{1, y} e^{h_{1} (y)} . \end{matrix}$ Next, let $x \in S_{1} ∖ {1} = {4, 7, 11, \dots}$ be arbitrary, and suppose that $X_{0} = x$ . In this case (2.13) yields that $P_{x} [X_{1} \in {x + 3, x - 3, x - 4}] = 1$ . Since $x - 4 \in S_{0}$ and $S_{0}$ is closed, using that $1 \notin S_{0}$ it follows that $P_{x} [X_{1} = x - 4, T_{1} < \infty] = 0$ , and then (2.22) implies that $\begin{matrix} e^{h_{1} (x)} = E_{x} [e^{- g_{1} T_{1}} I [X_{1} = x - 3, T_{1} < \infty]] + E_{x} [e^{- g_{1} T_{1}} I [X_{1} = x + 3, T_{1} < \infty]] . \end{matrix}$ By the Markov property, $\begin{matrix} \begin{matrix} E_{x} [e^{- g_{1} T_{1}} I [X_{1} = x + 3, T_{1} < \infty]] & = e^{- g_{1}} p_{x, x + 3} E_{x + 3} [e^{- g_{1} T_{1}} I [T_{1} < \infty]] \\ = e^{- g_{1}} p_{x, x + 3} e^{h_{1} (x + 3)} \end{matrix} \end{matrix}$ and $\begin{matrix} \begin{matrix} E_{x} [e^{- g_{1} T_{1}} I [X_{1} = x - 3, T_{1} < \infty]] & = e^{- g_{1}} p_{x, x - 3} E_{x - 3} [e^{- g_{1} T_{1}} I [T_{1} < \infty]] \\ = e^{- g_{1}} p_{x, x - 3} e^{h_{1} (x - 3)}, x > 3, \end{matrix} \end{matrix}$ whereas $\begin{matrix} \begin{matrix} E_{4} [e^{- g_{1} T_{1}} I [X_{1} = 4 - 3, T_{1} < \infty]] & = E_{4} [e^{- g_{1}} I [X_{1} = 1]] \\ = e^{- g_{1}} p_{4, 1} \\ = e^{- g_{1}} p_{4, 1} e^{h_{1} (1)}; \end{matrix} \end{matrix}$ see (2.22) for the second equality. Combining the last four displays it follows that $\begin{matrix} e^{h_{1} (x)} = e^{- g_{1}} \sum_{y \in S_{1}} p_{x, y} e^{h_{1} (y)}, x \in S_{1} ∖ {1} = {4, 7, 11, \dots} . \end{matrix}$ Since $R (x) = 0$ for $x \in S_{1} ∖ {1}$ , the above equality and (2.25) together yield that (2.24) holds when $r = 1$ , whereas the case $r = 2$ can be established along similar lines.

Via Remark 2.2(ii), it is sufficient to show that $\begin{matrix} (2.26) & e^{g_{r}} ⩾ \underset{n \to \infty}{lim sup} {(E_{x} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n]])}^{1 / n}, x \in S_{r} \end{matrix}$ for $r = 0, 1, 2$ . Recalling that $g_{0} = 0$ and $R (x) = 0$ for $x \in S_{0}$ , it follows that the above relation holds for $r = 0$ . Now, consider the case $r \in {1, 2}$ and observe that, conditionally on $X_{0} = r$ , the variables $I [X_{t} \in S_{r}, 0 ⩽ t < n]$ and $I [X_{t} = r, 0 ⩽ t < n]$ coincide almost surely, by (2.12), and then $\begin{matrix} E_{r} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n]] = E_{r} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} = r, 0 ⩽ t < n]] . \end{matrix}$ Therefore, using that $p_{r, r} = 1 / 2$ and $R (r) = r$ , by (2.12) and (2.14), it follows that $\begin{matrix} (2.27) & E_{r} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n]] = {(e^{r} / 2)}^{n} . \end{matrix}$ Now, let $x \in S_{r} ∖ {r} = {r + 3 k ∣ k = 1, 2, 3, \dots}$ be arbitrary. Using that the reward function is null on $S_{r} ∖ {r}$ , note that the Markov property and the above display together yield that $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n]] \\ = E_{x} [e^{\sum_{k = T_{r}}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n, T_{r} < n]] + E_{x} [I [X_{t} \in S_{r}, 0 ⩽ t < n, T_{r} > n]] \\ ⩽ E_{x} [I [T_{r} < n] {(e^{r} / 2)}^{n - T_{r}}] + P_{x} [T_{r} > n] \\ ⩽ P_{x} [T_{r} < n] {(e^{r} / 2)}^{n} + P_{x} [T_{r} > n] ⩽ {(e^{r} / 2)}^{n} . \end{matrix} \end{matrix}$ These two last displays together yield that $\begin{matrix} E_{x} [e^{\sum_{k = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{r}, 0 ⩽ t < n]] ⩽ {(e^{r} / 2)}^{n}, x \in S_{r}, \end{matrix}$ and (2.26) follows combining this relation with the equality $e^{g_{r}} = e^{r} / 2$ ; see (2.18) and (2.19). Thus, $\tilde{P}$ satisfies the five conditions in Definition 2.1, so that $\tilde{P}$ is a system of local Poisson equations. □

The remainder of the paper is dedicated to prove Theorems 2.1 and 2.2. The proof of the verification theorem, which will be presented in the following section, is grounded on the Markov property. On the other hand, the proof of Theorem 2.2 is somewhat involved. The argument is based on contractive (discounted) operators on the space $B (S)$ of bounded functions defined on S, whose fixed points are used to construct the different components of a system of local Poisson equations. After presenting the necessary preliminaries in Sections 4–6, the existence result will be proved in Section 7.
3. Proof of the verification theorem

In this section Theorem 2.1 will be established. Throughout the subsequent analysis Assumption 2.1 is enforced, and $\begin{matrix} P = ((S_{1}, g_{1}, h_{1}), (S_{2}, g_{2}, h_{2}), \dots, (S_{k}, g_{k}, h_{k})) \end{matrix}$ stands for a system of local Poisson equations in the sense of Definition 2.1. The starting point to the proof of the verification theorem is the following.

Lemma 3.1.
For each $i \in {1, 2, \dots, k}$ , the following relation holds for every positive integer n: $\begin{matrix} (3.1) & e^{n g_{i} + h_{i} (x)} = E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + h_{i} (X_{n})} I [X_{t} \in S_{i}, t ⩽ n]], x \in S_{i} . \end{matrix}$
Proof.
The argument is by induction. Note that (2.6) can be equivalently written as $\begin{matrix} e^{g_{i} + h_{i} (x)} = E_{x} [e^{R (X_{0}) + h_{i} (X_{1})} I [X_{1} \in S_{i}]], x \in S_{i}, \end{matrix}$ showing that (3.1) holds when $n = 1$ . Suppose now that (3.1) is valid for a positive integer n, let $x \in S_{i}$ be arbitrary and observe that the Markov property yields that $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n} R (X_{t}) + h_{i} (X_{n + 1})} I [X_{t} \in S_{i}, t ⩽ n + 1] ∣ X_{t}, t ⩽ n] \\ = I [X_{t} \in S_{i}, t ⩽ n] e^{\sum_{t = 0}^{n - 1} R (X_{t})} E_{X_{n}} [e^{R (X_{n}) + h_{i} (X_{n + 1})} I [X_{n + 1} \in S_{i}]] \\ = I [X_{t} \in S_{i}, t ⩽ n] e^{\sum_{t = 0}^{n - 1} R (X_{t})} e^{g_{i} + h_{i} (X_{n})}, \end{matrix} \end{matrix}$ where the second equality is due to (2.6). Thus, $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n} R (X_{t}) + h_{i} (X_{n + 1})} I [X_{t} \in S_{i}, t ⩽ n + 1]] \\ = e^{g} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + h_{i} (X_{n})} I [X_{t} \in S_{i}, t ⩽ n]], \end{matrix} \end{matrix}$ an equality that combined with the induction hypothesis yields that (3.1) holds with $n + 1$ instead of n, completing the induction argument. □
Remark 3.1.
Note that the proof of Lemma 3.1 depends only on property (iv) of a system of local Poisson equations.

The second instrument that will be used to derive Theorem 2.1 is the following:
Theorem 3.1.
The Varadhan function $J (\cdot)$ satisfies that $\begin{matrix} (3.2) & J (x) = \underset{n \to \infty}{lim sup} \frac{1}{n} J_{n} (x) ⩽ g_{i}, x \in S_{i}, i = 1, 2, \dots, k; \end{matrix}$ see ( 1.1 ) and ( 1.2 )

Before proceeding with the proof of this result, it will be combined with Lemma 3.1 to establish the verification theorem.
Proof of Theorem 2.1.
Let $i \in {1, 2, \dots, k}$ be arbitrary, select $x \in S_{i}$ and observe that for every positive integer n $\begin{matrix} \begin{matrix} e^{J_{n + 1} (x)} & = E_{x} [e^{\sum_{t = 0}^{n} R (X_{t})}] \\ ⩾ E_{x} [e^{\sum_{t = 0}^{n} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n]] \\ ⩾ E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n]] \\ ⩾ E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + h_{i} (X_{t}) - M_{i}} I [X_{t} \in S_{i}, t ⩽ n]], \end{matrix} \end{matrix}$ where the second inequality is due to the non-negativity of R, and the third one stems form the relation $h_{i} (y) - M_{i} ⩽ 0$ for every $y \in S_{i}$ ; see (2.5). Via Lemma 3.1, the above display yields that $e^{J_{n + 1} (x)} ⩾ e^{n g_{i} + h_{i} (x) - M_{i}}$ , and then ${lim inf}_{n \to \infty} \frac{1}{n + 1} J_{n + 1} (x) ⩾ g_{i}$ . Combining this relation with Theorem 3.1 it follows that $\begin{matrix} lim_{n \to \infty} \frac{1}{n} J_{n} (x) = g_{i}, x \in S_{i}, \end{matrix}$ and the conclusion follows, since $i \in {1, 2, \dots, k}$ is arbitrary. □

The remainder of the section is dedicated to establish Theorem 3.1. The argument relies on the following two lemmas. The first one shows that $g_{i}$ is a local rate, in the sense that it equals the grow rate of the aggregated rewards while the system stays in the set $S_{i}$ . Lemma 3.2.
For every $i = 1, 2, \dots, k$ , $\begin{matrix} (3.3) & lim_{n \to \infty} \frac{1}{n} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]) = g_{i}, x \in S_{i}, \end{matrix}$ and $\begin{matrix} (3.4) & g_{i} ⩾ 0 . \end{matrix}$
Proof.
Let $i \in {1, 2, \dots, k}$ , $x \in S_{i}$ and the positive integer n be arbitrary. Recalling that $R (\cdot) ⩾ 0$ , note that Lemma 3.1 and (2.5) together yield that $\begin{matrix} \begin{matrix} e^{n g_{i} + h_{i} (x)} & ⩽ e^{M_{i}} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n]] \\ ⩽ e^{M_{i}} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]], \end{matrix} \end{matrix}$ a relation that immediately leads to $\begin{matrix} \underset{n \to \infty}{lim inf} \frac{1}{n} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]) ⩾ g_{i} . \end{matrix}$ On the other hand, as already noted in Remark 2.2(ii), the property in Definition 2.1(v) is equivalent to $\begin{matrix} \underset{n \to \infty}{lim sup} \frac{1}{n} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]) ⩽ g_{i} . \end{matrix}$ Since $x \in S_{i}$ is arbitrary, these two last displays together imply the desired conclusion in (3.3). To verify the property (3.4), select $x \in S_{1}$ and, using that set $S_{1}$ is closed with respect to the transition matrix P, by condition (iii) in Definition 2.1, note that $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] = E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{1}, t < n]], \end{matrix}$ so that (3.3) implies that $\begin{matrix} g_{1} = lim_{n \to \infty} \frac{1}{n} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}]) ⩾ 0, \end{matrix}$ where the inequality is due to the non-negativity of R. Now, (3.4) follows combining this last display with the relation (2.4) in Definition 2.1(ii). □
Lemma 3.3.
For each $i \in {1, 2, \dots, k}$ the following assertion holds: Given $ε > 0$ , there exists $A_{i} (ε) \in [0, \infty)$ such that, for every positive integer n $\begin{matrix} (3.5) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ e^{n (g_{i} + ε) + A_{i} (ε)}, x \in S_{i} . \end{matrix}$
Proof.
Let $i \in {1, 2, 3, \dots, k}$ and $x \in S_{i}$ be arbitrary, and note that Lemma 3.2 implies that there exists a positive integer $N (x, ε)$ such that $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ e^{n (g_{i} + ε)}, n > N (x, ε) . \end{matrix}$ Now define the real number $A (x, ε)$ by $\begin{matrix} A (x, ε) : = max_{1 ⩽ n ⩽ N (x, ε)} log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]]), \end{matrix}$ and note that $E_{x} [e^{R (X_{0})} I [X_{0} \in S_{i}]] = e^{R (x)} ⩾ 1$ implies that $\begin{matrix} A (x, ε) ⩾ 0 . \end{matrix}$ Recalling that $x \in S_{i}$ is arbitrary, these three last displays together yield that $\begin{matrix} (3.6) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ e^{n (g_{i} + ε) + A_{i} (x, ε)}, x \in S_{i}, n = 1, 2, 3, \dots . \end{matrix}$ To conclude, it will be shown that $A_{i} (x, ε)$ can be selected independently of $x \in S_{i}$ . To achieve this goal, consider the following two exhaustive cases: Case 1 ( $S_{i} \cap supp (R) = \emptyset$ ).

In this context $E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] = P_{x} [X_{t} \in S_{i}, t ⩽ n - 1] ⩽ 1$ for every $x \in S_{i}$ . Thus, recalling that $g_{i} ⩾ 0$ (by (3.4)), it follows that (3.5) holds with $A_{i} (ε) = 0$ .

Case 2 ( $S_{i} \cap supp (R) \neq \emptyset$ ).

In this context set $\begin{matrix} A_{i} (ε) : = max_{x \in S_{i} \cap supp (R)} A (x, ε) ⩾ 0, \end{matrix}$ and observe that, for an arbitrary positive integer n, (3.6) leads to $\begin{matrix} (3.7) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ e^{n (g_{i} + ε) + A_{i} (ε)}, x \in S_{i} \cap supp (R) . \end{matrix}$ Next, select $x \in S_{i} ∖ supp (R)$ and note that $R (X_{t}) = 0$ for $t < T_{supp (R)}$ , so that $\begin{matrix} (3.8) & \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] \\ = \sum_{r = 1}^{n - 1} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} = r]] \\ + E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} ⩾ n]] \\ = \sum_{r = 1}^{n - 1} E_{x} [e^{\sum_{t = r}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} = r]] \\ + E_{x} [I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} ⩾ n]] \\ ⩽ \sum_{r = 1}^{n - 1} E_{x} [e^{\sum_{t = r}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} = r]] + P_{x} [T_{supp (R)} ⩾ n] . \end{matrix} \end{matrix}$ Next, given a positive integer $r < n$ , observe that the Markov property yields that $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = r}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} = r] ∣ X_{t}, t ⩽ r] \\ = I [X_{t} \in S_{i}, t ⩽ r, T_{supp (R)} = r] E_{X_{r}} [e^{\sum_{t = 0}^{n - r - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - r - 1]] \\ ⩽ I [X_{t} \in S_{i}, t ⩽ r, T_{supp (R)} = r] e^{(n - r) (g_{i} + ε) + A_{i} (ε)} \\ ⩽ I [T_{supp (R)} = r] e^{n (g_{i} + ε) + A_{i} (ε)}, \end{matrix} \end{matrix}$ where, using that $X_{r} \in S_{i} \cap supp (R)$ on the event $[X_{r} \in S_{i}, T_{supp (R)} = r]$ , the first inequality is due to (3.7), and the second one stems from the non-negativity of $g_{i}$ . Thus, $\begin{matrix} E_{x} [e^{\sum_{t = k}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1, T_{supp (R)} = r]] ⩽ P_{x} [T_{supp (R)} = r] e^{n (g_{i} + ε) + A_{i} (ε)}, \end{matrix}$ and combining this inequality with (3.8) it follows that $\begin{matrix} E_{x} [e^{\sum_{t = k}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ P_{x} [T_{supp (R)} ⩽ n - 1] e^{n (g_{i} + ε) + A_{i} (ε)} + P_{x} [T_{supp (R)} ⩾ n] . \end{matrix}$ Since $x \in S_{i} ∖ supp (R)$ is arbitrary and the numbers $g_{i}$ and $A_{i} (ε)$ are non-negative, the above relation yields that $\begin{matrix} E_{x} [e^{\sum_{t = k}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}, t ⩽ n - 1]] ⩽ e^{n (g_{i} + ε) + A_{i} (ε)}, x \in S_{i} ∖ supp (R) . \end{matrix}$ Thus, recalling that positive integer n is arbitrary, this last display and (3.7) together yield that (3.5) is also valid in the present case. □

Proof of Theorem 3.1.
Let $ε > 0$ be arbitrary and, for each $i \in {1, 2, \dots, k}$ , define $\begin{matrix} (3.9) & {\tilde{S}}_{i} : = ⋃_{j ⩽ i} S_{j} and {\tilde{A}}_{i} (ε) : = \sum_{1 ⩽ j ⩽ i} A_{j} (ε), \end{matrix}$ where $A_{1} (ε), \dots, A_{k} (ε)$ are the non-negative numbers in Lemma 3.3, so that the relations $\begin{matrix} (3.10) & {\tilde{A}}_{1} (ε) ⩽ {\tilde{A}}_{2} (ε) ⩽ \dots ⩽ {\tilde{A}}_{k} (ε) and {\tilde{A}}_{j} (ε) ⩾ A_{j} (ε), 1 ⩽ j ⩽ k, \end{matrix}$ hold. It will be verified, by induction, that the following assertion is valid for every positive integer $i ⩽ k$ : $\begin{matrix} (3.11) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] ⩽ n^{i - 1} e^{n (g_{i} + ε) + {\tilde{A}}_{i} (ε)}, x \in {\tilde{S}}_{i}, n = 1, 2, 3, \dots . \end{matrix}$

Suppose that $i = 1$ .

In this case ${\tilde{S}}_{1} = S_{1}$ and ${\tilde{A}}_{i} (ε) = A_{1} (ε)$ . Using that the set $S_{1}$ is closed with respect to the transition matrix P, by Definition 2.1(iii), it follows that for every $x \in {\tilde{S}}_{1}$ $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] = E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{1}, t ⩽ n - 1]], n = 1, 2, 3, \dots, \end{matrix}$ and then (3.11) follows from Lemma 3.3 with $i = 1$ .

Assume that (3.11) holds for a positive integer $i < k$ .

Using (2.4) and (3.10), observe that (3.11) yields that $\begin{matrix} (3.12) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] ⩽ n^{i} e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)}, x \in {\tilde{S}}_{i}, n = 1, 2, 3, \dots . \end{matrix}$ Next, let $x \in S_{i + 1}$ and the positive integer n be arbitrary, and observe that $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] = \sum_{m = 1}^{n - 1} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [T_{{\tilde{S}}_{i}} = m]] + E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [T_{{\tilde{S}}_{i}} ⩾ n]] . \end{matrix}$ Recalling that ${\tilde{S}}_{i + 1} = S_{i + 1} \cup {\tilde{S}}_{i}$ is closed with respect to the transition matrix P, observe that the following equalities hold $P_{x}$ -almost surely: $\begin{matrix} I [T_{{\tilde{S}}_{i}} ⩾ n] = [X_{t} \in S_{i + 1}, t ⩽ n - 1] and I [T_{{\tilde{S}}_{i}} = m] = [X_{t} \in S_{i + 1}, t ⩽ m - 1, X_{m} \in {\tilde{S}}_{i}] . \end{matrix}$ Combining these facts with the previous display it follows that $\begin{matrix} (3.13) & \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] = & \sum_{m = 1}^{n - 1} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} [X_{t} \in S_{i + 1}, t ⩽ m - 1, X_{m} \in {\tilde{S}}_{i}]] \\ + E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} [X_{t} \in S_{i + 1}, t ⩽ n - 1]] . \end{matrix} \end{matrix}$ Observe now that, by Lemma 3.3, the inclusion $x \in S_{i + 1}$ yields that $\begin{matrix} (3.14) & E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} [X_{t} \in S_{i + 1}, t ⩽ n - 1]] ⩽ e^{n (g_{i + 1} + ε) + A_{i + 1} (ε)} ⩽ e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)}, \end{matrix}$ where (3.10) was used to set the second inequality. On the other hand, for every $y \in {\tilde{S}}_{i}$ , an application of the Markov property leads to $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1, X_{m} = y] ∣ X_{t}, t ⩽ m] \\ = e^{\sum_{t = 0}^{m - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1] I [X_{m} = y] E_{y} [e^{\sum_{t = 0}^{n - m - 1} R (X_{t})}] \\ ⩽ e^{\sum_{t = 0}^{m - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1] I [X_{m} = y] {(n - m)}^{i - 1} e^{(n - m) (g_{i} + ε) + {\tilde{A}}_{i} (ε)}, \end{matrix} \end{matrix}$ where the inequality is due to the induction hypothesis. Therefore, $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1, X_{m} \in {\tilde{S}}_{i}]] \\ ⩽ E_{x} [e^{\sum_{t = 0}^{m - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1] I [X_{m} \in {\tilde{S}}_{i}]] {(n - m)}^{i - 1} e^{(n - m) (g_{i} + ε) + {\tilde{A}}_{i} (ε)} \\ ⩽ E_{x} [e^{\sum_{t = 0}^{m - 1} R (X_{t})} I [X_{t} \in S_{i + 1}, t ⩽ m - 1]] {(n - m)}^{i - 1} e^{(n - m) (g_{i} + ε) + {\tilde{A}}_{i} (ε)} \\ ⩽ e^{m (g_{i + 1} + ε) + A_{i + 1} (ε)} {(n - m)}^{i - 1} e^{(n - m) (g_{i} + ε) + {\tilde{A}}_{i} (ε)} \\ ⩽ e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)} n^{i - 1}, \end{matrix} \end{matrix}$ where the third inequality is due to Lemma 3.3, and the fourth one stems from (2.4) and (3.9). Combining the above display with (3.13) and (3.14) it follows that $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] ⩽ \sum_{m = 1}^{n - 1} e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)} n^{i - 1} + e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)}, \end{matrix}$ and then, since $x \in S_{i + 1}$ and the positive integer n are arbitrary, $\begin{matrix} E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}] ⩽ n^{i} e^{n (g_{i + 1} + ε) + {\tilde{A}}_{i + 1} (ε)}, x \in S_{i + 1}, n = 1, 2, 3, \dots . \end{matrix}$ Since ${\tilde{S}}_{i + 1} = S_{i + 1} \cup {\tilde{S}}_{i}$ , this last display and (3.12) together yield that assertion (3.11) is valid with $i + 1$ instead of i, completing the induction argument. To conclude, let $x \in S_{i} \subset {\tilde{S}}_{i}$ be arbitrary, and note that (3.11) implies that $\begin{matrix} J_{n} (x) = log (E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t})}]) ⩽ i log (n) + n (g_{i} + ε) + {\tilde{A}}_{i} (ε), \end{matrix}$ so that $\begin{matrix} \underset{n \to \infty}{lim sup} \frac{1}{n} J_{n} (x) ⩽ g_{i} + ε \end{matrix}$ and the conclusion of Theorem 3.1 follows, since $ε > 0$ is arbitrary. □

4. Contractive operators

The remainder of the paper is dedicated to establish Theorem 2.2, and the necessary tools are presented in this and the following two sections. As already mentioned, the approach relies on the discounted operators introduced below which, in the context of a finite state space, were used in Cavazos-Cadena and Hernández-Hernández [6] to approximate the Varadhan function, and in [1] to characterize the optimal average value function for controlled Markov chains under risk-aversion.

Definition 4.1.
Given $α \in (0, 1)$ , the operator $T_{α} : B (S) \to B (S)$ is specified as follows: For each $V \in B (S)$ , $\begin{matrix} (4.1) & T_{α} [V] (x) = log (e^{R (x)} \sum_{y \in S} p_{x, y} e^{α V (y)}), x \in S . \end{matrix}$

From this definition, the following monotonicity and α-homogeneity properties of an operator $T_{α}$ can be obtained:
If $V, W \in B (S)$ are such that $V ⩽ W$ , then $T_{α} [V] ⩽ T_{α} [W]$ ;

$T [V + r] = T [V] + α r$ for each $V \in B (S)$ and $r \in R$ .
Combining these two properties with the relation $W - ∥ W - V ∥ ⩽ V ⩽ W + ∥ W - V ∥$ , it follows that $\begin{matrix} T [W] - α ∥ W - V ∥ ⩽ T [V] ⩽ T [W] + α ∥ W - V ∥, \end{matrix}$ that is, $\begin{matrix} (4.2) & ∥ T [W] - T [V] ∥ ⩽ α ∥ V - W ∥, V, W \in B (S), \end{matrix}$ so that, for each $α \in (0, 1)$ , the operator $T_{α}$ is a contractive on the space $B (S)$ endowed with the supremum norm. Therefore, by Banach’s fixed point theorem, there exists a unique function $V_{α} \in B (S)$ satisfying $T_{α} [V_{α}] = V_{α}$ ; note that (4.2) yields that $\begin{matrix} (4.3) & ∥ V_{α} - T_{α}^{n} [W] ∥ = ∥ T_{α}^{n} [V_{α}] - T_{α}^{n} [W] ∥ ⩽ α^{n} ∥ V_{α} - W ∥ \to 0 as n \to \infty, W \in B (S), \end{matrix}$ where $T_{α}^{n}$ is the nth fold composition of $T_{α}$ with itself. Observe that, by (4.1), the equality $T_{α} [V_{α}] = V_{α}$ is equivalent to $\begin{matrix} (4.4) & e^{V_{α} (x)} = e^{R (x)} \sum_{y \in S} p_{x, y} e^{α V_{α} (y)}, x \in S, α \in (0, 1), \end{matrix}$ whereas $T_{α} [0] (x) = R (x)$ for each $x \in S$ . Hence, (4.2) yields that $\begin{matrix} ∥ V_{α} - R ∥ = ∥ T_{α} [V_{α}] - T [0] ∥ ⩽ α ∥ V_{α} - 0 ∥ = α ∥ V_{α} ∥, \end{matrix}$ and combining this relation with the inequality $∥ V_{α} - R ∥ ⩾ ∥ V_{α} ∥ - ∥ R ∥$ , it follows that $\begin{matrix} (4.5) & (1 - α) ∥ V_{α} ∥ ⩽ ∥ R ∥ . \end{matrix}$ In the following sections, the family ${V_{α}}_{α \in (0, 1)}$ of fixed points will be used to build a system of local Poisson equations. The construction relies on the relations on the state space introduced in the following definition. First, using Cantor’s diagonal method, select a sequence ${α_{m}} \subset (0, 1)$ such that the following requirements are satisfied: $\begin{matrix} (4.6) & α_{m} ↗ 1 as m ↗ \infty, \end{matrix}$ and $\begin{matrix} (4.7) & \begin{matrix} for every x, y \in S, the following limits exist: \\ lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] \in [- \infty, \infty] and lim_{m \to \infty} (1 - α_{m}) V_{α_{m}} (x) \in [- ∥ R ∥, ∥ R ∥], \end{matrix} \end{matrix}$ where the second inclusion follows from (4.5). Throughout the remainder of the paper the sequence ${α_{m}}$ satisfying these two last properties will be kept fixed.
Definition 4.2.

The relation ‘⪰’ on the state space S is defined as follows: For each $x, y \in S$ , $\begin{matrix} x ⪰ y ⟺ lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] > - \infty; \end{matrix}$ $x ⪰ y$ is read as ‘x dominates y’.

For $x, y \in S$ , $\begin{matrix} (4.8) & x \sim y ⟺ x ⪰ y and y ⪰ x . \end{matrix}$

From this definition and (4.7) it is not difficult to see that

‘⪰’ is a total order in S: for every $x, y \in S$ , at least one of $x ⪰ y$ or $y ⪰ x$ is valid;

‘⪰’ is transitive, that is for every states $x, y, z \in S$ , $\begin{matrix} (4.9) & x ⪰ y and y ⪰ z \Rightarrow x ⪰ z . \end{matrix}$

‘∼’ is an equivalence relation which can be more directly described as follows: $\begin{matrix} (4.10) & x \sim y ⟺ lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] \in R, \end{matrix}$ so that $\begin{matrix} (4.11) & x ≁ y ⟺ lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] = \infty or lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] = - \infty; \end{matrix}$ see (4.7). Also observe that $\begin{matrix} (4.12) & \begin{matrix} if x \sim x_{1} and y \sim y_{1} and lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] = \infty, \\ then lim_{m \to \infty} [V_{α_{m}} (x_{1}) - V_{α_{m}} (y_{1})] = \infty . \end{matrix} \end{matrix}$
Lemma 4.1.

If $R \in B (S)$ is non-negative, then $V_{α} ⩾ 0$ for every $α \in (0, 1)$ ;

For each state $x \in S$ , the set of all states that are dominated by x is closed with respect to the transition matrix $P = [p_{x, y}]$ . More explicitly, $\begin{matrix} p_{x, y} > 0 \Rightarrow x ⪰ y, x, y \in S . \end{matrix}$

Proof.

Let $α \in (0, 1)$ be arbitrary. As already noted, $T [0] = R$ , so that $T [0] ⩾ 0$ when R is non-negative. In this case the monotonicity of $T_{α}$ yields that $T_{α}^{n} [0] ⩾ 0$ for every positive integer n, and the desired conclusion follows via (4.3).

Let $x, y \in S$ be arbitrary, and note that (4.4) yields that $e^{V_{α} (x)} ⩾ e^{R (x)} p_{x, y} e^{α V_{α} (y)}$ ; combining this relation with the inequality $∥ R ∥ ⩾ (1 - α) V_{α} (x)$ obtained from (4.5), it follows that $e^{∥ R ∥ + α [V_{α} (x) - V_{α} (y)]} ⩾ e^{R (x)} p_{x, y}$ . From this point, replacing α by $α_{m}$ and taking the limit as m goes to ∞, (4.6) and (4.7) together imply that $\begin{matrix} e^{∥ R ∥ + {lim}_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)]} ⩾ e^{R (x)} p_{x, y}, \end{matrix}$ and then $\begin{matrix} p_{x, y} > 0 \Rightarrow lim_{m \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (y)] > - \infty \Rightarrow x ⪰ y; \end{matrix}$ see Definition 4.2. □

In the remainder of the paper the relations in Definition 4.2 will be used to build a system of local Poisson equations.
5. Partition of the state space and local rates

In this and the following section the relations introduced in Definition 4.2 will be used to construct the components of the triplets comprising a system of local Poisson equations. The present objective is to build the first two components, namely, a partition of the state space and the numbers (local rates) associated to each set in the partition as in Definition 2.1. Throughout the remainder of the paper, even without explicit reference, it is supposed that Assumption 2.1 holds, and the finite set $G \subset S$ is defined by $\begin{matrix} (5.1) & G : = F \cup supp (R) . \end{matrix}$ The starting point of the argument, which concerns the equivalence relation in Definition 4.2(ii), is stated in the following theorem and can be roughly described as follows: Every state is equivalent to some member of G.

Theorem 5.1.
Under Assumption 2.1, for each $x \in S$ there exists a state $x^{} \in G$ such that* $x \sim x^{}$ . Moreover, if* $x \notin G$ , then $P_{x} [X_{T_{G}} = x^{}] > 0$ .

The proof of this result relies on the following lemma. First, note that the inclusion $F \subset G$ and (2.1) together yield that $T_{G} ⩽ T_{F}$ , and then Assumption 2.1 yields that $\begin{matrix} (5.2) & P_{x} [T_{G} < \infty] = 1, x \in S . \end{matrix}$ Also, set $\begin{matrix} (5.3) & g_{α} (x) : = (1 - α) V_{α} (x) \in [0, ∥ R ∥], x \in S, α \in (0, 1), \end{matrix}$ where, using that the reward function R is non-negative, the inclusion follows from (4.5) and Lemma 4.1.
Lemma 5.1.
Suppose that Assumption* 2.1 holds. In this case, for each $α \in (0, 1)$ the following assertions (i) and (ii) are valid:
For each positive integer n and $x \in S$ , $\begin{matrix} (5.4) & e^{α V_{α} (x)} = E_{x} [e^{\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land n})}] . \end{matrix}$

For each $x \in S$ $\begin{matrix} (5.5) & e^{α V_{α} (x)} = e^{R (x)} E_{x} [e^{- \sum_{t = 0}^{T_{G} - 1} g_{α} (X_{t}) + α V_{α} (X_{T_{G}})}] . \end{matrix}$

Proof.

The proof is by induction. Combining (4.4) with (5.3) it follows that $\begin{matrix} (5.6) & e^{α V_{α} (x)} = e^{R (x) - g_{α} (x)} \sum_{y \in S} p_{x, y} e^{α V_{α} (y)} = E_{x} [e^{R (X_{0}) - g_{α} (X_{0}) + α V_{α} (X_{1})}], x \in S, \end{matrix}$ and using that $T_{G} ⩾ 1$ , it follows that (5.4) occurs with when $n = 1$ . Now suppose that (5.4) holds for certain positive integer n and apply the Markov property to obtain that $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land n})} I [T_{G} > n] ∣ X_{t}, t ⩽ n] \\ = E_{x} [e^{\sum_{t = 0}^{n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{n})} I [T_{G} > n] ∣ X_{t}, t ⩽ n] \\ = e^{\sum_{t = 0}^{n - 1} [R (X_{t}) - g_{α} (X_{t})]} I [T_{G} > n] e^{α V_{α} (X_{n})} \\ = e^{\sum_{t = 0}^{n - 1} [R (X_{t}) - g_{α} (X_{t})]} I [T_{G} > n] E_{X_{n}} [e^{R (X_{n}) - g_{α} (X_{n}) + α V_{α} (X_{n + 1})}] \\ = E_{x} [e^{\sum_{t = 0}^{n - 1} [R (X_{t}) - g_{α} (X_{t})]} I [T_{G} > n] e^{R (X_{n}) - g_{α} (X_{n}) + α V_{α} (X_{n + 1})} ∣ X_{t}, t ⩽ n], \end{matrix} \end{matrix}$ where the third equality is due to (5.6). Thus, $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land n})} I [T_{G} > n]] \\ = E_{x} [e^{\sum_{t = 0}^{n} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{n + 1})} I [T_{G} > n]]; \end{matrix} \end{matrix}$ observing that $T_{G} \land (n + 1) = n + 1$ on the event $[T_{G} > n]$ , the above equality can be written as $\begin{matrix} (5.7) & \begin{matrix} E_{x} [e^{\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land n})} I [T_{G} > n]] \\ = E_{x} [e^{\sum_{t = 0}^{T_{G} \land (n + 1) - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land (n + 1)})} I [T_{G} > n]] . \end{matrix} \end{matrix}$ To conclude, note that $T_{G} \land n = T_{G} \land (n + 1)$ on the event $[T_{G} ⩽ n]$ , so that $\begin{matrix} \begin{matrix} E_{x} [e^{\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land n})} I [T_{G} ⩽ n]] \\ = E_{x} [e^{\sum_{t = 0}^{T_{G} \land (n + 1) - 1} [R (X_{t}) - g_{α} (X_{t})] + α V_{α} (X_{T_{G} \land (n + 1)})} I [T_{G} ⩽ n]] . \end{matrix} \end{matrix}$ Combining these two last displays with the induction hypothesis, it follows that (5.4) also holds with $n + 1$ instead of n, completing the induction argument.

By (5.1), the support of R is contained in G. Since $X_{t} \notin G$ when $1 ⩽ t < T_{G}$ , by (2.1), it follows that $\sum_{t = 0}^{T_{G} \land n - 1} [R (X_{t}) - g_{α} (X_{t})] = R (X_{0}) - \sum_{t = 0}^{T_{G} \land n - 1} g_{α} (X_{t})$ for every positive integer n, and then part (i) yields that $\begin{matrix} (5.8) & e^{α V_{α} (x)} = e^{R (x)} E_{x} [e^{- \sum_{t = 0}^{T_{G} \land n - 1} g_{α} (X_{t}) + α V_{α} (X_{T_{G} \land n})}] . \end{matrix}$ Next, observe that $\begin{matrix} lim_{n \to \infty} e^{- \sum_{t = 0}^{T_{G} \land n - 1} g_{α} (X_{t}) + α V_{α} (X_{T_{G} \land n})} = e^{- \sum_{t = 0}^{T_{G} - 1} g_{α} (X_{t}) + α V_{α} (X_{T_{G}})} on [T_{G} < \infty], \end{matrix}$ whereas (4.5) and the non-negativity of $g_{α} (\cdot)$ (see (5.3)) together yield that $\begin{matrix} 0 ⩽ e^{- \sum_{t = 0}^{T_{G} \land n - 1} g_{α} (X_{t}) + α V_{α} (X_{T_{G} \land n})} ⩽ e^{α ∥ R ∥ / (1 - α)} . \end{matrix}$ Using (5.2), taking the limit as n goes to ∞ in (5.8), via the bounded convergence theorem the two last display together lead to (5.5). □

Proof of Theorem 5.1.
Since ‘∼’ is an equivalence relation, it is sufficient to prove the assertion in the theorem for x outside G.

Let $x \in S ∖ G$ be arbitrary. Define the set $G_{x}$ by $\begin{matrix} (5.9) & G_{x} : = {y \in G ∣ P_{x} [X_{T_{G}} = y] > 0}, \end{matrix}$ and note that, since $X_{T_{G}} \in G$ on the event $[T_{G} < \infty]$ and $P_{x} [T_{G} < \infty] = 1$ , (5.2) implies that $G_{x} \neq \emptyset$ . It will be proved that $\begin{matrix} (5.10) & y ⪰ x for some y \in G_{x} . \end{matrix}$ To achieve this goal, first note that $R (x) = 0$ , since $x \notin G$ , and recalling that $g_{α} (\cdot)$ is non-negative, use Lemma 5.1(ii) to obtain that $e^{α V_{α} (x)} ⩽ E_{x} [e^{α V_{α} (X_{T_{G}})}] = E_{x} [e^{α V_{α} (X_{T_{G}})} I [X_{T_{G}} \in G_{x}]]$ for every $α \in (0, 1)$ , so that $\begin{matrix} (5.11) & 1 ⩽ E_{x} [e^{α [V_{α} (X_{T_{G}}) - V_{α} (x)]} I [X_{T_{G}} \in G_{x}]] . \end{matrix}$ Proceeding by contradiction, assume that $y ⋡ x$ for every $y \in G_{x}$ . In this case Definition 4.2(i) and (4.7) together yield that $\begin{matrix} lim_{m \to \infty} [V_{α_{m}} (y) - V_{α_{m}} (x)] = - \infty, y \in G_{x}; \end{matrix}$ since $G_{x}$ is finite, after replacing α by $α_{m}$ in (5.11) and taking the limit as m goes to ∞ in the resulting inequality, the above displayed condition leads to $1 ⩽ 0$ , which is a contradiction, so that (5.10) holds. Now observe that (4.9) and Lemma 4.1(ii) yield that $x ⪰ y$ when $P_{x} [T_{G} = y]$ is positive, so that, by (5.9), $\begin{matrix} x ⪰ y for all y \in G_{x}; \end{matrix}$ since $\emptyset \neq G_{x} \subset G$ , this last display and (5.10) together imply that $x \sim x^{}$ for some $x^{} \in G_{x} \subset G$ . To conclude, note that the inclusion $x^{} \in G_{x}$ and (5.9) yield that $P_{x} [T_{G} = x^{}] > 0$ . □

Recalling that G is a finite set, Theorem 5.1 yields that the family of equivalence classes with respect to ‘∼’ is finite and consists of at most k sets, where $\begin{matrix} (5.12) & k ⩽ # G ⩽ # F + # supp (R), \end{matrix}$ and, for each set $B \subset S$ , $# B$ stands for the number of elements of B. Throughout the remainder, $\begin{matrix} (5.13) & S_{1}^{}, S_{2}^{}, \dots, S_{k}^{} is the partition of S into equivalence classes induced by ‘ \sim ’ \end{matrix}$ and, with this notation, Theorem 5.1 immediately implies the following conclusion.
Corollary 1.
For each* $i = 1, 2, \dots, k$ , $S_{i}^{} \cap G \neq \emptyset$ . Moreover,* $P_{x} [X_{T_{G}} \in S_{i}^{}] > 0$ for each* $x \in S_{i}^{} ∖ G$ .

Next, a total order in the family of equivalence classes is introduced.
Definition 5.1.
If $E$ and $E^{'}$ are two different equivalence classes with respect to the equivalence relation ‘∼’ in Definition 4.2(ii), then $\begin{matrix} E ≺ E^{'} ⟺ lim_{m \to \infty} [V_{α_{m}} (y) - V_{α_{m}} (x)] = \infty for some y \in E^{'} and some x \in E . \end{matrix}$

By (4.7), (4.11) and (4.12), this relation ‘≺’ is well defined and is a strict total order, that is, if $E$ and $E^{'}$ are two different equivalences classes, then exactly one of $E ≺ E^{'}$ or $E^{'} ≺ E$ occurs; also, note that the above definition and (4.12) together yield that $\begin{matrix} (5.14) & E ≺ E^{'} ⟺ lim_{m \to \infty} [V_{α_{m}} (y) - V_{α_{m}} (x)] = \infty for all y \in E^{'} and all x \in E . \end{matrix}$ Without loss of generality, throughout the remainder the different equivalence classes $S_{i}^{}$ are labeled in such a way that $\begin{matrix} (5.15) & S_{i}^{} ≺ S_{i + 1}^{}, 1 ⩽ i < k . \end{matrix}$
Lemma 5.2.
For every $i = 1, 2, \dots, k$ , the set $S_{1}^{} \cup S_{2}^{} \cup \dots \cup S_{i}^{}$ is closed with respect to the transition matrix* $P = [p_{x, y}]$ , that is, $\begin{matrix} (5.16) & \sum_{y \in S_{1}^{} \cup S_{2}^{} \cup \dots \cup S_{i}^{}} p_{x, y} = 1, x \in S_{i}^{} . \end{matrix}$
Proof.
Let $i \in {1, 2, \dots, k}$ and $x \in S_{i}^{}$ be fixed. Now, suppose that the integer j is such that $k ⩾ j > i$ and let $y \in S_{j}^{}$ be arbitrary. In this case $S_{i}^{} ≺ S_{j}^{}$ , by (5.15), and then (5.14) yields that $\begin{matrix} lim_{m \to \infty} [V_{α_{m}} (y) - V_{α_{m}} (x)] = \infty, \end{matrix}$ so that $x ⋡ y$ , by Definition 4.2(i). From this point, Lemma 4.1 yields that $p_{x, y} = 0$ . Hence, $\begin{matrix} p_{x, y} = 0 when x \in S_{i}^{} and y \in S_{j}^{} with k ⩾ j > i, \end{matrix}$ and the conclusion follows, since $S_{1}^{}, S_{2}^{}, \dots, S_{k}^{}$ is a partition of the state space. □

Now, a number will be associated to each equivalence class $S_{i}^{}$ .
Definition 5.2.
For $i \in {1, 2, \dots, k}$ , select a point $x_{i} \in S_{i}^{}$ and define the local rate $g_{i}$ by $\begin{matrix} (5.17) & g_{i}^{} : = lim_{m \to \infty} g_{α_{m}} (x_{i}) . \end{matrix}$

Since ${V_{α_{m}} (x) - V_{α_{m}} (x_{i})}_{m = 1, 2, 3, \dots}$ is a convergent sequence when $x \sim x_{i} \in S_{i}^{}$ , (4.6) and (5.3) yield that the value of $g_{i}^{}$ does not depend on the choice of $x_{i}$ , that is, $\begin{matrix} (5.18) & g_{i}^{} = lim_{m \to \infty} g_{α_{m}} (x), x \in S_{i}^{} . \end{matrix}$ Lemma 5.3.
The local rates $g_{i}^{}$ in Definition* 5.2 are increasing: $\begin{matrix} g_{i}^{} ⩽ g_{i + 1}^{}, 1 ⩽ i < k . \end{matrix}$
Proof.
Let $y \in S_{i + 1}^{}$ and $x \in S_{i}^{}$ be arbitrary. In this case Definition 5.1 and (5.15) together yield that the sequence ${V_{α_{m}} (y) - V_{α_{m}} (x)}_{m = 1, 2, 3, \dots}$ converges to ∞, and then it is bounded below, that is $\begin{matrix} V_{α_{m}} (y) - V_{α_{m}} (x) ⩾ M, m = 1, 2, 3, \dots \end{matrix}$ for a certain constant M. Multiplying both sides of this inequality by $(1 - α_{m})$ it follows that $g_{α_{m}} (y) - g_{α_{m}} (x) ⩾ (1 - α_{m}) M$ and, after taking the limit as m goes to ∞, (4.6) and (5.18) yield that $g_{i + 1}^{} ⩾ g_{i}^{}$ . □

6. Relative value functions

In this section a function $h_{i}^{*}$ will be associated with each set $S_{i}^{*}$ in (5.13). For each $x \in S_{i}^{*}$ , the number $h_{i}^{*} (x)$ will be obtained from the relative value of $V_{α_{m}} (x)$ with respect to an appropriately chosen element of $S_{i}^{*} \cap G$ , and taking the limit as m goes to ∞. To begin with, consider an index $i \in {1, 2, \dots, k}$ and, using Corollary 1 and the finiteness of G, given an integer m select $x_{m, i}^{*} \in S_{i}^{*} \cap G$ such that $V_{α_{m}} (x_{m, i}) ⩾ V_{α_{m}} (x)$ for every $x \in S_{i}^{*} \cap G$ . Via Cantor’s diagonal method, after taking an appropriate subsequence of ${α_{m}}$ , without loss of generality it can be assumed that each sequence ${x_{m, i}^{*}}_{m = 1, 2, 3, \dots}$ is constant, say $x_{m, i}^{*} = x_{i}^{*}$ , so that, for every $i \in {1, 2, \dots, k}$ , $\begin{matrix} (6.1) & x_{i}^{*} \in S_{i}^{*} \cap G and V_{α_{m}} (x_{i}^{*}) ⩾ V_{α_{m}} (x), x \in S_{i}^{*} \cap G, m = 1, 2, 3, \dots . \end{matrix}$

The following extensions of this property will be useful.

Lemma 6.1.
For each $i \in {1, 2, \dots, k}$ , the following assertions hold: There exist positive integers $M_{i}$ and ${\tilde{M}}_{i}$ such that $\begin{matrix} (6.2) & V_{α_{m}} (x) ⩽ V_{α_{m}} (x_{i}^{}), x \in S_{i}^{}, m ⩾ M_{i}, \end{matrix}$ and $\begin{matrix} (6.3) & V_{α_{m}} (x) ⩽ V_{α_{m}} (x_{i}^{}), x \in ⋃_{1 ⩽ j ⩽ i} S_{j}^{}, m ⩾ {\tilde{M}}_{i} . \end{matrix}$
Proof.
Let the index i between 1 and k and $x \in S_{i}^{} ∖ G$ be arbitrary. In this case, it was established in the proof of Theorem 5.1 that the inequality (5.11) occurs, and it follows that $\begin{matrix} 1 ⩽ E_{x} [e^{α_{m} [V_{α_{m}} (X_{T_{G}}) - V_{α_{m}} (x)]}], m = 1, 2, 3, \dots . \end{matrix}$ Using that $⋃_{j ⩽ i} S_{j}^{}$ is closed with respect to the transition matrix P, the inclusion $x \in S_{i}^{} ∖ G$ and (5.2) yield that $1 = P_{x} [X_{T_{G}} \in ⋃_{j ⩽ i} S_{j}^{}]$ . Since ${S_{j}^{}, 1 ⩽ j ⩽ k}$ is a partition of the state space, it follows that $\begin{matrix} \begin{matrix} E_{x} [e^{α_{m} [V_{α_{m}} (X_{T_{G}}) - V_{α_{m}} (x)]}] & = \sum_{j = 1}^{i} E_{x} [e^{α_{m} [V_{α_{m}} (X_{T_{G}}) - V_{α_{m}} (x)]} I [X_{T_{G}} \in S_{j}^{}]] \\ ⩽ \sum_{j = 1}^{i} E_{x} [e^{α_{m} [V_{α_{m}} (x_{j}^{}) - V_{α_{m}} (x)]} I [X_{T_{G}} \in S_{j}^{}]] \\ = \sum_{j = 1}^{i} e^{α_{m} [V_{α_{m}} (x_{j}^{}) - V_{α_{m}} (x)]} P_{x} [X_{T_{G}} \in S_{j}^{}], \end{matrix} \end{matrix}$ where the inequality is due to (6.1). Since $x \in S_{i}^{}$ and $S_{i}^{} ≻ S_{j}^{}$ for $j < i$ , it follows from (5.14) that there exists a positive integer $M_{i}$ such that $\begin{matrix} (6.4) & V_{α_{m}} (x_{j}^{}) - V_{α_{m}} (x_{i}^{}) < 0, j < i, m ⩾ M_{i}, \end{matrix}$ and combining these relation with the two previous displays it follows that $\begin{matrix} \begin{matrix} 1 ⩽ E_{x} [e^{α_{m} [V_{α_{m}} (X_{T_{G}}) - V_{α_{m}} (x)]}] \\ ⩽ \sum_{j ⩽ i} P_{x} [X_{T_{G}} \in S_{j}^{}] e^{α_{m} [V_{α_{m}} (x_{i}^{}) - V_{α_{m}} (x)]} = e^{α_{m} [V_{α_{m}} (x_{i}^{}) - V_{α_{m}} (x)]}, m ⩾ M_{i}; \end{matrix} \end{matrix}$ since $x \in S_{i}^{} ∖ G$ is arbitrary and $α_{m}$ is positive it follows that $\begin{matrix} V_{α_{m}} (x_{i}^{}) ⩾ V_{α_{m}} (x), x \in S_{i}^{} ∖ G, m ⩾ M_{i}, \end{matrix}$ and (6.2) follows combining this relation and (6.1). Finally, setting ${\tilde{M}}_{i} = {max}_{1 ⩽ j ⩽ i} M_{j}$ , (6.2) and (6.4) together imply assertion (6.3). □
Definition 6.1.
For each index i between 1 and k, the relative value function $h_{i}^{}$ on $S_{i}^{}$ is defined by $\begin{matrix} h_{i}^{} (x) = lim_{n \to \infty} [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{})], x \in S_{i}^{} . \end{matrix}$

The following result establishes two basic properties of the functions $h_{i}^{} (\cdot)$ . Lemma 6.2.
For each* $i = 1, 2, \dots, k$ , $\begin{matrix} (6.5) & h_{i}^{} (x) \in (- \infty, 0] for each x \in S_{i}^{}, \end{matrix}$ and the following local Poisson equation is satisfied: $\begin{matrix} (6.6) & e^{g_{i}^{} + h_{i}^{} (x)} = e^{R (x)} \sum_{y \in S_{i}^{}} p_{x, y} e^{h_{i}^{} (y)}, x \in S_{i}^{} . \end{matrix}$
Proof.
Let $x \in S_{i}^{}$ be arbitrary. In this case $x \sim x_{i}^{}$ , and then Definition 6.1, (4.10) and (6.2) together yield that $h_{i}^{} (x)$ is a finite non-positive number, establishing (6.5). On the other hand, replacing α by $α_{m}$ in (4.4) and multiplying both sides of the resulting equality by $e^{- V_{α_{m}} (x_{i}^{})}$ it follows that $\begin{matrix} (6.7) & \begin{matrix} e^{g_{α_{m}} (x_{i}^{}) + [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{})]} & = e^{R (x)} \sum_{y \in S} p_{x, y} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{})]} \\ = e^{R (x)} \sum_{1 ⩽ j ⩽ i} \sum_{y \in S_{j}^{}} p_{x, y} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{})]}, \end{matrix} \end{matrix}$ where the second equality is due to the fact that $⋃_{1 ⩽ j ⩽ i} S_{j}^{}$ is closed with respect to the transition matrix P. Next observe that (6.3) yields that, for m large enough, $\begin{matrix} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{})]} ⩽ 1, y \in ⋃_{1 ⩽ j ⩽ i} S_{j}^{}, \end{matrix}$ and that (5.14) and (5.15) imply that $\begin{matrix} lim_{m \to \infty} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{})]} = 0, y \in ⋃_{1 ⩽ j < i} S_{j}^{}, \end{matrix}$ whereas $\begin{matrix} lim_{m \to \infty} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{})]} = e^{h_{i}^{} (y)}, y \in S_{i}^{}, \end{matrix}$ by Definition 6.1. Taking the limit as m goes to ∞ in (6.7), via the bounded convergence theorem the three last displays together lead to (6.6). □

7. The system of local Poisson equations

In this section Theorem 2.2 will be finally proved. Define $\begin{matrix} (7.1) & P^{*} : = ((S_{1}^{*}, g_{1}^{*}, h_{1}^{*}), \dots, (S_{k}^{*}, g_{k}^{*}, h_{k}^{*})), \end{matrix}$ where the sets $S_{i}^{*}$ are as in (5.13), whereas the local rates $g_{i}^{*}$ and the relative value functions $h_{i}^{*}$ are as in Definitions 5.2 and 6.1, respectively.

Proof of Theorem 2.2.

It will be verified that the five properties in Definition 2.1 are satisfied by $P^{*}$ . Note that condition (i) holds, by (5.13), and that Lemmas 5.3 and 6.2 together show that condition (ii) is also valid, whereas properties (iii) and (iv) follow from Lemmas 5.2 and 6.2. To verify that the property in part (v) of Definition 2.1 is satisfied by $P^{*}$ , it must be proved that, for every index i between 1 and k, $\begin{matrix} (7.2) & \underset{n \to \infty}{lim inf} E_{ν_{i, x, n}^{*}} {[e^{h_{i}^{*} (X_{n})}]}^{1 / n} ⩾ 1, x \in S_{i}^{*}, \end{matrix}$ where, for each positive integer n, $E_{ν_{i, x, n}^{*}} [\cdot]$ is the expectation operator with respect to the measure $ν_{i, x, n}^{*}$ on ${S_{i}^{*}}^{n}$ given in (2.8) with $S_{i}^{*}$ instead of $S_{i}$ . Combining Lemma 3.1 and Remark 2.2(ii), the above property is equivalent to $\begin{matrix} (7.3) & e^{g_{i}^{*}} ⩾ \underset{n \to \infty}{lim sup} E_{x} {[e^{\sum_{t = 0}^{n - 1} R (X_{t})} I [X_{t} \in S_{i}^{*}, t ⩽ n - 1]]}^{1 / n}, x \in S_{i}^{*}, \end{matrix}$ a relation that will be now verified: Let $x_{i}^{*}$ be as in (6.1) and, given a positive integer m, replace α by $α_{m}$ in (4.4) and multiply both sides of the resulting inequality by $e^{- V_{α_{m}} (x_{i}^{*})}$ to obtain, via Definition 5.2, that $\begin{matrix} (7.4) & \begin{matrix} e^{g_{α_{m}} (x_{i}^{*}) + [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{*})]} & = e^{R (x)} \sum_{y \in S} p_{x, y} e^{α_{m} [V_{α_{m}} (y) - V_{α_{m}} (x_{i}^{*})]} \\ = E_{x} [e^{R (X_{0}) + α_{m} [V_{α_{m}} (X_{1}) - V_{α_{m}} (x_{i}^{*})]}], x \in S . \end{matrix} \end{matrix}$ Next, set $\begin{matrix} {\tilde{S}}_{i}^{*} : = ⋃_{1 ⩽ j ⩽ i} S_{j}^{*} \end{matrix}$ and, using that ${\tilde{S}}_{i}^{*}$ is closed with respect to the transition matrix P, by Lemma 5.2, note that (7.4) yields that $\begin{matrix} e^{g_{α_{m}} (x_{i}^{*}) + [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{*})]} = E_{x} [e^{R (X_{0}) + α_{m} [V_{α_{m}} (X_{1}) - V_{α_{m}} (x_{i}^{*})]} I [X_{1} \in {\tilde{S}}_{i}^{*}]], x \in {\tilde{S}}_{i}^{*} . \end{matrix}$ Now, select an arbitrary but fixed integer m such that $m ⩾ {\tilde{M}}_{i}$ , where ${\tilde{M}}_{i}$ is the positive integer in (6.2), so that $\begin{matrix} V_{α_{m}} (X_{1}) - V_{α_{m}} (x_{i}^{*}) ⩽ 0 on the event [X_{1} \in {\tilde{S}}_{i}^{*}], \end{matrix}$ a property that combined with the previous display leads to $\begin{matrix} e^{g_{α_{m}} (x_{i}^{*}) + [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{*})]} ⩾ E_{x} [e^{R (X_{0}) + [V_{α_{m}} (X_{1}) - V_{α_{m}} (x_{i}^{*})]} I [X_{1} \in {\tilde{S}}_{i}^{*}]], x \in {\tilde{S}}_{i}^{*} . \end{matrix}$ From this point, an induction argument similar to the one used to establish Lemma 3.1 yields that, for every positive integer n and $x \in {\tilde{S}}_{i}^{*}$ $\begin{matrix} e^{n g_{α_{m}} (x_{i}^{*}) + [V_{α_{m}} (x) - V_{α_{m}} (x_{i}^{*})]} ⩾ E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) + [V_{α_{m}} (X_{n}) - V_{α_{m}} (x_{i}^{*})]} I [X_{t} \in {\tilde{S}}_{i}^{*}, t ⩽ n]], \end{matrix}$ and then, recalling that $∥ V_{α_{m}} (\cdot) ∥ ⩽ ∥ R ∥ / (1 - α_{m})$ this yields to $\begin{matrix} \begin{matrix} e^{n g_{α_{m}} (x_{i}^{*}) + 2 ∥ R ∥ / (1 - α_{m})} & ⩾ E_{x} [e^{\sum_{t = 0}^{n - 1} R (X_{t}) - 2 ∥ R ∥ / (1 - α_{m})} I [X_{t} \in {\tilde{S}}_{i}^{*}, t ⩽ n]] \\ ⩾ e^{- ∥ R ∥ - 2 ∥ R ∥ / (1 - α_{m})} E_{x} [e^{\sum_{t = 0}^{n} R (X_{t})} I [X_{t} \in {\tilde{S}}_{i}^{*}, t ⩽ n]], x \in {\tilde{S}}_{i}^{*} . \end{matrix} \end{matrix}$ Since $S_{i}^{*} \subset {\tilde{S}}_{i}^{*}$ , it follows that, for every integer $n > 0$ and $x \in S_{i}^{*}$ , $\begin{matrix} e^{n g_{α_{m}} (x_{i}^{*}) + ∥ R ∥ + 4 ∥ R ∥ / (1 - α_{m})} ⩾ E_{x} [e^{\sum_{t = 0}^{n} R (X_{t})} I [X_{t} \in S_{i}^{*}, t ⩽ n]], \end{matrix}$ an inequality that immediately leads to $\begin{matrix} e^{g_{α_{m}} (x_{i}^{*})} ⩾ \underset{n \to \infty}{lim sup} E_{x} {[e^{\sum_{t = 0}^{n} R (X_{t})} I [X_{t} \in S_{i}^{*}, t ⩽ n]]}^{1 / (n + 1)}, x \in S_{i}^{*} . \end{matrix}$ Thus, since $m ⩾ {\tilde{M}}_{i}$ is arbitrary, after taking the limit as m goes to ∞ in the left-hand side of the above relation, the desired inequality (7.3) follows via (5.18). Summarizing, it has been shown that $P^{*}$ in (7.1) is a system of local Poisson equations for the reward function R and the transition law P, completing the proof. □

Footnotes

Acknowledgements

The authors are sincerely grateful to the reviewer by his careful reading of the original manuscript, constructive criticism and helpful suggestions to improve the paper. This work was partially supported by the PSF Organization under Grant No. 2-450-14, by PRODEP under Grant No. 17332-CA-23 and by CONACYT under Grant No. Laboratorio LEMME.

References

[1]

Alanís-Durán and

Cavazos-Cadena, An optimality system for finite average Markov decision chains under risk-aversion, Kybernetika 48 (2012), 83–104.

[2]

Biswas,

V.S.

Borkar and

Suresh Kumar, Risk-sensitive control with near monotone cost, Appl. Math. Opt. 62 (2009), 145–163.

[3]

V.S.

Borkar and

Suresh Kumar, Singular perturbations in risk-sensitive stochastic control, SIAM J. Control Optim. 48 (2010), 3675–3697.

[4]

Cavazos-Cadena, The risk-sensitive Poisson equation for a communicating Markov chain on a denumerable state space, Kybernetika 45 (2009), 716–736.

[5]

Cavazos-Cadena and

Hernández-Hernández, A characterization of exponential functionals in finite Markov chains, Math. Methods Oper. Res. 60 (2004), 399–414.

[6]

Cavazos-Cadena and

Hernández-Hernández, A system of Poisson equations for a non-constant Varadhan functional on a finite state space, Appl. Math. Opt. 53 (2006), 101–119.

[7]

Dembo and

Zeitouni, Large Deviations Techniques and Applications, Jones and Bartlett, Boston, MA, 1993.

[8]

G.B.

Di Masi and

Stettner, Risk-sensitive control of discrete time Markov processes with infinite horizon, SIAM J. Control Optim. 38 (1999), 61–78.

[9]

G.B.

Di Masi and

Stettner, Infinite horizon risk sensitive control of discrete time Markov processes with small risk, Syst. Control Lett. 40 (2000), 15–20.

10.

[10]

G.B.

Di Masi and

Stettner, Infinite horizon risk sensitive control of discrete time Markov processes under minorization property, SIAM J. Control Optim. 46 (2007), 231–252.

11.

[11]

M.D.

Donsker and

S.R.

Varadhan, Asymptotic evaluation of certain Markov process expectations for large time, I, Commun. Pur. Appl. Math. 28 (1975), 1–47.

12.

[12]

M.D.

Donsker and

S.R.

Varadhan, Asymptotic evaluation of certain Markov process expectations for large time, II, Commun. Pur. Appl. Math. 28 (1975), 279–301.

13.

[13]

M.D.

Donsker and

S.R.

Varadhan, Asymptotic evaluation of certain Markov process expectations for large time, III, Commun. Pur. Appl. Math. 29 (1975), 389–461.

14.

[14]

W.H.

Fleming and

W.M.

McEneaney, Risk sensitive control on an infinite horizon, SIAM J. Control Optim. 33 (1995), 1881–1915.

15.

[15]

W.H.

Fleming and

S.J.

Sheu, Asymptotics of the principal eigenvalue and eigenfunction of a nearly first-order operator with large potential, Ann. Probab. 25 (1997), 1953–1994.

16.

[16]

Hernández-Hernández and

S.I.

Marcus, Existence of risk sensitive optimal stationary polices for controlled Markov processes, Appl. Math. Opt. 40 (1999), 273–285.

17.

[17]

A.R.

Howard and

J.E.

Matheson, Risk-sensitive Markov decision processes, Manage. Sci. 18 (1972), 356–369.

18.

[18]

Ichihara, Phase transitions for controlled Markov chains on infinite graphs, Preprint, 2014.

19.

[19]

Jaśkiewicz, Average optimality for risk sensitive control with general state space, Ann. Appl. Probab. 17 (2007), 654–675.

20.

[20]

Kaise and

Nagai, Ergodic type Bellman equations of risk-sensitive control with large parameters and their singular limits, Asymptotic Analysis 20 (1999), 279–299.

21.

[21]

Kontoyiannis and

S.P.

Meyn, Spectral theory and limit theorems for geometrically ergodic Markov processes, Ann. Appl. Probab. 13 (2003), 304–362.

22.

[22]

C.D.

Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.

23.

[23]

M.L.

Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, New York, 2005.

Local Poisson equations associated with the Varadhan functional

Abstract

Keywords

1. Introduction

2. Local Poisson equations and main results

Case 2 ( S i ∩ supp ( R ) ≠ ∅ ).

Footnotes

Acknowledgements

References

Case 2 ( $S_{i} \cap supp (R) \neq \emptyset$ ).