Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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}...
Ribhu's user avatar
  • 311
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 ...
Benjamin Dickman's user avatar
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 ...
landau's user avatar
  • 23
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 ...
Rusbert's user avatar
  • 173
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 ...
Joël's user avatar
  • 25.7k
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 ...
R Hahn's user avatar
  • 2,721
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 ...
RaphaelB4's user avatar
  • 4,296
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 ...
Television's user avatar
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 ...
Television's user avatar
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-...
Davide Papapicco's user avatar
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 ...
Jacob's user avatar
  • 63
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 ...
Yi Huang's user avatar
  • 333
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 ...
0xbadf00d's user avatar
  • 161
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 ...
dohmatob's user avatar
  • 6,716
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. ...
user avatar
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 ...
user2679290's user avatar
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 ...
0xbadf00d's user avatar
  • 161
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 ...
0xbadf00d's user avatar
  • 161
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 ...
0xbadf00d's user avatar
  • 161
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 ...
Deepanshu Vasal's user avatar
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,...
Mark S's user avatar
  • 2,143
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}...
Hans's user avatar
  • 2,169
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}\...
Hans's user avatar
  • 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)...
Hans's user avatar
  • 2,169
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),...,\...
TheVal's user avatar
  • 151
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 ...
Julian Newman's user avatar
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 ...
Julian Newman's user avatar
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(-\...
Thomas Kojar's user avatar
  • 4,414
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/...
Chennes's user avatar
  • 385
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. ...
abcd's user avatar
  • 367
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,...
Ella Sharakanski's user avatar
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)}\\ & =\...
doubleG's user avatar
  • 11
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 $...
Myshkin's user avatar
  • 149
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 ...
0xbadf00d's user avatar
  • 161
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 ...
Matheus Manzatto's user avatar
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 ...
R Hahn's user avatar
  • 2,721
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\;):=...
0xbadf00d's user avatar
  • 161
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 ...
Hans's user avatar
  • 2,169
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 ...
gappy3000's user avatar
  • 461
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)=\...
user avatar
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] $$ ...
Gabriel's user avatar
  • 29
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 ...
Guillaume Aubrun's user avatar
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/...
munchhausen's user avatar
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 ...
A. Pongrácz's user avatar
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$ $(\...
0xbadf00d's user avatar
  • 161
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 . ...
Cristian Dumitrescu's user avatar
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{...
geo.wolfer's user avatar
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{...
Conformal's user avatar
  • 315
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 ...
Josh R's user avatar
  • 123
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 ...
user avatar

1 2 3
4
5
11