Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization
Zheyuan Lai, Michael C.H. Choi · 2025
Read Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization by Zheyuan Lai, Michael C.H. Choi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23340.txt.
Introduction
Zheyuan Lai and Michael Choi tackle how to shrink a multi part Markov chain without losing much information in a 2025 paper. A Markov chain steps between states by fixed odds, and real systems often have many coordinates at once. The team ask which coordinates to keep, or how to group them, so the smaller chain stays faithful. Their yardsticks are information based: entropy rate, distance from factorizing, independence, and steadiness.
Each yardstick turns out to have a submodular shape, positive or negative, which lets greedy algorithms work with proven guarantees. Along the way they generalize a known distorted greedy method. Tests on two classic models, a mixing urn scheme and a magnet model, show the theory and algorithms in action. Code is shared for others to use.
Catalog record
| CREATOR | Zheyuan Lai, Michael C.H. Choi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23340
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization Zheyuan Lai, Michael C.H. Choi Abstract We study the problem of optimally projecting the transition matrix of a finite ergodic multivariate Markov chain onto a lower-dimensional state space, as well as the problem of finding an optimal partition of coordinates such that the factorized Markov chain gives minimal information loss compared to the original multivariate chain. Specifically, we seek to construct a Markov chain that optimizes various information-theoretic criteria under cardinality constraints. These criteria include entropy rate, information-theoretic distance to factorizability, independence, and stationarity. We formulate these tasks as best subset or partition selection problems over multivariate Markov chains and leverage the ( k k -) submodular (or ( k k -) supermodular) structures of the objective functions to develop efficient greedy-based algorithms with theoretical guarantees. Along the way, we introduce a generalized version of the distorted greedy algorithm, which may be of independent interest. Finally, we illustrate the theory and algorithms through extensive numerical experiments with publicly available code on multivariate Markov chains associated with the Bernoulli–Laplace and Curie–Weiss models . Keywords : Markov chains, submodularity, greedy algorithms, Kullback-Leibler divergence AMS 2020 subject classification : 60J10, 60J22, 90C27, 94A15, 94A17 1 Introduction Consider a multivariate ergodic Markov chain with transition matrix P that admits a stationary distribution \pi on a finite product state space \mathcal{X} with d\in\mathbb{N} coordinates. Given a subset S\subseteq\{1,\ldots,d\} , let P^{(S)} denote the projected transition matrix onto S , and let \Pi be the transition matrix where each row is given by \pi . These notations are formally defined in Section 2 and 6 . A number of natural and interesting information-theoretic optimization problems arise in the context of subset selection for multivariate Markov chains. For example, among all subsets S with |S|\leq m , which projected transition matrix P^{(S)} maximizes the entropy rate, thereby identifying the most “random” coordinates? Similarly, which choice of S minimizes the Kullback-Leibler (KL) divergence between P^{(S)} and \Pi^{(S)} , making it closest to stationarity and highlighting subsets nearest to equilibrium? More generally, which choice of partition \mathbf{S} of coordinates approximates a complex transition matrix P by a simpler model that factorizes the groups of coordinates with respect to \mathbf{S} with minimal information losses? These insights have direct applications in Markov chain Monte Carlo (MCMC), where selecting and analyzing optimal subsets or partitions may lead to the design of accelerated MCMC samplers. For example, in Section 8.3 below, we make use of the identified subset from the output of submodular optimization algorithms to propose a heuristics that leads to an improved sampler for the Curie–Weiss model. Model reduction problems for Markov chains have been studied previously using spectral theory [ 3 ] . While such approach is powerful, combinatorial approaches to subset or partition selection in the context of Markov chains remain underexplored, a gap we address in this paper by leveraging submodular optimization. Spectral approaches rely on the knowledge of eigenvalues and eigenvectors of the underlying transition matrices, which might not be tractable especially under high-dimensional settings. On the other hand, the combinatorial approach given in this paper relies on the knowledge of the transition matrix, which is usually known or has a tractable structure in most models of interests. Our work builds on recent efforts, such as [ 2 ] , and adapts a combinatorial lens to develop efficient greedy-based algorithms for finding approximate optimizers. In this work, we are interested in selecting subset or partition of the coordinates of multivariate Markov chains, which is different from aggregating the states of Markov chains in the investigation of lumpability [ 8 ] . Our main contributions are as follows. Throughout, we use several information-theoretic “distance” functionals that compare the original chain to a reference model: distance to stationarity compares a projected Markov chain transition matrix and its projected stationary kernel, distance to independence quantifies how far a multivariate Markov chain is from behaving independently in an information-theoretic sense, and distance to factorizability measures the information loss when approximating a multivariate Markov chain by a model that factorizes according to a coordinate partition. Precise definitions are given in Sections 2 and 6 . • Identification of new submodular functions in Markov chain theory. We show that several natural set functionals arising from the above information-theoretic distances exhibit a diminishing returns (i.e. submodular) or increasing returns (i.e. supermodular) structure: under suitable assumptions, the distance-to-stationarity functional is supermodular , the distance-to-stationarity functional for the complement set is submodular , whereas the distance-to-independence functional for the complement set is submodular . This extends the line of work initiated in [ 2 ] . • Greedy subset/partition selection for Markov chains via submodular optimization. Leveraging the above diminishing returns properties, we adapt existing greedy-style algorithms with theoretical guarantees to approximately optimize these information-theoretic objectives under practical constraints (e.g., a budget on the number of selected coordinates, or a prescribed number of groups in a partition). To the best of our knowledge, this is the first systematic use of greedy submodular optimization for subset/partition selection problems tailored to multivariate Markov chains. • A generalized distorted greedy algorithm for k -submodular maximization under cardinality constraints. We generalize the distorted greedy algorithm of [ 9 ] into k -submodular setting, where the decision variable is a partition of coordinates up to k labeled groups, and we provide theoretical guarantees under cardinality-type constraints. This algorithmic result is of independent interest in k -submodular maximization problems beyond the Markov chain applications considered here. • Numerical validation on structured multivariate Markov chains. We conduct experiments on multivariate Markov chains associated with the Bernoulli–Laplace level model and the Curie–Weiss model, demonstrating that the proposed greedy procedures efficiently identify subsets/partitions that optimizes the targeted information-theoretic criteria. Relation to [ 2 ] . Although [ 2 ] also considers information-theoretic distances to factorizability or independence, in this paper we tackle this and other related problems from a submodular optimization perspective which is fundamentally different. In [ 2 ] , the goal is to construct or approximate a transition matrix that is “closest” to a given multivariate chain under structural constraints (such as factorization). In contrast, in this manuscript we do not modify the original chain P . Instead, we treat P as fixed and perform combinatorial selection over the coordinate set: we choose a subset S\subseteq\{1,\ldots,d\} (or a partition \mathbf{S} ) and evaluate the induced projected (or factorized-by-partition) dynamics. This leads to a different class of problems, that is to optimize information-theoretic criteria over subsets/partitions subject to natural cardinality-type constraints. Examples include selecting coordinates whose projection has large entropy rate, or selecting subsets/partitions whose induced dynamics are closest (in Kullback-Leibler divergence) to stationarity, independence, or factorizability. To the best of our knowledge, this subset/partition-selection formulation and its greedy submodular optimization approach have not been developed in the Markov chain literature. The remainder of this paper is organized as follows. Section 2.1 discusses the information-theoretic properties of multivariate Markov chains. Section 2.2 provides a review of submodularity and k -submodularity and some related examples in Markov chain theory . Section 2.3 introduces the distorted greedy algorithm and presents our generalized version with theoretical guarantees. We then explore optimization problems related to