# Blackwell Spaces andϵ-Approximations of Markov Chains

Authors: Giacomo Aletti; Diane Saada
Journal: International Journal of Stochastic Analysis
 (2011)

---

## Abstract

On a weakly Blackwell space we show how to define a Markov chain approximating problem, for the target problem. The approximating problem
is proved to converge to the optimal reduced problem under different pseudometrics.


---

## Body

## 1. Introduction

A target problem (TP) is defined as a homogeneous Markov chain stopped once it reaches a given absorbing class, the target. Our purpose is to only use the necessary information relevant with respect to the target and in consequence to reduce the available information. A new Markov chain, associated with a new equivalent but reduced matrix is defined. In the (large) finite case, the problem has been solved for TPs: in [1–3], it has been proved that any TP on a finite set of states has its “best target” equivalent Markov chain. Moreover, this chain is unique and there exists a polynomial time algorithm to reach this optimum.The question is now to find, in generality, anϵ-approximation of the Markov problem when the state space is measurable. The idea is to merge into one group the points that ϵ-behave the same with respect to the objective and, at the same time, to keep an almost equivalent Markov chain, with respect to the other “groups”. The construction of these groups is done through equivalence relations. Each group will correspond to a class of equivalence. In fact, there are many other mathematical fields where approximation problems are faced by equivalences. For instance, in integration theory, we use simple functions, in functional analysis, we use the density of countable generated subspaces, and, in numerical analysis, we use the finite elements method.In this paper, the approximation is made by means of discrete equivalences, which will be defined in the following. We prove that the sequence of approximations tends to the optimal exact equivalence relation defined in [1–3], when we refine the groups. Finer equivalence will imply better approximation, and accordingly the limit will be defined as a countably generated equivalence.Under a very general Blackwell-type hypothesis on the measurable space, we show that it is equivalent to speak on countably generated equivalence relationships or on measurable real functions on the measurable space of states. If we do not work under this framework of Blackwell spaces, we can be faced to paradoxes, as it is explained by [4], of enlarging σ-algebras, while decreasing the information available to a decision-maker. The ϵ-approximation of the Markov chain depends always upon the kind of objective. In [5], Jerrum deals with ergodic Markov chains. His objective is to approximate the stationary distribution by means of a discrete approximating Markov chain, whose limit distribution is close in a certain sense to the original one. However, unlike our following work, his purpose is not the explicit and unified construction of the approximating process. In this paper, we focus on the target problem. We solve extensively the TP, where the objective is connected with the conditional probability of reaching the target T, namely ℙ(Xn∈T∣X0=x), for any n,x. This part extends the work in [1–3].


## 2. Main Results

Let(X,𝒳) be a measurable space, equipped with a assumption (A0) that will be explained when necessary. Let P be any transition probability on (X,𝒳). A homogeneous Markov process (Xn)n≥0 is naturally associated to (X,𝒳,P). In the target problem, we are interested in the probabilities of reaching the target class T within n steps, namely in(2.1)P({Xn∈T}∣X0=x)foranynandx.
The set T is a priori given, and does not change through the computations. T is supposed to be an absorbing set lying in 𝒳.Definition 2.1.
Let(X,𝒳) be a measurable space and let T∈𝒳. Let ℱ⊆𝒳 be a sub σ-algebra of 𝒳 such that T∈ℱ. A function P:X×ℱ→[0,1] is a transition probability on(X,ℱ) if (i)
P(x,·) is a probability measure on ℱ, for any x∈X,(ii)
P(·,F) is ℱ-measurable, for any F∈ℱ.Given a transition probability P on (X,ℱ), we denote by Pn the transition probability on (X,ℱ) given inductively by
(2.2)P1=P;Pn+1(x,F)=∫XP(x,dy)Pn(y,F).
We denote by TrP(X,ℱ) the set of the transition probabilities on (X,ℱ). We denote by 𝕋ℙX=∪ℱ⊆𝒳TrP(X,ℱ) the set of all transition probabilities on X that we equip with a suitable pseudometric d:
(2.3)d(P1,P2)=sup⁡x∑nβn|P1n(x,T)-P2n(x,T)|,withβ∈(0,1).
It is such that
(2.4)d(P1,P2)=0⟺P1n(x,T)=P2n(x,T),foranynandx.
This pseudometric, which is compatible with T, allows to approximate P by simpler kernels.A target problem is defined through a transition probabilityP∈(𝕋ℙX,d). More precisely, we have the following definition.Definition 2.2.
Atarget problem is a quadruple (X,ℱ,T,P), where P∈TrP(X,ℱ) and T∈ℱ. A simple target problem is a target problem where ℱ is generated by an at most countable partition of X.The main purpose of this paper is to approximate any target problem by a sequence of simple target problems in the spirit of the construction of the Lebesgue integral, where the integral of a functionf is approximated by the integral of simple functions fn=∑i∈IciICi. The strategies will play the role of the approximating subdivisions (Ci)i∈I.Definition 2.3.
We callstrategyStr a sequence of maps (Strn)n≥0 from the set of the target problems to the set of the simple target problems. A strategy is a target algorithm if it is built as in Section 3.In the “Lebesgue example” given above, the strategy is related to the “objective” of the problem (the integral) and the pseudometricd(f,fn)=∫|f-fn|dx is required to go to 0 as n goes to infinity. Here also, a strategy is meaningful if d(P,Strn(P)) tends to 0 as n goes to infinity. Moreover, for what concerns applications, given a target problem (X,𝒳,T,P) a good strategy should not need the computation of Pn, n>1. The first main result of this paper states that the target algorithms are always good strategies.Theorem 2.4.
For any target problem(X,ℱ,T,P) and any target algorithm Str,
(2.5)lim⁡n→∞d(P,Pn)=0,
where (X,ℱn,T,Pn)=Strn(X,ℱ,T,P).Two questions immediately arise: does the sequence(Strn(P))n≥0 have a limit (and in which sense)? Moreover, since d is defined as a pseudometric, does this limit depend on the choice of Str?The extension of the concept of compatible projection given in [1–3] to our framework will enable us to understand better the answer to these questions. A measurable set A≠∅ of a measurable space (X,𝒳) is an 𝒳-atom if it has no nonempty measurable proper subset. No two distinct atoms intersect. If the σ-field is countably generated, say by the sequence {An} then the atoms of 𝒳 are of the form ∩nCn where each Cn is either An or X∖An.Definition 2.5.
An equivalence relationshipπ on a measurable space (X,𝒳) is measurable (discrete) if there exists a (discrete) random variable f:(X,𝒳)→(ℝ,ℬℝ) (ℬℝ denotes the Borel σ-algebra), such that
(2.6)xπy⟺f(x)=f(y),
and we denote it by π=πf. Let (X,ℱ,T,P) be a target problem. A compatible projection is a measurable equivalency πf such that T∈σ(f) and
(2.7)P(x,F)=P(y,F),∀xπfy,∀F∈σ(f).
We say that π⊇π′ if π corresponds to partitions finer than π′. Finally, a compatible projection π is said to be optimal if π⊇π′, for any other compatible projection π′.Remark 2.6.
This definition is well posed if(2.8)πf=πg⟺σ(f)=σ(g).
Assumption (A0) ensures that the definition of measurable equivalency is indeed well posed. This assumption will be stated and discussed in Section 4.Theorem 2.7.
Ifπ=πf is a compatible projection for the target problem (X,ℱ,T,P), then there exists a target problem (X,σ(f),T,Pπ). such that Pπ(x,F)=P(x,F) for any F∈σ(f).It is not said “a priori” that an optimal compatible projection must exist. If it is the case, then this equivalence is obviously unique.Theorem 2.8.
For any target problem(X,ℱ,T,P), there exists a (unique) optimal compatible projection π.To conclude the main results, let us first go back to the Lebesgue example. The simple functionsfn=∑i∈IciICi are chosen so that σ(Ci,i∈I) increases to σ(f) and fn(x)→f(x). The following theorem guarantees these two similar facts by showing the “convergence” of any strategy to the optimal problem.Theorem 2.9.
LetStrn(X,ℱ,T,P)=(X,ℱn,T,Pn), with Str target algorithm and let π be the optimal compatible projection associated to the target problem (X,ℱ,T,P). Then (i)
ℱn⊆ℱn+1 for any n, and ∨nℱn≥0=ℱπ;(ii)
limnPn(x,F)=Pπ(x,F), for any (x,F)∈(X×∪mℱm).Remark 2.10 (The topology top).
In Theorems2.4–2.9, we have proved the convergence of (Pn)n to Pπ with respect to the pseudometric d. The pseudometric topology top is the topology induced by the open balls Br(P)={Q∈𝕋ℙX:d(P,Q)<r}, which form a basis for the topology. Accordingly, the previous theorems may be reread in terms of convergence of Pn to P on the topological space (𝕋ℙX,Top).


### 2.1. Connection with Weak Convergence

Given a strategy(X,ℱn,T,Pn)n≥0, if we want to show a sort of weak convergence of Pn(x,·) to P(x,·), for any x, we face the two following problems: (i)
eachPn(x,·) is defined on a different domain (namely, on ℱn),(ii)
we did not have required a topology onX.We overcome the first restriction by introducing a new definition of probability convergence. The idea is given in the following example.Example 2.11.
Letℱn=σ({(i2-n,(i+1)2-n], i=0,…,2n-1}) be the σ-algebra on (0,1] generated by the dyadic subdivision. Suppose we know that νn:ℱn→[0,1] is the unique probability on ℱn s.t. for any i, νn((i2-n,(i+1)2-n])=2-n. Even if νn is not defined on the Borel sets of (0,1], it is clear that in “some” sense, it must happen that νn→ν*, where ν* is the Lebesgue measure on the Borel sets of (0,1]. Note that the cumulative function of νn is not defined, and therefore a standard weak convergence cannot be verified.
In fact, we know that(2.9)νn((-∞,i2n])=νn((0,i2n])=i2n,
that is, in this case, as n→∞, we can determine the cumulative function on a dense subset. This fact allows to hope that νn→ν* in a particular sense.Definition 2.12.
Let(X,𝒳,(𝒳n)n≥0) be a filtered space, and set 𝒳∞=∨n≥0𝒳n. Let νn:𝒳n→[0,1], n≥1 and ν∞:𝒳∞→[0,1] be probability measures. One says that νnconverges totally toν∞on the topological space(X,τ) as n tends to infinity if ν¯n→τwν∞ (converges in weak sense on (X,τ)), for any ν¯n:𝒳∞→[0,1], such that ν¯n|𝒳n=νn. One writes νn→τtotν∞.Going back to the example, it is simple to check thatνn→τ(0,1]totν*, where νn,ν* are given in Example 2.11 and τ(0,1] is the standard topology on (0,1]. In fact, let (ν¯n)n≥1 be any extension of (νn)n≥1 to the Borel sets of (0,1]. For any t∈(0,1), we have by (2.9) that(2.10)t-12n≤Fν¯n(t)≤t+12n,
where Fν¯n is the cumulative function of ν¯n, which implies the weak convergence of ν¯n to ν* and, therefore, νn→τ(0,1]totν*.For what concerns the topology onX, we will define the topological space (X,ϱP) induced by the pseudometric dP associated to the target problem (X,ℱ,T,P), and the pseudometric d. In this way ϱP is only defined with the data of the problem. One may ask: is this topology too poor? The answer is no, since it is defined by the pseudometric dP. In fact, dP(x,y)<ϵ means that x and y play “almost the same role” with respect to T. A direct algorithm which takes dP into account needs the computation of Pn at each step. In any case, even if dP may not be computable, it defines a nontrivial interesting topology ϱP on X. As expected, we have the following theorem.Theorem 2.13.
LetStrn(X,ℱ,T,P)=(X,ℱn,T,Pn), with Str target algorithm. Then, for any given x,
(2.11)Pn(x,⋅)⟶ϱPtotP(x,⋅).


## 2.1. Connection with Weak Convergence

Given a strategy(X,ℱn,T,Pn)n≥0, if we want to show a sort of weak convergence of Pn(x,·) to P(x,·), for any x, we face the two following problems: (i)
eachPn(x,·) is defined on a different domain (namely, on ℱn),(ii)
we did not have required a topology onX.We overcome the first restriction by introducing a new definition of probability convergence. The idea is given in the following example.Example 2.11.
Letℱn=σ({(i2-n,(i+1)2-n], i=0,…,2n-1}) be the σ-algebra on (0,1] generated by the dyadic subdivision. Suppose we know that νn:ℱn→[0,1] is the unique probability on ℱn s.t. for any i, νn((i2-n,(i+1)2-n])=2-n. Even if νn is not defined on the Borel sets of (0,1], it is clear that in “some” sense, it must happen that νn→ν*, where ν* is the Lebesgue measure on the Borel sets of (0,1]. Note that the cumulative function of νn is not defined, and therefore a standard weak convergence cannot be verified.
In fact, we know that(2.9)νn((-∞,i2n])=νn((0,i2n])=i2n,
that is, in this case, as n→∞, we can determine the cumulative function on a dense subset. This fact allows to hope that νn→ν* in a particular sense.Definition 2.12.
Let(X,𝒳,(𝒳n)n≥0) be a filtered space, and set 𝒳∞=∨n≥0𝒳n. Let νn:𝒳n→[0,1], n≥1 and ν∞:𝒳∞→[0,1] be probability measures. One says that νnconverges totally toν∞on the topological space(X,τ) as n tends to infinity if ν¯n→τwν∞ (converges in weak sense on (X,τ)), for any ν¯n:𝒳∞→[0,1], such that ν¯n|𝒳n=νn. One writes νn→τtotν∞.Going back to the example, it is simple to check thatνn→τ(0,1]totν*, where νn,ν* are given in Example 2.11 and τ(0,1] is the standard topology on (0,1]. In fact, let (ν¯n)n≥1 be any extension of (νn)n≥1 to the Borel sets of (0,1]. For any t∈(0,1), we have by (2.9) that(2.10)t-12n≤Fν¯n(t)≤t+12n,
where Fν¯n is the cumulative function of ν¯n, which implies the weak convergence of ν¯n to ν* and, therefore, νn→τ(0,1]totν*.For what concerns the topology onX, we will define the topological space (X,ϱP) induced by the pseudometric dP associated to the target problem (X,ℱ,T,P), and the pseudometric d. In this way ϱP is only defined with the data of the problem. One may ask: is this topology too poor? The answer is no, since it is defined by the pseudometric dP. In fact, dP(x,y)<ϵ means that x and y play “almost the same role” with respect to T. A direct algorithm which takes dP into account needs the computation of Pn at each step. In any case, even if dP may not be computable, it defines a nontrivial interesting topology ϱP on X. As expected, we have the following theorem.Theorem 2.13.
LetStrn(X,ℱ,T,P)=(X,ℱn,T,Pn), with Str target algorithm. Then, for any given x,
(2.11)Pn(x,⋅)⟶ϱPtotP(x,⋅).


## 3. The Target Algorithm

In this section, we introduce the core of the approximating target problem, namely a set of strategiesStr which solves the target problem.Given a measurable space(X,𝒳) and a target problem (X,ℱ,T,P), the target algorithm is built in the spirit of the exact one given in [1, 2], which starts from the largest classes T and X∖T and then reaches the optimal classes according to a backward construction.The target algorithm defines a strategyStr=(Strn)n≥0, where(3.1)Strn(X,F,T,P)=(X,Fn,T,Pn),
and it consists of three steps: (1)
the choice of a sequence(~ϵn)n≥1 of equivalences on the simplex defined on the unit ball of ℓ1 with ϵn→0;(2)
the definition of a filtration(ℱn)n based on (~ϵn)n≥1 where each ℱn is generated by a countable partition of X;(3)
the choice of a suitable measureμ and the definition of (Pn)n≥0.


### 3.1. Preliminary Results on Measurability and Equivalency and the Choice of(~ϵn)n≥1

Associated to each countably generated subσ-algebra 𝒜⊆𝒳, we define the equivalence relationship π𝒜 induced by the atoms of 𝒜:(3.2)xπAy⟺[x]A:=∩{A∈A:x∈A}=∩{A∈A:y∈A}=:[y]A.
Thus, if (𝒜n)n is a sequence of countably generated σ-algebras, then(3.3)π∨nAn=∩nπAn.Now, the atoms of theσ-algebra ℱ of each simple target problem (X,ℱ,T,Q) are at most countable, by definition. Then Q may be represented as a transition matrix on the state set ℕ. Each row of Q is a distribution probability on ℕ (i.e., a sequence (pn)n≥1 in the simplex S of ℓ1). The first step of the target algorithm is to equip S with the ℓ1-norm and then to define an ϵ-equivalence on S.We will alternatively use both the discrete equivalencies and the countable measurable partitions, as a consequence of the following result, whose proof is left to the appendices.Lemma 3.1.
Given a measurable space(X,𝒳), there exists a natural bijection between the set of discrete equivalencies on X and the set of the countable measurable partitions of it.LetSℓ1 be the unit sphere in ℓ1 and S={x≥0}∩Sℓ1 be the simplex on ℓ1. Let Ωn=[0,1], for any n, and τ be the standard topology on [0,1]. Denote by ℬ[0,1] the Borel σ-algebra on [0,1] generated by τ. We look at S as a subset of Πn=1∞Ωn so that the Borel σ-algebra ℬS induced on S is ⨂n=1∞ℬ[0,1]∩S.Definition 3.2.
~ϵ is an ϵ-equivalence onS if it is the product of finite equivalences on each (Ωn,ℬ[0,1]), and ∥p-q∥1<ϵ whenever p~ϵq.Remark 3.3.
The choice of theℓ1-norm on S is linked to the total variation distance between probability measures. This distance between two probability measures P and Q is defined by dTV(P,Q)=supA∈Ω|P(A)-Q(A)|. On the other hand, the total variation of a measure μ is ∥μ∥(Ω)=sup∑i|μ(Ai)|, where the supremum is taken over all the possible partitions of Ω. As (P-Q)(Ω)=0, we have that dTV(P,Q)=(1/2)∥P-Q∥; see [6]. To each p∈S corresponds the probability measure P on ℕ with P(i)=pi (and vice versa). In fact, p∈S implies pi≥0 and ∑ipi=1. Therefore, since ∥p-q∥1=∥P-Q∥=2dTV(P,Q), we have
(3.4)p∼ϵq⟹dTV(P,Q)<ϵ2.Example 3.4.
Define theϵ-cut as follows: p~ϵq⇔⌊pn/ϵ2-n⌋=⌊qn/ϵ2-n⌋, for all n, where ⌊x⌋ denotes the entire part of x.  ~ϵ is an ϵ-equivalence on S. Indeed, (i)
for eachn, define pn~nqn⇔⌊pn/ϵ2-n⌋=⌊qn/ϵ2-n⌋. Then ~n is a finite equivalence on Ωn and p~ϵq⇔(pn~nqn), for all n,(ii)
for anyp∈S(3.5)[p]={q∈S:π∼ϵ(q)=π∼ϵ(p)}=∏n[⌊2npn/ϵ⌋ϵ2n,(⌊2npn/ϵ⌋+1)ϵ2n)⋂S
is measurable with respect to ℬS,(iii)
for allp~ϵq,
(3.6)‖p-q‖1≤∑nϵ2-n=ϵ.


### 3.2. The Choice of(ℱn)n≥0

The following algorithm is a good candidate to be a strategy for the approximating problem we are facing. Given a sequence(~ϵn)n≥1 of ϵ-equivalences on S, we define (ℱn)n≥0 inductively. Consider the equivalence classes given by ℱn-1 and divide them again according to the next rule. Starting from any two points in the same class, we check whether the probabilities to attain any other ℱn-1-classes are ϵ-the same. Mathematically speaking: we have the following steps.Step 3.2.
ℱ0=σ(T)={∅,T,X∖T,X}.Step n.
ℱn is based on the equivalence ℱn-1 and on ~ϵn, inductively. ℱn-1 is generated by a countable partition of X, say (Ai(n-1))i. We define, for any couple (x,y)∈X2,
(3.7)(xπny)⟺(xπn-1y)∧((P(x,Ai(n-1))i)∼ϵn(P(y,Ai(n-1))i)).
Lemma 3.6 shows that πn is a discrete equivalency on (X,𝒳), and therefore it defines ℱn=σ(X/πn) as generated by a countable partition of X.Remark 3.5.
The choice of the “optimal” sequence(~ϵn)n≥1 is not the scope of this work. We only note that the definition of ~ϵ can be relaxed and the choice of the sequence (~ϵn)n≥1 may be done interactively, obtaining a fewer number of classes (Ai(n))i at each step.Lemma 3.6.
Let(X,ℱ,T,P) be a target problem. (ℱn)n≥0 defined as above, is a filtration on (X,ℱ) and for any n∈ℕ, πn is a finite (and hence discrete) equivalency on (X,𝒳).Proof.
The monotonicity of(ℱn)n≥0 is a simple consequence of (3.7).
The statement is true forn=0, since T∈𝒳. For the induction step, let {A1(n-1),A2(n-1),…,Akn(n-1)}∈𝒳 be the measurable partition of X given by X/πn-1. The map h:(X,𝒳)→(S,ℬ(S)) given by x↦(P(x,Ai(n-1)))i is therefore measurable. As ~ϵn is a finite equivalency on ∏1kn(Ωn,ℬ[0,1]), the map π~ϵn∘h:(X,𝒳)→(S/~ϵn,2S/~ϵn) is also measurable, where π~ϵn is the natural projection associated with ~ϵn. Thus, two points x,y∈X are such that(3.8)((P(x,Ai(n-1))i=1kn)∼ϵn(P(y,Ai(n-1))i=1kn))
if and only if their image by π~ϵn∘h is the same point of S/~ϵn. It results that the new partition of X built by πn is obtained as an intersection of the sets Ai(n-1),1≤i≤kn—which formed the πn-1-partition- with the counter-images of (∏i=1knΩi)/~ϵn by π~ϵn∘h. Intersections between two measurable finite partitions of X being a measurable finite partition of X, we are done.


### 3.3. The Choice ofμ and the Definition of (Pn)n≥0

Before defining(Pn)n≥0, we need the following result, which will be proved in Section 5.Theorem 3.7.
Let(πn)n≥0 be defined as in the previous section and let π∞=∩nπn. Then π∞ is a compatible projection.As a consequence of Theorems2.7 and 3.7, a target problem (X,∨nℱn,T,P∞) is well defined. We intend to define Pn as the μ-weighted mean average of P∞ given the information carried by ℱn.More precisely, letμ be a probability measure on (X,∨nℱn) such that μ(F)>0, for any F∈ℱn,F≠∅ (the existence of such a measure is shown in Example 3.8).For anyF∈ℱn, let YF be the ∨nℱn-random variable such that YF(ω)=P∞(ω,F). Define(3.9)Pn(x,F)=Eμ[YF∣Fn](x),∀x∈X,∀F∈Fn.Pn is uniquely defined on (X×ℱn), the only μ-null set of ℱn being the empty set. We claim that Pn(x,·) is a probability measure, for any x∈X.We give in the following an example of the measureμ that has been used in (3.9) which justifies its existence.Example 3.8.
Let(Yn)n≥0 be a sequence of independent and identically distributed geometric random variables, with ℙYi(j)=1/2j, j∈ℕ. Let 𝒜n=σ(Y0,…,Yn) and set 𝒜=∨𝒜n. There exists a probability measure ℙ on 𝒜 such that
(3.10)P(∩i=0n{Yli=yi})=PYl1(y1)⊗⋯⊗PYln(yn)=12∑i=0nyi,
and thus, ℙ(A)>0, for all A∈𝒜n,A≠∅. Moreover, it follows that for any n,
(3.11)A1∈An,A2∈σ(Yn+1),A1≠∅,A2≠∅,⟹P(A1∩A2)>0.
We check by induction that we can embed ℱn into 𝒜n, for any n≥0. The required measure μ will be the trace of ℙ on the embedded σ-field ∨nℱn.
Forn=0, define T↦{Y0=1}, X∖T↦{Y0≥2}. The embedding forms a nontrivial partition, and therefore the restriction of ℙ to the embedding of ℱ0 defines a probability measure on ℱ0 with μ0(F)>0 if F≠∅.
For the induction step, suppose it is true forn. Given Fi(n)∈ℱn, we have Fi(n)↦Ai(n), where (Ai(n))i is a nontrivial partition in 𝒜n and therefore the restriction of ℙ to the embedding of ℱn defines a probability measure μn on ℱn with μn(F)>0 if F≠∅.
GivenFi(n), let Hi(n+1):={Fj(n+1):Fj(n+1)⊆Fi(n)}. The monotonicity of πn ensures that each Fj(n+1) will belong to one and only one Hi(n+1). Moreover, by definition of Fj(n+1), we have that(3.12)Fi(n)=∪{Fj(n+1):Fj(n+1)∈Hi(n+1)}.
Since X/πn+1 is at most countable, we may order Hi(n+1) for any i. We have accordingly defined an injective map X/πn+1→ℕ2, where
(3.13)Fj(n+1)⟼(i,k)⟺Fj(n+1)isthekthelementinHi(n+1).
According to the cardinality ofHi(n+1), define the n+1-embedding(3.14)Fj(n+1)⟼(i,k)⟼Aj(n+1):=Ai(n)∩{{Yn+1=k}ifk<#{Hi(n+1)},{Yn+1≥k}ifk=#{Hi(n+1)}.
By definition of Aj(n+1) and (3.12), it follows that we have mapped ℱn+1 into a partition in 𝒜n+1. Moreover, ℙ(Aj(n+1))>0 as a consequence of (3.11). The restriction of ℙ to the embedding of ℱn+1 defines a probability measure on ℱn+1 with μn+1(F)>0 if F≠∅. Note that μn+1 is by construction an extension of μn to ℱn+1 since by (3.14),
(3.15)μn(Fi(n))=∑Fj(n+1)∈Hi(n+1)μn+1(Fj(n+1)).
Finally, the Carathéodory's extension theorem ensures the existence of the requiredμ, as μ(F)=μn(F), for any F∈ℱn. Note that μ is just mapped to the trace of ℙ on the embedded ℱ∞.


## 3.1. Preliminary Results on Measurability and Equivalency and the Choice of(~ϵn)n≥1

Associated to each countably generated subσ-algebra 𝒜⊆𝒳, we define the equivalence relationship π𝒜 induced by the atoms of 𝒜:(3.2)xπAy⟺[x]A:=∩{A∈A:x∈A}=∩{A∈A:y∈A}=:[y]A.
Thus, if (𝒜n)n is a sequence of countably generated σ-algebras, then(3.3)π∨nAn=∩nπAn.Now, the atoms of theσ-algebra ℱ of each simple target problem (X,ℱ,T,Q) are at most countable, by definition. Then Q may be represented as a transition matrix on the state set ℕ. Each row of Q is a distribution probability on ℕ (i.e., a sequence (pn)n≥1 in the simplex S of ℓ1). The first step of the target algorithm is to equip S with the ℓ1-norm and then to define an ϵ-equivalence on S.We will alternatively use both the discrete equivalencies and the countable measurable partitions, as a consequence of the following result, whose proof is left to the appendices.Lemma 3.1.
Given a measurable space(X,𝒳), there exists a natural bijection between the set of discrete equivalencies on X and the set of the countable measurable partitions of it.LetSℓ1 be the unit sphere in ℓ1 and S={x≥0}∩Sℓ1 be the simplex on ℓ1. Let Ωn=[0,1], for any n, and τ be the standard topology on [0,1]. Denote by ℬ[0,1] the Borel σ-algebra on [0,1] generated by τ. We look at S as a subset of Πn=1∞Ωn so that the Borel σ-algebra ℬS induced on S is ⨂n=1∞ℬ[0,1]∩S.Definition 3.2.
~ϵ is an ϵ-equivalence onS if it is the product of finite equivalences on each (Ωn,ℬ[0,1]), and ∥p-q∥1<ϵ whenever p~ϵq.Remark 3.3.
The choice of theℓ1-norm on S is linked to the total variation distance between probability measures. This distance between two probability measures P and Q is defined by dTV(P,Q)=supA∈Ω|P(A)-Q(A)|. On the other hand, the total variation of a measure μ is ∥μ∥(Ω)=sup∑i|μ(Ai)|, where the supremum is taken over all the possible partitions of Ω. As (P-Q)(Ω)=0, we have that dTV(P,Q)=(1/2)∥P-Q∥; see [6]. To each p∈S corresponds the probability measure P on ℕ with P(i)=pi (and vice versa). In fact, p∈S implies pi≥0 and ∑ipi=1. Therefore, since ∥p-q∥1=∥P-Q∥=2dTV(P,Q), we have
(3.4)p∼ϵq⟹dTV(P,Q)<ϵ2.Example 3.4.
Define theϵ-cut as follows: p~ϵq⇔⌊pn/ϵ2-n⌋=⌊qn/ϵ2-n⌋, for all n, where ⌊x⌋ denotes the entire part of x.  ~ϵ is an ϵ-equivalence on S. Indeed, (i)
for eachn, define pn~nqn⇔⌊pn/ϵ2-n⌋=⌊qn/ϵ2-n⌋. Then ~n is a finite equivalence on Ωn and p~ϵq⇔(pn~nqn), for all n,(ii)
for anyp∈S(3.5)[p]={q∈S:π∼ϵ(q)=π∼ϵ(p)}=∏n[⌊2npn/ϵ⌋ϵ2n,(⌊2npn/ϵ⌋+1)ϵ2n)⋂S
is measurable with respect to ℬS,(iii)
for allp~ϵq,
(3.6)‖p-q‖1≤∑nϵ2-n=ϵ.


## 3.2. The Choice of(ℱn)n≥0

The following algorithm is a good candidate to be a strategy for the approximating problem we are facing. Given a sequence(~ϵn)n≥1 of ϵ-equivalences on S, we define (ℱn)n≥0 inductively. Consider the equivalence classes given by ℱn-1 and divide them again according to the next rule. Starting from any two points in the same class, we check whether the probabilities to attain any other ℱn-1-classes are ϵ-the same. Mathematically speaking: we have the following steps.Step 3.2.
ℱ0=σ(T)={∅,T,X∖T,X}.Step n.
ℱn is based on the equivalence ℱn-1 and on ~ϵn, inductively. ℱn-1 is generated by a countable partition of X, say (Ai(n-1))i. We define, for any couple (x,y)∈X2,
(3.7)(xπny)⟺(xπn-1y)∧((P(x,Ai(n-1))i)∼ϵn(P(y,Ai(n-1))i)).
Lemma 3.6 shows that πn is a discrete equivalency on (X,𝒳), and therefore it defines ℱn=σ(X/πn) as generated by a countable partition of X.Remark 3.5.
The choice of the “optimal” sequence(~ϵn)n≥1 is not the scope of this work. We only note that the definition of ~ϵ can be relaxed and the choice of the sequence (~ϵn)n≥1 may be done interactively, obtaining a fewer number of classes (Ai(n))i at each step.Lemma 3.6.
Let(X,ℱ,T,P) be a target problem. (ℱn)n≥0 defined as above, is a filtration on (X,ℱ) and for any n∈ℕ, πn is a finite (and hence discrete) equivalency on (X,𝒳).Proof.
The monotonicity of(ℱn)n≥0 is a simple consequence of (3.7).
The statement is true forn=0, since T∈𝒳. For the induction step, let {A1(n-1),A2(n-1),…,Akn(n-1)}∈𝒳 be the measurable partition of X given by X/πn-1. The map h:(X,𝒳)→(S,ℬ(S)) given by x↦(P(x,Ai(n-1)))i is therefore measurable. As ~ϵn is a finite equivalency on ∏1kn(Ωn,ℬ[0,1]), the map π~ϵn∘h:(X,𝒳)→(S/~ϵn,2S/~ϵn) is also measurable, where π~ϵn is the natural projection associated with ~ϵn. Thus, two points x,y∈X are such that(3.8)((P(x,Ai(n-1))i=1kn)∼ϵn(P(y,Ai(n-1))i=1kn))
if and only if their image by π~ϵn∘h is the same point of S/~ϵn. It results that the new partition of X built by πn is obtained as an intersection of the sets Ai(n-1),1≤i≤kn—which formed the πn-1-partition- with the counter-images of (∏i=1knΩi)/~ϵn by π~ϵn∘h. Intersections between two measurable finite partitions of X being a measurable finite partition of X, we are done.


## 3.3. The Choice ofμ and the Definition of (Pn)n≥0

Before defining(Pn)n≥0, we need the following result, which will be proved in Section 5.Theorem 3.7.
Let(πn)n≥0 be defined as in the previous section and let π∞=∩nπn. Then π∞ is a compatible projection.As a consequence of Theorems2.7 and 3.7, a target problem (X,∨nℱn,T,P∞) is well defined. We intend to define Pn as the μ-weighted mean average of P∞ given the information carried by ℱn.More precisely, letμ be a probability measure on (X,∨nℱn) such that μ(F)>0, for any F∈ℱn,F≠∅ (the existence of such a measure is shown in Example 3.8).For anyF∈ℱn, let YF be the ∨nℱn-random variable such that YF(ω)=P∞(ω,F). Define(3.9)Pn(x,F)=Eμ[YF∣Fn](x),∀x∈X,∀F∈Fn.Pn is uniquely defined on (X×ℱn), the only μ-null set of ℱn being the empty set. We claim that Pn(x,·) is a probability measure, for any x∈X.We give in the following an example of the measureμ that has been used in (3.9) which justifies its existence.Example 3.8.
Let(Yn)n≥0 be a sequence of independent and identically distributed geometric random variables, with ℙYi(j)=1/2j, j∈ℕ. Let 𝒜n=σ(Y0,…,Yn) and set 𝒜=∨𝒜n. There exists a probability measure ℙ on 𝒜 such that
(3.10)P(∩i=0n{Yli=yi})=PYl1(y1)⊗⋯⊗PYln(yn)=12∑i=0nyi,
and thus, ℙ(A)>0, for all A∈𝒜n,A≠∅. Moreover, it follows that for any n,
(3.11)A1∈An,A2∈σ(Yn+1),A1≠∅,A2≠∅,⟹P(A1∩A2)>0.
We check by induction that we can embed ℱn into 𝒜n, for any n≥0. The required measure μ will be the trace of ℙ on the embedded σ-field ∨nℱn.
Forn=0, define T↦{Y0=1}, X∖T↦{Y0≥2}. The embedding forms a nontrivial partition, and therefore the restriction of ℙ to the embedding of ℱ0 defines a probability measure on ℱ0 with μ0(F)>0 if F≠∅.
For the induction step, suppose it is true forn. Given Fi(n)∈ℱn, we have Fi(n)↦Ai(n), where (Ai(n))i is a nontrivial partition in 𝒜n and therefore the restriction of ℙ to the embedding of ℱn defines a probability measure μn on ℱn with μn(F)>0 if F≠∅.
GivenFi(n), let Hi(n+1):={Fj(n+1):Fj(n+1)⊆Fi(n)}. The monotonicity of πn ensures that each Fj(n+1) will belong to one and only one Hi(n+1). Moreover, by definition of Fj(n+1), we have that(3.12)Fi(n)=∪{Fj(n+1):Fj(n+1)∈Hi(n+1)}.
Since X/πn+1 is at most countable, we may order Hi(n+1) for any i. We have accordingly defined an injective map X/πn+1→ℕ2, where
(3.13)Fj(n+1)⟼(i,k)⟺Fj(n+1)isthekthelementinHi(n+1).
According to the cardinality ofHi(n+1), define the n+1-embedding(3.14)Fj(n+1)⟼(i,k)⟼Aj(n+1):=Ai(n)∩{{Yn+1=k}ifk<#{Hi(n+1)},{Yn+1≥k}ifk=#{Hi(n+1)}.
By definition of Aj(n+1) and (3.12), it follows that we have mapped ℱn+1 into a partition in 𝒜n+1. Moreover, ℙ(Aj(n+1))>0 as a consequence of (3.11). The restriction of ℙ to the embedding of ℱn+1 defines a probability measure on ℱn+1 with μn+1(F)>0 if F≠∅. Note that μn+1 is by construction an extension of μn to ℱn+1 since by (3.14),
(3.15)μn(Fi(n))=∑Fj(n+1)∈Hi(n+1)μn+1(Fj(n+1)).
Finally, the Carathéodory's extension theorem ensures the existence of the requiredμ, as μ(F)=μn(F), for any F∈ℱn. Note that μ is just mapped to the trace of ℙ on the embedded ℱ∞.


## 4. Blackwell

The problem of approximation is mathematically different if we start from a Markov process with a countable set of states or with an uncountable one. Let us consider, for the moment, the countable case:X is an at most countable set of the states and 𝒳=2X is the power set. Each function on X is measurable. If we take any equivalence relation on X, it is both measurable and identified by the σ-algebra it induces (see Theorem 4.6). This is not in general the case when we deal with a measurable space (X,𝒳), with X uncountable. In this section, we want to connect the process of approximation with the upgrading information. More precisely, a measurable equivalence π=πf defines both the partition X/π and the sigma algebra σ(f). One wishes these two objects to be related, in the sense that ordering should be preserved. Example 4.5 shows a paradox concerning πf and σ(f) when X is uncountable. In fact, we have the following lemma.Lemma 4.1.
Let𝒜1⊆𝒜2 be countably generated sub σ-algebras of a measurable space (X,𝒳). Then [x]𝒜1⊇[x]𝒜2.
In particular, letf,g be random variables. If σ(f)⊇σ(g), then πf⊆πg.Proof.
See AppendixA.The problem is that even if a partition is more informative than another one, it is not true that it generates a finerσ-algebra, that is, the following implication is not always true for any couple of random variables f and g:(A0)πf⊆πg⟹σ(f)⊇σ(g).
Then Lemma 4.1 is not invertible, if we do not require the further assumption (A0) on the measurable space (X,𝒳). This last fact connects the space (X,𝒳) with the theory of Blackwell spaces (see Lemma 4.3). We will assume the sole assumption (A0).Example 4.2 (πf=πg⇏σ(f)=σ(g)).
We give here a counterexample to assumption (A0), where two random variables f,g generate two different sigma algebras σ(f)≠σ(g) with the same set of atoms. Obviously, assumption (A0) does not hold. Let (X,ℬX) be a Polish space and suppose ℬX⊊𝒳. Let A∈𝒳∖ℬX and consider the sequence {An, n∈ℕ} that determines ℬX, that is, ℬX=σ(An, n∈ℕ). Let 𝒜=σ(A,An,n∈ℕ). ℬX⊊𝒜. As a consequence of Lemma A.3, there exist two random variables f,g such that ℬX=σ(f) and 𝒜=σ(g). The atoms of ℬX are the points of X, and then the atoms of 𝒜 are also the points of X, since ℬX⊆𝒜.We recall here the definition of Blackwell spaces. A measurable space(X,𝒳) is said Blackwell if 𝒳 is a countably generated σ-algebra of X and 𝒜=𝒳 whenever 𝒜 is another countably generated σ-algebra of X such that 𝒜⊆𝒳, and 𝒜 has the same atoms as 𝒳. A metric space X is Blackwell if, when endowed with its Borel σ-algebra, it is Blackwell. The measurable space (X,𝒳) is said to be a strongly Blackwell space if 𝒳 is a countably generated σ-algebra of X and (A1)
𝒜1=𝒜2 if and only if the sets of their atoms coincide, where 𝒜1 and 𝒜2 are countably generated σ-algebras with 𝒜i⊆𝒳, i=1,2.For what concerns Blackwell spaces, the literature is quite extensive. Blackwell proved that every analytic subset of a Polish space is, with respect to its relative Borelσ-field, a strongly Blackwell space (see [7]). Therefore, if (X,ℬX) is (an analytic subset of) a Polish space and ℬX⊊𝒳, then (X,𝒳) cannot be a weakly Blackwell space (see Example 4.2). Moreover, as any (at most) countable set equipped with any σ-algebra may be seen as an analytic subset of a Polish space, then it is a strongly Blackwell space. More connections and examples involving Blackwell spaces, measurable sets and analytical sets in connection with continuum hypothesis (CH) may be found in [8–11]. Finally, note that assumption (A0) and assumption (A1) coincide, as the following lemma states.Lemma 4.3.
Let(X,𝒳) be a measurable space. Then (A0) holds if and only if (A1) holds.Proof.
LemmaA.3 in Appendix A asserts that 𝒜⊆𝒳 is countably generated if and only if there exists a random variable f such that 𝒜=σ(f). In addition, as a consequence of Lemma 4.1, we have only to prove that (A1) implies (A0). By contradiction, assume (A1), πf⊆πg, but σ(g)⊈σ(f). We have σ(f,g)≠σ(f), and then πσ(f,g)≠πf by (A1) and Lemma A.3. On the other hand, from (3.3), we have that πσ(f,g)=πσ(f)∨σ(g)=πf∩πg=πf.We callweakly Blackwell space a measurable space (X,𝒳) such that assumption (A0) holds. If (X,𝒳) is a weakly Blackwell space, then (X,ℱ) is a weakly Blackwell space, for any ℱ⊆𝒳. Moreover, every strong Blackwell space is both a Blackwell space and a weakly Blackwell space whilst the other inclusions are not true in general. In [12, 13], examples are provided of Blackwell spaces which may be shown not to be weakly Blackwell. The following example shows that a weakly Blackwell space need not be Blackwell.Example 4.4 (weakly Blackwell⇏ Blackwell).
LetX be an uncountable set and 𝒳 be the countable-cocountable σ-algebra on X. 𝒳 is easily shown to be not countably generated, and therefore (X,𝒳) is not a Blackwell space. Take any countably generated σ-field 𝒜⊆𝒳, that is, 𝒜=σ({Ai, i∈ℕ}). (i)
Since each set (or its complementary) of𝒳 is countable, then, without loss of generality, we can assume the cardinality of X∖Ai to be countable.(ii)
Each atomB of σ(Ai, i∈ℕ) is of the form
(4.1)B=⋂i=1,2,…Ci,whereCi=AiorCi=X∖Ai,foranyi.Note that the cardinality of the set A:=∪i(X∖Ai) is countable, as it is a countable union of countable sets. As a consequence of (4.1), we face two types of atoms: (1)
for anyi, Ci=Ai. This is the atom made by the intersections of all the uncountable generators. This is an uncountable atom, as it is equal to X∖A.(2)
existsi such that Ci=X∖Ai. This implies that this atom is a subset of the countable set A. Therefore, all the atoms (except X∖A) are disjoint subsets of the countable set A and hence they are countable.It follows that the number of atoms of 𝒜 is at most countable. Thus, (X,𝒜) is a strongly Blackwell space, that is, (X,𝒳) is a weakly Blackwell space.Example 4.5 (Information andσ-algebra (see [4])).
SupposeX=[0,1], 𝒳=σ(𝒴,A) where 𝒴 is the countable-cocountable σ-algebra on X and A=[0,1/2). Consider a decisionmaker who chooses action 1 if x<1/2 and action 2 if x≥1/2. Suppose now that the information is modeled either as the partition of all elements of X, τ={x, x∈X} and in this case the decisionmaker is perfectly informed, or as the partition τ′={A,X∖A}. If we deal with σ-algebras as a model of information then σ(τ)=𝒴 and σ(τ′)=σ(A). The partition τ is more informative than τ′, whereas σ(τ) is not finer than σ(τ′). In fact A∉𝒴 and therefore if the decisionmaker uses σ(τ) as its structure of information, believing it more detailed than σ(τ′), he will never know whether or not the event A has occurred and can be led to take the wrong decision. In this case, σ-algebras do not preserve information because they are not closed under arbitrary unions. However, if we deal with Blackwell spaces, any countably generated σ-algebra is identified by its atoms and therefore will possess an informational content (see, e.g., [14]).The following theorem, whose proof is in AppendixB, connects the measurability of any relation to the cardinality of the space and assumption (A0). It shows the main difference between the uncountable case and the countable one.Theorem 4.6.
Assume (CH). Let(X,𝒳) be a measurable space. The following properties are equivalent: (1)
any equivalence relationπ on X is measurable and assumption (A0) holds,(2)
(X,2X) is a weakly Blackwell space,(3)
X is countable and 𝒳=2X.


## 5. Proofs

The following theorem mathematically motivates our approximation problem: any limit of a monotone sequence of discrete equivalence relationships is a measurable equivalence.Theorem 5.1.
For alln∈ℕ, let πn be a discrete equivalency. Then π∞=∩nπn is a measurable equivalency. Conversely, for any measurable equivalency π, there exists a sequence (πn)n≥0 of discrete equivalencies such that π∞=∩nπn.Proof.
See AppendixA.Proof of Theorem2.7.
Letπ=πf be a compatible projection. We define
(5.1)Pπ(x,F):=P(x,F),∀x∈X,∀F∈σ(f).
What remains to prove is that Pπ∈TrP(X,𝒳,σ(f)). More precisely, we have to show that Pπ(·,F) is σ(f)-measurable, for all F∈σ(f). By contradiction, there exists F∈σ(f) such that the random variable YF(ω)=Pπ(ω,F) is not σ(f)-measurable. Then σ(YF)⊈σ(f), and hence πYF⊉πf by assumption (A0), which contradicts (2.7).Proof of Theorem3.7.
As a consequence of Theorem5.1, π∞=πf, where σ(f)=∨nℱn. Define
(5.2)P∞(x,F):=P(x,F),∀x∈X,∀F∈σ(f).
We will prove that, for any F∈σ(f), P∞(·,F) is σ(f)-measurable and consequently π∞ will be a compatible projection. This implies that there exists a measurable function hF:(ℝ,ℬR)→(ℝ,ℬR) so that P∞(ω,F)=hF(f(ω)). Therefore, if xπfy, then P∞(x,F)=P∞(y,F), which is the thesis.
We need to show that for anyF∈σ(f) and t∈ℝ, we have(5.3)H:={x:P(x,F)≤t}∈σ(f).
We first show that it is true when F∈ℱn by proving that
(5.4)H=⋂m>nπm-1πm(H),
which implies that H∈σ(f). The inclusion H⊆∩mπm-1πm(H) is always true. For the other inclusion, let y∈∩m>nπm-1πm(H). Let m>n; there exists xm∈H such that yπmxm. Therefore, (3.7) and the definition of ~ϵn imply P(y,F)≤P(xm,F)+ϵm≤t+ϵm, for any m>n. As ϵm↘0, we obtain that y∈H. Then (5.3) is true on the algebra Alg:=∪nℱn.
Actually, letFn∈Alg such that Fn↗F. We prove that (5.3) holds for F by showing that (5.5)H={x:P(x,F)≤t}=⋂n{x:P(x,Fn)≤t}=:⋂nHn.
Again, since Fn⊆F, then P(x,Fn)≤P(x,F) and therefore H⊆⋂nHn. Conversely, the set ∩nHn∖H is empty since the sequence of 𝒳-measurable maps P(·,F)-P(·,Fn) converges to 0:
(5.6)P(⋅,F)-P(⋅,Fn)=P(⋅,F∖Fn)⟶P(⋅,∅)=0.
Then (5.3) is true on the monotone class generated by the algebra Alg=∪nℱn, that is, on σ(f).Proof of Theorem2.8.
Given a target algorithm(X,ℱn,T,Pn)n, let π∞=πf be defined as in Theorem 3.7. We claim that π∞ is optimal. Let ψg be another compatible projection and let (X,σ(g),T,Pg) be the target problem given by Theorem 2.7. We are going to prove by induction on n that
(5.7)∀n∈N,Fn⊆σ(g).
In fact, for n=0 it is sufficient to note that ℱ0=σ({T})⊆σ(g).
Equation (3.7) states that ℱn=σ(ℱn-1,hn), where hn is the discrete random variable, given by Lemma 3.1, s.t.(5.8)
Letki(n-1):X→[0,1] be defined as ki(n-1)(x)=P(x,Ai(n-1)). Then(5.9)
Obviously, σ(hn)⊆σ(k1(n-1),k2(n-1),…). For the induction step, as Ai(n-1)∈ℱn-1⊆σ(g), we have that Pg(·,Ai(n-1)) is σ(g)-measurable, and therefore σ(ki(n-1))⊆σ(g). Then ℱn=σ(ℱn-1,hn)⊆σ(ℱn-1,k1(n-1),k2(n-1),…)⊆σ(g). Therefore σ(f)=∨nℱn⊆σ(g), which implies π∞⊇ψg by Lemma 4.1, and hence π∞ is optimal.Corollary 5.2.
π∞ does not depend on the choice of Str.Proof.
π∞=∩nπn is optimal, for all (πn)n≥0=Str(P). The optimal projection being unique, we are done.Proof of Theorem2.4.
Letπ∞=πf be defined as in Theorem 3.7 and (X,σ(f),T,P∞) be given by Theorem 2.7 so that P(x,F)=P∞(x,F) for any F∈σ(f). Then each Pn of (3.9) can be rewritten as
(5.10)Pn(x,F)=∫[x]nP∞(x,F)μ(dz)μ([x]n),∀x∈X,∀F∈Fn,
where [x]n is the πn-class of equivalence of x and μ([x]n)>0 since [x]n≠∅.
Note thatd(P,Pm)≤2∑nβn. Then, for any ϵ>0, there exists an N so that ∑n>Nβn≤ϵ/2. Therefore we are going to prove by induction on n that (5.11)sup⁡x|Pmn(x,T)-Pn(x,T)|⟶0asmtendstoinfinity,
which completes the proof. If n=1, then by definition of ϵm, since T∈ℱm-1, we have that
(5.12)|Pm(x,T)-P(x,T)|≤∫[x]m|P∞(z,T)-P(x,T)|μ(dz)μ([x]m)=∫[x]m|P(z,T)-P(x,T)|μ(dz)μ([x]m)≤ϵm∫[x]mμ(dz)μ([x]m)=ϵm.
For the induction step, we note that
(5.13)|Pmn+1(x,T)-Pn+1(x,T)|≤∑i|Pm(x,Ai(m))Pmn(Ai(m),T)-∫Ai(m)P(x,dz)Pn(z,T)|,
where (Ai(m))i is the partition of X given by πm. By induction hypothesis, for any ϵ̃>0,
(5.14)|Pmn(z,T)-Pn(z,T)|≤ϵ̃
for m≥m0 large enough. Since [z]m=Ai(m) if z∈Ai(m), it follows that
(5.15)∫Ai(m)P(x,dz)|Pmn(Ai(m),T)-Pn(z,T)|≤ϵ̃∫Ai(m)P(x,dz).
Equation (5.13) becomes
(5.16)|Pmn+1(x,T)-Pn+1(x,T)|≤ϵ̃+∑iPmn(Ai(m),T)|Pm(x,Ai(m))-P(x,Ai(m))|≤ϵ̃+∑i|Pm(x,Ai(m))-P(x,Ai(m))|.
On the other hand, by (5.10),
(5.17)Pm(x,Ai(m))-P(x,Ai(m))=∫[x]mP∞(z,Ai(m))-P(x,Ai(m))μ([x]m)μ(dz).
The definition of ~ϵm+1 states that
(5.18)∑i|P∞(z,Ai(m))-P(x,Ai(m))|≤ϵm+1
whenever z∈[x]m and therefore
(5.19)|Pmn+1(x,T)-Pn+1(x,T)|≤ϵ̃+∫[x]m∑i|P∞(z,Ai(m))-P(x,Ai(m))|μ(dz)μ([x]m)≤ϵ̃+ϵm+1.
Since ϵm→0 as m tends to infinity, we get the result.Proof of Theorem2.9.
By (3.9) and Lemma 3.6, (Pn(·,F))n≥m is a martingale with respect to the filtration (ℱn)n≥m, for any F∈ℱm. Then, if YF(x)=P(x,F) as in (3.9), we have that
(5.20)Pn(x,F)⟶n→∞Eμ[YF∣∨nFn](x)=YF(x),forμ-a.e.x∈X,∀F∈Fm.
Let π∞=πf be defined as in Theorem 3.7 and (X,σ(f),T,P∞) given by Theorem 2.7 so that P(x,F)=P∞(x,F) for any F∈σ(f). Unfortunately, (5.20) is not enough to state that
(5.21)Pn(x,F)⟶n→∞P∞(x,F),forx∈X,∀F∈⋃mFm,
even if σ(f) is countably generated (see, e.g., [15], for counterexample). In fact, Polish assumption is assumed in [15] to guarantee (5.21).
Here, we will deal with the specific properties ofPn and P∞ to deduce (5.21). Take F∈ℱm and n>m. By (5.10) and the definition of ϵn, since F∈ℱn-1, we have, for any x∈X, that(5.22)|Pn(x,F)-P(x,F)|≤∫[x]n|P∞(z,F)-P(x,F)|μ(dz)μ([x]n)=∫[x]n|P(z,F)-P(x,F)|μ(dz)μ([x]n)≤ϵn∫[x]nμ(dz)μ([x]n)=ϵn
since the only μ-null set in ℱn is the empty set. Then
(5.23)Pn(x,F)⟶n→∞P∞(x,F)
for any x∈X and F∈∪mℱm.


### 5.1. Weak Convergence of Conditional Probabilities

Let the target problem(X,ℱ,T,P) be given and let Str=(Strn)n, where Strn(X,ℱ,T,P)=(X,ℱ̃n,T,P̃n) be a target algorithm. In order to prove Theorem 2.13, which states the total convergence of the probability measure Pn(x,·) towards P(x,·), we proceed as follows: (i)
first, we define the topologyϱP on X;(ii)
then, we define a “natural” topologyτStr on X associated to any target algorithm (Strn)n. We prove in Theorem 5.4 the total convergence of (Pn)n≥0 to P∞, under this topology;(iii)
then, we define the topologyτP on X as the intersection of all the topologies τStr;(iv)
finally, we show Theorem2.13 by proving that ϱP⊆τStr. The nontriviality of ϱP will imply that of τP.We introduce the pseudometricdP on X as follows:(5.24)dP(x,y)=∑nβn|Pn(x,T)-Pn(y,T)|.Now, letτStr be the topology generated by ∪nℱn. C is a closed set if and only if C=∩nCn, Cn∈ℱn. In fact, if C∈ℱn, for a given n, then C∈ℱn+p, for any p and therefore C is closed. (X,τStr) is a topological space.Remark 5.3.
Let us go back to Example2.11. The topology defined by asking that the sets in each ℱn are closed is strictly finer than the standard topology. On the other hand, the same example may be explained with left closed-right opened dyadic subdivisions, which leads to a different topology that also contains the natural one. Any other “reasonable” choice of subdivision will lead to the same point: the topologies are different, and all contain the standard one. In the same manner, we are going to show that all the topologies τStr contain the standard one, ϱP.Theorem 5.4.
Let the target problem(X,ℱ,T,P) and the target algorithm (X,ℱn,T,Pn)n be given. For any target algorithm Str,
(5.25)Pn(x,⋅)⟶τStrtotP(x,⋅),∀x∈X.Proof.
Denote byP¯n any extension of Pn to ∨nℱn. We have to check that limsupnP¯n(x,C)≤P(x,C), for any closed set C of Str and x∈X (see, e.g., [6]).
Let{Cn∈ℱn}, with Cn⊇Cn+1 and C=∩nCn (take, e.g., Cn as the closure of C in ℱn).
Note that, sinceC∈∨nℱn, we have P(x,C)=P∞(x,C). But, P¯n(x,C)-P∞(x,C)≤P¯n(x,Cn-1)-P∞(x,C)=Pn(x,Cn-1)-P∞(x,C). Actually, (5.26)Pn(x,Cn-1)-P∞(x,C)=(Pn(x,Cn-1)-P∞(x,Cn-1)︸I)+(P∞(x,Cn-1)-P∞(x,C)︸II).I→0 as n tends to infinity, from the target algorithm and II→0 as n tends to infinity, from the continuity of the measure.An example of a natural extension ofPn to P¯n is given by(5.27)P¯n(x,F)=Eμ[YF∣Fn](x),∀x∈X,∀F∈∨nFn,
where, for any F∈∨nℱn, YF is the ∨nℱn-random variable such that YF(ω)=P∞(ω,F). As mentioned for Pn, P¯n(x,·) is a probability measure, for any x∈X.Corollary 5.5.
For any fixed strategyStr(P), let Pn be as in Theorem 2.4. We have
(5.28)Pn(x,⋅)⟶τPtotP(x,⋅),
for any given x.In order to describe the topologyτP, we will denote by [[F]]* the closure of a set F⊆X in a given topology *. Note that the monotonicity of πn implies(5.29)[[F]]τStr=⋂n[[F]]τStrn
where τStrn is the (discrete) topology on X generated by ℱn. Since τP is the intersection of all the topologies τStr, we have
(5.30)[[F]]τP⊇[[F]]τStr=⋂n[[F]]τStrn,∀F∈2X,∀Str.Proof of Theorem2.13.
LetF be the closed set in ϱP so defined
(5.31)F:={y∈X:dP(y,x)≥r},
that is, F is the complementary of an open ball in (X,dP) with center x and radius r. If we show that F∈τP, then we are done, as the arbitrary choice of x and r spans a base for the topology ϱP.
We are going to prove(5.32)F=[[F]]τStr=⋂m[[F]]τStrm,∀Str,
which implies [[F]]τP=F. It is always true that F⊆[[F]]*; we prove the nontrivial inclusion F⊇∩m[[F]]τStrm. Assume that y∈[[F]]τStr. Now, y∈[[F]]τStrm, for any m, and then there exists a sequence (ym)n≥0 with ym∈F such that yπmym, for any m. Thus, y∈∩m[ym]m, where [x]m is the πm-class of equivalence of x. Thus
(5.33)Pmn(ym,T)=Pmn(y,T),∀m,n
since Pm(·,T) is ℱm-measurable. By Theorem 2.4, for any n∈ℕ,
(5.34)|Pn(y,T)-Pmn(y,T)|+|Pmn(ym,T)-Pn(ym,T)|⟶m→∞0.
Now, let N be such that ∑n=N∞βn≤ϵ/4 and take n0 sufficiently large s.t.
(5.35)∑n=0N|Pn(y,T)-Pn0n(y,T)|+|Pn0n(yn0,T)-Pn(yn0,T)|≤ϵ2.
We have
(5.36)dP(yn0,y)=∑nβn|Pn(y,T)-Pn(yn0,T)|≤∑n=0N|Pn(y,T)-Pn(yn0,T)|+2∑n=N∞βn≤∑n=0N(|Pn(y,T)-Pn0n(y,T)|+|Pn0n(y,T)-Pn0n(yn0,T)|+|Pn0n(yn0,T)-Pn(yn0,T)|)+2ϵ4≤ϵ2+ϵ2=ϵ,
and therefore
(5.37)dP(x,y)≥dP(x,yn0)-dP(yn0,y)≥r-ϵ.
The arbitrary choice of ϵ implies y∈F, which is the thesis.


## 5.1. Weak Convergence of Conditional Probabilities

Let the target problem(X,ℱ,T,P) be given and let Str=(Strn)n, where Strn(X,ℱ,T,P)=(X,ℱ̃n,T,P̃n) be a target algorithm. In order to prove Theorem 2.13, which states the total convergence of the probability measure Pn(x,·) towards P(x,·), we proceed as follows: (i)
first, we define the topologyϱP on X;(ii)
then, we define a “natural” topologyτStr on X associated to any target algorithm (Strn)n. We prove in Theorem 5.4 the total convergence of (Pn)n≥0 to P∞, under this topology;(iii)
then, we define the topologyτP on X as the intersection of all the topologies τStr;(iv)
finally, we show Theorem2.13 by proving that ϱP⊆τStr. The nontriviality of ϱP will imply that of τP.We introduce the pseudometricdP on X as follows:(5.24)dP(x,y)=∑nβn|Pn(x,T)-Pn(y,T)|.Now, letτStr be the topology generated by ∪nℱn. C is a closed set if and only if C=∩nCn, Cn∈ℱn. In fact, if C∈ℱn, for a given n, then C∈ℱn+p, for any p and therefore C is closed. (X,τStr) is a topological space.Remark 5.3.
Let us go back to Example2.11. The topology defined by asking that the sets in each ℱn are closed is strictly finer than the standard topology. On the other hand, the same example may be explained with left closed-right opened dyadic subdivisions, which leads to a different topology that also contains the natural one. Any other “reasonable” choice of subdivision will lead to the same point: the topologies are different, and all contain the standard one. In the same manner, we are going to show that all the topologies τStr contain the standard one, ϱP.Theorem 5.4.
Let the target problem(X,ℱ,T,P) and the target algorithm (X,ℱn,T,Pn)n be given. For any target algorithm Str,
(5.25)Pn(x,⋅)⟶τStrtotP(x,⋅),∀x∈X.Proof.
Denote byP¯n any extension of Pn to ∨nℱn. We have to check that limsupnP¯n(x,C)≤P(x,C), for any closed set C of Str and x∈X (see, e.g., [6]).
Let{Cn∈ℱn}, with Cn⊇Cn+1 and C=∩nCn (take, e.g., Cn as the closure of C in ℱn).
Note that, sinceC∈∨nℱn, we have P(x,C)=P∞(x,C). But, P¯n(x,C)-P∞(x,C)≤P¯n(x,Cn-1)-P∞(x,C)=Pn(x,Cn-1)-P∞(x,C). Actually, (5.26)Pn(x,Cn-1)-P∞(x,C)=(Pn(x,Cn-1)-P∞(x,Cn-1)︸I)+(P∞(x,Cn-1)-P∞(x,C)︸II).I→0 as n tends to infinity, from the target algorithm and II→0 as n tends to infinity, from the continuity of the measure.An example of a natural extension ofPn to P¯n is given by(5.27)P¯n(x,F)=Eμ[YF∣Fn](x),∀x∈X,∀F∈∨nFn,
where, for any F∈∨nℱn, YF is the ∨nℱn-random variable such that YF(ω)=P∞(ω,F). As mentioned for Pn, P¯n(x,·) is a probability measure, for any x∈X.Corollary 5.5.
For any fixed strategyStr(P), let Pn be as in Theorem 2.4. We have
(5.28)Pn(x,⋅)⟶τPtotP(x,⋅),
for any given x.In order to describe the topologyτP, we will denote by [[F]]* the closure of a set F⊆X in a given topology *. Note that the monotonicity of πn implies(5.29)[[F]]τStr=⋂n[[F]]τStrn
where τStrn is the (discrete) topology on X generated by ℱn. Since τP is the intersection of all the topologies τStr, we have
(5.30)[[F]]τP⊇[[F]]τStr=⋂n[[F]]τStrn,∀F∈2X,∀Str.Proof of Theorem2.13.
LetF be the closed set in ϱP so defined
(5.31)F:={y∈X:dP(y,x)≥r},
that is, F is the complementary of an open ball in (X,dP) with center x and radius r. If we show that F∈τP, then we are done, as the arbitrary choice of x and r spans a base for the topology ϱP.
We are going to prove(5.32)F=[[F]]τStr=⋂m[[F]]τStrm,∀Str,
which implies [[F]]τP=F. It is always true that F⊆[[F]]*; we prove the nontrivial inclusion F⊇∩m[[F]]τStrm. Assume that y∈[[F]]τStr. Now, y∈[[F]]τStrm, for any m, and then there exists a sequence (ym)n≥0 with ym∈F such that yπmym, for any m. Thus, y∈∩m[ym]m, where [x]m is the πm-class of equivalence of x. Thus
(5.33)Pmn(ym,T)=Pmn(y,T),∀m,n
since Pm(·,T) is ℱm-measurable. By Theorem 2.4, for any n∈ℕ,
(5.34)|Pn(y,T)-Pmn(y,T)|+|Pmn(ym,T)-Pn(ym,T)|⟶m→∞0.
Now, let N be such that ∑n=N∞βn≤ϵ/4 and take n0 sufficiently large s.t.
(5.35)∑n=0N|Pn(y,T)-Pn0n(y,T)|+|Pn0n(yn0,T)-Pn(yn0,T)|≤ϵ2.
We have
(5.36)dP(yn0,y)=∑nβn|Pn(y,T)-Pn(yn0,T)|≤∑n=0N|Pn(y,T)-Pn(yn0,T)|+2∑n=N∞βn≤∑n=0N(|Pn(y,T)-Pn0n(y,T)|+|Pn0n(y,T)-Pn0n(yn0,T)|+|Pn0n(yn0,T)-Pn(yn0,T)|)+2ϵ4≤ϵ2+ϵ2=ϵ,
and therefore
(5.37)dP(x,y)≥dP(x,yn0)-dP(yn0,y)≥r-ϵ.
The arbitrary choice of ϵ implies y∈F, which is the thesis.



---

*Source: 801303-2011-08-11.xml*