## Markov Models

*18 Apr 2022 18:35*

Markov processes are my life. Which means I don't have time to explain them. Even as a pile of pointers, this is more inadequate than usual.

Topics of particular interest: statistical inference for Markov and hidden Markov models;
model selection for Markov models and HMMs;
Markovian representation results, i.e., ways of representing non-Markovian
processes as functions of Markov processes.
Ergodic and
large-deviations results. (Ergodic theory
for Markov processes gets notebook.) Markov
random fields. Abstractions of the usual Markov property,
i.e., graphical models. Relationship
between Markov properties and statistical
sufficiency, i.e., if I construct a minimal predictive sufficient statistic
for some process, is that statistic always Markovian? (I believe the answer is
"yes"; but as Wolfgang Loehr pointed out to me, it is false without the
restriction to *minimal* sufficient statistics.) Differential-equation
approximations of Markov processes and vice versa are covered
under convergence of
stochastic processes.

See also: Chains with Complete Connections; Compartment Models; Convergence of Stochastic Processes; Ergodic Theory of Markov and Related Processes; Filtering and State Estimation; Hidden Markov Models; Interacting Particle Systems; Inference for Markov and Hidden Markov Models; Monte Carlo; Prediction Processes; Markovian (and Conceivably Causal) Representations of Stochastic Processes; Random Fields; Stochastic Differential Equations

- Recommended, big picture:
- Pierre Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
- J. Doob, Stochastic Processes [comments]
- Grimmett and Stirzaker, Probability and Random Processes
- Andrzej Lasota and Michael C. Mackey, Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics [Really, an excellent textbook on Markov operators, particularly those arising from deterministic dynamical systems.]

- Recommended, close-ups, approximation of Markov processes by ODEs and vice versa:
- Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence [comments]
- Thomas G. Kurtz
- "Solutions of Ordinary Differential Equations as Limits of
Pure Jump Markov Processes", Journal of Applied Probability
**7**(1970): 49--58 - "Limit Theorems for Sequences of Jump Markov Processes
Approximating Ordinary Differential Processes", Journal of Applied
Probability
**8**(1971): 344--356 - Approximation of Population Processes [comments]

- "Solutions of Ordinary Differential Equations as Limits of
Pure Jump Markov Processes", Journal of Applied Probability

- Recommended, close-ups, the Gibbs-Markov correspondence:
- David Griffeath, "Introduction to Markov Random Fields", ch. 12 in Kemeny, Knapp and Snell, Denumerable Markov Chains [One of the proofs of the equivalence between the Markov property and having a Gibbs distribution, conventionally but misleadingly called the Hammersley-Clifford Theorem. Pollard, below, provides an on-line summary.]
- David Pollard, "Markov random fields and Gibbs distributions" [Online PDF. A proof of the theorem linking Markov random fields to Gibbs distributions, following the approach of David Griffeath.]

- Recommended, close-ups on Markovian representations of non-Markov processes:
- Hirotugu Akaike, "Markovian representation of stochastic processes and its application to the analysis of autoregressive moving average processes",
Annals of the Institute of Statistical
Mathematics
**26**(1974): 363--387 [Reprinted on pp. 223--247 of Akaike's Selected Papers; thanks to Victor Solo for alerting me to this paper] - David Blackwell and Lambert Koopmans, "On the Identifiability Problem
for Functions of Finite Markov Chains", Annals of Mathematical
Statistics
**28**(1957): 1011--1015 - R. V. Erickson, "Functions of Markov Chains",
Annals of
Mathematical Statistics
**41**(1970): 843--850 [Necessary and sufficient conditions for a discrete-valued stochastic process to be a function of a Markov chain] - Alex Heller, "On Stochastic processes Derived from Markov
Chains", Annals
of Mathematical Statistics
**36**(1965): 1286--1291 - Olof Görnerup and Martin Nilsson Jacobi, "A method for
inferring hierarchical dynamics in stochastic processes",
Advances in Complex Systems
**11**(2008): 1--16, nlin.AO/0703034 [A method for finding coarse-grainings of stochastic processes which are Markovian, whether or not the original process is Markovian.] - Martin Nilsson Jacobi, Olof Goernerup, "A dual eigenvector condition for strong lumpability of Markov chains", arxiv:0710.1986
- Frank Knight [The most powerful and general Markovian
representation results known to me, which in fact include chunks of my thesis
as a special case. Specifically, for essentially any stochastic process one
might care to consider, Knight shows how to construct a homogeneous Markov
process, which he calls the "measure-theoretic prediction process", which
generates the original, observed process. The states of the prediction process
correspond to conditional distributions over future observations: hence its
name. The prediction process is, though he doesn't put it this way, the
minimal sufficient predictive statistic for the future of the observable
process. I recommend starting with "A Predictive View" before tackling
Foundations; I tried it the other way around and found it very
painful.]
- "A Predictive View of Continuous Time Processes", The Annals of Probability
**3**(1975): 573--596 - Foundations of the Prediction Process

- "A Predictive View of Continuous Time Processes", The Annals of Probability
- Laurence K. Saul and Michael I. Jordan, "Mixed Memory Markov
Models: Decomposing Complex Stochastic Processes as Mixtures of Simpler
Ones", Machine Learning
**37**(1999): 75--87 - A. I. Shushin, "Non-Markovian stochastic Liouville equation and its
Markovian representation", Physical Review E
**67**(2003): 061107 [This is very much a physicist's paper. It*starts*with non-Markovian fluctuations driving a relaxation process, and then*postulates*that those fluctuations are in turn driven by a Markov process. That is, there is no systematic construction of Markovian representations, just the hope that they exist, and the demonstration that the author is clever enough to find them for some important special cases. (Which is certainly more than I could do.) Whether systematic representation results could improve on this at all is an interesting question.]

- Recommended, close-ups, not otherwise categorized:
- M. Abel, K. H. Andersen and G. Lacorata, "Hierarchical Markovian modeling of multi-time scale systems", nlin.CD/0201027
- Gely P. Basharin, Amy N. Langville and Valeriy A.
Naumov, "The Life and Work of A. A. Markov", Linear Algebra and its
Applications
**386**(2004): 3--26 [Online PDF. Includes a very nice discussion of Markov's original, elegant proof of the weak law of large numbers for his chains.] - Patrick Billingsley, Statistical Inference for Markov Chains
- Ross Kindermann and J. Laurie Snell, Markov Random Fields and their Applications [1980 classic; dreadful typography; full text free online]
- Sergey Kirshner, Padhraic Smyth and Andrew Robertson, "Conditional Chow-Liu Tree Structures for Modeling Discrete-Valued Vector Time Series", in Chickering and Halpern (eds.), Uncertainty in Artificial Intelligence: Proceedings of the Twentieth Conference (UAI 2004), pp. 317--324 [longer technical report version in PDF]
- Vivien Lecomte, Cecile Appert-Rolland and Frederic van Wijland,
"Chaotic properties of systems with Markov
dynamics", Physical
Review Letters
**95**(2005): 010601, cond-mat/0505483 [Showing that the thermodynamic formalism can work for continuous-time Markov processes, which is very nice] - L. C. G. Rogers and D. Williams, Diffusions, Markov Processes and Martingales [comments]
- Enrique Vidal, Franck Thollard, Colin de la Higuera, Francisco Casacuberta and Rafael C. Carrasco, "Probabilistic Finite-State Machines", Parts I,
IEEE Transactions on Pattern Analysis and Machine Intelligence
**27**(2005): 1013--1025 and II, IEEE Transactions on Pattern Analysis and Machine Intelligence**27**(2005): 1026--1039

- Modesty forbids me to recommend:
- CRS, Almost None of the Theory of Stochastic Processes

- To read, teaching:
- S. R. Adke and and S. M. Manjunath, An Introduction to Finite Markov Processes [Continuous-time finite-state processes, and their likelihood-based inference]
- J. R. Norris, Markov Chains

- To read, learning, variants on Markov processes over time:
- Vlad Stefan Barbu and Nikolaos Limnios, Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications
- Jacques Janssen and Raimondo Manca, Applied Semi-Markov Processes [Blurb]

- To read, multiple interacting Markov chains:
- Albert Benveniste, Eric Fabre and Stefan Haar, "Markov
Nets: Probabilistic Models for Distributed and Concurrent Systems",
IEEE Transactions on
Automatic Control
**48**(2003): 1936--1950 - Holger Hermanns, Interactive Markov Chains [Markov models for distributed system analysis and design]
- Jane Hillston, A Compositional Approach to Performance Modelling [blurb]

- To read, learning, Markov random fields and co.:
- Ruslan K. Chornei, Hans Daduna, and Pavel S. Knopov, "Controlled
Markov Fields with Finite State Space on
Graphs", Stochastic
Models
**21**(2005): 847--874 - M. Cassandro, A. Galves and E. Löcherbach, "Partially Observed Markov Random Fields Are Variable Neighborhood Random Fields", Journal of Statistical Physics
**147**(2012): 795--807, arxiv:1111.1177 - B. M. Gurevich and A. A. Tempelman, "Markov approximation of
homogeneous lattice random fields", Probability Theory and
Related Fields
**131**(2005): 519--527 - M. B. Hastings, "Locality in Quantum and Markov Dynamics on
Lattices and Networks", Physical Review
Letters
**93**(2004): 140402 - Yaron Rachlin, Rohit Negi and Pradeep Khosla, "Sensing Capacity for Markov Random Fields", cs.IT/0508054

- To read, learning, Markov processes on index sets other than \( \mathbb{N}^d \), \( \mathbb{Z}^d \) or \( \mathbb{R}^d \):
- Raluca Balan and Gail Ivanoff, "A Markov property for set-indexed
processes", Journal of Theoretical Probability
**15**(2002): 553--588 = math.PR/0412350 - Krzysztof Burdzy, Soumik Pal, "Markov processes on time-like graphs", Annals of Probability
**39**(2011): 1332--1364, arxiv:0912.0328 - Eugen A. Ghenciu, R. Daniel Mauldin, "Conformal Graph Directed Markov Systems", arxiv:0711.1182
- Daniel Mauldin and Mariusz Urbanski, Graph Directed Markov Systems: Geometry and Dynamics of Limit Sets

- To read, learning, meta-stability and long-range dependence:
- Richard G. Clegg and Maurice Dodson, "Markov chain-based method for
generating long-range dependence", Physical Review
E
**72**(2005): 026118 [Sounds like a sofic system to me...] - Mernan Larralde and Frencois Leyvraz, "Metastability for Markov
Processes with Detailed Balance", PRL
**94**(2005): 160201 - Francois Leyvraz, Hernan Larralde, and David P. Sanders, "A Definition of Metastability for Markov Processes with Detailed Balance", cond-mat/0509754
- Andrew J. Majda, Christian L. Franzke, Alexander Fischer and Daniel
T. Crommelin, "Distinct metastable atmospheric regimes despite nearly Gaussian
statistics: A paradigm
model", Proceedings
of the National Academy of Sciences (USA)
**103**(2006): 8309--8314 [An HMM for low-frequency modes in the atmosphere] - Salvatore Miccichè, "Modeling long-range
memory with stationary Markovian processes", Physical Review
E
**79**(2009): 031116, arxiv:0806.0722

- To read, learning, Markovian representations of non-Markov processes:
- A. Baule and R. Friedrich, "Joint probability distributions
for a class of non-Markovian processes", Physical Review E
**71**(2005): 026101 [From the abstract: "We consider joint probability distributions for the class of coupled Langevin equations introduced by Fogedby.... We generalize well-known results for the single-time probability distributions to the case of N-time joint probability distributions. ... [T]hese probability distribution functions can be obtained by an integral transform from distributions of a Markovian process. The integral kernel obeys a partial differential equation with fractional time derivatives reflecting the non-Markovian character of the process."] - M. Fabrizio, C. Giorgi and V. Pata, "A New Approach to Equations with Memory", arxiv:0901.4063 ["novel approach to the mathematical analysis of equations with memory based on the notion of a state, namely, the initial configuration of the system which can be unambiguously determined by the knowledge of the future dynamics" — which sounds like a Markovian representation result]
- Sandro Gallo, Matthieu Lerasle, Daniel Yasumasa Takahashi, "Upper Bounds for Markov Approximations of Ergodic Processes", arxiv:1107.4353
- Robert L. Grossman and Richard G. Larson, "State Space Realization Theorems For Data Mining", arxiv:0901.2745
- Frank B. Knight, Essays on the Prediction Process [Full text now free online]
- Fabrizio Lillo, Salvatore Miccichè and Rosario N. Mantegna, "Long-range correlated stationary Markovian processes," cond-mat/0203442 [From the abstract, this sounds like they've rediscovered sofic processes.]
- Wolfgang Stadje, "The evolution of aggregated Markov chains",
Statistics and
Probability Letters
**74**(2005): 303--311 ["Given a stationary two-sided Markov chain ... with finite state space ... and a partition ... we consider the aggregated sequence defined by [applying the partition], which is also stationary but in general not Markovian. We present a tractable way to determine the transition probabilities of [the aggregated process], either given a finite part of its past or given its infinite past. These probabilities are linked to the Radon-Nikodym derivative of [the density of an exponentially-decaying sum of aggregated values, conditional on the unaggregated process] with respect to [the unconditional distribution of the exponentially-decaying sum]".]

- To read, learning, making other Markov processes look like random walks:
- Onn Chan and T. K. Lam, "Lifting Markov Chains to Random Walks on
Groups", Combinatorics,
Probability and Computing
**14**(2005): 269--273 - Kouji Yano, Kenji Yasutomi, "Realization of a finite-state stationary Markov chain as a random walk subject to a synchronizing road coloring", arxiv:1006.0534

- To read, learning, mixing / recurrence / hitting / etc. times:
- Frank Aurzada, Hanna Doering, Marcel Ortgiese, Michael Scheutzow, "Moments of recurrence times for Markov chains", arxiv:1104.1884
- Peter G. Doyle, Jean Steiner, "Commuting time geometry of ergodic Markov chains", arxiv:1107.2612
- David A. Levin, Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times

- To read, learning, deviation inequalities, empirical processes, etc.:
- Radoslaw Adamczak, "A tail inequality for suprema of unbounded empirical processes with applications to Markov chains", arxiv:0709.3110
- Dominique Bakry, Patrick Cattiaux, Arnaud Guillin, "Rate of Convergence for ergodic continuous Markov processes: Lyapunov versus Poincare", math.PR/0703355
- Patrick Cattiaux and Arnaud Guillin, "Deviation bounds for additive functionals of Markov process", math.PR/0603021 [Non-asymptotic bounds for the probability that time averages deviate from expectations with respect to the invariant measure, when the process is stationary and ergodic and the invariant measure is reasonably regular.] <
- Vladislav Kargin, "A Large Deviation Inequality for Vector Functions on Finite Reversible Markov Chains", math.PR/0508538
- Carlos A. Leon and Francois Perron, "Optimal Hoeffding bounds for discrete reversible Markov chains", math.PR/0405296
- Pascal Lezaud, "Chernoff-Type Bound for Finite Markov Chains",
The Annals of Applied Probability
**8**(1998): 849--867

- To read, learning, large deviations properties:
- Vivien Lecomte, Cécile Appert-Rolland, and
Frédéric van Wijland
- "Thermodynamic formalism for systems with Markov dynamics", cond-mat/0606211
- "Thermodynamic formalism and large deviation functions in continuous time Markov dynamics", cond-mat/0703435

- J. T. Lewis, C.-E. Pfister and W. G. Sullivan, "Entropy, Concentration of Probability and Conditional Limit Theorems", Markov Processes
and Related Fields
**1**(1995): 319--386 [PDF preprint]

- To read, learning, information-theoretic aspects:
- Armen E. Allahverdyan, "Entropy of Hidden Markov Processes via Cycle Expansion", arxiv:0810.4341
- Ziad Rached, Fady Alajaji and L. Lorne Campbell, "Rényi's
Divergence and Entropy Rates for Finite Alphabet Markov Sources", IEEE Transactions on
Information Theory
**47**(2001): 1553--1561

- To read, learning, Markov models of learning and/or Markovian learning processes:
- Raluca Balan, "Q-Markov random probability measures and their
posterior distributions", Stochastic Processes and Their
Applications
**109**(2004): 295--316 = math.PR/0412349 - Sean Escola, Michael Eisele, Kenneth Miller and Liam
Paninski, "Maximally Reliable Markov Chains Under Energy Constraints",
Neural Computation
**21**(2009): 1863--1912 - Marius Iosifescu and Radu Theodorescu, Random Processes and Learning
- Thomas Wennekers and Nihat Ay, "Finite State Automata Resulting
from Temporal Information Maximization and a Temporal Learning Rule",
Neural
Computation
**17**(2005): 2258--2290

- To read, learning, martingale problems:
- Abhay G. Bhatt, Rajeeva L. Karandikar, B. V. Rao, "On characterisation of Markov processes via martingale problems", math.PR/0607613 [Extending the martingale problem \( \leftrightarrow \) Markov process connection from cadlag processes to ones which are just continuous in probability.]
- Hajo Holzmann, "Martingale approximations for continuous-time and
discrete-time stationary Markov processes", Stochastic Processes
and their Applications
**115**(2005): 1518--1529 [More exactly, martingale approximations to additive functionals of stationary ergodic Markov processes]

- To read, learning, generic / typical / randomly-selected Markov processes;
- Martin Horvat, "The ensemble of random Markov matrices", arxiv:0812.0567
- A. Vershik, "What does a generic Markov operator look like", math.FA/0510320

- To read, learning, analytic aspects of continuous-time Markov processes:
- Vassili N. Kolokoltsov, "Nonlinear Markov Semigroups and
Interacting Lévy Type
Processes", Journal
of Statistical Physics
**126**(2007): 585-642 - Vadim Kostrykin, Jürgen Potthoff, Robert Schrader, "A Note on Feller Semigroups and Resolvents", arxiv:1102.3979

- To read, learning, not otherwise categorized yet:
- Patrice Bertail, Paul Doukhan and Philippe Soulier (eds.), Dependence in Probability and Statistics ["recent developments in the field of probability and statistics for dependent data... from Markov chain theory and weak dependence with an emphasis on some recent developments on dynamical systems, to strong dependence in times series and random fields. ... section on statistical estimation problems and specific applications". Full blurb, contents]
- Giovanni Bussi, Alessandro Laio and Michele Parrinello,
"Equilibrium Free Energies from Nonequilibrium Metadynamics",
Physical Review
Letters
**96**(2006): 090601 ["In this Letter we propose a new formalism to map history-dependent metadynamics in a Markovian process."] - Krzysztof Burdzy, David White, "Markov processes with product-form stationary distribution", arxiv:0711.0493
- Massimo Campanino and Dimitri Petritis, "On the physical relevance of random walks: an example of random walks on a randomly oriented lattice," math.PR/0201130
- Jean-Rene Chazottes, Edgardo Ugalde
- "Projection of Markov Measures May be Gibbsian",
Journal of Statistical Physics
**111**(2003): 1245--1272 - "On the preservation of Gibbsianness under symbol amalgamation", arxiv:0907.0528

- "Projection of Markov Measures May be Gibbsian",
Journal of Statistical Physics
- R. W. R. Darling and J. R. Norris, "Structure of large random
hypergraphs", Annals of Applied
Probability
**15**(2005): 125--152 = math.PR/0503460 - L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, "The compositional construction of Markov processes", arxiv:0901.2434
- Amir Dembo, Jean-Dominique Deuschel, "Markovian perturbation, response and fluctuation dissipation theorem", arxiv:0710.4394
- Gregor Diezemann, "Fluctuation-dissipation relations for Markov
processes", Physical Review
E
**72**(2005): 0111104 - R. Douc, E. Moulines, and Jeffrey S. Rosenthal, "Quantitative
bounds on convergence of time-inhomogeneous Markov chains", Annals of Applied
Probability
**14**(2004): 1643--1665 = math.PR/0403532 - Paul Dupuis and Hui Wang, "Dynamic importance sampling for
uniformly recurrent Markov chains", Annals of Applied
Probability
**15**(2005): 1--38, math.PR/0503454 - E. B. Dynkin
- Markov Processes
- Markov Processes and Related Problems of Analysis: Selected Papers [Blurb. Memo to self, see how many of the papers are already in open-access archives; "Sufficient Statistics and Extreme Points", for instance, certainly is.]

- Wendell H. Fleming and Michel Viot, "Some Measure-Valued Markov Processes in Population Genetics Theory", Indiana University Mathematics Journal
**28**(1979): 817--843 [JSTOR] - Gersende Fort, Sean Meyn, Eric Moulines, and Pierre Priouret, "ODE methods for skip-free Markov chain stability with applications to MCMC", math.PR/0607800
- Katarzyna Horbacz, Jozef Myjak and Tomasz Szarek, "On Stability of
Some General Random Dynamical System", Journal of Statistical
Physics
**119**(2005): 35--60 - Mark Jerrum, "On the approximation of one Markov chain by
another", Probability Theory and
Related Fields
**135**(2006): 1--14 - Sophia L. Kalpazidou, Cycle Representations of Markov Processes
- John G. Kemeny, J. Laurie Snell and Anthony W. Knapp, with David Griffeath, Denumerable Markov Chains
- Stephan Lawi, "A characterization of Markov processes enjoying the time-inversion property", math.PR/0506013
- Christian Leonard, "Stochastic derivatives and generalized h-transforms of Markov processes", arxiv:1102.3172
- Thomas M. Liggett, Continuous Time Markov Processes: An Introduction [Including a chapter on interacting particle systems, Liggett's particular specialty.]
- David Link, "Chains to the West: Markov's Theory of Connected
Events and Its Transmission to Western
Europe", Science in
Context
**19**(2007): 561--589 [Apparently accompanied by translations of two papers by Markov] - Michael B. Marcus and Jay Rosen, Markov Processes, Gaussian Processes, and Local Times
- Donald E. K. Martin, "A recursive algorithm for computing the
distribution of the number of successes in higher-order Markovian
trials", Computational
Statistics and Data Analysis
**50**(2005): 604--610 - Sean P. Meyn and Richard L. Tweedie, Markov Chains and Stochastic Stability [Full text free online, courtesy of Prof. Meyn.]
- Jan Nauddts and Erik Van der Straeten, "Transition records of
stationary Markov
chains", Physical Review
E
**74**(2006): 040103, cond-mat/0607485 - Fabien Panloup and Gilles Pages, "Approximation of the distribution of a stationary Markov process with application to option pricing",
arxiv:0704.0335 [The goal here is
to approximate the
*process*distribution from an increasingly fine sequence of discrete-time simulations.] - Andrea Puglisi, Lamberto Rondoni and Angelo Vulpiani, "Relevance of initial and final conditions for the Fluctuation Relation in Markov processes",cond-mat/0606526
- Murray Rosenblatt, Markov Processes: Structure and Asymptotic Behavior
- William J. Stewart, Introduction to the Numerical Solution of Markov Chains
- R. L. Stratonovich, Conditional Markov Processes and Their Application to the Theory of Optimal Control
- Stroock
- An Introduction to Markov Processes
- Markov Processes from K. Ito's Perspective

- Amanda G. Turner, "Convergence of Markov processes near saddle fixed points", math.PR/0412051