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 (...
- 11
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 ...
- 33
-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, ...
- 1
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 ...
- 1,605
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 ...
- 31
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 ...
- 201
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 ...
- 540
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, ...
- 2,164
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 ...
- 2,713
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\\ \...
- 271
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 ...
- 113
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 ...
- 91
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{...
- 271
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 ...
- 109
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 ...
- 201
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 ...
- 91
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 ...
- 201
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_{...
- 1,107
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 ...
- 131
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 ...
- 211
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 ...
- 371
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+\...
- 3
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
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 ...
- 319
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?
...
- 1,443
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 ...
- 211
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 ...
- 211
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 ...
- 201
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 $(\...
- 131
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(...
- 5,128
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$, ...
- 63
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, ...
- 131
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: \...
- 189
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$ (...
- 245
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$...
- 131
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}$ ...
- 131
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,...
- 129
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(...
- 131
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}$ ...
- 131
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,\...
- 131
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 ...
- 131
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 $(\...
- 131
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 ...
- 11
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 &...
- 31
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 ...
- 319