{'fraction_non_alphanumeric': 0.06098602721337482, 'fraction_numerical': 0.016474464579901153, 'mean_word_length': 3.877827380952381, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximation schemes for countably-infinite linear programs with moment bounds

We introduce approximation schemes for a type of countably-infinite-dimensional linear programs (CILPs) whose feasible points are unsigned measures and whose optimal values are bounds on the averages of these measures. In particular, we explain how to approximate the program's optimal value, optimal points, and minimal point (should one exist) by solving finite-dimensional linear programs. We show that the approximations converge to the CILP's optimal value, optimal points, and minimal point as the size of the finite-dimensional program approaches that of the CILP. Inbuilt in our schemes is a degree of error control: they yield lower and upper bounds on the optimal values and we give a simple bound on the approximation error of the minimal point. To motivate our work, we discuss applications of our schemes taken from the Markov chain literature: stationary distributions, occupation measures, and exit distributions.


Introduction
Countably infinite linear programs (CILPs) are linear programs (LPs) with countably many decision variables and constraints. CILPs arise in network flow problems [31,35,32], infinite-horizon planning and stochastic programming applications such as production planning, equipment replacement, and capacity expansion [17,24,23], semi-infinite linear programs [3,19], search problems in robotics [7], robust optimisation [11], and, prominently, in optimal control problems tied to Markov chains [30,21,2,10]. In this paper, we consider CILPs that arise in the analysis of Markov chains with unbounded state space. In particular, measures of importance to these chains (e.g., the stationary distributions and occupation measures in Sec. 2.1) are feasible points of the CILPs and the optimal values of these programs are bounds on the averages of these measures.
Due to their infinite size, CILPs cannot be solved directly and one must resort to an approximation scheme. We introduce two such schemes-Schemes A and B-that ignore all but finitely many of the CILP's decision variables and replace its countably-many constraints with finitely-many ones.
Scheme A yields lower and upper bounds on the optimal value of the CILP and approximations of its optimal points. Scheme B consists of iterating scheme A and is applicable to CILPs that posses a minimal point, i.e., a feasible point that is element-wise no greater than every other feasible point. It yields approximations of this minimal point whose error is straightforward to bound in practice. Both schemes are shown to converge: the bounds on the optimal value, the approximations of the optimal points, and those of the minimal point tend to the optimal value, optimal point, and minimal point (respectively) as the size of the approximating LPs approaches that of the original CILP.
To derive our approximation schemes, we append a moment bound as an explicit constraint to our CILP (see (2.4) in Sec. 2). The moment bound is satisfied by the feasible points of the CILP and can readily be computed using either Foster-Lyapunov criteria [28,29,16,25] or mathematical programming [22,34,18,25,26,33,8,9,15]. The inclusion of this bound allows us to establish the strong form of convergence of the schemes and to quantify the approximation error. The latter property is our main innovation compared with previous approximation schemes [14,1,19,5,13,35,27,32,12].
The outline of the paper is as follows. In Sec. 2, we introduce the class of LPs we consider, motivate our work with two problems taken from the Markov chain literature, and introduce the notation and assumptions used throughout the paper. In Sec. 3, we introduce Scheme A and prove its convergence. In Sec. 4, we prove the convergence of Scheme B and show how to bound its error. In Sec. 5, we explain how to apply Schemes A and B to the motivating problems introduced in Sec. 2. We conclude the paper with a discussion in Sec. 6. The paper has two appendices: the first contains the proof of Theorem 3.2 omitted from the main text to ease the paper's reading, the second explains how to extend our results beyond Assumption (3.2) made throughout the paper.

The linear program and two motivating problems
We consider a measure ρ on a countable set X that a) satisfies |X | linear equations where |X | denotes the cardinality of X and H := (h(x, y)) x,y∈X is a Metzler matrix; and b) its image under a non-negative matrix G := (g(x, y)) x∈X ,y∈Y is a probability distribution: and Y denotes a second countable set. If X is infinite, or finite but large, (2.1)-(2.3) cannot be solved directly. However, a variety of analytical and numerical methods yield bounds on the moments of ρ (or moment bounds for short). That is, a constant c ≥ 0 such that where w is a norm-like function meaning a non-negative function on X with finite sublevel sets: The set of (unsigned) measures that satisfy (2.1), (2.3), and (2.4), forms the feasible set of a linear program with |X | decision variables, |X | + 1 equality constraints, and |X | + 1 inequality constraints. In particular, the linear programs we approximate in this paper are where l f and u f denote the optimal values and f is any given real-valued function on X such that the integrals in (3.8) are well-defined. Any feasible point ρ * ∈ L achieving this infimum (resp. supremum): is said to be an optimal point. It is straightforward to verify that L posses at most one feasible point ρ m that is element-wise no greater than all other feasible points: If it exists, we refer to ρ m as the minimal point of L. Even though we focus on the LPs in (2.7), the constraints in the definition of L may be substantially modified without affecting the results of this paper, see Sec. 6.

Motivating problems
Two problems encountered in the analysis of Markov processes on countably infinite state spaces (Markov chains or chains, for short) encouraged us to develop the approaches presented in this paper. The first is computation of exit distributions and occupation measures associated with the exit times (or first passage times) of the chain. The second is the computation of the stationary distributions of chains.
In what follows, we use {X n } n∈N to denote a time-homogeneous discrete-time Markov chain taking values in a countable state space S. Let P := (p(x, y)) x,y∈S denote the chain's one-step matrix and λ := {λ(x)} x∈S its initial distribution: for each x, y ∈ S, where P λ denotes the underlying probability measure (we append the subscript λ to emphasise that the chain's starting position is sampled from the distribution λ). Similarly, we use {X t } t≥0 to denote a minimal time-homogeneous continuous-time Markov chain that also takes values in a countable state space S. Let Q := (q(x, y)) x,y∈S denote the chain's rate matrix and λ := {λ(x)} x∈S its initial distribution: for each x, y ∈ S, where T ∞ denotes the chain's explosion time and P λ denotes the underlying probability measure. We assume that Q is stable and conservative: where the sum is meant to be taken over all states y in S except for x.

Exit distributions and occupation measures
We begin with the discrete-time case and then proceed to the continuous-time one.
Discrete-time chains The exit time σ of {X n } n∈N from a given subset D of the state space (known as the domain) is the first time that the chain lies outside of D (or plus infinity if it never does): σ := inf {n ∈ N : X n ∈ S\D}.
With the exit time σ, we associate the exit distribution µ and occupation measure ν defined by In other words, µ(x) denotes the probability that the chain exits the domain via state x while ν(x) denotes the expected number of visits that the chain will make to x before exiting the domain. As shown in [25,Theorem 2.9], if the chain starts inside of the domain with probability one (λ(D) = 1) and the occupation measure ν satisfies the moment bound ν(w) ≤ c, then the occupation measure is the minimal feasible point of L in (2.6) with g(x, y) := p(x, y) ∀x ∈ D, y ∈ D, (2.10) and the exit distribution is given by µ = νG. Moments bounds of the sort (2.4) can be obtained analytically using the Foster-Lyapunov criterion in [29, Sec. 14.2.1] or computationally using the semidefinite programming approach discussed in [25,Chap. 4].
Continuous-time chains Just as in the discrete-time case, the exit time τ of the continuous time chain {X t } t≥0 from a domain D is the first time that the chain lies outside of D: With the exit time τ , we associate the exit distribution µ and occupation measure ν defined by These tell us where on the boundary of the domain the chain exits (µ) and where inside the domain it spends its time up until the exit time (ν). As shown in [25,Theorem 2.37], if the exit time is almost surely finite, the chain starts inside of the domain (λ(D) = 1), and the occupation measure ν satisfies the moment bound ν(w) ≤ c, then the occupation measure is the minimal feasible point of L in (2.6) where g(x, y) := q(x, y) ∀x ∈ D, y ∈ D, (2.11) and the exit distribution is given by µ = νG. In this case, moment bounds can be obtained using the Foster-Lyapunov criterion [25,Thrm. 2.57] or the computational approaches discussed in [18,25].

Stationary distributions
Once again, we begin with the discrete-time case and then proceed to the continuous-time one.
Discrete-time chains A probability measure π on S is said to be a stationary distribution of the chain if sampling its initial position from π ensures that the chain remains distributed according to π for all time: P π ({X n = x}) = π(x) ∀x ∈ S, n ∈ N.
Classical theory (e.g., [4, Theorem A.I.3.1]) tells us that the set of stationary distributions that satisfy the moment bound π(w) ≤ c is L in (2.6) with In this case, moment bounds can be computed using the Foster-Lyapunov criteria in [16,29] (and references therein) or the semidefinite programming approach of [22,Sec. 12.4].
Continuous-time chains A probability measure π on S is said to be a stationary distribution of the chain if sampling the chain's starting location from π ensures that the chain remains distributed according to π for all time: Assuming that the rate matrix Q is regular, the set of stationary distributions that satisfy the moment bound π(w) ≤ c is L in (2.6) with  [28,16] or the computational approaches in [34,26,25,33,8,9,15]. We extensively study the application of the schemes in this paper to this problem in [26].

Notation and assumptions
Throughout this paper, we adhere to the convention that the supremum (resp. infimum) of the empty set is minus infinity (resp. plus infinity) and we denote the sets of real numbers, natural numbers, and positive integers by R, N, and Z + . We use X and Y to denote two countable sets. We denote the cardinality of X by |X | and its power set by 2 X . By a "measure ρ on X ", we mean a σ-finite (possibly signed) measure on (X , 2 X ) and use ρ ≥ 0 to signify that ρ is unsigned where it may otherwise be ambiguous. We abuse our notation by using ρ to denote both the measure and its density with respect to the counting measure on (X , 2 X ). That is, we write ρ( Given the above, we identify the space of measures, and that of functions, on X with R |X | . Clearly, ρ is unsigned if and only if ρ(x) ≥ 0 for all x ∈ X . Next, to quantify the error of our approximations, we use the total variation norm: (2.14) In (2.1)-(2.6), H := (h(z, x)) z,x∈X and G := (g(x, y)) x∈X ,y∈Y denote matrices of real numbers indexed by X 2 and X × Y (respectively) that satisfy Assumption 2.1 below.

Assumption 2.1. (i) H is Metzler and G is nonnegative:
is finite for all x ∈ X ), and we have at our disposal constants a 1 , a 2 , . . . such that Assumption 2.1(i) ensures that the sums ρH(x) and ρG(y) are absolutely convergent for any x ∈ X , y ∈ Y, and feasible point ρ of L. Assumption 2.1(ii) and the constraints ρ ≥ 0 and ρ(g) = 1 in (2.6) guarantee that the entries ρ(x) of the feasible points ρ of L are bounded: a fact that will be important for the proofs of Secs. 3-4. In terms of the problems discussed in Sec. 2.1, (2.15) is satisfied because one-step matrices P of discrete-time chains and rate matrices Q of continuous-time chains are Metzler. In the case of the stationary distributions, G is the identity matrix on R |X | and so Assumption 2.1(ii) is trivially satisfied. Similarly, our choice of truncations X r in (2.5) ensures that (2.16) is satisfied with a r := r −1 . Because one-step matrices P of discrete-time chains are row stochastic ( y∈X p(x, y) = 1 for all x), (2.16) also holds with a r := r −1 for the exit time problem of these chains. In the continuous-time case, the matter is not so simple for the exit time problem unless we pick w(x) to be (−q(x, x)) d for some d > 1, in which case (2.9) implies that (2.16) holds with a r = r 1−d . However, these bounds a r for the exit time problem (both in discrete-time and in continuous-time) will be generally conservative: sharper bounds can be obtained on a case-by-case basis. Lastly, even though Assumption 2.1(ii) is not automatically satisfied for the exit time problem, it is a very mild restriction: it asks that the chain must be able to leave the domain from every state x for which w(x) = 0. Indeed, if the exit time is almost surely finite, states from which the chain cannot leave the domain are irrelevant to the question as the chain has zero probability of visiting them.

Scheme A: Bounding optimal values and approximating optimal points
The starting point of our schemes is replacing the indexing set X with its truncation X r defined in (2.5). We then derive a sequence of computationally tractable sets {L r } r∈N that approximate L; computationally tractable meaning that optimising over L r consists of solving finite-dimensional linear programs. In particular, we will choose these sets to be outer approximations of L in the sense that a) if ρ belongs to L, then its restriction ρ |r to the truncation X r belongs to L r , where the restriction is defined by: and b) L r is approximately equal to L for large enough r (we formalise this in Sec. 3.2).
To obtain these outer approximations, we make one further assumption: each equation in (2.1) only involves finitely many entries of ρ (this assumption can be circumvented, see App. B). Hence the support of each of the columns of H is finite: similar assumptions can be found in the works [35,13,14] discussing approximation schemes for other types of CILPs. In the context of the Markov chains in Sec. 2.1, (3.2) requires that each state is reachable in a single jump from at most finitely many others.

Outer approximations and bounding the optimal values
Let E r denote the set of indices x in the truncation such that the support of the corresponding column h(·, x) of H is contained in the truncation: 3) The first step in deriving our outer approximation is to strike all other equations from (2.1) resulting in a set of finitely many equations each involving finitely many unknowns (i.e., |E r | ≤ |X r | equations and |X r | unknowns). Because w is a nonnegative function, it follows immediately from the definition (2.6) of L that Given (3.3)-(3.4), we only need now to approximate the constraints "ρ(g) = 1" with one that only involves ρ |r . To do so, we use the moment bound (2.4) and the following generalisation of Markov's inequality that allows us to control the tail {ρ(x)} x ∈Xr of ρ: as long as f is a nonnegative function on X and ρ belongs to L, where 1 X c r denotes the indicator function of the complement X c r of the truncation X r . Setting f to be the row sums g of G in (2.3), we find that for all ρ in L, where the first inequality follows from (2.16), the second from Markov's inequality (3.5), and the first and last equalities follow from the constraint ρ(g) = 1 in (2.6).

Putting (3.3)-(3.6) together shows that
is an outer approximation of L in (2.6). In contrast with L which involves |X | decision variables and a comparable number of constraints, L r only involves |X r | decision variables, |E r | equality constraints, and |X r | + 3 inequality constraints (note that the constraints ρ(X c r ) = 0 and ρ ≥ 0 imply that ρ(x) = 0 for every x outside of the truncation X r ). Because w is a norm-like function, |X r | is a finite number for any positive integer r and so L r is the feasible set of a finite-dimensional linear program regardless of whether |X | is finite.
Due to the outer approximation property, we obtain bounds on the feasible points of L by optimising over L r . In particular, for any real-valued function f on X , consider the finite-dimensional LPs: Because L r is an outer approximation of L and ρ(f In summary, we have the following. Lemma 3.1. Suppose that Assumption 2.1 is satisfied. If L is non-empty, then L r is non-empty for each r > 0. Moreover, if f is any real-valued function on X , l r f and u r f are defined as in (3.8), and ρ belongs to L, then l r f ≤ ρ |r (f ) ≤ u r f , where ρ |r is the restriction of ρ to X defined in (3.1). Consequently, if f is ρ-integrable, we have that Furthermore, if f is non-negative (resp. non-positive) on X c r , then Proof. Shown in (3.3)-(3.9).
Putting together the lower and upper bound in (3.10)-(3.11), we quantify the uncertainty in our knowledge of the ρ(f ). Moreover, because the bounds (3.10)-(3.11) hold for all feasible points ρ of L they also hold if we replace the average ρ(f ) with the corresponding optimal values in (2.7). In the next section, we show that the sequences {l r f } r∈Z + and {u r f } r∈Z + obtained by computing these bounds for ever larger truncations X r converge to l f and u f , respectively.

The scheme's convergence
Our definition (2.5) of the truncations implies that they form an increasing sequence with X as its limit: (3.12) Here, we show that the outer approximations L r converge in a strong manner to L. The type of convergence we deal with is ρ r → ρ as r → ∞ if and only if where W denotes the vector space of real-valued functions on X that eventually grow strictly slower than the norm-like function w in (2.4): If (3.13) holds, we say that ρ r converges to ρ in weak * . In our setting of countable spaces X , weak * convergence implies convergence in total variation [25,Rem. 5.10]. The next theorem shows that any sequence {ρ r } r∈Z + of feasible points ρ 1 ∈ L 1 , ρ 2 ∈ L 2 , . . . is weak * sequentially compact and that each of its accumulation points belongs to L. In other words, each subsequence {ρ r k } k∈Z + of {ρ r } r∈Z + has a weak * converging subsubsequence {ρ r k i } i∈Z + and its limit belongs to L. Proof. See Appendix A.
Theorem 3.2 tells us that, for sufficiently large r, the optimal values l r f and u r f in (3.8) of the finite-dimensional LPs are close to the optimal values l f and u f of the the infinite-dimensional LP. As we now discuss, the same also holds for the optimal points of L r achieving l r f and u r f and those of L achieving l f and u f .

Approximating the optimal points and their images
We have the following corollary of Theorem 3.2.

Corollary 3.3. Suppose that the premise of Theorem 3.2 is satisfied.
(i) Suppose that there exists a unique ρ * in L such that ρ * (f ) = l f (resp. ρ * (f ) = u f ) for a given f in W. If, for each positive integer r, ρ r in L r is such that ρ r (f ) = l r f (resp. ρ r (f ) = u r f ), then the sequence {ρ r } r∈Z + converges in weak * to ρ * .
(ii) Suppose that L is the singleton {ρ}. If ρ r belongs L r for each positive integer r, then the sequence {ρ r } r∈Z + converges in weak * to ρ.
Proof. (i) We only show this for {l r f } r∈Z + : the proof for the {u r f } r∈Z + is entirely analogous. Theorem 3.2 tells us that {ρ r } r∈Z + is weak * sequentially compact with accumulation points in L. Pick any accumulation point ρ of {ρ r } r∈Z + and let {ρ r j } j∈Z + be any subsequence of {ρ r } r∈Z + converging to ρ. Theorem 3.2 implies that, Because ρ belongs to L, the uniqueness of ρ * then implies that ρ = ρ * . Since this holds for any accumulation point ρ of {ρ r } r∈Z + and the sequence is sequentially compact, we have that {ρ r } r∈Z + converges in weak * to ρ * . (ii) This follows immediately from (i) by setting f := 0.
In other words, if L is a singleton {ρ}, then Corollary 3.3(ii) shows that any feasible point ρ r of L r is close to ρ for large enough r. If L is not a singleton, then Corollary 3.3(i) justifies using Scheme A to approximate optimal points ρ * of L achieving infimum (resp. supremum) ρ * (f ) = l f (resp. ρ * (f ) = u f ), assuming that these are unique.
To approximate the images ψ through G of the feasible points ρ (see (2.2)), we combine Corollary 3.3 with the following lemma.
Proof. Using the definition of the total variation norm (2.14) we have that for any r, n ∈ Z + . Due to (2.16), the remainder of the proof is analogous to Part (c) of the proof of Theorem 3.2.
Suppose that L has a unique feasible point ρ. In practice, we are faced with the crucial question: "what r should we pick to ensure that Scheme A returns accurate approximations of ρ?". Herein lies the main drawback of Scheme A: we know of no practical way of deciding whether the truncation employed is large enough. To overcome this issue, we introduce Scheme B in the next section. It computes a collection of element-wise lower bounds on the unknown measure ρ by repeatedly applying Scheme A. Using this collection of lower bounds as an approximation of ρ, it is straightforward to bound its error (defined as the total variation distance between the lower bounds and ρ). If this error bound proves to be unsatisfactorily large, we increase the truncation, re-compute the bounds, and re-evaluate the error bound. As we will show, the collection of bounds also converges in weak * to ρ and the error bound converges to zero as the truncation approaches the entire index set X . For this reason, by repeatedly increasing r, we will always be able to achieve any desired error tolerance.

Scheme B: Approximating the minimal point
Suppose that L has a minimal point meaning a feasible point ρ m satisfying (2.8). Let where l r x is as in (3.8) with f := 1 {x} . Lemma 3.1 shows that l r bounds all feasible points ρ of L from below: Theorem 3.2 tell us that l r converges pointwise to ρ m : These lower bounds actually converge in weak * . Furthermore, in contrast with the approximations ρ r of Scheme A, bounding the total variation distance between l r and ρ m is straightforward: Suppose that premise of Theorem 3.2 is satisfied.
(i) For each positive integer r, where u r Xr is as in (3.8) with f := 1 Xr .
(ii) If L has a minimal point ρ m (in the sense of (2.8)), then l r converges to ρ m in weak * as r tends to infinity.
(iii) If L has a unique feasible point ρ, then not only does the error ||ρ − l r || tend to zero as r approaches infinity, but so does the error bound u r Xr + c/r − l r (X r ).
Proof. (i) Because (4.2) shows that ρ − l r is an unsigned measure for each ρ ∈ L, this follows immediately from Lemma 3.1 and the fact that the total variation norm of an unsigned measure is its mass. (ii) Theorem 3.2 shows that the limit l(x) := lim r→∞ l r (x) exists for each x ∈ X . Fatou's Lemma and (4.2)-(4.3) show that Pick any f ∈ W, fix r, n ∈ Z + , and note that Given (4.3), (4.4), and the above, the remainder of the proof is analogous to Part (c) of the proof of Theorem 3.2. (iii) This follows immediately from (ii) and Theorem 3.2.
To approximate the image ψ m := ρ m G through G of the minimal solution ρ m we use where l r gy is as in (3.8) with f (·) = g y (·) := g(·, y) and Y r is any finite subset of Y.

Corollary 4.2. Suppose that premise of Theorem 3.2 is satisfied and that
(i) For each positive integer r, l r ψ (y) ≤ ρG(y) ∀y ∈ Y, ρ ∈ L.
(iii) If L has a minimal point ρ m (in the sense of (2.8)), then ψ m := ρ m G = ρG for all ρ ∈ L and the lower bounds l r ψ converge in total variation to ψ m as r tends to infinity.
Proof. (i) This follows directly from (4.2) and non-negativity of G. (ii) Part (i) tells us that ρG− l r ψ is an unsigned measure on (Y, 2 Y ) and the result follows. (iii) Inequality (2.8) and non-negativity of G implies that ρ m G(y) ≤ ρG(y) for every y ∈ Y and ρ ∈ L. Thus, showing that ρG = ρ m G for each ρ ∈ L. Fix an ε > 0. Note that ψ m (Y) = ρ m (g) = 1 so there exists an R such that ψ m (Y c R ) ≤ ε/4. Thus, where l gy is as in (2.7) with f := g y , the first inequality follows from non-negativity of ψ m and l r ψ , the second from (i), and the final from the fact that ρG = ρ m G for each ρ ∈ L. Because the non-negativity of G and (2.16) implies that g y belongs to W for each y ∈ Y, finiteness of Y R and Theorem 3.2 imply that y∈Y R (l gy − l r gy ) is smaller than ε/2 for all sufficiently large r completing the proof.
We refer to the process of computing the lower bounds l r (or l r ψ ) and evaluating the error using Theorem 4.1 (or its corollary) as "Scheme B". The error control of Scheme B comes at a price: the scheme is more computationally expensive than Scheme A as it entails solving |X r | (or |Y r |) LPs instead of a single one. Parallelising the computation of the bounds mitigates some of this extra cost. Lastly, replacing l r x with u r x in (4.1), where u r x denotes u r f in (3.8) with f := 1 x , we obtain a measure u r of upper bounds on the feasible points of L analogous to l r (also accompanied by an error bound). Even though Lemma 3.1 shows that u r converges pointwise, no weak * convergence can be recovered, see [25] for details.

Motivating problems revisited
Before concluding the paper, we quickly point out how to apply the results of Secs. 3-4 to the problems of Sec. 2.1 that motivate this work.

Exit distributions and occupation measures
With H and G as in (2.10) (resp. (2.11)

Stationary distributions
In the case of a unique stationary distribution π satisfying the moment bound π(w) ≤ c, Corollary 3.3(ii) yields converging approximations of π as long as H and G are as in (2.12) (resp. (2.13) in the continuous-time case). Furthermore Corollary 4.2 yields converging approximations of π whose error can be evaluated exactly, see [26] and [25,Chap. 6.2] for numerical examples.
In the non-unique case, [6, Theorem I.7.1] (or [25,Theorem 2.44] in the continuous-time case) tells us that the set of stationary distributions π satisfying the moment bound π(w) ≤ c is the set of convex combinations of the ergodic distributions satisfying the moment bound: where {π i : i ∈ I} denotes the set of ergodic distributions satisfying π i (w) ≤ c. Each of these distributions π i has support on a closed communicating class C i ⊆ S of the state space. Because these classes are disjoint sets, we obtain converging approximations of π i by using Corollary 3.3(i) with f := 1 x for any state x inside the class C i . Moreover, because L r is an outer approximation of L, our lower bounds function as a uniqueness test: if l r (x) > 0 for some r and x, then L must be a singleton. Otherwise (5.1) and the disjointness of the communicating classes imply that there exists a π in L such that π(x) = 0 contradicting the lower-bound property of l r (x). See [26] and [25,Chap. 6.2] for the details.

Concluding remarks
In this paper, we approximate a class of countably infinite linear programs with finite-dimensional ones and show how to bound their approximation errors. As discussed at the end of Sec. 3, any desired error tolerance is achieved by iterating our approach with ever increasing truncations. The convergence results of Secs. 3-4 guarantee that this procedure will terminate.
To simplify the exposition we focused on the particular type of LP in (2.7) motivated by the problems discussed in Sec. 2.1. However, our approximation schemes can be modified to apply to other CILPs that are not necessarily tied to Markov chains. Specifically, the constraints ρH = φ can be removed from (2.6) and/or any equality ρ(f ) = α or inequality ρ(f ) ≤ α can be added as long as f is a function belonging to W. The techniques of Sec. 3 carry over if the constraints of the new CILP either involve only finitely many entries of the feasible points ρ, or are of the type ρ(f ) ≤ α for a nonnegative function f . Otherwise, the techniques of App. B apply. The critical ingredients required to guarantee convergence of the schemes are a moment bound and the boundedness of the entries of the feasible points ρ, which in our case this followed from Assumption 2.1(ii) and the constraints ρ(g) = 1 and ρ ≥ 0.
Hernández-Lerma and Lasserre [19,20,21,22] introduced a series of approximation schemes for infinite-dimensional linear programs that are closely related to ours. The underlying idea of approximating an infinite-dimensional LP by a finite-dimensional one in their schemes is the same as in ours. In their words, we obtain the approximating finite-dimensional LP L r by aggregating the constraints {ρH(x) = φ(x) ∀x ∈ X } in L into {ρH(x) = φ(x) ∀x ∈ X r } and relaxing the constraint ρ(g) = 1 in L into 1 − ca r ≤ ρ(g) ≤ 1. Similarly, in the proof of Theorem 3.2 we employed ideas analogous to theirs even if their proofs require more technically involved results (e.g. Prokhorov's Theorem or functional analytic machinery) due to the more general setting they consider.
The main difference between their approach and ours is that they do not employ an explicit moment bound in their LPs. Instead, they choose an objective that consists of minimising the integral of a norm-like function to recover the weak * sequential compactness. Because of their fixed objective, they only obtain lower bounds on the optimal value. The absence of upper bounds makes it difficult to bound the approximation error. Similarly, because they cannot bound other averages, it is not possible to construct measures of bounds with easy-to-quantify-errors along the lines of l r and l r ψ in Sec. 4. Conversely, their approach has the advantage that it does not rely on a moment bound but only assumes that optimal value is finite.
The applications in [19,20,21,22] involve uncountable index sets X . To obtain finite-dimensional LPs, Hernández-Lerma and Lasserre must discretise X in one manner or another (they find a dense countable subset of a space that contains the measures they wish to approximate). Because of this discretisation, the restrictions of the measure of interest are not necessarily feasible points of the finite-dimensional LPs. For this reason, their schemes yield only converging approximations of the quantities of interest instead of converging bounds. Since using an explicit moment bound does not overcome this difficulty, we did not attempt to extend the schemes beyond the countable case. For a more detailed comparison, see [25,Sec. 5.5].
Finally, we mention that our method can be adapted to compute marginal probability distributions by redefining G, see [ S : w(x) < n} is a finite set for each n ∈ Z + . The pointwise convergence then tell us that for any fixed n ∈ Z + x∈Xn ρ(x)w(x) = lim k→∞ x∈Xn The Monotone Convergence Theorem and the above imply that ρ(w) ≤ c.
Fix ε > 0. Because f belongs to W, we can find an m ∈ Z + such that sup x ∈Xm (|f (x)| /w(x)) ≤ ε 4c and thus x ∈Xm Because w is norm-like, S m is a finite set and so the pointwise convergence ρ r k to ρ implies that there exist a K such that Since the ε was arbitrary, we have the desired limit lim k→∞ ρ r k (f ) = ρ(f ).
Because the above holds for every f ∈ W, we have that ρ r k not only converges pointwise to ρ but also in the weak * topology. Weak * sequential compactness of the sequence follows.
(d) Pick any converging subsequence {ρ r k } k∈Z + of {ρ r } r≥0 with limit ρ. Assumption 2.1 and (3.2) imply that g and y → h(y, x), for any x ∈ X , belong to W. Because w is norm-like, (3.2) further implies that {E r } r∈Z + is also an increasing sequence of sets that approaches X : Putting these observations together with the weak * convergence of the subsequence we have that ρH(x) = lim k→∞ ρ r k H(x) = φ(x) ∀x ∈ X , ρ(g) = lim k→∞ ρ r k (g) = 1, where the last equality follows from the constraint 1 − ca r ≤ ρ(g) ≤ 1 in (3.7). Because we already argued in (b) that ρ ≥ 0 and ρ(w) ≤ c, the above shows that that ρ ∈ L.
(e) We argue this only for {l r Now, to recover a finite dimensional outer approximation of L, pick any index x in our truncation X r and consider its associated equation: where the measure ǫ r is defined by Because H is Metzler and any feasible point ρ of L is non-negative, we have that ǫ r (x) ≥ 0, ∀x ∈ X r . ρH(x) + ǫ(x) = φ(x), ∀x ∈ X r , 1 − ca r ≤ ρ(g) ≤ 1, ǫ(X r ) ≤ cb r , ρ(w) ≤ c, ρ ≥ 0, ǫ ≥ 0, ρ(X c r ) + ǫ(X c r ) = 0. The only difference is that in contrast with L r in (3.7), L r involves |X r | equalities, 2|X r | + 4 inequalities, and 2|X r | variables.