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]

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
• 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
• 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