# Questions tagged [markov-chains]

The markov-chains tag has no usage guidance.

509
questions

1
vote

0
answers

34
views

### Time-inhomogeneous Krylov-Bogoliubov Existence Theorem

I am interested in what is known about the application of the Krylov-Bogoliubov existence theorem to the time-inhomogeneous case, especially as it relates to an underlying random dynamical system (...

3
votes

1
answer

45
views

### Comparison of time until absorption for two absorbing Markov chains

Let $\{X_t, t \geq 0\}$ and $\{X_t', t \geq 0\}$ denote two markov chains on the same state space $\{1, ..., n+1\}$ with transition probability matrices $P$ and $P'$ respectively. Suppose that both ...

-1
votes

0
answers

29
views

### Methods for high-dimensional integration of joint PDFs over unbounded regions

I am currently grappling with an issue related to high-dimensional integration of joint Probability Density Functions (PDFs) over unbounded regions. The specifics of the problem are a bit intricate, ...

0
votes

0
answers

62
views

### Convergence bounds for ergodic random walk

We are given a simple connected graph $G(V,E)$, where $V$ and $E$ denote the vertex and edge sets respectively. Let $G'(V,E')$ be the graph generated by $G$ by adding one self-loop edge for each ...

0
votes

0
answers

21
views

### Langevin dynamics or stochastic gradient flow for grand canonical ensemble

We know that for a measure exp(-U(X)) (canonical ensemble), we can use the dynamic dX=-DU(X)+ noise to sample the measure as t goes to infinity.
Is there any dynamic corresponding to the grand ...

0
votes

0
answers

42
views

### About cutoff for quasi-random graphs

In this paper by Hermon, Sly and Sousi about mixing time of a random walk on a random graph, there is a concept of $\textit{regeneration edges}$ which I'm trying to understand. This is defined in page ...

3
votes

1
answer

198
views

### Spectral Radius and Spectral Norm for Markov Operators

My question concerns differences between the spectral radius $\rho$ and norm $\| \cdot \|$ of Markov operators in infinite-dimensional Banach spaces. This is far from my area of expertise, that is ...

1
vote

0
answers

72
views

### Derive a closed-form expression of this recursive formula

$$\begin{equation}
S(r,k) = f(r)S(0,k-1) + g(r)S(r+1,k-1)
\end{equation}\ ,$$
where $r=0,1,2,\dots$ and $k=1,2,3,\dots$ . Also, $0<f(r)<1$ is an increasing function and $0<g(r)<1$ is a ...

0
votes

0
answers

26
views

### Prove the explicit form of the ratio function in a Markov Chain

Let $(A_M^{\mathbb{Z}_+}, \Omega, P, \lambda)$ be a Markov Shift where $A$ is a finite alphabet set, $M$ is the admissibility matrix, $P = [P_{i, j}]_{i, j\in A}$ is a stochastic matrix that is ...

2
votes

1
answer

185
views

### When is a stationary measure of a Markov chain "exponentially localized"?

Here exponentially localized can be thought in a non-rigorous manner as a measure that is mostly supported on a sparse number of nodes.
Some intuition can gained by thinking about a diffusion process, ...

0
votes

1
answer

39
views

### Diameter of the range of composition of random maps on the circle

My questions are related to the paper https://hal.science/hal-03933493v1 (accepted with corrections in Ergodic Theory and Dynamical Systems).
I fix an irrational number $\theta \in [0,1[$. I define ...

0
votes

0
answers

91
views

### On the exponentiation of a stochastic matrix where the exponent is a function of matrix size

In this question, I asked about any arbitrary stochastic matrix $A(n)$ of the particular form
$$A(n) = \begin{pmatrix} 1 & 0 & \cdots & 0\\ x_{21} & x_{22} & \cdots & 0\\ \...

0
votes

0
answers

46
views

### The Rate of converging to the stationary distribution given a time in-homogenous but fast converging transition probabilities

Let $P_n$ be a sequence of transition probabilities and $X_n$ be the corresponding Markov chain. That is , $X_n=d_0P_1...P_{n}$, where $d_0$ is the initial distribution. Suppose each $P_n$ has its ...

0
votes

0
answers

31
views

### Fluctuation-dissipation theorem for Markov processes

In the context of particle systems of non-gradient types (see e.g. here, Step 2 on page 633), I recently encountered the concept of fluctuation-dissipation theorem (FDT). Since it is a major result in ...

4
votes

1
answer

230
views

### Random walk visiting a cylinder infinitely often

I wonder whether a $d$-dimensional random walk $S_n$, generated by the infinite i.i.d. copies of X given by:
$X=e_1=(1, 0, 0, ..., 0)$ (with probability $p_1$)
$X=e_2=(0, 1, 0, ..., 0)$ (with ...

8
votes

7
answers

964
views

### One observation of special type of square matrix exponentiation

I was studying the following type of matrices,
$$
A = \begin{pmatrix}
1 & x_{12} & \cdots &x_{1n}\\
0 & x_{22} & \cdots &x_{2n}\\
\vdots\\
0&\cdots&0&x_{nn}
\end{...

0
votes

0
answers

57
views

### Markov renewal process with varying waiting times: What does the past waiting time reveal?

In summary, I want to know how -- when generalizing the Markov renewal process to have different parameterized waiting times at different states -- the information of the last waiting time tells us ...

0
votes

0
answers

57
views

### Gibbs with gradient Markov chain

I'm reading a paper where a Markov chain called "Gibbs with gradient" is used on discrete state spaces and I don't understand the transition probabilities of this Markov chain. This is ...

1
vote

0
answers

42
views

### Sample complexity of estimating a doubly stochastic matrix

Let $P\in\mathbb{R}^{n\times n}$ be a doubly-stochastic matrix. That is:
$$P(x,y)\geq 0,\quad \sum_xP(x,y)=1,\quad \sum_yP(x,y)=1.$$
I would like to know if lower and upper bounds on the sample ...

2
votes

0
answers

49
views

### Training an energy-based model (EBM) using MCMC

I'm reading this paper about training energy-based models (EBMs) and don't understand the parameters that we are training for? The part that is relevant to the question is in pages 1-4. Here is the ...

3
votes

1
answer

310
views

### Importance resampling with exponential weighting

Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...

2
votes

2
answers

205
views

### Is there something like a "self-avoiding Markov chain" on a continuous space?

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.
However, as far as I can see they are ...

0
votes

0
answers

111
views

### Approximate range of Radon-Nikodym derivative in a dynamical system

Suppose $(X, G, \Omega, \mu)$ is a dynamical system where $(X, \Omega, \mu)$ is a Borel measure space and $G$ is acting on $X$ such that each group action $x\mapsto g\cdot x$ defines a measurable ...

2
votes

1
answer

134
views

### Joint irreducibility and aperiodicity of two independent Markov chains

Let $(X_i)_i, (Y_i)_i$ be two independent Markov chains on Polish state spaces $\mathcal{X}, \mathcal{Y}$ and with kernels $P, Q$. Suppose that they are both $\psi$-irreducible and aperiodic and have ...

1
vote

0
answers

39
views

### Deducing differential equations from a time-continuous Markov chain via its rate matrix

I have only basic level knowledge of probability theory and I am researching in a different field. So please do not be too harsh on me if my question turns out to be silly.
Let $(X, \Sigma, \mu)$ be a ...

0
votes

1
answer

81
views

### Inhomogeneous Markov chains and the product-integral as a solution to the Kolmogorov forward equation

We have a inhomogeneous continous $K$-State Markov chain $X(t)$ with transition intensity matrix $Q(t)$. Therefore its entries are:
$$q_{ij}(t)= \lim_{\delta \to 0} \frac{1}{\delta} \mathbb{P}(X(t+\...

0
votes

1
answer

47
views

### Skip-free random walks: recurrence and transience

Let us define a one dimensional random walk: for all $n\in\mathbb{N}$
$$
X_n:=\sum_{i=1}^nZ_i
$$
with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...

1
vote

0
answers

22
views

### How slowly can one be absorbed in the absorbing phase of the directed percolation universality class?

In absorbing state transitions on a lattice, one often considers "active" and "inactive" sites, with update rules describing how activity spreads or decays. When the lattice sites ...

2
votes

1
answer

83
views

### On the distance to the stationary distribution

A Markov Chain $M$ has only one stationary distribution $q$.
For distribution $p$, with $D_{TV}(p,Mp)=x$, can we bound $D_{TV}(p,q)$?
Clearly, $x=0$ implies $D_{TV}(p,q)=0$. Does general bound hold?
...

0
votes

0
answers

29
views

### Positivity of pseudo spectral gap of Markov chain

In this paper (https://projecteuclid.org/euclid.ejp/1465067185) a pseudo spectral gap is introduced of a time homogeneous, $\phi$-irreducible, aperiodic Markov chain on a Polish state space with ...

2
votes

0
answers

40
views

### Right spectral gap of vector of two independent Markov chains

Let $(X_i)$ be a stationary Markov chain on $S$ (a potentially uncountable space with a Borel sigma algebra) with stationary distribution $\pi$ and transition kernel $P$. Let $(Y_i)$ be a stationary ...

2
votes

2
answers

212
views

### Polynomial time mixing Markov chain for multimodal distribution

Is there a discrete space Markov chain, starting from a fixed state, whose stationary distribution is a multimodal distribution and that mixes in polynomial time?
For example, Ising model on say a ...

1
vote

0
answers

28
views

### If $(\kappa_t)_{t\ge0}$ is a Markov semigroup with invariant measure $μ$, under which assumption is $t\mapsto\kappa_tf$ measurable for $f\in L^p(μ)$?

Let
$(E,\mathcal E)$ be a measurable space;
$(\kappa_t)_{t\ge0}$ be a Markov semigroup on $(E,\mathcal E)$;
$\mu$ be a finite measure on $(E,\mathcal E)$ which is subinvariant with respect to $(\...

2
votes

1
answer

225
views

### Idempotent splitting for Markov kernels

Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation,
$$e(A|x) = \int_X e(...

1
vote

2
answers

158
views

### Connection between invariant measure and positive recurrence for continuum state space markov chain

Let $\{ X_n(\omega,x)\}_{n \ge 0}$ be a Markov chain with and underlying probability space $(\Omega,\Sigma,\mathbb{P})$ and state space $X= \mathbb{S}^1$. Suppose this markov chain admits unique ...

6
votes

1
answer

337
views

### Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...

0
votes

1
answer

84
views

### What is the significance of Blumenthal and Getoor's result on the boundedness of paths of a standard Markov process?

In the book Markov processes and Potential Theory of Blumenthal and Getoor we can find the following result:
I don't understand the significance of this result. If I don't misinterpret the assertion, ...

0
votes

0
answers

29
views

### Separable bivariate markov chain

Let $Z = (X,Y)$ be a discrete random variable, and let $X$ and $Y$ be independent. Consider a Markov chain $Z \xrightarrow{f_1} Z_1 \xrightarrow{f_2} \dots \xrightarrow{f_N} Z_N$ where each $f_n: \...

4
votes

0
answers

141
views

### Random walk on hexagonal lattice. First return to the origin

I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $2n$ that start at the origin $O$ and go back to $O$ but doing so for the first time at step $2n$ (...

0
votes

0
answers

42
views

### If $\kappa$ is a Markov kernel with density $p$, does it generally hold $p(x,z)=\int p(x,y)p(y,z)\:{\rm d}y$?

Let $(E,\mathcal E)$ be a measurable space and $\kappa$ be a Markov kernel on $(E,\mathcal E)$. Assume that $$\kappa(x,B)=\int_Bp(x,y)\:\lambda({\rm d}y)\;\;\;\text{for all }(x,B)\in E\times\mathcal E$...

0
votes

0
answers

67
views

### Determine the adjoint of the generator of a Markov semigroup

Let
$(E,\mathcal E)$ be a measurable space and $$\mathcal E_b:=\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\}$$ be equipped with the supremum norm;
$(\kappa_t)_{t\ge0}$ ...

0
votes

1
answer

138
views

### Constructing Markov chain

Let $(A_1,B_1)$ and $(A_2,B_2)$ be two random variables with the joint distributions $p_{A_1B_1}$ and $p_{A_2B_2}$, respectively. Moreover, we have
$$\mathbb{P}[(A_1,B_1)\neq (A_2,B_2)]=\alpha.$$
Then,...

0
votes

0
answers

34
views

### Properties of the weak generator of a Markov semigroup

Let
$(E,\mathcal E)$ be a measurable space
$\mathcal E_b:=\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\}$
$(\kappa_t)_{t\ge0}$ be a Markov semigroup on $E$
$(\mathcal D(...

2
votes

1
answer

162
views

### If $X$ is a Markov process, can we find a mild assumption ensuring that $\frac1t\operatorname E_x\left[\int_0^tc(X_s)\:{\rm d}s\right]\to c(x)$?

Let
$(E,\mathcal E)$ be a measurable space with $\{x\}\in\mathcal E$ for all $x\in E$
$\mathcal E_b:=\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\}$
$(\kappa_t)_{t\ge0}$ ...

0
votes

1
answer

246
views

### Construction of a Markov process with prescribed local behavior and state-dependent jump distribution

Let
$(E,\mathcal E)$ be a measurable space
$\mathcal E_b:=\left\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\right\}$
$(\kappa_t)_{t\ge0}$ be a Markov semigroup on $(E,\...

0
votes

0
answers

69
views

### Generator of the concatenation of two Markov processes

Let
$(E_n,\mathcal E_n)$ be a measurable space with $\{x\}\in\mathcal E_n$ for all $x\in E_n$ and $\Delta_n\not\in E_n$ with $E_1\cap E_2=\emptyset$;
$(\kappa^n_t)_{t\ge0}$ be a sub-Markov semigroup ...

1
vote

1
answer

256
views

### How can we determine the generator of this Markov process (at least formally)?

Let
$(\Omega,\mathcal A)$ be a measurable space;
$(E,\mathcal E)$ be a measurable space with $\{x\}\in\mathcal E$;
$(Y_t)_{t\ge0}$ be an $(E,\mathcal E)$-valued time-homogeneous Markov process on $(\...

1
vote

0
answers

37
views

### What's the autocovariance of 2 concurrent hidden states of a stochastic gaussian walk, using the Kalman filter?

A latent variable evolves as $x_t = x_{t-1} + e_t$ where $e_t$ has a gaussian distribution with 0 mean and a variance which defines the volatility of the overall process. Let $o_t$ be the noisy ...

3
votes

1
answer

129
views

### Carne-Varopoulos bound and stationary measure

Let $\Gamma$ denote the Cayley graph for a finitely generated group $G$, and let $p_n(x, y)$ denote the transition probability that a random walk starting at $x$ reaches $y$ at time $n$. A famous &...

4
votes

1
answer

170
views

### Population growth with good and evil children - probability good outnumbers evil

Consider the following discrete-time population model. We start with a single "good" individual who reproduces asexually into $k$ children and dies in the process. At generation $t=2$, those ...