Markov Models

16 Dec 2008 12:20

---

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. 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.)

See also: ergodic theory of Markov and related processes; filtering and state estimation; interacting particle systems; inference for Markov and hidden Markov models; Monte Carlo; stochastic differential equations

Recommended (more general):
• Pierre Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
• J. Doob, Stochastic Processes
• Andrew M. Fraser, Hidden Markov Models and Dynamical Systems
• 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.]
• Lawrence R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition", Proceedings of the IEEE 77 (1989): 257--286

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.]
• M. J. Beal, Z. Ghahramani and C. E. Rasmussen, "The Infinite Hidden Markov Model", in NIPS 14 [link]
• Patrick Billingsley, Statistical Inference for Markov Chains
• Robert J. Elliott, Lakhdar Aggoun and John B. Moore, Hidden Markov Models: Estimation and Control
• Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence [OK, I haven't read all of this...]
• Ghahramani and Jordan, "Factorial Hidden Markov Models," Machine Learning 29 (1997): 245--273
• Olof Gonerup and Martin Nilsson Jacobi, "A method for inferring hierarchical dynamics in stochastic processes", 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.]
• Seyoung Kim and Padhraic Smyth, "Segmental Hidden Markov Models with Random Effects for Waveform Modeling", Journal of Machine Learning Research 7 (2006): 945--969
• 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
• Vivien Lecomte, Cecile Appert-Rolland and Frederic van Wijland, "Chaotic properties of systems with Markov dynamics", cond-mat/0505483 = Physical Review Letters 95 (2005): 010601 [Showing that the thermodynamic formalism can work for continuous-time Markov processes, which is very nice]
• Jie Li, Jiaxin Wang, Yannan Zhao and Zehong Yang, "Self-adaptive design of hidden Markov models,", Pattern Recognition Letters 25 (2004): 197--210 [A penalized maximum-likelihood approach to selecting the right number of states and, potentially, architecture for HMMs. The penalization scheme is based on various entropies associated with the HMM; it's hard to give these as straight-forward an information-theoretic interpretation as one would like --- it definitely does not seem to be a description length.]
• 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
• 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
• Olivier Aycard, Jean-Francois Mari and Richard Washington, "Learning to automatically detect features for mobile robots using second-order Hidden Markov Models", cs.AI/0501068
• 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
• 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."]
• 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
• 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
• 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 ["The theme of this paper is the derivation of analytical formulae for certain large combinatorial structures. The formulae are obtained via fluid limits of pure jump-type Markov processes..."]
• 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
• P. Dupont, F. Denis and Y. Esposito, "Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms", Pattern Recognition 38 (2005): 1349--1371
• Paul Dupuis and Hui Wang, "Dynamic importance sampling for uniformly recurrent markov chains", Annals of Applied Probability 15 (2005): 1--38 = math.PR/0503454 [Promises interesting large deviations techniques in the abstract]
• E. B. Dynkin, Markov Processes
• Gersende Fort, Sean Meyn, Eric Moulines, and Pierre Priouret, "ODE methods for skip-free Markov chain stability with applications to MCMC", math.PR/0607800
• Halina Frydman and Peter Lakner, "Maximum likelihood estimation of hidden Markov processes", Annals of Applied Probability 13 (2003): 1296--1312
• 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."]
• B. M. Gurevich and A. A. Tempelman, "Markov approximation of homogeneous lattice random fields", Probability Theory and Related Fields 131 (2005): 519--527
• Guangyue Han and Brian Marcus, "Analyticity of Entropy Rate in Families of Hidden Markov Chains", math.PR/0507235
• 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]
• D. Hernando, V. Crespi and G. Cybenko, "Efficient Computation of the Hidden Markov Model Entropy for a Given Observation Sequence", IEEE Transactions on Information Theory 51 (2005): 2681--2685 [By "hidden Markov model entropy" they mean the Shannon entropy of the set of hidden-state trajectories compatible with the observation sequence. This has certain connections to the Lloyd-Pagels "thermodynamic depth" complexity measure...]
• 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 ["We consider a new random dynamical system which generalizes Markov processes corresponding to iterated function systems and Poisson driven stochastic differential equations. It can be used as a description of many physical and biological phenomena. Under the suitable assumption will be proved its stability."]
• Masashi Inoue and Naonori Ueda, "Exploitation of Unlabeled Sequences in Hidden Markov Models", IEEE Transactions on Pattern Analysis and Machine Intelligence 25 (2003): 1570--1581
• 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
• Andrew Kempe, "Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers", cmp-lg/9802001
• Vassili N. Kolokoltsov, "Nonlinear Markov Semigroups and Interacting Lévy Type Processes", Journal of Statistical Physics 126 (2007): 585-642
• Hans R. Künsch, "State Space and Hidden Markov Models", pp. 109--173 in Ole E. Barndorff-Nielsen, David R. Cox and Claudia Klüppelberg (eds.), Complex Stochastic Systems
• 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
• Pascal Lezaud, "Chernoff-Type Bound for Finite Markov Chains", The Annals of Applied Probability 8 (1998): 849--867 [JSTOR]
• 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
• Yujian Li, "Hidden Markov models with states depending on observations", Pattern Recognition Letters 26 (2005): 977--984 [From the abstract, this sounds like a rediscovery of stochastic finite automata.]
• 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 & 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.]
• Jan Nauddts and Erik Van der Straeten, "Transition records of stationary Markov chains", cond-mat/0607485 = Physical Review E 74 (2006): 040103
• P. Ney and Esa Nummelin, "Regeneration for infinite memory chains", Probability Theory and Related Fields 96 (1994): 503--520 [Predates the on-line archive for the journal, so I need to actually go to the library]
• 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
• Mohammad Rezaeian, "Hidden Markov Process: A New Representation, Entropy Rate and Estimation Entropy", cs.IT/0606114
• Murray Rosenblatt, Markov Processes: Structure and Asymptotic Behavior ("Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, Band 184")
• Sajid Siddiqi and Andrew Moore, "Fast Inference and Learning in Large-State-Space HMMs", ICML 2005 [Abstract, PDF]
• Padhraic Smyth, "Belief networks, hidden Markov models, and Markov random fields: a unifying view", Pattern Recognition Letters 18 (1997): 1261--1268 [PDF preprint]
• Padhraic Smyth, David Heckerman and Michael I. Jordan, "Probabilistic Independence Networks for Hidden Markov Probability Models", Neural Computation 9 (1997): 227--269 [PDF preprint. Reprinted in Jordan and Sejnowski (eds.), Graphical Models, pp. 1--44]
• 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
• Vladislav B. Tadic and Arnaud Doucet, "Exponential forgetting and geometric ergodicity for optimal filtering in general state-space models", Stochastic Processes and their Applications 115 (2005): 1408--1436
• 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
• L. Xie, V. A. Ugrinovskii and I. R. Petersen, "Probabilistic Distances Between Finite-State Finite-Alphabet Hidden Markov Models", IEEE Transactions on Automatic Control 50 (2005): 505--511
• G. G. Yin and V. Kirshnamurthy, "LMS Algorithms for Tracking Slow Markov Chains With Applications to Hidden Markov Estimation and Adaptive Multiuser Detection", IEEE Transactions on Information Theory 51 (2005): 2475--2490
• Xiaoxi Zhang, Timothy D. Johnson, Roderick J. A. Little, Yue Cao, "Quantitative magnetic resonance image analysis via the EM algorithm with stochastic variation", Annals of Applied Statistics 2 (2008): 736--755 = arxiv:0807.4672
• Or Zuk, Eytan Domany, Ido Kanter, Michael Aizenman
  • "Taylor series expansions for the entropy rate of Hidden Markov Processes", cs.IT/0510005
  • "From finite-system entropy to entropy rate for a Hidden Markov Process", cs.IT/0510016