Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T13:38:43.979Z Has data issue: false hasContentIssue false
  • English
  • Français

SIEGMUND DUALITY FOR MARKOV CHAINS ON PARTIALLY ORDERED STATE SPACES

Published online by Cambridge University Press:  04 September 2017

Paweł Lorek Open the ORCID record for Paweł Lorek [Opens in a new window]
Paweł Lorek*
Affiliation:
Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For a Markov chain on a finite partially ordered state space, we show that its Siegmund dual exists if and only if the chain is Möbius monotone. This is an extension of Siegmund's result for totally ordered state spaces, in which case the existence of the dual is equivalent to the usual stochastic monotonicity. Exploiting the relation between the stationary distribution of an ergodic chain and the absorption probabilities of its Siegmund dual, we present three applications: calculating the absorption probabilities of a chain with two absorbing states knowing the stationary distribution of the other chain; calculating the stationary distribution of an ergodic chain knowing the absorption probabilities of the other chain; and providing a stable simulation scheme for the stationary distribution of a chain provided we can simulate its Siegmund dual. These are accompanied by concrete examples: the gambler's ruin problem with arbitrary winning/losing probabilities; a non-symmetric game; an extension of a birth and death chain; a chain corresponding to the Fisher–Wright model; a non-standard tandem network of two servers, and the Ising model on a circle. We also show that one can construct a strong stationary dual chain by taking the appropriate Doob transform of the Siegmund dual of the time-reversed chain.

Keywords

Doob h-transformgambler's ruin problemMarkov chainsMöbius monotonicitypartial orderingSiegmund dualitystrong stationary duality
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 32 , Issue 4 , October 2018 , pp. 495 - 521
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Athreya, K.B. & Majumdar, M. (2003). Estimating the stationary distribution of a Markov chain. Economic Theory 21(2): 729–742.Google Scholar
2.Błaszczyszyn, B. & Sigman, K. (1999). Risk and duality in multidimensions. Stochastic Processes and their Applications 83: 331–356.Google Scholar
3.Cox, J.T. & Rösler, U. (1984). A duality relation for entrance and exit laws for Markov processes. Stochastic Processes and their Applications 16: 141–156.Google Scholar
4.Dette, H., Fill, J.A., Pitman, J. & Studden, W.J. (1997). Wall and Siegmund duality relations for birth and death chains with reflecting barrier. Journal of Theoretical Probability 10(2): 349–374.Google Scholar
5.Diaconis, P. & Fill, J.A. (1990). Strong stationary times via a new form of duality. The Annals of Probability 18(4): 1483–1522.Google Scholar
6.Ewens, W. (2004). Mathematical population genetics. New York: Springer-Verlag.Google Scholar
7.Falin, G.I. (1988). Monotonicity of random walks in partially ordered sets. Russian Mathematical Surveys 43(2): 167–168.Google Scholar
8.Feller, W. (1951). Diffusion processes in genetics. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. The Regents of the University of California, pp. 227–246.Google Scholar
9.Fill, J.A. & Lyzinski, V. (2016). Strong stationary duality for diffusion processes. Journal of Theoretical Probability 29(4): 1298–1338.Google Scholar
10.Foley, R.D. & McDonald, D.R. (2005). Large deviations of a modified Jackson network: Stability and rough asymptotics. The Annals of Applied Probability 15(1B): 519–541.Google Scholar
11.Harrison, J.M. & Williams, R.J. (1987). Multidimensional reflected Brownian motions having exponential stationary distributions. The Annals of Probability 15(1): 115–137.Google Scholar
12.Huillet, T. (2010). Siegmund duality with applications to the neutral Moran model conditioned on never being absorbed. Journal of Physics A: Mathematical and Theoretical 43(37): 1–14.Google Scholar
13.Huillet, T. & Martínez, S. (2016). On Möbius duality and coarse-graining. Journal of Theoretical Probability 29(1): 143–179.Google Scholar
14.Hunter, B., Krinik, A.C., Nguyen, C., Switkes, J.M. & Von Bremen, H.F. (2008). Gamblers ruin with catastrophes and windfalls. Journal of Statistical Theory and Practice 2(2): 199–219.Google Scholar
15.Lee, C.E., Ozdaglar, A. & Shah, D. (2013). Approximating the stationary probability of a single state in a Markov chain. ArXiv preprint arXiv:1312.1986, pp. 1–55.Google Scholar
16.Liggett, T.M. (2004). Interacting Particle Systems. Berlin, Heidelberg: Springer-Verlag.Google Scholar
17.Lindley, D.V. (1952). The theory of queues with a single server. Mathematical Proceedings of the Cambridge Philosophical Society 48(2): 277–289.Google Scholar
18.Lorek, P. (2007). Speed of convergence to stationarity for stochastically monotone Markov chains. PhD thesis, University of Wrocław, Wrocław, Poland.Google Scholar
19.Lorek, P. (2017). Generalized Gambler's ruin problem: Explicit formulas via Siegmund duality. Methodology and Computing in Applied Probability 19(2): 603–613.Google Scholar
20.Lorek, P. & Markowski, P. (2017). Monotonicity requirements for efficient exact sampling with Markov chains. To appear in Markov Processes and Related Fields.Google Scholar
21.Lorek, P. & Szekli, R. (2012). Strong stationary duality for Möbius monotone Markov chains. Queueing Systems 71(1-2): 79–95.Google Scholar
22.Lorek, P. & Szekli, R. (2016). Strong stationary duality for Möbius monotone Markov chains: Examples. Probability and Mathematical Statistics 36(1): 75–97.Google Scholar
23.Miclo, L. (2017). Strong stationary times for one-dimensional diffusions. Annales de l'Institut Henri Poincaré Probability Statistics 53(7): 957–996.Google Scholar
24.Parzen, E. (1962). Stochastic Processes. San Francisco: Holden-Day, Inc.Google Scholar
25.Propp, J.G. & Wilson, D.B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9: 223–252.Google Scholar
26.Rota, G.-C. (1964). On the foundations of combinatorial theory I. Theory of Möbius functions. Probability Theory and Related Fields 368: 340–368.Google Scholar
27.Siegmund, D. (1976). The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes. The Annals of Probability 4(6): 914–924.Google Scholar