Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
539
questions
0
votes
1
answer
67
views
Friedrich's extension of the generator of a continuous time markov chaoin
Consider the infinitesimal generator $G$ of a Markov chain with state space $\mathbb{Z}$ such that it is symmetric with respect to a measure $\mu$ on $\mathbb{Z}$. Then, the operator $(G,C_c(\mathbb{Z}...
2
votes
3
answers
374
views
Generations until fixation: A nontrivial generalization of a dice convergence problem
In spite of its "recreational" aspect, this question appears to me to be research-level and (I hope) clearly formulated and tagged.
Edit 4/4/20: You can find a related question with the ...
2
votes
1
answer
182
views
Diagonalizable stochastic matrix that satisfies an equation
Given an arbitrary discrete probability distribution $a = (a_1, ..., a_n)$ and another arbitrary discrete probability distribution $b = (b_1, ..., b_n)$, what is the easiest known way to find a ...
2
votes
0
answers
176
views
Gurevich's entropy and topological entropy in a countable Markov shift
Good afternoon, I understand that Gurevich's entropy and topological entropy coincide when the countable Markov shift is topologically mixing (right?)
Does anyone know of an example or a reference ...
6
votes
1
answer
346
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
0
votes
1
answer
158
views
Law of large numbers for Harris recurrent Markov chains
I'm trying to familiarize myself with the details of the proof that the Markov chains produce by the Metropolis-Hastings algorithm have a law of large numbers. I've found a half dozen or more ...
3
votes
3
answers
159
views
A stopping time that gives the metric
Let $\Omega$ a finite metric space with $\forall x,y,z\in \Omega:d(x,y)<d(x,z)+d(z,y)$. Does there exists a continuous-time Markov process $X$ on $\Omega$ such that $$\mathbb{E}_x(T_y)=d(x,y)$$ for ...
2
votes
1
answer
174
views
Concentration in Markov chains
Consider a discrete state space $\mathcal{X}$. The expander Chernoff inequality gives subgaussian concentration for the sample mean $\frac1n \sum_{t=1}^n f(X_t)$ for some function $f : \mathcal{X} \to ...
6
votes
1
answer
356
views
Maximum eigenvalue of a doubly stochastic matrix with deleted row and column
Consider an $n \times n$ irreducible and reversible (in the sense of a Markov chain) stochastic matrix $P$; assume that it has uniform stationary distribution (so, by reversibility, the matrix is ...
2
votes
1
answer
218
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
1
vote
0
answers
111
views
Showing existence of a solution to an underdetermined system of equations with non-negativity constraints
Let $K$ be a positive integer, let $p\in (0,1)$, and let $\{W(k,i),W^B(k,i), \varphi_k(i)\}_{1\leq i\leq k\leq K}$ be variables.
I need to prove that there exists a solution to the following system ...
2
votes
1
answer
168
views
Entropy rate problem of ergodic Markov process with non-ergodic joint
I have a problem with the entropy rate when two ergodic Markov processes who are independent of each other having a non-ergodic joint. More specifically let us consider two finite-state Markov ...
0
votes
2
answers
217
views
Spectrum of a Markov kernel acting on $L^2$
Let $P$ be a Markov kernel on a measurable space $(E,\mathcal E)$ admitting an invariant probability measure $\pi$. $P$ acts on $L^2(\pi)$ via $$Pf:=\int\kappa(\;\cdot\;{\rm d}y)f(y).$$ The invariance ...
2
votes
1
answer
264
views
Uniform upper bound on contraction coefficient w.r.t total-variation metric, of a certain set of block-diagonal Markov kernels
Disclaimer. This is related to another question I've asked on the TCS site https://cstheory.stackexchange.com/q/46097/44644. I'm new to information theory (and other relevant fields). It's even ...
1
vote
1
answer
277
views
Symmetric random walks - bounds on the amount of time spent in a subset $A$?
For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$?
Let $S_n$ be a symmetric random walk on the integers. ...
1
vote
1
answer
142
views
Distribution of non-overlapping words in randomly generated text
The question can be described in the following way:
Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$.
I have a string that is composed of a concatenated series of $n$ instances ...
1
vote
0
answers
71
views
Reduce the asymptotic variance for a class of Metropolis-Hasting estimates
I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
1
vote
0
answers
103
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 ...
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 ...
1
vote
0
answers
117
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 ...
11
votes
0
answers
539
views
Does Chu and Hough's solution to the mixing time of the 15-puzzle carry over to the Rubik's cube?
In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states:
Here is a simplified version: Consider the blank as a $16$th block,...
1
vote
1
answer
98
views
Comparison of hitting probability of two Markov chains both with only one absorbing state version 3
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_t\in N_n\}\big)_{t=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$. Define
$p_{i,j}...
1
vote
1
answer
136
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}\...
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)...
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),...,\...
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 ...
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 ...
0
votes
2
answers
126
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(-\...
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/...
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.
...
2
votes
0
answers
318
views
Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?
In Bobkov and Tetali - Modified Log-Sobolev Inequalities, Mixing and Hypercontractivity (extended version Modified Logarithmic Sobolev Inequalities in Discrete Settings), at the beginning of section 3,...
1
vote
0
answers
80
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)}\\
& =\...
1
vote
1
answer
440
views
Markov chain and random iteration of functions
Could anyone give me some references for the convergence rate of Markov chain arising from the random iteration of Lipschitz functions which moves as follows:
$$ X_{n+1}= f_{\omega_n}(X_n)$$ where $...
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 ...
2
votes
1
answer
358
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 ...
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 ...
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\;):=...
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 ...
4
votes
2
answers
445
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 ...
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)=\...
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]
$$
...
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
votes
1
answer
168
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/...
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 ...
0
votes
0
answers
204
views
Show convergence of a sequence of resolvent operators
Let
$E$ be a locally compact separable metric space
$(\mathcal D(A),A)$ be the generator of a strongly continuous contraction semigroup on $C_0(E)$
$E_n$ be a metric space for $n\in\mathbb N$
$(\...
0
votes
2
answers
262
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 . ...
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{...
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{...
2
votes
1
answer
838
views
Comparing mixing time of lazy and non-lazy Markov chains
Suppose we have a probability distribution $\pi : X \rightarrow [0,1]$ where $X$ is finite and let $Q : X \times X \rightarrow [0,1]$ be a Markov kernel that is reversible with respect to $\pi$. That ...
1
vote
1
answer
309
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 ...