Abstract
This paper develops a systematic treatment of monotonicitybased pathwise dualities for Markov processes taking values in partially ordered sets. We show that every Markov process that takes values in a finite partially ordered set and whose generator can be represented in monotone maps has a pathwise dual process. In the special setting of attractive spin systems, this has been discovered earlier by Gray. We show that the dual simplifies a lot when the state space is a lattice (in the ordertheoretic meaning of the word) and all monotone maps satisfy an additivity condition. This leads to a unified treatment of several wellknown dualities, including Siegmund’s dual for processes with a totally ordered state space, duality of additive spin systems, and a duality due to Krone for the twostage contact process, and allows for the construction of new dualities as well. We show that the wellknown representation of additive spin systems in terms of open paths in a graphical representation can be generalized to additive Markov processes taking values in general lattices, but for the process and its dual to be representable on the same underlying space, we need to assume that the lattice is distributive. In the final section, we show how our results can be generalized from finite state spaces to interacting particle systems with finite local state spaces.
This is a preview of subscription content, access via your institution.
Notes
 1.
More formally, we require that there exist four functions \({{\mathbf {X}}}_{s,t}\), \({{\mathbf {X}}}_{s,t}\), \({{\mathbf {X}}}_{s,t}\), and \({{\mathbf {X}}}_{s,t}\) such that \({{\mathbf {X}}}_{s,t}=\lim _{u\uparrow s}{{\mathbf {X}}}_{u,t}\) and \({{\mathbf {X}}}_{s,t}=\lim _{u\downarrow s}{{\mathbf {X}}}_{u,t}\), and likewise with t replaced by \(t\), and with the roles of the first and second variable interchanged.
 2.
The alternative is to take \({{\mathbf {Y}}}_{u,(t)}(y)\) which is rightcontinuous but notationally cumbersome.
 3.
The connection between pathwise duality and invariant subspaces exposed here has an analog for (nonpathwise) duality. In [24, Prop 2.2], it is shown that if S, T are finite sets and \(\psi :S\times T\rightarrow {{\mathbb {R}}}\) is such that the functions \(\{\psi (\cdot ,y):y\in T\}\) are linearly independent, then a Markov process X with state space S has a dual w.r.t. to the duality function \(\psi \) if and only if the semigroup of X maps the convex hull of \(\{\psi (\cdot ,y):y\in T\}\) into itself.
 4.
Theorem 9 shows that a process X has a pathwise dual w.r.t. to the duality function \(\phi \) from (28) if X is monotonically representable. This condition is also necessary: If a map m has a dual w.r.t. to \(\phi \), then \(m^{1}\) maps decreasing sets into decreasing sets and hence, by Lemma 5, m is monotone.
 5.
See formulas (10)–(12) of [12]. His notation for \({{\mathbf {X}}}_{s,t}(x)\) is \(\xi (s,t,x)\).
 6.
Gray does not state his definition entirely correctly. In his definition of minimality, he also includes, probably inadvertently, the condition that \({\tilde{\pi }}(s)=x\).
 7.
Alternatively, one may consider the map \(x\mapsto \big (\{x\}^\uparrow \cap \varLambda \big )^{\mathrm{c}}\) where \(\varLambda \) is the set of meetirreducible elements of S. As a result of Birkhoff’s representation theorem, one can prove that this map is onto, and as a result sets up an isomorphism between the lattices S and \({{\mathcal {P}}}_{\mathrm{dec}}(\varLambda )\), if and only if S is distributive.
 8.
Let S and T be partially ordered sets. If a map \(m:S\rightarrow T\) is monotone, then it is also monotone with respect to the reversed orders on S and T. In view of this and Lemma 5 (i), a map \(m:S\rightarrow T\) is monotone if and only if \(m^{1}(A)\in {{\mathcal {P}}}_{\mathrm{inc}}(S)\) for all \(A\in {{\mathcal {P}}}_{\mathrm{inc}}(T)\).
References
 1.
Alkemper, R., Hutzenthaler, M.: Graphical representation of some duality relations in stochastic population models. Electron. Commun. Probab. 12, 206–220 (2007)
 2.
Athreya, S.R., Swart, J.M.: Branchingcoalescing particle systems. Probab. Theory Relat. Fields 131(3), 376–414 (2005)
 3.
Birkhoff, G.: Rings of sets. Duke Math. J. 3(3), 443–454 (1937)
 4.
Carinci, G., Giardinà, C., Giberti, C., Redig, F.: Dualities in population genetics: a fresh look with new dualities. Stoch. Process. Appl. 125(3), 941–969 (2015)
 5.
Cox, J.T., Roesler, U.: A duality relation for entrance and exit laws for Markov processes. Stoch. Process. Appl. 16, 141–156 (1984)
 6.
Clifford, P., Sudbury, A.: A sample path proof of the duality for stochastically monotone Markov processes. Ann. Probab. 13, 558–565 (1985)
 7.
Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge (2002)
 8.
Diaconis, P., Fill, J.A.: Strong stationary times via a new form of duality. Ann. Probab. 18(4), 1483–1522 (1990)
 9.
Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, London (1986)
 10.
Fill, J.A., Machida, M.: Stochastic monotonicity and realizable monotonicity. Ann. Probab. 29(2), 938–978 (2001)
 11.
Giardinà, C., Kurchan, J., Redig, F., Vafayi, K.: Duality and hidden symmetries in interacting particle systems. J. Stat. Phys. 135(1), 25–55 (2009)
 12.
Gray, L.: Duality for general attractive spin systems with applications in one dimension. Ann. Probab. 14(2), 371–396 (1986)
 13.
Griffeath, D.: Additive and Cancellative Interacting Particle Systems. Lecture Notes in Mathematics, vol. 724. Springer, Berlin (1979)
 14.
Harris, T.E.: Additive setvalued Markov processes and graphical methods. Ann. Probab. 6, 355–378 (1978)
 15.
Huillet, T., Martinez, S.: Duality and intertwining for discrete Markov kernels: relations and examples. Adv. Appl. Probab. 43(2), 437–460 (2011)
 16.
Jansen, S., Kurt, N.: On the notion(s) of duality for Markov processes. Probab. Surv. 11, 59–120 (2014)
 17.
Kamae, T., Krengel, U., O’Brien, G.L.: Stochastic inequalities on partially ordered spaces. Ann. Probab. 5(6), 899–912 (1977)
 18.
Kolokoltsov, V.: Stochastic monotonicity and duality for onedimensional Markov processes. Math. Notes 89(5), 652–660 (2011)
 19.
Kolokoltsov, V., Lee, R.X.: Stochastic duality of Markov processes: a study via generators. Stoch. Anal. Appl. 31, 992–1023 (2013)
 20.
Krone, S.: The twostage contact process. Ann. Appl. Probab. 9(2), 331–351 (1999)
 21.
Lee, R.X.: The existence and characterisation of duality of Markov processes in the Euclidean space. Ph.D. thesis, University of Warwick. http://go.warwick.ac.uk/wrap/61991 (2013)
 22.
Liggett, T.M.: Interacting Particle Systems. Springer, New York (1985)
 23.
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. AMS, Providence (2009)
 24.
Möhle, M.: Duality and cones of Markov processes and their semigroups. Markov Process. Relat. Fields 19(1), 149–162 (2013)
 25.
Neuhauser, C.: A long range sexual reproduction process. Stoch. Process. Appl. 53, 193–220 (1994)
 26.
Noble, C.: Equilibrium behavior of the sexual reproduction process with rapid diffusion. Ann. Probab. 20(2), 724–745 (1992)
 27.
Ross, D.A.: A coherence theorem for ordered families of probability measures on a partially ordered space. Unpublished manuscript (1993)
 28.
Siegmund, D.: The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes. Ann. Probab. 4(6), 914–924 (1976)
 29.
Sudbury, A., Lloyd, P.: Quantum operators in classical probability theory. II: the concept of duality in interacting particle systems. Ann. Probab. 23(4), 1816–1830 (1995)
 30.
Sudbury, A., Lloyd, P.: Quantum operators in classical probability theory. IV: quasiduality and thinnings of interacting particle systems. Ann. Probab. 25(1), 96–114 (1997)
 31.
Sturm, A., Swart, J.M.: A particle system with cooperative branching and coalescence. Ann. Appl. Probab. 25(3), 1616–1649 (2015)
 32.
Sturm, A., Swart, J.M.: Monotone and additive Markov process duality. Preprint. arXiv:1510.06284v1 (2015)
 33.
Sudbury, A.: Dual families of interacting particle systems on graphs. J. Theor. Probab. 13(3), 695–716 (2000)
 34.
Swart, J.M.: Duals and thinnings of some relatives of the contact process. Preprint (18 pages). arXiv:math.PR/0604335
 35.
Swart, J.M.: Duals and thinnings of some relatives of the contact process. In: Hukov, M., Janura, M. (eds.) Prague Stochastics 2006, pp. 203–214. Matfyzpress, Prague (2006)
 36.
Swart, J.M.: Interacting Particle Systems. Lecture Notes. http://staff.utia.cas.cz/swart/tea_index.html (2016)
Acknowledgements
We thank Fero Matúš and June Huh for useful discussions, and László Csirmaz for help with the proof of Lemma 15. We also thank two anonymous referees for a careful reading of the manuscript and some helpful suggestions.
Author information
Affiliations
Corresponding author
Additional information
Work sponsored by GAČR Grant P201/12/2613 and by DFG priority programme 1590 Grant STU527/11.
Appendices
Appendix 1: A Bit of Lattice Theory
In this appendix, we collect some elementary properties of partially ordered sets and lattices that are used in the paper.
Let S be a any set. Recall that a relation \(\le \) on S is called a partial order if it satisfies the axioms

(i)
\(x\le x\) \((x\in S)\).

(ii)
\(x\le y\) and \(y\le x\) implies \(x=y\) \((x,y\in S)\).

(iii)
\(x\le y\le z\) implies \(x\le z\) \((x,y\in S)\).
A partially ordered set (also called poset) is a set with a partial order defined on it. A total order is a partial order such that, moreover,

(iv)
\(x\le y\) or \(y\le x\) (or both) \((x,y\in S)\).
Increasing and decreasing sets and the notation \(A^\uparrow \) and \(A^\downarrow \) have already been defined in Sect. 2.3.
By definition, a minimal element of a set \(A\subset S\) is an \(x\in A\) such that \(\{y\in A:y\le x\}=\{x\}\). Maximal elements are minimal elements for the reversed order. The following simple observation is wellknown.
Lemma 34
(Maximal elements) Let S be a partially ordered set and let \(A\subset S\) be finite. Then, for every \(x\in A\) there exists a maximal element \(y\in A\) such that \(y\ge x\).
Proof
Either x is a maximal element or there exists some \(x^{\prime }\in A\), \(x^{\prime }\ne x\), such that \(x^{\prime }\ge x\). Continuing this process, using the finiteness of A, we arrive after a finite number of steps at a maximal element. \(\square \)
In particular, Lemma 34 shows that every nonempty finite \(A\subset S\) has a maximal element. Applying this to the reversed order, we see that A also contains a minimal element.
Let S be a partially ordered set and \(A\subset S\). An upper bound of A is an element \(x\in S\) such that \(y\le x\) for all \(y\in A\). Note that in general x does not have to be an element of A. If there exists an element \(x\in A\) that is an upper bound of A, then such an element is necessarily unique. (Indeed, imagine that \(x^{\prime }\in A\) is also an upper bound for A, then \(x^{\prime }\le x\) and \(x\le x^{\prime }\).)
If A is decreasing and there exists an element \(x\in A\) that is an upper bound of A, then \(A=\{x\}^\downarrow \). Indeed, the fact that x is an upper bound means that \(A\subset \{x\}^\downarrow \) while by the facts that \(x\in A\) and A is decreasing, we have \(A\supset \{x\}^\downarrow \). A least upper bound of A is an element \(x\in S\) that is an upper bound of A and that satisfies \(x\le x^{\prime }\) for any (other) upper bound \(x^{\prime }\) of A. Note that \(\bigcap _{x\in A}\{x\}^\uparrow \) is the set of all upper bounds of A, which is an increasing set. Thus, a least upper bound of A is an element \(x\in \bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow \) that is a lower bound of \(\bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow \). By our earlier remarks, such an element is unique. Also, since \(\bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow \) is an increasing set, if there exists an element \(x\in \bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow \) that is a lower bound of \(\bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow \), then \(\bigcap _{x^{\prime }\in A}\{x^{\prime }\}^\uparrow =\{x\}^\uparrow \).
A partially ordered set S is a joinsemilattice if and only if for each \(y,z\in S\), the set \(\{y,z\}\) has a least upper bound. Equivalently, this says that there exists an element \(x\in \{y\}^\uparrow \cap \{z\}^\uparrow \) that is a lower bound of \(\{y\}^\uparrow \cap \{z\}^\uparrow \). By our earlier remarks, such an element is unique and one must in fact have \(\{y\}^\uparrow \cap \{z\}^\uparrow =\{x\}^\uparrow \). We denote this unique element by \(x=:y\vee z\) and call it the supremum or join of x and y. Note that this (more traditional) definition of suprema and joinsemilattices is equivalent to the definition in (19). Infima and meetsemilattices are defined in the same way, but with respect to the reversed order.
Each finite joinsemilattice S is clearly bounded from above, since \(\bigvee _{x\in S}x\) is an upper bound; similarly finite meetsemilattices are bounded from below.
As already mentioned in Sect. 2.3, if S is a partially ordered set, then a nonempty increasing set \(A\subset S\) such that for every \(x,y\in A\) there exists a \(z\in A\) with \(z\le x,y\) is called a filter and a nonempty decreasing set A such that for every \(x,y\in A\) there exists a \(z\in A\) with \(x,y\le z\) is called an ideal.
The following lemma characterizes ideals in joinsemilattices. An analog statement holds for filters. In a latticetheoretic setting, this lemma is often taken as the definition of an ideal.
Lemma 35
(Ideals in joinsemilattices) Let S be a joinsemilattice and let \(A\subset S\). Then A is an ideal if and only if A is nonempty, decreasing, and \(x,y\in A\) imply \(x\vee y\) in A.
Proof
Let A be nonempty and decreasing. If \(x,y\in A\) imply \(x\vee y\) in A, then for every \(x,y\in A\) there is an element of A, namely \(x\vee y\), such that \(x\vee y\ge x,y\), showing that A is an ideal. Conversely, if A is an ideal, then for every \(x,y\in A\) there is an element \(z\in A\) such that \(z\ge x,y\) and hence \(z\ge x\vee y\), which by the fact that A is decreasing proves that \(x\vee y\in A\). \(\square \)
As already mentioned in Sect. 2.3, a principal filter is a filter that contains a minimal element and a principal ideal is an ideal that contains a maximal element. We state the following facts for ideals only; applying them to the reversed order yields analog statements for filters.
Lemma 36
(Principal ideals) Let S be a partially ordered set and let \(A\subset S\). Then:

1.
If A is an ideal, then A contains at most one maximal element.

2.
A is a principal ideal if and only if there exists some \(z\in S\) such that \(A=\{z\}^\downarrow \).
If A is moreover finite, then the following conditions are equivalent:

(i)
A is a principal ideal.

(ii)
A is an ideal.

(iii)
A is decreasing and contains a unique maximal element.
Proof
1. If A is an ideal and \(x,y\in A\) are maximal, then there exists some \(z\in A\) such that \(z\ge x,y\) and hence \(x=z=y\) by the definition of maximality.
2. Let A be a principal ideal with maximal element z. Then \(\{z\}^\downarrow \subset A\) by the fact that A is decreasing. The inclusion \(\{z\}^\downarrow \supset A\) follows by observing that if \(x\in A\), then by the definition of an ideal there exists some \(y\in A\) with \(y\le x,z\), and hence \(y=z\) by the maximality of z, so \(x\le y=z\). Conversely, it is straightforward to check that each set of the form \(\{z\}^\downarrow \) is a principal ideal.
The implications (i)\(\Rightarrow \)(ii) and (i)\(\Rightarrow \)(iii) are trivial. Assume that \(A\subset S\) is finite. Then (ii)\(\Rightarrow \)(i) by Lemma 34. We claim that moreover (iii)\(\Rightarrow \)(i). Let z be the unique maximal element of A. By 2, it suffices to prove that \(A=\{z\}^\downarrow \). Since A is decreasing, we have \(\{z\}^\downarrow \subset A\). To prove the other inclusion, we observe that for any \(x\in A\), by Lemma 34, there exists a maximal element \(y\in A\) such that \(y\ge x\). By assumption, z is the unique maximal element of A, so \(y=z\) and hence \(x\le z\), proving that \(x\in \{z\}^\downarrow \).
\(\square \)
Appendix 2: List of Notation

\(\subset \) used in the meaning of \(\subseteq \) throughout the paper.

0, 1 general notation for the lower and upper bound of a partially ordered set [as defined below (19)].

\(\langle x,y\rangle :=1_{\textstyle \{x\le y^{\prime }\}}, x\in S,\ y\in S^{\prime }\) [see (23)].

\(\leadsto \) indicates the existence of an open path in a percolation substructure (see Sect. 2.6).

\(\vee ,\wedge \) supremum, infimum [see (19)].

\(A^\uparrow :=\{x\in S:x\ge y \text{ for } \text{ some } y\in A\}\supset A\).

\(A^\downarrow :=\{x\in S:x\le y \text{ for } \text{ some } y\in A\}\supset A\).

\(A_{\mathrm{max}},A_{\mathrm{min}}\) set of maximal, resp. minimal elements of A [see (29)].

\({{\mathcal {F}}}(S,T)\) space of all functions \(f:S\rightarrow T\).

\({{\mathcal {F}}}_{\mathrm{mon}}(S,T)\) space of all monotone maps \(m:S\rightarrow T\) [see (20)].

\({{\mathcal {G}}}\) set of maps used in the random mapping representation of a generator (see Sect. 2.2).

G, H Markov process generator and dual generator [see (10) and (13)].

\(H_\dagger , H_*, H_\circ , H_\bullet \) dual generators [see (34)].

\({{\mathcal {K}}}(S,T)\) space of all probability kernels from S to T.

\(P_t\) transition probabilities (see Sect. 2.1).

\({{\mathcal {P}}}(S):=\{A:A\subset S\}\) set of all subsets of S.

\(\displaystyle {{\mathcal {P}}}_{\mathrm{inc}}(S),\displaystyle {{\mathcal {P}}}_{\mathrm{dec}}(S)\) increasing, decreasing subsets of S [see (18)].

\(\displaystyle {{\mathcal {P}}}_{\mathrm{!inc}}(S),\displaystyle {{\mathcal {P}}}_{\mathrm{!dec}}(S)\) principal filters, ideals of S [see (18)].

S, T state spaces, mostly endowed with a partial order \(\le .\)

\(S^{\prime }\) dual of the partially ordered space S [see (22)].

\(X_t,Y_t\) Markov process and dual Markov process (see Sect. 2.1).

\({{\mathbf {X}}}_{s,t},{{\mathbf {Y}}}_{s,t}\) stochastic flows associated with Markov processes X, Y (see Sect. 2.1).

\(m:S\rightarrow S\) and \({\hat{m}}:T\rightarrow T\) map and dual map with respect to \(\psi \) [see (12)].

\(m^{\prime }\) dual map associated with an additive map m (see Lemma 6).

\(m^\dagger , m^*, m^\circ , m^\bullet \) dual maps associated with a monotone map m [see (30) and (36)].

\(x^{\mathrm{c}}\) complement of a set x.

\(x^{\prime },y^{\prime }\) elements of the dual space \(S^{\prime }\) associated with \(x,y\in S\) [see (22)].

\(\Delta ,\Delta _{s,t}\) Poisson point sets used in the graphical representation of a Markov process (see Sect. 2.2).

\(\varLambda \) a finite set (in Sects. 1, 2, 3, 4) or a countable set (in Sect. 5).

\(\phi , {\tilde{\phi }}:\) duality functions [see (28) and (35)].

\(\psi :S\times T\rightarrow {{\mathbb {R}}}\) duality function [see (2) and (4)].
Rights and permissions
About this article
Cite this article
Sturm, A., Swart, J.M. Pathwise Duals of Monotone and Additive Markov Processes. J Theor Probab 31, 932–983 (2018). https://doi.org/10.1007/s1095901607215
Received:
Revised:
Published:
Issue Date:
Keywords
 Pathwise duality
 Monotone Markov process
 Additive Markov process
 Interacting particle system
Mathematics Subject Classification (2010)
 82C22
 60J27
 06A06
 06B10