tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

- Algorithms for Partially Observable Markov Decision Processes
- Variational inference for Markov jump processes
- Strong Markov property of Poisson processes and Slivnyak formula
- An ergodic control problem for constrained diffusion processes Existence of optimal Markov
- The policy iteration algorithm for average reward Markov decision processes with general st
- Optimality inequalities for average cost Markov decision processes and the optimality of (s
- Markov property of monotone L'evy processes
- Taylor series expansions for the entropy rate of Hidden Markov Processes
- A Markov Property for Covariance Structures
- Good policies for partially-observable Markov decision processes are hard to find
- A Discrete Construction for Gaussian Markov Processes
- A FUNCTIONAL CENTRAL LIMIT THEOREM FOR MARKOV ADDITIVE PROCESSES
- A technique of exponential change of measure for Markov processes, Bernoulli (to appear
- On level crossings for a general class of piecewise-deterministic Markov processes
- A large-deviation theorem for tree-indexed Markov chains

arXiv:math/0412350v1 [math.PR] 17 Dec 2004

A Markov Property For Set-Indexed Processes

R.M. Balan?? B.G. Ivano??§ February 1, 2008

Abstract We consider a type of Markov property for set-indexed processes which is satis?ed by all processes with independent increments and which allows us to introduce a transition system theory leading to the construction of the process. A set-indexed generator is de?ned such that it completely characterizes the distribution of the process.

Keywords: set-indexed process; Markov property; transition system; generator.

1

Introduction

The Markov property is without doubt one of the most appealing notions that exists in the classical theory of stochastic processes and many processes modelling physical phenomena enjoy it. Attempts have been made to generalize this concept to processes where the index set is not totally ordered. However, to de?ne a Markov property for processes indexed by an uncountable partially ordered set is not a straightforward task for someone who has as declared goals to prove that: (i) all processes with independent increments possess this property; (ii) there exists a systematic procedure which allows us to construct a general process which enjoys this property; and (iii) we can de?ne a generator which completely characterizes the ?nite dimensional distributions of the process. (The case of Markov processes indexed by discrete partially ordered sets was considered by various authors [6], [13] for solving stochastic optimal

? Corresponding author. Department of Mathematics and Statistics, University of Ottawa, P.O. Box 450, Stn. A, Ottawa, ON, K1N 6N5, CANADA, Tel: (613) 260-0683. E-mail address: s1412643@matrix.cc.uottawa.ca ? This paper is based on a portion of the ?rst author’s doctoral thesis. Research supported by a scholarship from the Natural Sciences and Engineering Research Council of Canada and by an Ontario Graduate Scholarship in Science and Technology. ? Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON, CANADA. E-mail address: givano?@science.uottawa.ca § Research supported by a grant from the Natural Sciences and Engineering Research Council of Canada.

1

A Markov property for set-indexed processes

2

control problems; as our framework is di?erent, we will not discuss this case here.) In the present paper we will de?ne a new type of Markov property for processes indexed by a semilattice of sets, which will attain these three goals. This paper represents a successful manner of approaching a problem to which much e?ort has been dedicated in the literature to date. In fact it will be seen that our de?nition is completely analogous to the classical de?nition of the Markov property on R, and our approach avoids many of the technical problems which arise with other de?nitions of Markov properties. We begin now to describe the two levels of generality of this problem. The ?rst level deals with the case when the index set is the Euclidean space [0, 1]2 (or, more generally [0, 1]d) and therefore it inherits the extra structure introduced by the total ordering of the coordinate axes. In this case, there are at least three types of Markov properties which can be considered: the sharp Markov property, the germ Markov property, and the ‘simultaneously vertical and horizontal’ Markov property. The basic idea behind the sharp Markov property (?rst introduced in 1948 by L?vy [14]) was to consider as the history of the process at location z in e the plane or space, all the information that we have about the values of the process inside the rectangle [0, z] ; all the information about the values of the process outside the rectangle was regarded as ‘future’; and the past and the future should be independent given the values of the process on the boundary of the rectangle. In 1984, Russo [19] proved that all processes with independent increments are sharp Markov with respect to all ?nite unions of rectangles. The next step was to see if we can replace the rectangles with more general sets; in other words a two-parameter process (Xz )z∈[0,1]2 is said to have the sharp Markov property with respect to a set A if the σ- ?elds FA and FAc are conditionally independent given F?A where FD = σ(Xz ; z ∈ D) for any set D ? [0, 1]2 . The advantage of this de?nition is that it does not rely on the partial order of the space. Unfortunately, it turned out that processes having this property are di?cult to handle. To attain goal (i) the following question had to be answered: what is the largest class of sets for which all processes with independent increments are sharp Markov? (To answer this question the Gaussian and the jump parts have been treated separately.) Goals (ii) and (iii) do not seem to be even speci?ed anywhere in the literature. (In 1976 Walsh [20] showed that the Brownian sheet fails to have the sharp Markov property with respect to a very simple set, the triangle with vertices (0, 0), (0, 1) and (1, 0). This led to the conclusion that, instead of the sharp σ-?eld F?A one has to consider a larger one, called the germ σ-?eld, which is de?ned as G?A = ∩G FG where the intersection is taken over all open sets G containing ?A. The new Markov property, for which FA and FAc are conditionally independent given G?A , was called the germ Markov property and it was ?rst introduced by McKean [16]. In 1980 Nualart [17] showed that the Brownian sheet satis?es the germ Markov property with respect to all open sets.) The complete answer was given in 1992 in the form of two thorough papers

A Markov property for set-indexed processes

3

written by Dalang and Walsh: in [8] it is shown that the Brownian sheet satis?es the sharp Markov property with respect to all domains whose boundaries are singular curves of bounded variation; on the other hand, the main result of [7] states that for jump proceses with independent increments which have only positive jumps, the sharp Markov property holds with respect to all domains. The third Markov property de?ned for two-parameter processes was introduced in 1979 by Nualart and Sanz [18] and it was ?rst studied in the Gaussian case. Korezlioglu, Lefort and Mazziotto [12] generalized it and proved that any process satisfying this property is sharp Markov with respect to any ?nite union of rectangles and germ Markov with respect to any relatively convex domain. The basic idea in this third Markov property is the separation of parameters, that is, the simultaneous de?nition of a horizontal and vertical Markov property. It is an easy exercise to show that any process with independent increments satis?es this property. The general construction of a process satisfying this property, which corresponds to a certain transition semigroup, was made by Mazziotto [15] (the trajectories of this process have also nice regularity properties). The second level of generality deals with the case of processes indexed by a collection A of closed connected subsets of a compact space. The collection A is partially ordered by set-inclusion and has the additional structure of a semilattice, being closed under arbitrary intersections. This new approach in the modern theory of stochastic processes indexed by partially ordered sets (which is known in the literature as the theory of set-indexed processes) was initiated and developed by Ivano? and Merzbach for the martingale case [11]. (Other authors [1],[5] were interested in processes indexed by Borel subsets of [0, 1]d , but the approach taken by Ivano? and Merzbach introduces tools which permit the development of a general theory.) If we identify this class with the class of the rectangles [0, z], z ∈ [0, 1]d and we denote by Xz the value of the set-indexed process at the rectangle [0, z], then (Xz )z will be a d-dimensional process; hence, we can view this theory as a generalization of the theory of multiparameter processes. In [10] both sharp Markov and (‘simultaneously vertical and horizontal’) Markov properties have been introduced in the set-indexed framework, in such a manner that they generalize the corresponding notions de?ned in the multiparameter case. In fact, in this new set-up, the Markov property implies the sharp Markov property and there are certain circumstances when they are actually equivalent. Moreover, a highly non-trivial result of [10] shows that all processes with independent increments are Markov (in the speci?ed sense), so that goal (i) is attained; however, the authors of [10] do not consider goals (ii) and (iii) and they do not attempt to construct a general Markov process. In this paper we will consider another type of Markov property for setindexed processes, which is less general than the Markov property introduced by Ivano? and Merzbach, but which has the merit of attaining the three goals (i), (ii) and (iii). This Markov property will be called the set-Markov property and we will show that it implies the sharp Markov property. The de?nition

A Markov property for set-indexed processes

4

requires that the value XA\B = XA∪B ? XB of an additive set-indexed process (XA )A∈A over the increment A\B be conditionally independent of the history FB := σ({XA′ ; A′ ∈ A, A′ ? B}) given the present status XB . We believe that this is a natural de?nition because: (a) it captures the essence of the Markov property in terms of the increments, allowing us to have a perfect analogy with the classical case; (b) all processes with independent increments are (trivially) set-Markov; (c) a process is set-Markov if and only if it becomes Markov in the classical sense when it is transported by a ‘?ow’. (A ‘?ow’ is an increasing function mapping a bounded interval of the real line into the collection of all ?nite unions of sets in A.) This property provides us with the means to de?ne a generator for a set-Markov process. The paper is organized as follows: In Section 2 we de?ne the general framework which is used in the theory of set-indexed processes. The main structure that we need is a semilattice of sets which leads us to a semialgebra and an algebra of sets. All the processes that we consider are assumed to be a.s. ?nitely additive on this algebra. In Section 3 we de?ne the set-Markov property in terms of the increments of the process. We will prove that this property has two equivalent formulations. The ?rst one (Proposition 1) requires that the ‘future’ behaviour of the process at a set B ′ (? B) be conditionally independent of its history FB knowing its present status at the set B. The second formulation (Proposition 2) requires that the (one-parameter) processes X f obtained as ‘traces’ of the original setindexed process X along the paths of all ?ows f be Markov in the classical sense; this allows us to make use of the rich theory that exists for Markov processes indexed by the real line. In Section 4 we turn to the question of existence of a set-Markov process and we prove that we can construct such a process if we specify the laws QBB ′ that characterize the transition from a set B to a set B ′ (? B). A set-Markov process with a given transition system Q := (QBB ′ )B?B ′ is called ‘Q-Markov’ and can be constructed as soon as we specify its ?nite dimensional distributions (by Kolmogorov’s existence theorem). However, the formula that we obtain for the ?nite dimensional distribution over some k-tuple A1 , . . . , Ak of sets turns out to be dependent on the ordering of the sets; hence we have to impose a natural consistency condition (Assumption 1) which makes the ?nite dimensional distribution ‘invariant’ under permutations. An important consequence of this condition is that the ?nite dimensional distributions of a Q-Markov process are also additive (Lemma 5). In Section 5 we de?ne the generator of a Q-Markov process X as the class {G f ; f ∈ S}, where G f is the generator of the (one-parameter) Markov process X f and S is a large enough (uncountable) collection of ?ows. In other words, at

A Markov property for set-indexed processes

5

any set B there are in?nitely many generators depending on which ‘direction’ we approach this set along the path of a ?ow f in S (note that in the classical case, the class S of ?ows can be taken to have a single element). In this section we address the question of existence of a Q-Markov process given its generator. More precisely, we start with a collection {G f ; f ∈ S}, each G f being the generator of a given semigroup T f . To simplify the problem we will assume that each T f is the semigroup asociated to a transition system Qf . The consistency conditions that have to be imposed on the collection {Qf ; f ∈ S} so that it leads to a set-indexed transition system Q (and hence to a Q-Markov process) are given in Section 4 (Assumptions 2 and 3). Using an integral form of the Kolomogorov-Feller equations, we prove that these conditions can be expressed equivalently in terms of the generators G f and the semigroups T f . (We conjecture that the same formulas will be valid in the general case when there is no transition system Qf associated to the semigroup T f .) Throughout, we shall illustrate our results with three examples of set-Markov processes: processes with independent increments, the empirical process, and the Dirichlet process. We note in passing that set-Markov processes satisfy a type of strong Markov property which is studied in a separate paper [2].

2

The Set-Indexed Framework

This section introduces the general de?nitions, properties and assumptions that are used in the theory of set-indexed processes, as presented in [11]. We will also give several examples, in addition to the multiparameter case. Let A be a semilattice of closed subsets of a compact Hausdor? topological space T (i.e. A is closed under arbitrary intersections), which contains the empty set and the space T itself, but does not contain disjoint (non-empty) sets. In addition, we assume that the collection A is separable from above, in the sense that any set A ∈ A can be approximated from above as A = ∩n gn (A); gn+1 (A) ? gn (A), A ? gn (A)0 ?n where the approximation set gn (A) can be written as a ?nite union of sets that lie in a ?nite sub-semilattice An of A; moreover, An ? An+1 ?n and gn preserves arbitrary intersections and ?nite unions i.e. gn (∩α∈Λ Aα ) = ∩α∈Λ gn (Aα ), ?Aα ∈ A; and ∪k Ai = ∪m A′ ? ∪k gn (Ai ) = ∪m gn (A′ ), ?Ai , A′ ∈ A. By i=1 j=1 j i=1 j=1 j j convention, gn (?) = ?. There are many examples of classes of sets which have these properties. Examples 1. 1. T = [0, 1]d , A = {[0, z]; z ∈ T } ∪ {?}. 2. T = [0, 1]d, A = {A; A a compact lower layer in T } ∪ {?}. (A is a lower layer if z ∈ A ? [0, z] ? A)

A Markov property for set-indexed processes 3. T = [a, b]d , a < 0 < b, A = {[0, z]; z ∈ T } ∪ {?}. 4. T = [a, b]d , a < 0 < b, A = {A; A a compact lower layer in T } ∪ {?}.

6

5. T = B(0, t0 ) (compact ball in R3 ), A = {AR,t ; R := ‘[a, b] × [c, d]′ , 0 ≤ a < b < 2π, ?π ≤ c < d ≤ π, t ∈ [0, t0 ]}, where the set AR,t := {(r cos θ cos τ, r sin θ cos τ, r sin τ ); θ ∈ [a, b], τ ∈ [c, d], r ∈ [0, t]} can be interpreted as the history of the region R := ‘[a, b] × [c, d]′ = {(cos θ cos τ, sin θ cos τ, sin τ ); θ ∈ [a, b], τ ∈ [c, d]} of the Earth from the beginning until time t. (Here θ represents the longitude of the generic point in the region R, while τ is the latitude.) Hence, A can be identi?ed with the history of the world until time t0 . Let ?′ := ∩A∈A\{?} A be the minimal set in A (?′ = ?). The role played by ?′ will be similar to the role played by 0 in the classical theory. We will consider the following classes of sets generated by A: ? A(u) is the class of all ?nite unions of sets in A ? C is the class of all sets of the form C = A\B with A ∈ A, B ∈ A(u) ? C(u) is the class of all ?nite unions of sets in C Note that A(u) is closed under ?nite intersections or ?nite unions, C is a semialgebra and C(u) is the algebra generated by C. The value XC = XA∪B ?XB of an (additive) set-indexed process (XA )A∈A over the set C = A\B = (A ∪ B)\B will play the role of the increment Xt ? Xs , s < t of a one-dimensional process (Xt )t∈[0,a] . Any set B ∈ A(u) admits at least one extremal representation of the form B = ∪n Ai , Ai ∈ A with Ai ? ∪j=i Aj ?i. For a set C ∈ C we will i=1 say that the representation C = A\B is extremal if the representation of B is extremal. Since the ?nite sub-semilattices of the indexing collection A play a very important role in the theory of set-indexed processes, having an appropriate ordering on the sets of a ?nite sub-semilattice proves to be a very useful tool in handling these objects. The ordering that we have in mind will be de?ned in such a manner that a set is never numbered before any of its subsets. We will call such an ordering consistent (with the strong past). More precisely, if A′ is a ?nite sub-semilattice of A we set A0 := ?′ and A1 := ∩A∈A′ A (note that the sets A0 and A1 are not necessarily distinct). Proceeding inductively, assuming that the distinct sets A1 , . . . , Ai ∈ A′ have already been counted, choose Ai+1 ∈ A′ \{A1 . . . , Ai } such that if there exists a set A ∈ A′ with

A Markov property for set-indexed processes

7

A ? Ai+1 , A = Ai+1 then A = Aj for some j ≤ i. It is clear that such an ordering always exists although in general, it is not unique. If {A0 = ?′ , A1 , . . . , An } is a consistent ordering of a ?nite sub-semilattice ′ A , the set Ci = Ai \ ∪i?1 Aj ∈ C is called the left neighbourhood of the set j=0 Ai (we make the convention that the left neighbourhood of A0 = ?′ is itself). The de?nition of the left neighbourhood does not depend on the ordering since one can show that Ci = Ai \(∪A∈A′ ,Ai ?A A). Comments 1. 1. If B1 , . . . , Bm ∈ A(u) are such that B1 ? · · · ? Bm then there exists a ?nite sub-semilattice A′ of A and a consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ such that Bl = ∪il Aj , for some 0 < i1 ≤ . . . ≤ j=0 im = n. 2. If A′ , A′′ are two ?nite sub-semilattices of A such that A′ ? A′′ , there exists a consistent ordering {A0 = ?′ , A1 , . . . , An } of A′′ such that if A′ = {Ai0 = ?′ , Ai1 , . . . , Aim } with 0 = i0 < i1 ≤ . . . ≤ im , then ∪l Ais = s=1 ∪il Aj for any l = 1, . . . , m. j=1 Let us consider now a complete probability space (?, F , P ) and let X := (XA )A∈A be an R-valued process de?ned on this space, indexed by the class A. We say that the process X has an (almost surely) unique additive extension to A(u) if whenever the set B ∈ A(u) can be written as B = ∪n Ai = ∪m A′ with A1 , . . . , An , A′ , . . . , A′ ∈ A we have 1 m j=1 j i=1

n

X Ai ?

i=1 m 1≤i1 <i2 ≤n

XAi1 ∩Ai2 + · · · + (?1)n+1 XA1 ∩...∩An = X A′ j

1≤j1 <j2 ≤m

X A′ ? j

j=1

1

∩A′ j

2

+ · · · + (?1)m+1 XA′ ∩...∩A′ a.s. m 1

In this case, outside a set of measure 0, we can de?ne XB as being either one of the members of the above almost sure equality. In order to verify that a process has a unique additive extension to A(u) it is enough to prove the previous almost sure equality only in the case when n = 1. The general case will follow since if ∪n Ai = ∪m A′ , then each of the sets Ai1 ∩ Ai2 ∩ . . . ∩ Aik ∈ A can be written i=1 j=1 j as the union ∪m (Ai1 ∩ Ai2 ∩ . . . ∩ Aik ∩ A′ ). j j=1 Similarly, the process X is said to have an (almost surely) unique additive extension to C if whenever the set C ∈ C can be written as C = A\B = A′ \B ′ with A, A′ ∈ A and B, B ′ ∈ A(u) we have XA ? XA∩B = XA′ ? XA′ ∩B ′ a.s. The additive extension to C(u) is de?ned in the obvious manner.

A Markov property for set-indexed processes

8

A set-indexed process X := (XA )A∈A with a unique additive extension to C(u), for which XC1 , . . . , XCn are independent whenever the sets C1 , . . . , Cn ∈ C are disjoint, is called a process with independent increments. An example of a process which has a unique additive extension to C(u) is the empirical process of size n, corresponding to a probability measure F on T , de?ned by XA := n I{Zj ∈A} , A ∈ A, where (Zj )j≥1 are i.i.d. T -valued j=1 random variables with common distribution F . Another example is the Dirichlet process with parameter measure α, where α is a ?nite positive measure on σ(A) (see Ferguson [9]). This process is in fact almost surely countably additive on σ(A) and takes values in [0, 1]; moreover XT = 1 a.s. Its ?nite dimensional distribution of this process over any disjoint sets A1 , . . . , Ak with Ai ∈ σ(A) is the (non-singular) Dirichlet distribution with parameters (α(A1 ), . . . , α(Ak ); α((∪k Ai )c )) (see Ferguson [9]). i=1 In what follows we will examine the information structure that can be associated with a set-indexed process. A collection (FA )A∈A of sub-σ-?elds of F is called a ?ltration if FA ? FA′ whenever A, A′ ∈ A, A ? A′ . We will consider only complete ?ltrations. An A-indexed ?ltration (FA )A∈A can be extended to a ?ltration indexed by A(u) by de?ning for each B ∈ A(u), FB :=

A∈A,A?B

FA

(1)

A set-indexed process X is adapted with respect to the ?ltration (FA )A∈A if XA is FA -measurable for any A ∈ A. If X is adapted and has a unique additive extension to A(u) then XB is FB -measurable for any B ∈ A(u). Given a set-indexed process X, the minimal ?ltration with respect to which X is adapted is given by FB := σ({XA ; A ∈ A, A ? B}). Any map f : [0, a] → A(u) which is increasing with respect to the partial order induced by the set-inclusion is called a ?ow. De?nition 1. A ?ow f : [0, a] → A(u) is a) continuous if for any t ∈ [0, a] and for any decreasing sequence (tn )n with limn→∞ tn = t we have f (t) = ∩n f (tn ), and for any increasing sequence (tn )n with limn→∞ tn = t we have f (t) = ∪n f (tn ). b) simple if it is continuous and there exists a partition 0 = t0 < t1 < . . . < tn = a and ?ows fi+1 : [ti , ti+1 ] → A, i = 0, . . . n ? 1 such that f (0) = ?′ and f (t) = ∪i fj (tj ) ∪ fi+1 (t), t ∈ [ti , ti+1 ], i = 0, . . . , n ? 1. (In other j=1 words, a simple ?ow is piecewise A-valued.) If A′ is a ?nite sub-semilattice and ord= {?′ = A0 , A1 , . . . , An } is a consistent ordering of A′ , we say that a simple ?ow f connects the sets of the semilattice A′ , in the sense of the ordering ord, if f (t) = ∪i Aj ∪ fi+1 (t), t ∈ [ti , ti+1 ], j=1

A Markov property for set-indexed processes

9

where t0 = 0 < t1 < . . . < tn = a is a partition of the domain of de?nition of f and fi+1 : [ti , ti+1 ] → A are continuous ?ows with fi+1 (ti ) = Ai , fi+1 (ti+1 ) = Ai+1 . Lemma 1. (Lemma 5.1.7, [11]) For every ?nite sub-semilattice A′ and for each consistent ordering ord of A′ , there exists a simple ?ow f which connects the sets of the semilattice A′ , in the sense of the ordering ord. Comment 2. A consequence of the previous lemma is the following: given B1 , . . . , Bm ∈ A(u) such that B1 ? . . . ? Bm there exists a simple ?ow f and t1 ≤ . . . ≤ tm such that Bi = f (ti ); i = 1, . . . , m.

3

Set-Markov Processes

In this section we will introduce the de?nition of the set-Markov property. Two immediate consequences of the de?nition will be: (a) any process with independent increments is set-Markov; and (b) the set-Markov property is equivalent to the classical Markov property on every ?ow. Finally we will prove that any set-Markov process is also sharp Markov. If F , G, H are three sub-σ-?elds of the same probabilistic space, we will use the notation F ⊥ H | G if F and H are conditionally independent given G. De?nition 2. Let X := (XA )A∈A be a set-indexed process with a unique additive extension to C(u) and (FA )A∈A its minimal ?ltration. We say that the process X is set-Markov if ?A ∈ A, ?B ∈ A(u), FB ⊥ σ(XA\B ) | σ(XB ). It is easy to see that in the classical case the set-Markov property is equivalent to the usual Markov property. Examples 2. 1. Any process X := (XA )A∈A with independent increments is set-Markov since ?A ∈ A, ?B ∈ A(u), XA\B is independent of FB . 2. The empirical process of size n (corresponding to F ) is set-Markov since ?A ∈ A, ?B ∈ A(u), for any partition B = ∪p Ci , Ci ∈ C and for any i=1 p l, k1 , . . . , kp ∈ {0, 1, . . . , n}; k := i=1 ki with k + l ≤ n l ki l k |XCi = ; i = 1, . . . , p] = P [XA\B = |XB = ] n n n n both sides being equal to the value at l of the binomial distribution with n ? k trials and F (A\B) probability of success. 1?F (B) P [XA\B = 3. The Dirichlet process X := (XA )A∈σ(A) with parameter measure α is setMarkov since ?A ∈ A, ?B ∈ A(u), for any partition B = ∪p Ci , Ci ∈ C i=1 and for any y, x1 , . . . , xp ∈ [0, 1]; x := p xi with x + y ≤ 1 i=1 P [XA\B ≤ y|XCi = xi ; i = 1, . . . , p] = P [XA\B ≤ y|XB = x]

A Markov property for set-indexed processes

10

y both sides being equal to the value at 1?x of the Beta distribution with c parameters (α(A\B); α((A ∪ B) )) (we use property 7.7.3, p. 180, [21] of the Dirichlet distribution).

We shall make repeated use of the following elementary result. Lemma 2. Let G ′ ? G be two σ-?elds in the same probability space and X, Y two random vectors on this space such that Y is G-measurable. Suppose that E[f (X)|G] = E[f (X)|G ′ ] for every bounded measurable function f . Then E[h(X, Y )|G] = E[h(X, Y )|G ′ , Y ] for every bounded measurable function h. Proposition 1. Let X := (XA )A∈A be a set-indexed process with a unique additive extension to C(u) and (FA )A∈A its minimal ?ltration. The process X is set-Markov if and only if ?B, B ′ ∈ A(u), B ? B ′ , FB ⊥ σ(XB ′ ) | σ(XB ). Proof: Using Lemma 2 and the additivity of the process, it follows that X is set-Markov if and only if ?A ∈ A ?B ∈ A(u), FB ⊥ σ(XA∪B ) | σ(XB ). (Write XA∪B = XA\B + XB and use the fact that XB is FB -measurable.) Let B, B ′ ∈ A(u) be such that B ? B ′ . Say B ′ = ∪k Ai , Ai ∈ A is an arbitrary i=1 representation. Then B ′ = B ∪ B ′ = B ∪ ∪k Ai and the result follows by i=1 induction on k. 2 Comment 3. Using Proposition 1 and Lemma 2, we can say that a process X := (XA )A∈A is set-Markov if and only if ?B, B ′ ∈ A(u), B ? B ′ , FB ⊥ σ(XB ′ \B ) | σ(XB ). The following result says that a process is set-Markov if and only if it is Markov (in the usual sense) along any ?ow. Moreover, it su?ces to restrict our attention only to simple ?ows. Proposition 2. Let X := (XA )A∈A be a set-indexed process with a unique additive extension to C(u) and (FA )A∈A its minimal ?ltration. Then X is setMarkov if and only if for every simple ?ow f : [0, a] → A(u) the process X f := (Xf (t) )t∈[0,a] is Markov with respect to the ?ltration (Ff (t) )t∈[0,a] . (For necessity, we can consider any ?ow, not only the simple ones.) Proof: The process X f is Markov with respect to the ?ltration (Ff (t) )t if and only if ?s, t ∈ [0, a], s < t, Ff (s) ⊥ σ(Xf (t) ) | σ(Xf (s) ). (We note that the ?ltration (Ff (t) )t∈[0,a] is not the minimal ?ltration associated to the process X f .) This is equivalent to the set-Markov property since we know that whenever the sets B, B ′ ∈ A(u) are such that B ? B ′ there exists a simple ?ow f and some s < t such that f (s) = B and f (t) = B ′ (Comment 2). 2 The preceding proposition, while simple, is crucial since (as noted in the Introduction) it provides us with the means to de?ne the generator of a setMarkov process. This will be done in Section 5. We now show that every set-Markov process satis?es the sharp-Markov property de?ned in [10]. In analogy with the minimal ?ltration (FB )B∈A(u) we de?ne

A Markov property for set-indexed processes

11

the following σ-?elds, for an arbitrary set B ∈ A(u): F?B := σ({XA ; A ∈ A, A ? B, A ? B 0 }) FB c := σ({XA ; A ∈ A, A ? B}) De?nition 3. Let X := (XA )A∈A be a set-indexed process with a unique additive extension to C(u) and (FA )A∈A its minimal ?ltration. We say that the process X is sharp-Markov if ?B ∈ A(u), FB ⊥ FB c | F?B . The next lemma will be essential in proving that a set-Markov process is sharp Markov. Lemma 3. If X := (XA )A∈A is a set-Markov process, then ?B ∈ A(u) ?Ai ∈ A; i = 1, . . . , n, FB ⊥ σ(XA1 \B , . . . , XAn \B ) | σ(XB ). Proof: Let B ∈ A(u),A1 , . . . An ∈ A and h : Rn → R an arbitrary bounded measurable function. Without loss of generality we can assume that Ai ? B ?i; ′ say B = ∪m j=n+1 Aj , Aj ∈ A. Let A be the smallest ?nite sub-semilattice ′ ′ which contains A1 , . . . Am , {A0 = ? , A′ , . . . , A′ } a consistent ordering of A′ , 1 p ′ and Ci the left neighborhood of A′ in A′ . Say Aj = A′ j for j = 1 . . . n; then i i ′ ′ Aj \B = A′ j \B = ∪i∈Ij Ci with Ij ? {1, . . . , ij } and XAj \B = i∈Ij XCi . i Therefore we can say that h(XA1 \B , . . . , XAn \B ) = h1 (XCl′ , . . . , XCl′ ), for s 1 a certain bounded measurable function h1 and some l1 ≤ . . . ≤ ls , Cl′i ? B. In order to simplify the notation, let us denote Di := Cl′i , i = 1, . . . , s. Let Bi = B ∪ ∪i Dk for i = 1, . . . , s. Then Di = Bi \Bi?1 and XDi = XBi ? k=1 XBi?1 ; hence XD1 , . . . , XDs?1 are FBls?1 -measurable. Because each Di is the left neighbourhood of A′i , we also have Bi = B ∪ ∪i A′k and therefore Di = k=1 l l (A′i ∪Bi?1 )\Bi?1 = A′i \Bi?1 . Using the equivalent de?nition of the set-Markov l l property given by Comment 3, we have E[f (XDs )|FBs?1 ] = E[f (XDs )|XBs?1 ] for any bounded measurable function f . Now we are in the position to apply Lemma 2 to get E[h1 (XD1 , . . . , XDs )|FBs?1 ] = E[h1 (XD1 , . . . , XDs )|XBs?1 , XD1 , . . . , XDs?1 ]. Hence E[h(XA1 \B , . . . , XAn \B )|FB ] = E[E[h1 (XD1 , . . . , XDs )|FBs?1 ]|FB ] = E[E[h1 (XD1 , . . . , XDs )|XBs?1 , XD1 , . . . , XDs?1 ]|FB ]. Writing XBs?1 = XB + s?1 k=1 XDk we get E[h(XA1 \B , . . . , XAk \B )|FB ] = E[h2 (XD1 , . . . , XDs?1 , XB )| FB ]. Continuing in the same manner, reducing at each step another set Di , we ?nally get E[h(XA1 \B , . . . , XAn \B )|FB ] = E[h(XA1 \B , . . . , XAn \B )|XB ]. 2 Proposition 3. Any set-Markov process is sharp Markov. Proof: Let B ∈ A(u), Ai ∈ A, Ai ? B; i = 1, . . . , n and h : Rn → R an arbitrary bounded measurable function. Writing XAi = XAi ∩B + XAi \B and using Lemma 2 we can say that E[h(XA1 , . . . , XAn )|FB ] = E[h(XA1 , . . . , XAn )|XB , XAi ∩B , i = 1, . . . n], which is F?B -measurable, by Lemma 2.4, [10]. 2

A Markov property for set-indexed processes

12

In what follows we will give an important characterization of the set-Markov processes that will be instrumental for the construction of these processes. We will need the following elementary result. Lemma 4. Let Fi , i = 1, . . . , 4 be four σ-?elds in the same probability space. If F1 ⊥ F3 | F2 and F1 ∨ F2 ⊥ F4 | F3 , then F1 ⊥ F3 ∨ F4 | F2 . Proposition 4. A set-indexed process X := (XA )A∈A with a unique additive extension to C(u), is set-Markov if and only if for every ?nite sub-semilattice A′ and for every consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ σ(XA0 , XA0 ∪A1 , . . . , X∪i?1 Aj ) ⊥ σ(X∪i+1 Aj )|σ(X∪i Aj ) ?i = 1, . . . , n ? 1 (2) j=0

j=0 j=0

Proof: We will use the characterization of the set-Markov property given by Proposition 1. Necessity follows immediately. For su?ciency note ?rst that equation (2) implies a similar equation where the union of the ?rst i + 1 sets is replaced by the union of the ?rst i + p sets. In fact it is easily shown by induction on p and using Lemma 4, that σ(XA0 , XA0 ∪A1 , . . . , X∪i?1 Aj ) ⊥ σ(X∪i+k Aj ; k = 1, . . . , p)|σ(X∪i Aj ) ?i (3) j=0

j=0 j=0

Consider now arbitrary sets B, B ′ ∈ A(u) with B ? B ′ . By a monotone class argument it is enough to show that ?A′ ∈ A, A′ ? B; l = 1, . . . , m, l l σ(XA′ , . . . , XA′ ) ⊥ σ(XB ′ )|σ(XB ). Without loss of generality we may asm 1 sume that {A′ = ?′ , A′ , . . . , A′ } is a ?nite sub-semilattice and that the or0 1 m dering {A′ = ?′ , A′ , . . . , A′ } is consistent. Because the process X has a 0 1 m unique additive extension to A(u), there exists a bijective map ψ such that (XA′ , XA′ , . . . , XA′ ) = ψ(XA′ , XA′ ∪A′ , . . . , X∪m A′ ) a.s.. Consequently, we m 1 2 1 1 2 l=1 l have σ(XA′ , XA′ , . . . , XA′ ) = σ(XA′ , XA′ ∪A′ , . . . , X∪m A′ ). m 1 2 1 1 2 l=1 l By Comment 1.1, there exists a ?nite sub-semilattice A′ of A and a consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ , such that A′ = ∪i1 Aj , A′ ∪ 1 1 j=0

m+2 m+1 A′ = ∪i2 Aj , . . . , ∪m A′ = ∪im Aj , B = ∪j=0 Aj , B ′ = ∪j=0 Aj for some 2 j=0 j=0 l=1 l i1 ≤ i2 ≤ . . . ≤ im+2 . Using (3), it follows that σ(XA′ , XA′ ∪A′ , . . . , X∪m A′ ) ⊥ 1 1 2 l=1 l σ(XB ′ )|σ(XB ). 2

i

i

4

Construction of the Process

In this section we will introduce a special class of set-Markov processes for which the mechanism of transition from one state to another is completely known, and we will construct such a process. In light of Proposition 2, we will also determine the necessary and su?cient conditions that have to be imposed on a family of one-dimensional transition systems, indexed by a collection of simple ?ows, such that on each simple ?ow f from the chosen collection, the corresponding Markov process has the law of X f , where X is set-Markov (i.e., under what

A Markov property for set-indexed processes

13

circumstances a class of one dimensional transition systems determines a setMarkov process). Let B(R) denote the Borel subsets of R. We begin with the de?nition of the transition system. De?nition 4. (a) For each B, B ′ ∈ A(u), B ? B ′ let QBB ′ (x; Γ), x ∈ R, Γ ∈ B(R), be a transition probability on R i.e., QBB ′ (x; ·) is a probability measure ?x, and QBB ′ (·; Γ) is measurable ?Γ. The family Q := (QBB ′ ) of all these transition probabilities is called a transition system if ?B ∈ A(u), QBB (x; ·) = δx and ?B, B ′ , B ′′ ∈ A(u), B ? B ′ ? B ′′ QBB ′′ (x; Γ) =

R

QB ′ B ′′ (y; Γ)QBB ′ (x; dy) ?x ∈ R, ?Γ ∈ B(R)

(b) Let Q := (QBB ′ )B,B ′ ∈A(u);B?B ′ be a transition system. A set-indexed process X := (XA )A∈A with a unique additive extension to C(u) is called Q-Markov if ?B, B ′ ∈ A(u), B ? B ′ P [XB ′ ∈ Γ|FB ] = QBB ′ (XB ; Γ) ?Γ ∈ B(R) where (FA )A∈A is the minimal ?ltration of the process X. In other words, a Q-Markov process is a set-Markov process for which QBB ′ is a version of the conditional distribution of XB ′ given XB , for every B, B ′ ∈ A(u), B ? B ′ . Examples 3. 1. Any process X := (XA )A∈A with independent increments is Q-Markov with QBB ′ (x; Γ) := FB ′ \B (Γ?x), where FC is the distribution of XC , C ∈ C(u). The Poisson process and the Brownian motion are the particular cases for which FC is a Poisson distribution with mean ΛC , respectively, a normal distribution with mean 0 and variance ΛC . 2. The empirical process of size n, corresponding to a probability measure F , k is Q-Markov with QBB ′ ( n ; { m }); k, m ∈ {0, 1, . . . , n}, k ≤ m given by the n ′ value at m ? k of the binomial distribution with n ? k trials and F (B \B)

1?F (B)

probability of success. 3. The Dirichlet process with parameter measure α is Q-Markov with QBB ′ (x; [0, z]); x, z ∈ [0, 1] given by the value at y?x of the Beta dis1?x tribution with parameters (α(B ′ \B); α(B ′c )). The following result gives equivalent characterizations of a Q-Markov process.

A Markov property for set-indexed processes

14

Proposition 5. Let Q := (QBB ′ )B,B ′ ∈A(u);B?B ′ be a transition system, X := (XA )A∈A a set-indexed process with a unique additive extension to C(u) and initial distribution ?, and (FA )A∈A the minimal ?ltration of the process X. The following statements are equivalent: (a) The process X is Q-Markov. (b) For every simple ?ow f : [0, a] → A(u) the process X f := (Xf (t) )t∈[0,a] is Qf -Markov (with respect to (Ff (t) )t∈[0,a] ), where Qf := Qf (s),f (t) . st (c) For every ?nite sub-semilattice A′ , for every consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ and for every i = 1, . . . , n ? 1 σ(XA0 , XA1 , XA1 ∪A2 , . . . , X∪i?1 Aj ) ⊥ σ(X∪i+1 Aj ) | σ(X∪i Aj ) j=1

j=1 j=1

and Q∪i Aj,∪i+1 Aj is a version of the conditional distribution of X∪i+1 Aj j=1 j=1 j=1 given X∪i Aj . j=1 (d) For every ?nite sub-semilattice A′ and for every consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ P (XA0 ∈ Γ0 , XA1 ∈ Γ1 , XA1 ∪A2 ∈ Γ2 , . . . , X∪n Aj ∈ Γn ) = j=1

n Rn+1

IΓ0 (x0 )

i=1

IΓi (xi )Q∪n?1 Aj ,∪n

j=1

j=1

Aj (xn?1 ; dxn ) . . .

QA1 ,A1 ∪A2 (x1 ; dx2 )Q?′ A1 (x0 ; dx1 )?(dx0 ) for every Γ0 , Γ1 , . . . , Γn ∈ B(R). (e) For every ?nite sub-semilattice A′ , for every consistent ordering {A0 = ?′ , A1 , . . . , An } of A′ , if we denote with Ci the left neighbourhood of the set Ai , then P (XC0 ∈ Γ0 , XC1 ∈ Γ1 , XC2 ∈ Γ2 , . . . , XCn ∈ Γn ) =

n Rn+1

IΓ0 (x0 )IΓ1 (x1 )

i=2

IΓi (xi ? xi?1 )Q∪n?1 Aj ,∪n

j=1

j=1

Aj (xn?1 ; dxn ) . . .

QA1 ,A1 ∪A2 (x1 ; dx2 )Q?′ A1 (x0 ; dx1 )?(dx0 ) for every Γ0 , Γ1 , . . . , Γn ∈ B(R). Proof: The equivalences (a)-(b), (a)-(c) follow by arguments similar to those used to prove Proposition 2, respectively, Proposition 4. The equivalence (c)-(d) follows exactly as in the classical case. Finally, the equivalence (d)-(e) follows by a change of variables, since XCi = X∪i Aj ? X∪i?1 Aj a.s. 2 j=1

j=1

A Markov property for set-indexed processes

15

The general construction of a Q-Markov process will be made using increments: i.e., the sets in C. The following assumption is necessary. It requires that the distribution of the process over the left-neighbourhoods C0 , C1 , . . . , Cn of a ?nite sub-semilattice, does not depend on the consistent ordering of the semilattice. Assumption 1. If {A0 = ?′ , A1 , . . . , An } and {A0 = ?′ , A′ , . . . , A′ } are 1 n two consistent orderings of the same ?nite sub-semilattice A′ and π is the permutation of {1, . . . , n} with π(1) = 1 such that Ai = A′ π(i) ?i, then

n Rn+1

IΓ0 (x0 )IΓ1 (x1 )

i=2

IΓi (xi ? xi?1 )Q∪n?1 Aj ,∪n

j=1

j=1

Aj (xn?1 ; dxn ) . . .

QA1 ,A1 ∪A2 (x1 ; dx2 )Q?′ A1 (x0 ; dx1 )?(dx0 ) =

n Rn+1

IΓ0 (y0 )IΓ1 (y1 )

i=2

IΓi (yπ(i) ? yπ(i)?1 )Q∪n?1 A′ ,∪n

j=1 j

′ j=1 Aj

(yn?1 ; dyn ) . . .

QA′ ,A′ ∪A′ (y1 ; dy2 )Q?′ A′ (y0 ; dy1 )?(dy0 ) 1 1 2 1 for every Γ0 , Γ1 , . . . , Γn ∈ B(R). The ?nite dimensional distributions of a Q-Markov process over the sets in C have to be de?ned so that they ensure the (almost sure) additivity of the process. The next result gives the de?nition of the ?nite dimensional distribution (of an additive Q-Markov process) over an arbitrary k-tuple of sets in C and shows that, if the transition system Q satis?es Assumption 1, then the de?nition will not depend on the extremal representations of these sets. Lemma 5. Let Q := (QBB ′ )B?B ′ be a transition system satisfying Assumption 1. Let (C1 , . . . , Ck ) be a k-tuple of distinct sets in C and suppose that each set Ci admits two extremal representations Ci = Ai \ ∪ni Aij = A′ \ ∪mi A′ . i j=1 ij j=1 Let A′ , A′′ be the minimal ?nite sub-semilattices of A which contain the sets ′ ′ ′ Ai , Aij , respectively A′ , A′ , {B0 = ?′ , B1 , . . . , Bn }, {B0 = ?′ , B1 , . . . , Bm } two i ij ′ ′′ ′ consistent orderings of A , A and Dj , Dl the left neighbourhoods of the sets ′ Bj , Bl for j = 1, . . . , n; l = 1, . . . , m. If each set Ci ; i = 1, . . . , k can be written ′ as Ci = ∪j∈Ji Dj = ∪l∈Li Dl for some Ji ? {1, . . . , n}, Li ? {1, . . . , m}, then

k

IΓi (

Rn+1 i=1 j∈Ji

(xj ? xj?1 ))Q∪n?1 Bj ,∪n

j=1

j=1

Bj (xn?1 ; dxn ) . . .

QB1 ,B1 ∪B2 (x1 ; dx2 )Q?′ B1 (x; dx1 )?(dx) =

k

IΓi (

Rm+1 i=1 l∈Li

(yl ? yl?1 ))Q∪m?1 B ′ ,∪m

l=1 l

l=1

′ Bl (ym?1 ; dym ) . . .

A Markov property for set-indexed processes

16

′ ′ ′ ′ QB1 ,B1 ∪B2 (y1 ; dy2 )Q?′ B1 (y; dy1 )?(dy)

for every Γ1 , . . . , Γk ∈ B(R), with the convention x0 = y0 = 0. ? Proof: Let A be the minimal ?nite sub-semilattice of A determined by the sets ′ ′′ ? ? in A and A ; clearly A′ ? A, A′′ ? A. Let ord1 = {E0 = ?′ , E1 , . . . , EN } and 2 ′ ′ ′ ′ ? ord = {E0 = ? , E1 , . . . , EN } be two consistent orderings of A such that, if ′ ′ Bj = Eij ; j = 1, . . . , n and Bl = Ekl ; l = 1, . . . , m for some indices i1 < i2 < . . . < in , respectively k1 < k2 < . . . < km , then B1 = ∪i1 Ep , B1 ∪ B2 = ∪i2 Ep , . . . , ∪n Bj = ∪in Ep j=1 p=1 p=1 p=1

′ ′ ′ ′ ′ ′ ′ B1 = ∪k1 Eq , B1 ∪ B2 = ∪k2 Eq , . . . , ∪m Bl = ∪km Eq l=1 q=1 q=1 q=1 ′ Let π be the permutation of {1, . . . , N } such that Ep = Eπ(p) ; p = 1, . . . , N . ′ ′ Denote by Hp , Hq the left neighbourhoods of Ep , Eq with respect to the or′ derings ord1 , ord2 ; clearly Hp = Hπ(p) , ?p = 1, . . . , N . Note that Dj =

j j?1 j (∪j Bv )\(∪j?1 Bv ) = (∪p=1 Ep )\(∪p=1 Ep ) = ∪p=ij?1 +1 Hp ; j = 1, . . . , n and v=1 v=1

i

i

i

′ ′ similarly Dl = ∪kl l?1 +1 Hq ; l = 1, . . . , m. Hence q=k

Ci

j j ′ = ∪j∈Ji Dj = ∪j∈Ji ∪p=ij?1 +1 Hp = ∪j∈Ji ∪p=ij?1 +1 Hπ(p)

i

i

′ ′ = ∪l∈Li Dl = ∪l∈Li ∪kl l?1 +1 Hq q=k

and we can conclude that {π(p); p ∈ ∪j∈Ji {ij?1 + 1, ij?1 + 2, . . . , ij }} = ∪l∈Li {kl?1 + 1, kl?1 + 2, . . . , kl } This implies that

k RN +1 i=1 ij

IΓi (

(xp ? xp?1 ))Q∪N ?1 Ep ,∪N

p=1

j∈Ji p=ij?1 +1

p=1 Ep

(xN ?1 ; dxN ) . . .

QE1 ,E1 ∪E2 (x1 ; dx2 )Q?′ E1 (x; dx1 )?(dx)

k kl

=

RN +1 i=1

IΓi (

l∈Li q=kl?1 +1

(yq ? yq?1 ))Q∪N ?1 E ′ ,∪N

q=1 q

′ q=1 Eq

(yN ?1 ; dyN ) . . .

′ ′ ′ ′ QE1 ,E1 ∪E2 (y1 ; dy2 )Q?′ E1 (y; dy1 )?(dy)

with the convention x0 = y0 = 0. This gives us the desired relationship, because ij p=ij?1 +1 (xp ? xp?1 ) = xij ? xij?1 , the left-hand side integral collapses to an integral with respect to Q∪n Bj ,∪n?1 Bj (xin?1 ; dxin ) . . . QB1 ,B1 ∪B2 (xi1 ; dxi2 )

j=1 j=1

Q?′ B1 (x; dxi1 )?(dx), and a similar phenomenon happens in the right-hand side. 2

A Markov property for set-indexed processes

17

We are now ready to prove the main result of this section, which says that in fact the previous assumption is also su?cient to construct a Q-Markov process. Theorem 1. If ? is a probability measure on R and Q := (QBB ′ )B?B ′ is a transition system which satis?es the consistency Assumption 1, then there exists a Q-Markov process X := (XA )A∈A with initial distribution ?. Proof: Let (RC , RC ) := C∈C (RC , RC ) where (RC , RC ), C ∈ C represent C copies of the real space R with its Borel subsets. For each k-tuple (C1 , . . . , Ck ) of distinct sets in C we will de?ne a probability measure ?C1 ...Ck on (Rk , Rk ) such that the system of all these probability measures satisfy the following two consistency conditions:

′ ′ ′ (C1) If (C1 . . . Ck ) is another ordering of the k-tuple (C1 . . . Ck ), say Ci = Cπ(i) , π is a permutation of {1, . . . , k}, then

′ ′ ?C1 ...Ck (Γ1 × . . . × Γk ) = ?C1 ...Ck (Γπ?1 (1) × . . . × Γπ?1 (k) )

for every Γ1 , . . . , Γk ∈ B(R). (C2) If C1 , . . . , Ck , Ck+1 are k + 1 distinct sets in C, then ?C1 ...Ck (Γ1 × . . . × Γk ) = ?C1 ...Ck Ck+1 (Γ1 × . . . × Γk × R) for every Γ1 , . . . , Γk ∈ B(R). By Kolmogorov’s extension theorem there exists a probability measure P on (RC , RC ) such that the coordinate-variable process X := (XC )C∈C de?ned by XC (x) := xC has the measures ?C1 ...Ck as its ?nite dimensional distributions. We will prove that the process X has an (almost surely) unique additive extension to C(u). The Q-Markov property of this process will follow from the way we choose its ?nite dimensional distributions ?C0 C1 ...Cn over the left neighbourhoods of a ?nite sub-semilattice, according to Proposition 5, (e). Step 1 (Construction of the ?nite dimensional distributions) We de?ne ?? := δ0 . Let (C1 , . . . , Ck ) be a k-tuple of distinct nonempty sets in C and Ci = Ai \ ∪ni Aij ; i = 1, . . . , k some extremal representations. Let j=1 A′ be the minimal ?nite sub-semilattice of A which contains the sets Ai , Aij , {B0 = ?′ , B1 , . . . , Bn } a consistent ordering of A′ and Dj the left neighbourhood of the set Bj for j = 1, . . . , n. De?ne

n

?D0 D1 ...Dn (Γ0 × Γ1 × . . . × Γn ) := Q∪n?1 Bj ,∪n

j=1

Rn+1

IΓ0 (x0 )IΓ1 (x1 )

i=2

IΓi (xi ? xi?1 )

j=1

Bj (xn?1 ; dxn ) . . . QB1 ,B1 ∪B2 (x1 ; dx2 )Q?′ B1 (x0 ; dx1 )?(dx0 )

for every Γ0 , Γ1 , . . . , Γn ∈ B(R).

A Markov property for set-indexed processes

18

Say Ci = ∪j∈Ji Dj for some Ji ? {1, . . . , n}; i = 1, . . . , k, let α : Rn+1 → R , α(x0 , x1 , . . . , xn ) := ( j∈J1 xj , . . . , j∈Jk xj ) and de?ne

k

?C1 ...Ck := ?D0 D1 ...Dn ? α?1 The fact that ?C1 ...Ck does not depend on the ordering of the semilattice A′ is a consequence of Assumption 1. The fact that ?C1 ...Ck does not depend on the extremal representations of the sets Ci is also a consequence of Assumption 1, using Lemma 5. Finally, we observe that the ?nite dimensional distributions are additive. Step 2 (Consistency condition (C1)) ′ ′ ′ Let (C1 . . . Ck ) be another ordering of the k-tuple (C1 . . . Ck ), with Ci = Cπ(i) , ni π being a permutation of {1, . . . , k}. Let Ci = Ai \ ∪j=1 Aij ; i = 1, . . . , k be extremal representations, A′ the minimal ?nite sub-semilattice of A which contains the sets Ai , Aij , {B0 = ?′ , B1 , . . . , Bn } a consistent ordering of A′ and Dj the left neighbourhood of the set Bj for each j = 1, . . . , n. Say Ci = ′ ′ ∪j∈Ji Dj , Ci = ∪j∈Ji Dj and let α(x0 , x1 , . . . , xn ) := ( j∈J1 xj , . . . , j∈Jk xj ), ′ β(x0 , x1 , . . . , xn ) := ( j∈J ′ xj , . . . , j∈J ′ xj ). We have Ji = Jπ(i) . Hence

1 k

?C1 ...Ck (Γ1 × . . . × Γk ) = = =

?D0 D1 ...Dn (α?1 (Γ1 × . . . × Γk )) ?D0 D1 ...Dn (β ?1 (Γπ?1 (1) × . . . × Γπ?1 (k) ))

′ ′ ?C1 ...Ck (Γπ?1 (1) × . . . × Γπ?1 (k) )

for every Γ1 , . . . , Γk ∈ B(R). Step 3 (Consistency Condition (C2)) Let C1 , . . . , Ck , Ck+1 be k + 1 distinct sets in C and Ci = Ai \ ∪ni Aij ; i = j=1 1, . . . , k + 1 some extremal representations. Let A′ , A′′ be the minimal ?nite sub-semilattices of A which contain the sets Ai , Aij ; i = 1, . . . , k; j = 1, . . . , ni , respectively Ai , Aij ; i = 1, . . . , k + 1; j = 1, . . . , ni . Clearly A′ ? A′′ . Using Comment 1.2 there exists a consistent ordering {B0 = ?′ , B1 , . . . , Bn } of A′′ such that, if A′ = {Bi0 = ?′ , Bi1 , . . . , Bim } with 0 = i0 < i1 < . . . < im , then ∪l Bis = ∪il Bj for all l = 1, . . . , m. For each j = 1, . . . , n; l = 1, . . . , m, let s=1 j=1 Dj , El be the left neighbourhoods of Bj in A′′ , respectively of Bil in A′ and note that El = ∪il l?1 +1 Dj for each l = 1, . . . , m. Let γ(x0 , x1 , . . . , xn ) := j=i (x0 ,

i1 j=1

xj ,

i2 j=i1 +1

xj , . . . ,

im j=im?1 +1

xj ) and for the moment suppose that (4)

?E0 E1 ...Em = ?D0 D1 ...Dn ? γ ?1

Say Ci = ∪j∈Ji Dj ; i = 1, . . . , k + 1 for some Ji ? {1, . . . , n} and de?ne α(x0 , x1 , . . . , xn ) := ( j∈J1 xj , . . . , j∈Jk+1 xj ). On the other hand, if we say that for each i = 1, . . . , k we have Ci = ∪l∈Li El for some Li ? {1, . . . , m}, then Ji = ∪l∈Li {il?1 + 1, il?1 + 2, . . . , il }; de?ne β(y0 , y1 , . . . , ym ) := ( l∈L1 yl , . . . , l∈Lk yl ). Then ?C1 ...Ck (Γ1 × . . . × Γk ) = ?E0 E1 ...Em (β ?1 (Γ1 × . . . × Γk ))

A Markov property for set-indexed processes ?D0 D1 ...Dn (γ ?1 (β ?1 (Γ1 × . . . × Γk ))) ?D0 D1 ...Dn (α?1 (Γ1 × . . . × Γk × R)) ?C1 ...Ck Ck+1 (Γ1 × . . . × Γk × R)

19

= = =

for every Γ1 , . . . , Γk ∈ B(R). In order to prove (4) let Γ0 , Γ1 , . . . , Γm ∈ B(R) be arbitrary. Then ?D0 D1 ...Dn (γ ?1 (Γ0 × Γ1 × . . . × Γm )) = IΓ0 ×Γ1 ×...×Γm (γ(x0 , x1 , x2 ? x1 , . . . , xn ? xn?1 ))

Rn+1

Q∪n?1 Bj ,∪n

j=1

j=1

Bj (xn?1 ; dxn ) . . . QB1 ,B1 ∪B2 (x1 ; dx2 )Q?′ B1 (x0 ; dx1 )?(dx0 )

Note that γ(x0 , x1 , x2 ? x1 , . . . , xn ? xn?1 ) = (x0 , xi1 , xi2 ? xi1 , . . . , xim ? xim?1 ) and hence the integrand does not depend on the variables xj , j ∈ {i0 , i1 , . . . , im }. By the de?nition of the transition system, the above integral collapses to

m Rm+1

IΓ0 (x0 )IΓ1 (xi1 )

l=2

IΓl (xil ? xil?1 )Q∪im?1 B

j=1

im j ,∪j=1 Bj

(xim?1 ; dxim ) . . .

Q∪i1

j=1

2 Bj ,∪j=1 Bj

i

(xi1 ; dxi2 )Q?′ ,∪i1

j=1

Bj

(x0 ; dxi1 )?(dx0 )

which is exactly the de?nition of ?E0 E1 ...Em (Γ0 ×Γ1 ×. . .×Γm ) because ∪il Bj = j=1 ∪l Bis for every l = 1, . . . , m. This concludes the proof of (4). s=1 Step 4 (Almost Sure Additivity of the Canonical Process) We will show that the canonical process X on the space (RC , RC ) has an (almost surely) unique additive extension to C(u) (with respect to the probability measure P given by Kolmogorov’s extension theorem). Let C, C1 , . . . , Ck ∈ C be such that C = ∪k Ci , and suppose that Ci = Ai \ ∪ni Aij ; i = 1, . . . , k are exi=1 j=1 tremal representations. Let A′ be the minimal ?nite sub-semilattice of A which contains the sets Ai , Aij , {B0 = ?′ , B1 , . . . , Bn } a consistent ordering of A′ and Dj the left neighbourhood of Bj . Assume that each Ci = ∪j∈Ji Dj for some Ji ? {1, . . . , n}. Because the ?nite dimensional distributions of X were chosen in an additive way, we have XCi = j∈Ji XDj a.s., XCi1 ∩Ci2 = j∈Ii ∩Ii XDj 2 1 a.s., . . . , X∩k Ci = j∈∪k Ji XDj a.s. Hence j∈∩k Ii XDj a.s., XC = i=1 XDj = XC a.s. 2 Finally we will translate the preceding result in terms of ?ows. Let ? be an arbitrary probability measure on R. For each ?nite sub-semilattice A′ and for each consistent ordering ord= {A0 = ?′ , A1 , . . . , An } of A′ pick one simple ?ow f := fA′ ,ord which connects the sets of A′ in the sense of the ordering ord. Let S be the collection of all the simple ?ows fA′ ,ord and {Qf := (Qf )s<t ; f ∈ S} a collection of one-dimensional st transition systems indexed by S.

i1 <i2 j∈∪k Ji i=1 k i=1

i=1 i=1

XC i ?

XCi1 ∩Ci2 + . . . + (?1)k X∩k Ci = i=1

A Markov property for set-indexed processes

20

The next assumption will provide a necessary and su?cient condition which will allow us to reconstruct a set-indexed transition system Q from a class of one-dimensional transition systems {Qf }. It requires that whenever we have two simple ?ows f, g ∈ S such that f (s) = g(u), f (t) = g(v) for some s < t, u < v, we must have Qf = Qg . st uv Assumption 2. If ord1= {A0 = ?′ , A1 , . . . , An } and ord2= {A0 = ?′ , A′ , 1 . . . , A′ } are two consistent orderings of some ?nite semilattices A′ , A′′ such m that ∪n Aj = ∪m A′ , ∪k Aj = ∪l A′ for some k < n, l < m, and we j=1 j=1 j j=1 j=1 j denote f := fA′ ,ord1 , g := fA′′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ , then j=1 j=1 j Qf 1 = Qg 1 and Qfk tn = Qg l um u t 0u 0t The following assumption is easily seen to be equivalent to Assumption 1. Assumption 3. If ord1 = {A0 = ?′ , A1 , . . . , An } and ord2 = {A0 = ?′ , A′ , 1 . . . , A′ } are two consistent orderings of the same ?nite semilattice A′ with Ai = n A′ , where π is a permutation of {1, . . . , n} with π(1) = 1, and we denote π(i) f := fA′ ,ord1 , g := fA′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ , then j=1 j=1 j

n Rn+1

IΓ0 (x0 )IΓ1 (x1 )

i=2

IΓi (xi ? xi?1 )Qfn?1 tn (xn?1 ; dxn ) . . . t

(5)

Qf1 t2 (x1 ; dx2 )Qf 1 (x0 ; dx1 )?(dx0 ) = t 0t

n Rn+1

IΓ0 (y0 )IΓ1 (y1 )

i=2

IΓi (yπ(i) ? yπ(i)?1 )Qg n?1 un (yn?1 ; dyn ) . . . u

Qg 1 u2 (y1 ; dy2 )Qg 1 (y0 ; dy1 )?(dy0 ) u 0u for every Γ0 , Γ1 , . . . , Γn ∈ B(R). The following result is immediate. Corollary 1. If ? is a probability measure on R and {Qf := (Qf )s<t ; st f ∈ S} is a collection of one-dimensional transition systems which satis?es the matching Assumption 2 and the consistency Assumption 3, then there exist a set-indexed transition system Q := (QBB ′ )B?B ′ and a Q-Markov process X := (XA )A∈A with initial distribution ?, such that ?f ∈ S, X f := (Xf (t) )t is Qf Markov. Proof: Let B, B ′ ∈ A(u) be such that B ? B ′ . Let B = ∪m A′ , B ′ = ∪p A′′ j=1 j l=1 l be some extremal representations, A′ the minimal ?nite sub-semilattice of A which contains the sets A′ , A′′ and ord={A0 = ?′ , A1 , . . . , An } a consistent j l ordering of A′ such that B = ∪k Aj and B ′ = ∪n Aj . Denote f := fA′ ,ord j=1 j=1 with f (ti ) = ∪i Aj . We de?ne QBB ′ := Qfk tn . t j=1

A Markov property for set-indexed processes

21

The de?nition of QBB ′ does not depend on the extremal representations of B, B ′ , because of Assumption 2. Finally it is not hard to see that the family Q := (QBB ′ )B?B ′ is a transition system which satis?es Assumption 1. 2

5

The Generator

In this section we will make use of ?ows to introduce the generator of a Q-Markov process. Corollary 1 allows us to characterize a Q-Markov process by a class {Qf ; f ∈ S} of one-dimensional transition systems. These transition sytems in turn are characterized by their corresponding generators. This observation permits us to de?ne a generator for a Q-Markov process as a class of generators indexed by a suitable class of ?ows. The generator completely characterizes the distribution of a Q-Markov process. We will also determine necessary and su?cient conditions that will ensure that a family of one-dimensional generators, indexed by a collection of simple ?ows, is the generator of a Q-Markov process. Let B(R) be the Banach space of all bounded measurable functions h : R → R with the supremum norm. Let Q := (QBB ′ )B?B ′ be a transition system and X := (XA )A∈A a QMarkov process with initial distribution ?. For each ?nite sub-semilattice A′ and for each consistent ordering ord= {A0 = ?′ , A1 , . . . , An } of A′ pick one simple ?ow f := fA′ ,ord which connects the sets of A′ in the sense of the ordering ord. Let S be the collection of all the simple ?ows fA′ ,ord . f For each f ∈ S, let T f := (Tst )s<t be the semigroup associated to the transi?f f tion system Qf and Gs , Gs the backward, respectively the forward generator of f f ?f the process X at time s, with domains D(Gs ), D(Gs ). We will make the usual ?f f assumption that all the domains D(Gs ) and D(Gs ) have a common subspace f D, which is dense in B(R), such that for every s < t, Tst (D) ? D and for every f h ∈ D, the function Tst h is strongly continuously di?erentiable with respect to s and t with ?+ f ?? f ?( Trs h)|r=s = ( Tst h)|t=s ?s ?r ?t f ?f The operator Gs = Gs de?ned on D, will be called the generator of the process X f at time s. A consequence of Kolmogorov-Feller equations is that

f Tst h ? h = s f f De?nition 5. The collection {G f := (Gs )s ; f ∈ S}, where Gs is the generaf tor of the one-dimensional process X at time s, is called the generator of the set-indexed process X. t f f Gv Tvt h dv, ?h ∈ D

(6)

Corollary 2. The generator of a Q-Markov process determines its distribution.

A Markov property for set-indexed processes

22

Proof: Since G f determines T f and Qf , the result is an immediate consequence of Corollary 1. 2 Examples 4. 1. The generator of a process with independent increments, which is stochastically continuous and weakly di?erentiable on every simple ?ow f ∈ S, is given by 1 f f (Gs h)(x) = (γs )′ h′ (x) + (Λf )′ h′′ (x)+ 2 s

{|y|>1}

(h(x + y) ? h(x))(Πf )′ (dx) + s (h(x + y) ? h(x) ? yh′ (x))(Πf )′ (dx) s

{|y|≤1}

f where γt , Λf , Πf (dy) are respectively, the translation function, the varit t ance measure, and the L?vy measure of the process on the ?ow f and e f (γs )′ , (Λf )′ , (Πf )′ (dy) denote the derivatives at s of these functions. The s s f 2 domain of Gs contains the dense subspace Cb of twice continuously di?er′ entiable functions h : R → R such that h, h , h′′ are bounded.

2. The generator of the empirical process of size n, corresponding to a probability measure F which has the property that ?f ∈ S F ?f is di?erentiable, is given by

f (Gs h)

k n

= (n ? k) h

k+1 n

?h

k n

(F ? f )′ (s) , k < n, 1 ? F ? f (s)

f where (F ? f )′ (s) denotes the derivative at s of F ? f . The domain of Gs is the space of all ?nite arrays h := (h(k))k=0,...,n .

3. The generator of the Dirichlet process with parameter measure α which has the property that ?f ∈ S α ? f is di?erentiable, is given by

f (Gs h)(x)

= (α ? f ) (s)

0

′

1?x

h(x + y) ? h(x) y

1?x?y 1?x

α(f (s)c )?1

dy

f where (α ? f )′ (s) denotes the derivative at s of α ? f . The domain of Gs 1 contains the dense subspace Cb of continuously di?erentiable functions h : R → R such that h, h′ are bounded.

The goal is to ?nd the conditions that have to be satis?ed by the collection f {G f := (Gs )s ; f ∈ S} of generators such that the associated collection {Qf ; f ∈ S} of one-parameter transition systems satis?es the matching Assumption 2 and the consistency Assumption 3. By invoking Corollary 1, we will be able

A Markov property for set-indexed processes

23

to conclude next that there exists a set-indexed transition system Q and a QMarkov process X := (XA )A∈A with initial distribution ?, whose generator is f exactly the collection {G f := (Gs )s ; f ∈ S}. Using the integral equation (6), we will ?rst give the equivalent form in terms of generators of the matching Assumption 2. Assumption 4. If ord1 = {A0 = ?′ , A1 , . . . , An } and ord2 = {A0 = ?′ , A′ , 1 . . . , A′ } are two consistent orderings of some ?nite semilattices A′ , A′′ , such m that ∪n Aj = ∪m A′ , ∪k Aj = ∪l A′ for some k < n, l < m, and we j=1 j=1 j j=1 j=1 j denote f := fA′ ,ord1, g := fA′′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ , then j=1 j=1 j for every h ∈ D

t1 0 f f Gv Tvt1 hdv = u1 0 g g Gv Tvu1 hdv and tn tk f f Gv Tvtn hdv = um ul g g Gv Tvum hdv

We will need the following notational convention. If Q1 (x1 ; dx2 ), Q2 (x2 ; dx3 ), . . . , Qn?1 (xn?1 ; dxn ) are transition probabilities on R, T1 , T2 , . . . , Tn?1 are their associated bounded linear operators, and h : Rn → R is a bounded measurable function, then T1 T2 . . . Tn?1 [h(x1 , x2 , . . . , xn )](x1 ) : =

def

h(x1 , x2 , . . . , xn )Qn?1 (xn?1 ; dxn ) . . . Q2 (x2 ; dx3 )Q1 (x1 ; dx2 )

Rn?1

If in addition, G is a linear operator on B(R) with domain D(G), and the function h is chosen such that for every x1 , . . . , xk ∈ R, the function h(x1 , x2 , . . . , xn )Qn?1 (xn?1 ; dxn ) . . . Qk+1 (xk+1 ; dxk+2 )Qk (·; dxk+1 )

Rn?k

is in D(G), then T1 T2 . . . Tk?1 GTk . . . Tn?1 [h(x1 , x2 , . . . , xn )](x1 ) : = (G

Rk?1 Rn?k def

h(x1 , x2 , . . . , xn )Qn?1 (xn?1 ; dxn ) . . . Qk+1 (xk+1 ; dxk+2 )

Qk (·; dxk+1 ))(xk )Qk?1 (xk?1 ; dxk ) . . . Q2 (x2 ; dx3 )Q1 (x1 ; dx2 ). In order to understand the consistency Assumption 3 and to see how we can express it in terms of the generators, we consider a simple example. Let A′ be a ?nite semilattice consisting of 6 sets, ord1 = {A0 = ?′ , A1 , . . . , A6 } and ord2 = {A0 = ?′ , A′ , . . . , A′ } two consistent orderings of A′ with Ai = A′ , where π 1 6 π(i) ′ is the permutation (1)(24)(36)(5). Denote with Ci , Ci the left neighbourhoods of Ai respectively A′ . i

A Markov property for set-indexed processes

24

A6 A4 A5 A1 A2 A3

A′ 3 A′ A′ 2 5 A′ A′ 1 4 A′ 6

Set f := fA′ ,ord1 , g := fA′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ j=1 j=1 j for i = 1, . . . , 6. Suppose that a Q-Markov process (XA )A∈A exists; denote X := X f and Y := X g . We have Xt2 ? Xt1 = Yu4 ? Yu3 ; Xt3 ? Xt2 = Yu6 ? Yu5 ; Xt4 ? Xt3 = Yu2 ? Yu1 Xt5 ? Xt4 = Yu5 ? Yu4 ; Xt6 ? Xt5 = Yu3 ? Yu2 Using these equalities we will ?rst ?nd the relationship between Ttf ti and i?1 f f g Tuπ(i)?1 ,uπ(i) and then between the generators (Gw )w∈[ti?1 ,ti ] and (Gv )v∈[uπ(i)?1 ,uπ(i) ] for i = 2, . . . , 6. For i = 2 we have P [Xt2 ? Xt1 ∈ Γ|Xt1 = x1 ] = P [Yu4 ? Yu3 ∈ Γ|Yu1 = x1 ] which leads us to the equation: ?h ∈ B(R) h(x2 )Qf1 t2 (x1 ; dx2 ) = t h(x1 + y4 ? y3 )Qg 3 u4 (y3 ; dy4 )Qg 1 u3 (x1 ; dy3 ) u u

R

R2

Using the above notational convention, this can be written as

g g (Ttf t2 h)(x1 ) = Tu1 u3 Tu3 u4 [h(x1 + y4 ? y3 )](x1 ). 1

(7)

Let h ∈ D and subtract h(x1 ) from both sides of this equation. Using (6) and Fubini’s theorem, we get

t2 t1 f f (Gw Twt2 h)(x1 )dw = u4 u3 g g g Tu1 u3 Gv Tvu4 [h(x1 + y4 ? y3 )](x1 )dv

(8)

Note that (7) and (8) are equivalent (since D is dense in B(R)). For i = 3, P [Xt2 ? Xt1 ∈ Γ1 , Xt3 ? Xt2 ∈ Γ2 |Xt1 = x1 ] = P [Yu4 ? Yu3 ∈ Γ1 , Yu6 ? Yu5 ∈ Γ2 |Yu1 = x1 ] which leads us to the equation: ?h1 , h2 ∈ B(R)

g g Tu1 u3 Tu3 u4 [h1 (y4 ? y3 )(Ttf t3 h2 )(x1 + y4 ? y3 )](x1 ) 2 g g g g = Tu1 u3 Tu3 u4 Tu4 u5 Tu5 u6 [h1 (y4 ? y3 )h2 (x1 + y4 ? y3 + y6 ? y5 )](x1 )

(9)

A Markov property for set-indexed processes

25

g g Let h1 , h2 ∈ D and subtract Tu1 u3 Tu3 u4 [h1 (y4 ? y3 )h2 (x1 + y4 ? y3 )](x1 ) from both sides of this equation. On the left-hand side we get t3 t2 f f g g Tu1 u3 Tu3 u4 [h1 (y4 ? y3 )(Gw Twt3 h2 )(x1 + y4 ? y3 )](x1 )

On the right-hand side we have

g g g g Tu1 u3 Tu3 u4 Tu4 u5 [(Tu5 u6 h′ (x1 , y3 , y4 , y5 , ·))(y5 ) ? h(x1 , y3 , y4 )](x1 )

with h′ (x1 , y3 , y4 , y5 , y6 ) := h1 (y4 ?y3 )h2 (x1 +y4 ?y3 +y6 ?y5 ) and h(x1 , y3 , y4 ) = h1 (y4 ? y3 )h2 (x1 + y4 ? y3 ), which becomes

u6 u5 g g g g g Tu1 u3 Tu3 u4 Tu4 u5 Gv Tvu6 [h1 (y4 ? y3 )h2 (x1 + y4 ? y3 + y6 ? y5 )](x1 )

because h′ (x1 , y3 , y4 , y5 , y5 ) = h(x1 , y3 , y4 ). Therefore, the equivalent form of (9) in terms of the generators is

t3 t2 u6 f f g g Tu1 u3 Tu3 u4 [h1 (y4 ? y3 )(Gw Twt3 h2 )(x1 + y4 ? y3 )](x1 )

(10)

=

u5

g g g g g Tu1 u3 Tu3 u4 Tu4 u5 Gv Tvu6 [h1 (y4 ? y3 )h2 (x1 + y4 ? y3 + y6 ? y5 )](x1 )

Continuing in the same manner for i = 4 we will get the necessary relag tionship between Ttf t4 and Tu1 u2 . (When we write down this relationship we 3 have to specify the ordering of π(2) ? 1, π(2), π(3) ? 1, π(3), π(4) ? 1, π(4).) This f relationship will have an equivalent form in terms of the generators (Gw )w∈[t3 ,t4 ] and (Gv )v∈[u1 ,u2 ] . At the end of this procedure we discover a collection of 5 necessary relationships that have to be satis?ed by the generators G f and G g of the process. A very important fact is that these relationships are also su?cient, i.e. if they hold then the ?nite dimensional distribution of the process over the semilattice A′ is ‘invariant’ under the two orderings ord1 and ord2. We return now to the general context. Let ?f1 be the probability measure t de?ned by ?f1 (Γ) := R Qf 1 (x; Γ)?(dx). The following result is crucial and its t 0t non-trivial proof can be found in the appendix. Lemma 6. Let ord1 = {A0 = ?′ , A1 , . . . , An } and ord2 = {A0 = ?′ , A′ , 1 . . . , A′ } be two consistent orderings of the same ?nite semilattice A′ with Ai = n A′ , where π is a permutation of {1, . . . , n} with π(1) = 1, and set f := π(i) fA′ ,ord1 , g := fA′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ . j=1 j=1 j Suppose that Qf 1 = Qg 1 . The following statements are equivalent: 0u 0t (a) the integral condition (5) of the consistency Assumption 3 holds;

A Markov property for set-indexed processes

26

(b) for each i = 2, . . . , n, if we denote with l1 ≤ l2 ≤ . . . ≤ l2(i?1) the increasing ordering of the values π(2) ? 1, π(2), π(3) ? 1, π(3), . . . , π(i) ? 1, π(i), and with p the index for which π(i) ? 1 = lp?1 , π(i) = lp , then for every h2 , . . . , hi ∈ D and for ?f1 -almost all x1 t (b1) if p = 2(i ? 1) we have

ti ti?1 i?1 g g g Tu1 ul1 Tul1 ul2 . . . Tul ulp?2

p?3

i?1 f f hj (yπ(j) ? yπ(j)?1 )(Gw Twti hi )(x1 + j=2 ulp

[

j=2

(yπ(j) ? yπ(j)?1 ))](x1 )dw

=

ulp?1 i?1

g g Tu1 ul Tul

1

1

ul2

g . . . Tul

p?3

g g g ulp?2 Tulp?2 ulp?1 Gv Tvulp

i

[

j=2

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))](x1 )dv;

(b2) if p < 2(i ? 1) we have

ti ti?1 i?1 g g Tu1 ul1 . . . Tul g g ulp?2 Tulp?2 ulp+1 Tulp+1 ulp+2 i?1 f f hj (yπ(j) ? yπ(j)?1 )(Gw Twti hi )(x1 + j=2 ulp g . . . Tul ul2(i?1)

p?3

2(i?1)?1

[

j=2

(yπ(j) ? yπ(j)?1 ))](x1 )dw

=

ulp?1 g Tulp ul g Tul

g g Tu1 ul Tul

1

1

ul2

g . . . Tul

p?3

g g g ulp?2 Tulp?2 ulp?1 Gv Tvulp i?1

p+1

u p+1 lp+2

g . . . Tul

{ u 2(i?1)?1 l2(i?1)

j=2 i?1

hj (yπ(j) ? yπ(j)?1 )·

i

[hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 )) ? hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))]}(x1 )dv.

The following assumption is the equivalent form in terms of generators of the consistency Assumption 3. Assumption 5. If ord1 = {A0 = ?′ , A1 , . . . , An } and ord2 = {A0 = ?′ , A′ , 1 . . . , A′ } are two consistent orderings of the same ?nite semilattice A′ with Ai = n A′ , where π is a permutation of {1, . . . , n} with π(1) = 1, and we denote π(i) f := fA′ ,ord1 , g := fA′ ,ord2 with f (ti ) = ∪i Aj , g(ui ) = ∪i A′ , then the j=1 j=1 j generators G f and G g satisfy condition (b) stated in Lemma 6.

A Markov property for set-indexed processes

27

Clearly Assumptions 4 and 5 are necessary conditions satis?ed by the generator of any set-indexed Q-Markov process. The following result is an immediate consequence of Corollary 1 which says that in fact, these two assumptions are also su?cient for the construction of the process.

f Theorem 2. Let ? be a probability measure on R and {G f := (Gs )s ; f ∈ S} a collection of families of linear operators on B(R) such that each operator f Gs is de?ned on a dense subspace D of B(R) and is the generator at time f s of a semigroup T f := (Tst )s<t associated with a transition system Qf := (Qf )s<t . If the family {G f ; f ∈ S} satis?es the matching Assumption 4 and st the consistency Assumption 5, then there exist a set-indexed transition system Q := (QBB ′ )B,B ′ ∈A(u);B?B ′ and a Q-Markov process X := (XA )A∈A with initial f distribution ?, whose generator is exactly the collection {Gs ; f ∈ S}.

Acknowledgement. The authors greatly appreciate the thoughtful comments and suggestions of Professor Donald. A. Dawson regarding the use of the integral equation (6) for proving the equivalence of statements (a) and (b) in Lemma 6.

A

Proof of Lemma 6

We will prove the desired equivalence by means of an intermediate condition (b’). We will show that (a) ? (b’) and (b’) ? (b). Here is this condition. (b’) For each i = 2, . . . , n, if we denote with l1 ≤ l2 ≤ . . . ≤ l2(i?1) the increasing ordering of the values π(2) ? 1, π(2), π(3) ? 1, π(3), . . . , π(i) ? 1, π(i), and with p the index for which π(i) ? 1 = lp?1 , π(i) = lp , then for every h2 , . . . , hi ∈ B(R) and for ?f1 -almost all x1 t

g g g Tu1 ul1 Tul1 ul2 . . . Tul i?1

p?3

g g ulp?2 Tulp?2 ulp+1 Tulp+1 ulp+2 i?1

g . . . Tul

2(i?1)?1

ul2(i?1)

(11)

[

j=2

hj (yπ(j) ? yπ(j)?1 )(Ttf ti hi )(x1 + i?1

j=2 g g = Tu1 ul Tul

1 1

(yπ(j) ? yπ(j)?1 ))](x1 )

ul2(i?1)

ul2

g . . . Tul

2(i?1)?1

i?1

i

[

j=2

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))](x1 );

Proof of (a) ? (b’): Let X be a Qf -Markov process and Y a Qg -Markov process with the same initial distribution ?. Since Qf 1 = Qg 1 , both Xt1 and 0u 0t Yu1 have the same distribution ?f1 . The integral condition (5) of the consistency t Assumption 6 is equivalent to saying that for ?f1 -almost all x1 , the conditional t distribution of (Xt2 ? Xt1 , . . . , Xtn ? Xtn?1 ) given Xt1 = x1 coincide with the

A Markov property for set-indexed processes

28

conditional distribution of (Yuπ(2) ? Yuπ(2)?1 , . . . , Yuπ(n) ? Yuπ(n)?1 ) given Yu1 = x1 . For i = 2 we will use the following relationship: for every Γ2 ∈ B(R) and for ?f1 -almost all x1 t P [Xt2 ? Xt1 ∈ Γ2 |Xt1 = x1 ] = P [Yuπ(2) ? Yuπ(2)?1 ∈ Γ2 |Yu1 = x1 ] Using the Markov property, the left-hand side is whereas on the right-hand side we have (x )Qf1 t2 (x1 ; dx2 ), I t R Γ2 +x1 2

R2

IΓ2 (yuπ(2) ? yuπ(2)?1 )Qg π(2)?1 uπ(2) (yπ(2)?1 ; dyπ(2) )Qg 1 uπ(2)?1 (x1 ; dyπ(2)?1 ) u u

By a monotone class argument we can conclude that for every h2 ∈ B(R) and for ?f1 -almost all x1 t h2 (x2 )Qf1 t2 (x1 ; dx2 ) = t h2 (x1 + yuπ(2) ? yuπ(2)?1 ) (12)

R

R2

Qg π(2)?1 uπ(2) (yπ(2)?1 ; dyπ(2) )Qg 1 uπ(2)?1 (x1 ; dyπ(2)?1 ) u u which is the desired relationship for i = 2. For i = 3 we will use the following relationship: for every Γ2 , Γ3 ∈ B(R) and for ?f1 -almost all x1 t P [Xt2 ? Xt1 ∈ Γ2 , Xt3 ? Xt2 ∈ Γ3 |Xt1 = x1 ] = P [Yuπ(2) ? Yuπ(2)?1 ∈ Γ2 , Yuπ(3) ? Yuπ(3)?1 ∈ Γ3 |Yu1 = x1 ] The left-hand side can be written as IΓ2 +x1 (x2 )IΓ3 +x2 (x3 )Qf2 t3 (x2 ; dx3 )Qf1 t2 (x1 ; dx2 ) t t

R2

which becomes IΓ2 (yπ(2) ? yπ(2)?1 )IΓ3 +x1 +yπ(2) ?yπ(2)?1 (x3 )Qf2 t3 (x1 + yπ(2) ? yπ(2)?1 ; dx3 ) t Qg π(2)?1 uπ(2) (yπ(2)?1 ; dyπ(2) )g Qg 1 uπ(2)?1 (x1 ; dyπ(2)?1 ) u u using equation (12). The right-hand side can be written as IΓ2 (yπ(2) ? yπ(2)?1 )IΓ3 (yπ(3) ? yπ(3)?1 )Qg l3 ,ul4 (yl3 ; dyl4 )Qg l2 ,ul3 (yl2 ; dyl3 ) u u Qg l1 ,ul2 (yl1 ; dyl2 )Qg 1 ,ul1 (x1 ; dyl1 ) u u

R3

R4

A Markov property for set-indexed processes

29

where l1 ≤ l2 ≤ l3 ≤ l4 is the increasing ordering of the values π(2)?1, π(2), π(3) ? 1, π(3). By a monotone class argument we can conclude that for every h2 , h3 ∈ B(R) and for ?f1 -almost all x1 t h2 (yπ(2) ? yπ(2)?1 )h3 (x3 )Qf2 t3 (x1 + yπ(2) ? yπ(2)?1 ; dx3 ) t Qg π(2)?1 uπ(2) (yπ(2)?1 ; dyπ(2) )Qg 1 uπ(2)?1 (x1 ; dyπ(2)?1 ) u u =

R4

(13)

R3

h2 (yπ(2) ?yπ(2)?1 )h3 (x1 +yπ(2) ?yπ(2)?1 +yπ(3) ?yπ(3)?1 )Qg l u Qg l u

2

3

,ul4 (yl3 ; dyl4 )

g g ,ul3 (yl2 ; dyl3 )Qul1 ,ul2 (yl1 ; dyl2 )Qu1 ,ul1 (x1 ; dyl1 )

which is the desired relationship for i = 3. The inductive argument will be omitted since it is identical, but notationally complex. Proof of (b’) ? (a): Let Γ0 , Γ1 , . . . , Γn ∈ B(R) be arbitrary. Using the fact that Qf 1 = Qg 1 and equation (12), the left-hand side of the integral condition 0u 0t (5) becomes IΓ0 (y0 )IΓ1 (y1 )IΓ2 (yπ(2) ? yπ(2)?1 )IΓ3 +y1 +yπ(2) ?yπ(2)?1 (x3 )IΓ4 +x3 (x4 ) . . .

Rn+2

IΓn +xn?1 (xn )Qfn?1 tn (xn?1 ; dxn ) . . . Qf3 t4 (x3 ; dx4 )Qf2 t3 (y1 +yπ(2) ?yπ(2)?1 ; dx3 ) t t t Qg π(2)?1 uπ(2) (yπ(2)?1 ; dyπ(2) )Qg 1 uπ(2)?1 (y1 ; dyπ(2)?1 )Qg 1 (y0 ; dy1 )?(dy0 ) u u 0u which in turn can be written as

Rn+3

IΓ0 (y0 )IΓ1 (y1 )IΓ2 (yπ(2) ? yπ(2)?1 )IΓ3 (yπ(3) ? yπ(3)?1 )

(yπ(j) ?yπ(j)?1 )

IΓ4 +y1 + Qf3 t4 (y1 + t

3 j=2

(x4 ) . . . IΓn +xn?1 (xn )Qfn?1 tn (xn?1 ; dxn ) . . . t

g ,ul4 (yl3 ; dyl4 )Qul2 ,ul3 (yl2 ; dyl3 )

3

(yπ(j) ? yπ(j)?1 ); dx4 )Qg l u

j=2

3

Qg l1 ,ul2 (yl1 ; dyl2 )Qg 1 ,ul1 (y1 ; dyl1 )Qg 1 (y0 ; dy1 )?(dy0 ) u u 0u using equation (13), where l1 ≤ l2 ≤ l3 ≤ l4 is the increasing ordering of the values π(2) ? 1, π(2), π(3) ? 1, π(3). Continuing in the same manner at the last step we will get exactly the desired right-hand side of equation (5), since the increasing ordering of the values π(2) ? 1, π(2), . . . , π(n) ? 1, π(n) is exactly 1 ≤ 2 ≤ . . . ≤ n. Proof of (b’) ? (b): The basic ingredient will be equation (6), which gives the integral expression of a semigroup in terms of its generator.

A Markov property for set-indexed processes

30

Since D is dense we can assume that the functions h2 , . . . , hi are in D in the expression given by (b’). Subtract

g g Tu1 ul Tul

1 1

ul2

g . . . Tul

p?3

g g ulp?2 Tulp?2 ulp+1 Tulp+1 ulp+2 i?1

g . . . Tul

2(i?1)?1

ul2(i?1)

i?1

[

j=2

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))](x1 )

from both sides of this expression. On the left-hand side we will have

g g Tu1 ul Tul

1 1

ul2

g . . . Tul

p?3

g g ulp?2 Tulp?2 ulp+1 Tulp+1 ulp+2 i?1

g . . . Tul

2(i?1)?1

ul2(i?1)

i?1

[

j=2

hj (yπ(j) ? yπ(j)?1 )(Ttf ti hi ? hi )(x1 + i?1

j=2

(yπ(j) ? yπ(j)?1 ))](x1 )

which can be written as

ti ti?1 g g Tu1 ul Tul

1 1

ul2

g . . . Tul

p?3

g g ulp?2 Tulp?2 ulp+1 Tulp+1 ulp+2 i?1

g . . . Tul

2(i?1)?1

ul2(i?1)

i?1

[

j=2

f f hj (yπ(j) ? yπ(j)?1 )(Gw Twti hi )(x1 + j=2

(yπ(j) ? yπ(j)?1 ))](x1 )dw

using the integral expression (6) and Fubini’s theorem. On the right-hand side we have

g g g Tu1 ul1 Tul1 ul2 . . . Tul g {Tul i?1

p?3

g ulp?2 Tulp?2 ulp?1 g . . . Tul ul2(i?1)

p?1

g g ulp Tulp ulp+1 Tulp+1 ulp+2 i

2(i?1)?1

[

j=2

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

j=2 g ?Tul

p?1

(yπ(j) ? yπ(j)?1 ))](ylp?1 )?

g . . . Tul ul2(i?1)

g ulp+1 Tulp+1 ulp+2 i?1

2(i?1)?1

i?1

[

j=2

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))](ylp?1 )}(x1 )

If we denote

i?1

h′ (x1 , yl1 , . . . , ylp?1 , ylp ) :=

i

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

R2(i?1)?p j=2 j=2

(yπ(j) ? yπ(j)?1 ))

A Markov property for set-indexed processes Qg l u

g ul2(i?1) (yl2(i?1)?1 ; dyl2(i?1) ) . . . Qulp+1 ulp+2 (ylp+1 ; dylp+2 )

31

2(i?1)?1

Qg lp ul u and

p+1

(ylp ; dylp+1 )

h(x1 , yl1 , . . . , ylp?1 ) :=

i?1 i?1

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

R2(i?1)?p j=2 j=2

(yπ(j) ? yπ(j)?1 ))

Qg l u

2(i?1)?1

g ul2(i?1) (yl2(i?1)?1 ; dyl2(i?1) ) . . . Qulp+1 ulp+2 (ylp+1 ; dylp+2 )

Qg l u

p?1

ulp+1 (ylp?1 ; dylp+1 )

then the right-hand side becomes

g g Tu1 ul Tul

1 1

ul2

g . . . Tul

p?3

g ulp?2 Tulp?2 ulp?1

g [(Tul

p?1

ulp h

′

(x1 , yl1 , . . . , ylp?1 , ·))(ylp?1 ) ? h(x1 , yl1 , . . . , ylp?1 )](x1 )

g g g = Tu1 ul1 Tul1 ul2 . . . Tul

p?3

g ulp?2 Tulp?2 ulp?1

[h′ (x1 , yl1 , . . . , ylp?1 , ylp?1 ) ? h(x1 , yl1 , . . . , ylp?1 )+

ulp

+

ulp?1

g g (Gv Tvulp h′ (x1 , yl1 , . . . , ylp?1 , ·))(ylp?1 )dv](x1 )

since h′ (x1 , yl1 , . . . , ylp?1 , ·) ∈ D for every x1 , yl1 , . . . , ylp?1 . We have two cases: Case 1) If p = 2(i ? 1), then all the integrals with respect to Qg lp ul , u p+1 g Qul ul , . . . , Qg l disappear in the preceding expressions. Hence u 2(i?1)?1 ul2(i?1) p+1 p+2 h′ (x1 , yl1 , . . . , ylp?1 , ylp?1 ) = h(x1 , yl1 , . . . , ylp?1 ) and the result follows. Case 2) If p < 2(i ? 1), then

g h′ (x1 , yl1 , . . . , ylp?1 , ylp?1 ) = (Tulp ul g h(x1 , yl1 , . . . , ylp?1 ) = (Tul

p+1

H(x1 , yl1 , . . . , ylp?1 , ·))(ylp?1 )

p?1

ulp+1 H(x1 , yl1 , . . . , ylp?1 , ·))(ylp?1 )

where H(x1 , yl1 , . . . , ylp?1 , ylp+1 ) :=

i?1 i?1

hj (yπ(j) ? yπ(j)?1 )hi (x1 +

R2(i?1)?p?1 j=2 j=2

(yπ(j) ? yπ(j)?1 ))

Qg l u

2(i?1)?1

g ul2(i?1) (yl2(i?1)?1 ; dyl2(i?1) ) . . . Qulp+1 ulp+2 (ylp+1 ; dylp+2 )

A Markov property for set-indexed processes

32

To simplify the notation we will omit the arguments of the function H. Hence h′ (x1 , yl1 , . . . , ylp?1 , ylp?1 ) ? h(x1 , yl1 , . . . , ylp?1 )

g = (Tulp ul

p+1

g H)(ylp?1 ) ? [Tul ulp

p?1

g ulp (Tulp ulp+1 H)](ylp?1 )

=?

ulp?1

g g g (Gv Tvulp (Tulp ul

p+1

H))(ylp?1 )dv

since H(x1 , yl1 , . . . , ylp?1 , ·) ∈ D, for every x1 , yl1 , . . . , ylp?1 . Using Fubini’s theorem, the right-hand side becomes

ulp ulp?1 g g Tu1 ul Tul

1

1

ul2

g . . . Tul

p?3

g ulp?2 Tulp?2 ulp?1

g g [(Gv Tvulp U (x1 , yl1 , . . . , ylp?1 , ·))(ylp?1 )](x1 )dv

where U (x1 , yl1 , . . . , ylp?1 , ylp ) :=

g = h (x1 , yl1 , . . . , ylp?1 , ylp ) ? (Tulp ul i?1 ′

p+1

H(x1 , yl1 , yl2 , . . . , ylp?1 , ·))(ylp )

=

R2(i?1)?p j=2 i

hj (yπ(j) ? yπ(j)?1 )

i?1

[hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 )) ? hi (x1 +

j=2

(yπ(j) ? yπ(j)?1 ))]

Qg l u

2(i?1)?1

g ul2(i?1) (yl2(i?1)?1 ; dyl2(i?1) ) . . . Qulp ulp+1 (ylp ; dylp+1 )

This concludes the proof. 2

References

[1] Adler, R.J., and Feigin, P.D. (1984). On the cadlaguity of random measures. Ann. Probab. 12, 615-630. [2] Balan, R.M. (2001). A strong Markov property for set-indexed processes. Stat. Probab. Letters 53, 219-226. [3] Balan, R.M. (2001). Set-Markov processes. Ph.D. Thesis, Univ. of Ottawa. [4] Balan, R.M. Set-indexed processes with independent increments. Submitted. [5] Bass, R.F., and Pyke, R. (1984). The existence of set-indexed L?vy proe cesses. Z. Wahrsch. verw. Gebiete 66, 157-172.

A Markov property for set-indexed processes

33

[6] Cairoli, R., and Dalang, R.C. (1996). Sequential Stochastic Optimization, John Wiley, New York. [7] Dalang, R.C., and Walsh, J.B. (1992). The sharp Markov property for L?vy e sheets. Ann. Probab. 20, 591-626. [8] Dalang R.C., and Walsh, J.B. (1992). The sharp Markov property for the Brownian sheet and related processes. Acta Math. 168, 153-218. [9] Ferguson, T.S. (1973). A Bayesian analysis of some nonparametric problems. Ann. Stat. 1, 209-230. [10] Ivano?, B.G., and Merzbach, E. (2000). Set-indexed Markov Processes. In Stochastic Models, Proceedings of the International Conference on Stochastic Models, June 1998, Carleton University. Canadian Mathematical Society Conference Proceedings 26, pp. 217-232. [11] Ivano?, B.G., and Merzbach, E. (2000). Set-Indexed Martingales, Chapman & Hall/CRC, Boca Raton, London. [12] Korezlioglu, H., Lefort, P., and Mazziotto, G. (1981). Une propri?t? ee markovienne et di?usions associ?es. Lect. Notes in Math. 863, Springere Verlag, 245-276. [13] Lawler, G.F., and Vanderbei, R.J. (1981). Markov strategies for optimal control problems indexed by a partially ordered set. Ann. Probab. 11, 642647. [14] L?vy, P. (1948). Exemples de processus doubles de Marko?. C.R.A.S. 226, e 307-308. [15] Mazziotto, G. (1988). Two-parameter Hunt processes and a potential theory. Ann. Probab. 16, 600-619. [16] McKean, J.H.P. (1963). Brownian motion with a several-dimensional time. Th. Probab. Applic. 8, 335-354. [17] Nualart, D. (1980). Propriedad de Markov para functiones aleatorias gaussianas. Cuadern. Estadistica Mat. Univ. Granada Ser. A Prob. 5, 30-43. [18] Nualart, D., and Sanz, M. (1979). A Markov property for two-parameter Gaussian processes. Stochastica 3, 1-16. [19] Russo, F. (1984). Etude de la propri?t? de Markov ?troite en relation ee e avec les processus planaires ` accroissements ind?pendantes. Lect. Notes a e in Math. 1059, Springer-Verlag, 353-378.

A Markov property for set-indexed processes

34

[20] Walsh, J.B. (1976-1977). Martingales with a multidimensional parameter and stochastic integrals in the plane. Cours III cycle, Laboratoire de Probabilit?s, Univ. Paris VI. e [21] Wilks, S. S. (1963). Mathematical Statistics, John Wiley.