搜索结果：Markov

We develop a generalized Markov theory for the Markov--Lagrange and Markov spectra. The classical discrete Markov spectrum is governed by Markov numbers, the positive integers occurring in solutions of the Markov equation. We show that this relation admits a cluster-combinatorial extension governed by generalized Markov numbers. Replacing the Christoffel-word formalism by snake graphs, we construct generalized discrete Markov spectra attached to the generalized Markov equations \[ x^2+y^2+z^2+k_1yz+k_2zx+k_3xy=(3+k_1+k_2+k_3)xyz. \] Every element of these spectra is realized simultaneously as a Lagrange constant of a quadratic irrational and as a Markov constant of a real indefinite binary quadratic form. We also prove structural results for these spectra, determine their contribution in the transition interval below Freiman's constant, and identify the boundary value obtained from regular lines of irrational slope, again realizing it both as a Lagrange constant and as a Markov constant.

We propose a structural vector autoregressive model with a new and flexible specification of the volatility process which we call Sparse Heterogeneous Markov-Switching Heteroskedasticity. In this model, the conditional variance of each structural shock changes in time according to its own Markov process. Additionally, it features a sparse representation of Markov processes, in which the number of regimes is set to exceed that of the data-generating process, with some regimes allowed to have zero occurrences throughout the sample. We complement these developments with a definition of a new distribution for normalised conditional variances that facilitates Gibbs sampling and identification verification. In effect, our model: (i) normalises the system and estimates the structural parameters more precisely than popular alternatives; (ii) can be used to verify homoskedasticity reliably and, thus, inform identification through heteroskedasticity; and (iii) features excellent forecasting performance comparable with Stochastic Volatility. Finally, revisiting a prominent macro-financial structural system, we provide evidence for the identification of the US monetary policy shock via heteros

Partial Markov categories are a recent framework for categorical probability theory that provide an abstract account of partial probabilistic computation with updating semantics. In this article, we discuss two order relations on the morphisms of a partial Markov category. In particular, we prove that every partial Markov category is canonically preorder-enriched, recovering several well-known order enrichments. We also demonstrate that the existence of codiagonal maps (comparators) is closely related to order properties of partial Markov categories. Finally, we introduce a synthetic version of the Cauchy--Schwarz inequality and, from it, we prove that updating increases validity.

Attention-based transformers have achieved tremendous success across a variety of disciplines including natural languages. To deepen our understanding of their sequential modeling capabilities, there is a growing interest in using Markov input processes to study them. A key finding is that when trained on first-order Markov chains, transformers with two or more layers consistently develop an induction head mechanism to estimate the in-context bigram conditional distribution. In contrast, single-layer transformers, unable to form an induction head, directly learn the Markov kernel but often face a surprising challenge: they become trapped in local minima representing the unigram distribution, whereas deeper models reliably converge to the ground-truth bigram. While single-layer transformers can theoretically model first-order Markov chains, their empirical failure to learn this simple kernel in practice remains a curious phenomenon. To explain this contrasting behavior of single-layer models, in this paper we introduce a new framework for a principled analysis of transformers via Markov chains. Leveraging our framework, we theoretically characterize the loss landscape of single-laye

We introduce partial Markov categories as a synthetic framework for synthetic probabilistic inference, blending the work of Cho and Jacobs, Fritz, and Golubtsov on Markov categories with the work of Cockett and Lack on cartesian restriction categories. We describe observations, Bayes' theorem, normalisation, and both Pearl's and Jeffrey's updates in purely categorical terms.

In this paper, we study positive integer solutions to a generalized form of the Markov equation, given as $x^2 + y^2 + z^2 + k(yz + zx + xy) = (3 + 3k)xyz$. This equation extends the classical Markov equation $x^2 + y^2 + z^2 = 3xyz$. We generalize the concept of Cohn triples for the classical Markov equation to the generalized Markov equations. Using this, we provide a generalization of the uniqueness theorem of Markov numbers that are prime powers.

We formally introduce and study locally-balanced Markov jump processes (LBMJPs) defined on a general state space. These continuous-time stochastic processes with a user-specified limiting distribution are designed for sampling in settings involving discrete parameters and/or non-smooth distributions, addressing limitations of other processes such as the overdamped Langevin diffusion. The paper establishes the well-posedness, non-explosivity, and ergodicity of LBMJPs under mild conditions. We further explore regularity properties such as the Feller property and characterise the weak generator of the process. We then derive conditions for exponential ergodicity via spectral gaps and establish comparison theorems for different balancing functions. In particular we show an equivalence between the spectral gaps of Metropolis--Hastings algorithms and LBMJPs with bounded balancing function, but show that LBMJPs can exhibit uniform ergodicity on unbounded state spaces when the balancing function is unbounded, even when the limiting distribution is not sub-Gaussian. We also establish a diffusion limit for an LBMJP in the small jump limit, and discuss applications to Monte Carlo sampling and

Rowmotion is a certain well-studied bijective operator on the distributive lattice $J(P)$ of order ideals of a finite poset $P$. We introduce the rowmotion Markov chain ${\bf M}_{J(P)}$ by assigning a probability $p_x$ to each $x\in P$ and using these probabilities to insert randomness into the original definition of rowmotion. More generally, we introduce a very broad family of toggle Markov chains inspired by Striker's notion of generalized toggling. We characterize when toggle Markov chains are irreducible, and we show that each toggle Markov chain has a remarkably simple stationary distribution. We also provide a second generalization of rowmotion Markov chains to the context of semidistrim lattices. Given a semidistrim lattice $L$, we assign a probability $p_j$ to each join-irreducible element $j$ of $L$ and use these probabilities to construct a rowmotion Markov chain ${\bf M}_L$. Under the assumption that each probability $p_j$ is strictly between $0$ and $1$, we prove that ${\bf M}_{L}$ is irreducible. We also compute the stationary distribution of the rowmotion Markov chain of a lattice obtained by adding a minimal element and a maximal element to a disjoint union of two c

Traditional hidden Markov models have been a useful tool to understand and model stochastic dynamic data; in the case of non-Gaussian data, models such as mixture of Gaussian hidden Markov models can be used. However, these suffer from the computation of precision matrices and have a lot of unnecessary parameters. As a consequence, such models often perform better when it is assumed that all variables are independent, a hypothesis that may be unrealistic. Hidden Markov models based on kernel density estimation are also capable of modeling non-Gaussian data, but they assume independence between variables. In this article, we introduce a new hidden Markov model based on kernel density estimation, which is capable of capturing kernel dependencies using context-specific Bayesian networks. The proposed model is described, together with a learning algorithm based on the expectation-maximization algorithm. Additionally, the model is compared to related HMMs on synthetic and real data. From the results, the benefits in likelihood and classification accuracy from the proposed model are quantified and analyzed.

We present a method to sample Markov-chain trajectories constrained to both the initial and final conditions, which we term Markov bridges. The trajectories are conditioned to end in a specific state at a given time. We derive the master equation for Markov bridges, which exhibits the original transition rates scaled by a time-dependent factor. Trajectories can then be generated using a refined version of the Gillespie algorithm. We illustrate the benefits of our method by sampling trajectories in the Müller-Brown potential. This allows us to generate transition paths which would otherwise be obtained at a high computational cost with standard Kinetic Monte Carlo methods because commitment to a transition path is essentially a rare event. We then apply our method to a single-cell RNA sequencing dataset from mouse pancreatic cells to investigate the cell differentiation pathways of endocrine-cell precursors. By sampling Markov bridges for a specific differentiation pathway we obtain a time-resolved dynamics that can reveal features such as cell types which behave as bottlenecks. The ensemble of trajectories also gives information about the fluctuations around the most likely path. F

In this article we discuss potential Markov partitions for three different Wang tile protosets. The first partition is for the order-24 aperiodic Wang tile protoset that was recently shown in the Ph.D. thesis of H. Jang to encode all tilings by the Penrose rhombs. The second is a partition for an order-16 aperiodic Wang protoset that encodes all tilings by the Ammann A2 aperiodic protoset. The third partition is for an order-11 Wang tile protoset identified by Jeandel and Rao as a candidate order-11 aperiodic Wang tile protoset. The emphasis is on some experimental methodology to generate potential Markov partitions that encode tilings. We also apply some of the theory developed by Labbé in analyzing such an experimentally discovered partition.

We prove that under mild positivity assumptions the entropy rate of a hidden Markov chain varies analytically as a function of the underlying Markov chain parameters. A general principle to determine the domain of analyticity is stated. An example is given to estimate the radius of convergence for the entropy rate. We then show that the positivity assumptions can be relaxed, and examples are given for the relaxed conditions. We study a special class of hidden Markov chains in more detail: binary hidden Markov chains with an unambiguous symbol, and we give necessary and sufficient conditions for analyticity of the entropy rate for this case. Finally, we show that under the positivity assumptions the hidden Markov chain {\em itself} varies analytically, in a strong sense, as a function of the underlying Markov chain parameters.

$M_n(\mathbb{C})$ denotes the set of $n$ by $n$ complex matrices. Consider continuous time quantum semigroups $\mathcal{P}_t= e^{t\, \mathcal{L}}$, $t \geq 0$, where $\mathcal{L}:M_n(\mathbb{C}) \to M_n(\mathbb{C})$ is the infinitesimal generator. If we assume that $\mathcal{L}(I)=0$, we will call $e^{t\, \mathcal{L}}$, $t \geq 0$ a quantum Markov semigroup. Given a stationary density matrix $ρ= ρ_{\mathcal{L}}$, for the quantum Markov semigroup $\mathcal{P}_t$, $t \geq 0$, we can define a continuous time stationary quantum Markov process, denoted by $X_t$, $t \geq 0.$ Given an {\it a priori} Laplacian operator $\mathcal{L}_0:M_n(\mathbb{C}) \to M_n(\mathbb{C})$, we will present a natural concept of entropy for a class of density matrices on $M_n(\mathbb{C})$. Given an Hermitian operator $A:\mathbb{C}^n\to \mathbb{C}^n$ (which plays the role of an Hamiltonian), we will study a version of the variational principle of pressure for $A$. A density matrix $ρ_A$ maximizing pressure will be called an equilibrium density matrix. From $ρ_A$ we will derive a new infinitesimal generator $\mathcal{L}_A$. Finally, the continuous time quantum Markov process defined by the semigroup $\mathcal{P}_

Perturbation analysis of Markov chains provides bounds on the effect that a change in a Markov transition matrix has on the corresponding stationary distribution. This paper compares and analyzes bounds found in the literature for finite and denumerable Markov chains and introduces new bounds based on series expansions. We discuss a series of examples to illustrate the applicability and numerical efficiency of the various bounds. Specifically, we address the question on how the bounds developed for finite Markov chains behave as the size of the system grows. In addition, we provide for the first time an analysis of the relative error of these bounds. For the case of a scaled perturbation we show that perturbation bounds can be used to analyze stability of a stable Markov chain with respect to perturbation with an unstable chain.

Let $(X_n)_{n \ge 0}$ be an irreducible, aperiodic, homogeneous Markov chain, with state space a totally ordered finite alphabet of size $m$. Using combinatorial constructions and weak invariance principles, we obtain the limiting shape of the associated RSK Young diagrams as a multidimensional Brownian functional. Since the length of the top row of the Young diagrams is also the length of the longest weakly increasing subsequences of $(X_k)_{1\le k \le n}$, the corresponding limiting law follows. We relate our results to a conjecture of Kuperberg by providing, under a cyclic condition, a spectral characterization of the Markov transition matrix precisely characterizing when the limiting shape is the spectrum of the $m \times m$ traceless GUE. For each $m \ge 4$, this characterization identifies a proper, non-trivial class of cyclic transition matrices producing such a limiting shape. However, for $m=3$, all cyclic Markov chains have such a limiting shape, a fact previously only known for $m=2$. For $m$ arbitrary, we also study reversible Markov chains and obtain a characterization of symmetric Markov chains for which the limiting shape is the spectrum of the traceless GUE. To fini

Markov switching models are a popular family of models that introduces time-variation in the parameters in the form of their state- or regime-specific values. Importantly, this time-variation is governed by a discrete-valued latent stochastic process with limited memory. More specifically, the current value of the state indicator is determined only by the value of the state indicator from the previous period, thus the Markov property, and the transition matrix. The latter characterizes the properties of the Markov process by determining with what probability each of the states can be visited next period, given the state in the current period. This setup decides on the two main advantages of the Markov switching models. Namely, the estimation of the probability of state occurrences in each of the sample periods by using filtering and smoothing methods and the estimation of the state-specific parameters. These two features open the possibility for improved interpretations of the parameters associated with specific regimes combined with the corresponding regime probabilities, as well as for improved forecasting performance based on persistent regimes and parameters characterizing them

This review paper provides an introduction of Markov chains and their convergence rates which is an important and interesting mathematical topic which also has important applications for very widely used Markov chain Monte Carlo (MCMC) algorithm. We first discuss eigenvalue analysis for Markov chains on finite state spaces. Then, using the coupling construction, we prove two quantitative bounds based on minorization condition and drift conditions, and provide descriptive and intuitive examples to showcase how these theorems can be implemented in practice. This paper is meant to provide a general overview of the subject and spark interest in new Markov chain research areas.

In this article, we use the theory of quantum channels and open quantum systems to provide an efficient unitary characterization of a class of stochastic generators known as quantum hidden Markov models (QHMMs). By utilizing the unitary characterization, we demonstrate that any QHMM can be implemented as a quantum circuit with mid-circuit measurement. We prove that QHMMs are more compact and more expressive definitions of stochastic process languages compared to the equivalent classical hidden Markov models (HMMs). Starting with the formulation of QHMMs as quantum channels, we employ Stinespring's construction to represent these models as unitary quantum circuits with mid-circuit measurement. By utilizing the unitary parameterization of QHMMs, we define a formal QHMM learning model. The model formalizes the empirical distributions of target stochastic process languages, defines hypothesis space of quantum circuits, and introduces an empirical stochastic divergence measure - hypothesis fitness - as a success criterion for learning. We demonstrate that the learning model has a smooth search landscape due to the continuity of Stinespring's dilation. The smooth mapping between the hypo

We study the following learning problem with dependent data: Observing a trajectory of length $n$ from a stationary Markov chain with $k$ states, the goal is to predict the next state. For $3 \leq k \leq O(\sqrt{n})$, using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be $Θ(\frac{k^2}{n}\log \frac{n}{k^2})$, in contrast to the optimal rate of $Θ(\frac{\log \log n}{n})$ for $k=2$ previously shown in Falahatgar et al. (2016). These rates, slower than the parametric rate of $O(\frac{k^2}{n})$, can be attributed to the memory in the data, as the spectral gap of the Markov chain can be arbitrarily small. To quantify the memory effect, we study irreducible reversible chains with a prescribed spectral gap. In addition to characterizing the optimal prediction risk for two states, we show that, as long as the spectral gap is not excessively small, the prediction risk in the Markov model is $O(\frac{k^2}{n})$, which coincides with that of an iid model with the same number of parameters. Extensions to higher-order Markov chains are also obtained.

A fundamental assumption of reinforcement learning in Markov decision processes (MDPs) is that the relevant decision process is, in fact, Markov. However, when MDPs have rich observations, agents typically learn by way of an abstract state representation, and such representations are not guaranteed to preserve the Markov property. We introduce a novel set of conditions and prove that they are sufficient for learning a Markov abstract state representation. We then describe a practical training procedure that combines inverse model estimation and temporal contrastive learning to learn an abstraction that approximately satisfies these conditions. Our novel training objective is compatible with both online and offline training: it does not require a reward signal, but agents can capitalize on reward information when available. We empirically evaluate our approach on a visual gridworld domain and a set of continuous control benchmarks. Our approach learns representations that capture the underlying structure of the domain and lead to improved sample efficiency over state-of-the-art deep reinforcement learning with visual features -- often matching or exceeding the performance achieved w