More Like this

1. Max Markov Chain

   https://doi.org/10.24963/ijcai.2023/639  

   Zhang, Yu; Bucklew, Mitchell (August 2023, International Joint Conferences on Artificial Intelligence Organization)

   In this paper, we introduce Max Markov Chain (MMC), a novel model for sequential data with sparse correlations among the state variables.It may also be viewed as a special class of approximate models for High-order Markov Chains (HMCs).MMC is desirable for domains where the sparse correlations are long-term and vary in their temporal stretches.Although generally intractable, parameter optimization for MMC can be solved analytically.However, based on this result,we derive an approximate solution that is highly efficient empirically.When compared with HMC and approximate HMC models, MMCcombines better sample efficiency, model parsimony, and an outstanding computational advantage.Such a quality allows MMC to scale to large domainswhere the competing models would struggle to perform.We compare MMC with several baselines with synthetic and real-world datasets to demonstrate MMC as a valuable alternative for stochastic modeling. 

   more » « less
2. Markov genealogy processes

   https://doi.org/10.1016/j.tpb.2021.11.003  

   King, Aaron A.; Lin, Qianying; Ionides, Edward L. (February 2022, Theoretical Population Biology)
3. Virtual Markov Chains

   https://doi.org/10.53733/147  

   Evans, Steven; Jaffe, Adam (September 2021, New Zealand Journal of Mathematics)

   We introduce the space of virtual Markov chains (VMCs) as a projective limit of the spaces of all finite state space Markov chains (MCs), in the same way that the space of virtual permutations is the projective limit of the spaces of all permutations of finite sets.We introduce the notions of virtual initial distribution (VID) and a virtual transition matrix (VTM), and we show that the law of any VMC is uniquely characterized by a pair of a VID and VTM which have to satisfy a certain compatibility condition.Lastly, we study various properties of compact convex sets associated to the theory of VMCs, including that the Birkhoff-von Neumann theorem fails in the virtual setting. 

   more » « less
4. Tensor product Markov chains

   https://doi.org/10.1016/j.jalgebra.2019.10.038  

   Benkart, Georgia; Diaconis, Persi; Liebeck, Martin W.; Tiep, Pham Huu (November 2020, Journal of Algebra)

   null (Ed.)
5. Double coset Markov chains

   https://doi.org/10.1017/fms.2022.106  

   Diaconis, Persi; Ram, Arun; Simper, Mackenzie (January 2023, Forum of Mathematics, Sigma)

   Abstract Let G be a finite group. Let $H, K$ be subgroups of G and $$H \backslash G / K$$ the double coset space. If Q is a probability on G which is constant on conjugacy classes ( $$Q(s^{-1} t s) = Q(t)$$ ), then the random walk driven by Q on G projects to a Markov chain on $$H \backslash G /K$$ . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $$GL_n(q)$$ onto a Markov chain on $$S_n$$ via the Bruhat decomposition. The chain on $$S_n$$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed. 

   more » « less