## Markov Models

*10 Dec 2018 20:32*

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 models;
statistical inference for 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; 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 (more general):
- 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 (more specialized):
- M. Abel, K. H. Andersen and G. Lacorata, "Hierarchical Markovian modeling of multi-time scale systems", nlin.CD/0201027
- 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] - 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
- 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] - Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence [comments]
- 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.] - 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.]
- Alex Heller, "On Stochastic processes Derived from Markov
Chains", Annals
of Mathematical Statistics
**36**(1965): 1286--1291 - Martin Nilsson Jacobi, Olof Goernerup, "A dual eigenvector condition for strong lumpability of Markov chains", arxiv:0710.1986
- 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]
- 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
- 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
- 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] - 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.]
- L. C. G. Rogers and D. Williams, Diffusions, Markov Processes and Martingales [comments]
- 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.] - 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

- 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:
- Radoslaw Adamczak, "A tail inequality for suprema of unbounded empirical processes with applications to Markov chains", arxiv:0709.3110
- Armen E. Allahverdyan, "Entropy of Hidden Markov Processes via Cycle Expansion", arxiv:0810.4341
- Frank Aurzada, Hanna Doering, Marcel Ortgiese, Michael Scheutzow, "Moments of recurrence times for Markov chains", arxiv:1104.1884
- Dominique Bakry, Patrick Cattiaux, Arnaud Guillin, "Rate of Convergence for ergodic continuous Markov processes: Lyapunov versus Poincare", math.PR/0703355
- Raluca Balan, "Q-Markov random probability measures and their
posterior distributions", Stochastic Processes and Their
Applications
**109**(2004): 295--316 = math.PR/0412349 - Raluca Balan and Gail Ivanoff, "A Markov property for set-indexed
processes", Journal of Theoretical Probability
**15**(2002): 553--588 = math.PR/0412350 - Vlad Stefan Barbu and Nikolaos Limnios, Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications
- 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."] - 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 - 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]
- Abhay G. Bhatt, Rajeeva L. Karandikar, B. V. Rao, "On characterisation of Markov processes via martingale problems", math.PR/0607613 [Extending the martingale problem <-> Markov process connection from cadlag processes to ones which are just continuous in probability.]
- 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, Soumik Pal, "Markov processes on time-like graphs", Annals of Probability
**39**(2011): 1332--1364, arxiv:0912.0328 - 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
- 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 - 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.]
- Onn Chan and T. K. Lam, "Lifting Markov Chains to Random Walks on
Groups", Combinatorics,
Probability and Computing
**14**(2005): 269--273 - 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
- Ruslan K. Chornei, Hans Daduna, and Pavel S. Knopov, "Controlled
Markov Fields with Finite State Space on
Graphs", Stochastic
Models
**21**(2005): 847--874 [PS.gz preprint] - 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...] - 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 - Peter G. Doyle, Jean Steiner, "Commuting time geometry of ergodic Markov chains", arxiv:1107.2612
- 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.]

- Sean Escola, Michael Eisele, Kenneth Miller and Liam
Paninski, "Maximally Reliable Markov Chains Under Energy Constraints",
Neural Computation
**21**(2009): 1863--1912 - M. Fabrizio, C. Giorgi and V. Pata, "A New Approach to Equatios 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]
- 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
- Sandro Gallo, Matthieu Lerasle, Daniel Yasumasa Takahashi, "Upper Bounds for Markov Approximations of Ergodic Processes", arxiv:1107.4353
- Eugen A. Ghenciu, R. Daniel Mauldin, "Conformal Graph Directed Markov Systems", arxiv:0711.1182
- Beniamin Goldys and Bohdan Maslowski, "The Ornstein Uhlenbeck Bridge and Applications to Markov Semigroups", math.PR/0610386 ["For an arbitrary Hilbert space-valued Ornstein-Uhlenbeck process we construct the Ornstein-Uhlenbeck Bridge connecting a starting point $x$ and an endpoint $y$ that belongs to a certain linear subspace of full measure. We derive also a stochastic evolution equation satisfied by the OU Bridge and study its basic properties. The OU Bridge is then used to investigate the Markov transition semigroup associated to a nonlinear stochastic evolution equation with additive noise."]
- Robert L. Grossman and Richard G. Larson, "State Space Realization Theorems For Data Mining", arxiv:0901.2745
- 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 - Holger Hermanns, Interactive Markov Chains [Markov models for distributed system analysis and design]
- Jane Hillston, A Compositional Approach to Performance Modelling [blurb]
- 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] - Katarzyna Horbacz, Jozef Myjak and Tomasz Szarek, "On Stability of
Some General Random Dynamical System", Journal of Statistical
Physics
**119**(2005): 35--60 - Martin Horvat, "The ensemble of random Markov matrices", arxiv:0812.0567
- Marius Iosifescu and Radu Theodorescu, Random Processes and Learning
- Jacques Janssen and Raimondo Manca, Applied Semi-Markov Processes [Blurb]
- 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
- Vladislav Kargin, "A Large Deviation Inequality for Vector Functions on Finite Reversible Markov Chains", math.PR/0508538
- John G. Kemeny, J. Laurie Snell and Anthony W. Knapp, with David Griffeath, Denumerable Markov Chains
- Frank B. Knight, Essays on the Prediction Process [Full text now free online]
- 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
- Mernan Larralde and Frencois Leyvraz, "Metastability for Markov
Processes with Detailed Balance", PRL
**94**(2005): 160201 - Stephan Lawi, "A characterization of Markov processes enjoying the time-inversion property", math.PR/0506013
- 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

- Carlos A. Leon and Francois Perron, "Optimal Hoeffding bounds for discrete reversible Markov chains", math.PR/0405296
- Christian Leonard, "Stochastic derivatives and generalized h-transforms of Markov processes", arxiv:1102.3172
- David A. Levin, Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times
- Pascal Lezaud, "Chernoff-Type Bound for Finite Markov Chains",
The Annals of Applied Probability
**8**(1998): 849--867 - 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 [Abstract here. How can our library NOT subscribe to Markov Processes and Related Fields?!?] - Francois Leyvraz, Hernan Larralde, and David P. Sanders, "A Definition of Metastability for Markov Processes with Detailed Balance", cond-mat/0509754
- Thomas M. Liggett, Continuous Time Markov Processes: An Introduction [Including a chapter on interacting particle systems, Liggett's particular specialty.]
- 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.]
- 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] - 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] - 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 - Daniel Mauldin and Mariusz Urbanski, Graph Directed Markov Systems: Geometry and Dynamics of Limit Sets
- Sean P. Meyn and Richard L. Tweedie, Markov Chains and Stochastic Stability [Full text free online, courtesy of Prof. Meyn.]
- Salvatore Miccichè, "Modeling long-range
memory with stationary Markovian processes", Physical Review
E
**79**(2009): 031116, arxiv:0806.0722 - 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
- 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 - Yaron Rachlin, Rohit Negi and Pradeep Khosla, "Sensing Capacity for Markov Random Fields", cs.IT/0508054
- Murray Rosenblatt, Markov Processes: Structure and Asymptotic Behavior
- 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]".] - 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
- A. Vershik, "What does a generic Markov operator look like", math.FA/0510320 ["We consider generic i.e., forming an everywhere dense massive subset classes of Markov operators in the space $L^2(X,\mu)$ with a finite continuous measure. Since there is a canonical correspondence that associates with each Markov operator a multivalued measure-preserving transformation (i.e., a polymorphism), as well as a stationary Markov chain, we can also speak about generic polymorphisms and generic Markov chains. The most important and inexpected generic properties of Markov operators (or Markov chains or polymorphisms) is nonmixing and totally nondeterministicity."]
- Thomas Wennekers and Nihat Ay, "Finite State Automata Resulting
from Temporal Information Maximization and a Temporal Learning Rule",
Neural
Computation
**17**(2005): 2258--2290 - 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