Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
540
questions
1
vote
0
answers
104
views
Show a Poincaré inequality for a Markov kernel and minimize the Poincaré constant
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$ (see definitions ...
- 161
1
vote
1
answer
160
views
Stationary distribution of Markov Chain with departure
I have a Markov Chain of $N$ states. Such states represent the energy levels in a molecule.
The states' connectivity is as follows:
States $j\in\{0,\ldots,N\}$ transition to $k\in\{\max(j-M,0),...,\...
- 151
1
vote
0
answers
118
views
Is there any equivalent Foster-Lyapunov Theorem where expected Lyapunov drift is negative though not uniformly upper bounded by a negative number
I have a process $\{X_t\}_t$, where $x_t$ in $[0,1]$, and a Lyapunov function $V(x)=x$ such that the drift
$$E[X_{t+1}|x_t] - x_t < -k(1-x_t)$$
for $x_t \in (1-\epsilon,1]$, where $k>0$. Thus ...
1
vote
0
answers
54
views
Minimizing the rate of geometric ergodicity of a Metropolis-Hastings kernel depending on a parameter
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$.
I want to ...
- 161
1
vote
1
answer
138
views
Comparison of hitting probability of two Markov chains both with only one absorbing state version 2 under stronger condition
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$.
$\text{Pr}\...
- 2,169
1
vote
4
answers
271
views
Probability of traversing all other states and finally landing on one state
This is a cross-post from math.stackexchange.com. There has been no response there.
Given a Markov chain of finite states with constant transition probabilities, what is the method to compute the ...
- 2,169
1
vote
1
answer
115
views
Comparison of hitting probability of two Markov chains both with only one absorbing state
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have one absorbing state $1$.
Pr$(X^{(1)}_{i+1}=1|X_i=1)...
- 2,169
0
votes
1
answer
80
views
In smooth stochastic dynamics, if a Lebesgue-like measure is both forward-time and reverse-time stationary, is the measure necessarily incompressible?
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact connected $C^\infty$-smooth manifold. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to ...
- 16.7k
0
votes
1
answer
93
views
If a probability measure is stationary in both forward time and reverse time, does this imply that the measure is incompressible?
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact metric space. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to X$ be measurable ...
- 16.7k
0
votes
2
answers
127
views
Markov with epsilon memory and Quantitative Strong Markov property
We have a process $\{X_{t}\}_{t\geq 0}$ ,with fixed parameter $\epsilon>0$, starting from zero that satisfies
The process is strictly monotone $X_{t+r}-X_{t}>0$ with moments existing $p\in(-\...
- 4,449
0
votes
1
answer
80
views
A question about positive operator pregenerator [closed]
Thank you for reading.
My question was raised up when I tried to prove an example in the book of Liggett(1985), which is in P13 Example 2.3(a).
Here is a link of the page:
https://books.google.com/...
- 15.5k
1
vote
1
answer
163
views
Coupling argument involved in the contracting and mixing properties of the Glauber dynamics for an Ising model
While doing a research work, I had to read about the Glauber dynamics for an Ising model. A wonderful account on this is given in the book Markov Chains and Mixing Times by Levin, Peres and Wilmer.
...
- 60.4k
1
vote
0
answers
81
views
Convexity of conditional relative entropy for Markov distributions
Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is
\begin{align}
D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\
& =\...
3
votes
0
answers
200
views
Maximize an $L^p$-functional subject to a set of constraints
Let
$(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces
$f\in L^2(\lambda)$
$I$ be a finite nonempty set
$\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
- 161
2
votes
0
answers
113
views
Characterizing the relationship between element-wise Markov transitions and the full-conditionals of the stationary distribution
Consider a $p$ dimensional random variable with a discrete support. Consider a Markov transition kernel on the state space that is defined in terms of element-wise transition distributions.
One can ...
- 2,721
2
votes
1
answer
366
views
Existence and uniqueness of a stationary measure
This same question was also posted on MSE https://math.stackexchange.com/questions/3327007/existence-and-uniqueness-of-a-stationary-measure.
Recently I have posted the following question on MO ...
- 22.5k
1
vote
1
answer
170
views
Can we show that $\mathbb R^{\mathbb N}\ni x\mapsto\bigotimes_{n\in\mathbb N}\mathcal N_{x,\:\sigma^2}$ is a Markov kernel?
Let $\sigma>0$ and $\mathcal N_{x,\:\sigma^2}$ denote the normal distribution with mean $x\in\mathbb R$ and variance $\sigma^2$. From the Ionescu-Tulcea theorem, we know that $$\kappa(x,\;\cdot\;):=...
- 161
4
votes
2
answers
446
views
Stationary distribution of a Markov process defined on the space of permutations
Let $S$ be the set of $n!$ permutations of the first $n$ integers. Let $p\in(0,1)$. Consider the Markov Process defined on the elements of $S$.
Let $x\in S$. Choose $1\le i <i+1 < n$ uniformly ...
- 5,926
2
votes
2
answers
957
views
Non-backtracking random walk in regular (finite) graphs
I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
- 37.2k
3
votes
2
answers
841
views
How much larger than the relaxation time can the mixing time be?
The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.
Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
- 60.4k
0
votes
0
answers
81
views
A closed form of mean-field equations
Assume that a system at time t, for example number of costumers in a line at time $t$ which is denoted by $q(t)$, follows a Markov chain with these dynamics (probabilities)
$$P(q(t+\Delta t)-q(t)=1)=\...
- 178k
2
votes
0
answers
94
views
Distribution of a linear pure-birth process' integral
I stumbled across the following random variable, defined as the integral of a linear pure-birth process i.e. a Yule process:
$$
Z_t = \mathbb{E}\bigg[\int_0^t Y_s ds \bigg| Y_t=k , Y_0=1\bigg]
$$
...
- 3,309
7
votes
2
answers
258
views
Slowest initial state for convergence of finite birth-and-death Markov chains
Consider the continuous-time birth-and-death Markov chain on $\{1,\cdots,n\}$ with all rates equal to $1$. Is it true that the convergence to equilibrium, in total variation distance, is slowest when ...
- 5,945
3
votes
3
answers
2k
views
Proof of the existence of an optimal MDP with a stochastic reward signal?
I'm following Sutton's book on Reinforcement Learning, and he casually states that "There is always at least one policy that is better than
or equal to all other policies" for a given finite MDP. This ...
- 334
2
votes
1
answer
222
views
If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?
Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
- 14k
14
votes
2
answers
1k
views
Diagonalizing some matrices arising from Fourier transform on $S_n$.
Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $\hat{f}(\rho)$ evaluated at the ...
- 966
5
votes
1
answer
173
views
Reference request: When is the variance in the central limit theorem for Markov chains positive?
I'm looking for a reference which gives sufficient conditions for the variance to be positive in the central limit theorem for Markov chains (cf https://en.wikipedia.org/wiki/...
- 11.9k
3
votes
0
answers
87
views
Joint drunkard walks
The drunkard walk is a game where two players have $a$ and $b$ dollars, respectively, and they play a series of fair games (both risking one dollar in each game) until one of them goes broke.
My ...
- 131
0
votes
2
answers
267
views
Lower bounds on discrete time finite Markov chains hitting probabilities
I am interested in some general theorems related to lower bounds on discrete time finite Markov chains hitting probabilities (preferably ergodic chains , but not necessarily ), with references . ...
- 14k
1
vote
0
answers
111
views
Must this upper bound on mixing time depend on the minimum stationary probability?
It is known fact that for a finite-state, reversible and ergodic Markov chain with transition matrix $M$, the following control on the mixing time holds
$$\left( \frac{1}{\gamma_\star - 1}\right)\ln{...
- 141
0
votes
1
answer
315
views
Expectation of a linear operator
We define $T: C[0,1]\to C[0,1]\ni T(f(x))= \sum\limits_{k=1}^{m} p_k (f\circ f_k)(x):=\mathbb E( f(X_{n+1}|X_n=x)$ for a system $X_{n+1}=f_{\omega_n}(X_n), n=0,1,2\dots.$ and $\omega_n$ are i.i.d ...
- 149
3
votes
1
answer
210
views
Total offspring of Poisson multitype branching process
A normal branching process $Z_n$ initialized with $Z_0=1$ and offspring generated from $Pois(p),p<1,$ has a total progeny / total off spring distribution
$$X=\sum_{n=0}^\infty Z_n$$
$X\in \mathbb{...
- 59.8k
1
vote
1
answer
310
views
Obtaining generator matrix and first-passage time distribution for CTMC?
Setup:
I have a model of a biological process described by two ODEs as follows:
$$\dot{X_1} = (\beta_1-d-1)X_1 + 2X_1^2 - X_1^3 + dX_2$$
$$\dot{X_2} = (\beta_2-d-1)X_2 + 2X_2^2 - X_2^3 + dX_1$$
I ...
- 5,945
2
votes
0
answers
69
views
If $X^n$ is a sequence of càdlàg processes whose FDDs converge to a continous process $X$, does $X^n$ converge to $X$ in the Skorohod topology?
Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space, $E$ be a complete locally compact separable metric space, $(X^n_t)_{t\ge0}$ be an $E$-valued càdlàg process on $(\Omega,\mathcal A,\...
- 161
1
vote
0
answers
100
views
Prior state dependent transition probability ABRACADABRA problem
The power of the martingale trick for computing the expected stopping time is amply demonstrated in this question and this answer as an advanced version of the ABRACADABRA problem. However, it seems ...
- 2,169
3
votes
1
answer
210
views
A 2d recurrence equation representing a step-free continuous-time Markov process on N^2 with frequency-dependent rates
$\textbf{Background:}$ Consider a particle in $\mathbb{N}^2$ starting at a point $(x,y)$ that can only move one step at a time along the lattice. The particle moves each up or down in continuous time ...
- 3,555
6
votes
0
answers
219
views
Is there a "promise" at the heart of mixing times for random walks on Cayley-graphs?
I'm interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik's Cube Group $G$. Determining ...
- 2,143
0
votes
0
answers
93
views
Formal definition of episodic Markov Decision process?
David Silver, in his lecture 4 from his Youtube lectures, speaks about episodic Markov Decision Processes (MDPs) and Monte-Carlo Policy Evaluation.
I could not find a formal definition of episodic ...
- 3,554
2
votes
0
answers
36
views
Exclusion processes from point of view of a tagged particle
I'm interested in the simple exclusion processes on $Z^d$ and the ergodic theorems that can be proved from the point of view of the particle. Ellen Saada proved the following in 1987 (Annals of Prob): ...
- 921
1
vote
1
answer
302
views
Existence of a Lyapunov function for a log-concave measure
Let $d\in\mathbb N$, $f:\mathbb R^d\to\mathbb R$ be convex with $$\int e^{-f(x)}\:{\rm d}x<\infty\tag1$$ and $\mu$ denote the measure with density $e^{-f}$ with respect to the Lebesgue measure on $\...
- 161
1
vote
0
answers
96
views
How is the dominated convergence theorem applied in the proof of Lyapunov’s criterion?
Let $$\Gamma(f,g):=\frac12f'g'\;\;\;\text{for }f,g\in C^1(\mathbb R),$$ $\mu$ be a probability measure on $(\mathbb R,\mathcal B(\mathbb R))$ with a continuously differentiable and positive density $\...
- 161
0
votes
1
answer
182
views
How is the Cauchy-Schwarz inequality used in the proof of Lyapunov's criterion in the book "Analysis and Geometry of Markov Diffusion Operators"
Let $(E,\mu,\Gamma)$ be a full Markov triple (see definition below), $J\in\mathcal A$ with $J\ge1$ and $g\in\mathcal A_0$. In the proof of Theorem 4.6.2 of the book "Analysis and Geometry of Markov ...
- 118k
1
vote
0
answers
81
views
If $\text P\left[X_2\in B_2\mid X_1\right]=\kappa(X_1,B_2)$ a.s. for all $B_2$, can we select a common null-set over all $B_2$?
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E_i,\mathcal E_i)$ be a measurable space
$X_1:\Omega\to E_1$
$X_2:\Omega\to E_2$ be $(\mathcal A,\mathcal E_2)$-measurable
$\kappa$ ...
- 161
0
votes
0
answers
88
views
How can we show that the total variation distance of $X_s$ and $Y_s$ is bounded by the distance of $(X_t)_{t\ge s}$ and $(Y_t)_{t\ge s}$?
Let $(X_t)_{t\ge0}$ and $(Y_t)_{t\ge0}$ be real-valued time-homogeneous Markov processes with a common transition semigroup $(\kappa_t)_{t\ge0}$. Let $\mathcal L(Z)$ denote the distribution of a ...
- 161
-1
votes
1
answer
321
views
What's the probability of two independent events in time domain?
Suppose there are two independent events A and B. The probability that A or ...
- 178k
1
vote
0
answers
76
views
Discrete Markov process on finite interval
Consider an contiguous array of $N$ states, numbered from $1$ to $N$.
At every time step $t$, the process should transition to an adjacent state.
The probability of moving to the right (from state $n\...
3
votes
2
answers
262
views
Probability of one species reaching zero before the other in a Markov process on a 2d lattice
$\textbf{Background}$: Say we've got a two-variable system of stochastic chemical reactions, with quantities $\vec{x}(t) = (x_1(t),x_2(t)) \in \mathbb{N}^2$ evolving according to the following system, ...
- 3,787
4
votes
2
answers
895
views
Are there known expressions for total variation distance between mean centered multivariate normal densities $N(0,\Sigma_{1})$ and $N(0,\Sigma_{2})$
Consider two mean centered multivariate normal densities $N(0,\Sigma_{1})$ and $N(0,\Sigma_{2})$. Are there known expressions (as opposed to bounds provided by the Pinsker inequality) for the total ...
1
vote
0
answers
134
views
Construction of Feller's pseudo-poisson process
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$(Y_n)_{n\in\mathbb N_0}$ be a $(E,\mathcal E)$-valued time-homogeneous Markov chain on $(\...
- 161
1
vote
0
answers
92
views
Existence of Time-Reversed Markov Kernels
Suppose I have a probability measure $\pi$ and a Markov kernel $q$ which leaves $\pi$ invariant, in the sense that
\begin{align}
\int_x \pi(dx) q(x \to dy) = \pi(dy)
\end{align}
Then, a (the) time-...
- 706