Markov Models

22 Aug 2019 13:27

---

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