# Questions tagged [markov-chains]

The markov-chains tag has no usage guidance.

408
questions

**2**

votes

**1**answer

137 views

### Calculate Radon-Nikodym derivative

For the laws of two pure-jump Markov processes $\mu_1$ and $\mu_2$ on $\mathbb R^n$, which generators are
$H_1f(x)=\int h(x,dy) (f(y)-f(x))$
and $H_2f(x)=\int e^{-g(x,y)} h(x,dy) (f(y)-f(x))$ (...

**2**

votes

**1**answer

92 views

### Eigenspace of Gaussian Markov operator

Consider the (one-dimensional) Gaussian distribution $Q := N(\nu,\tau^2)$ and the (Gaussian) Markov operator
\begin{equation*}
\begin{array}{rccc}
R : & L_1(\mathbb{R},\mathcal{B}(\mathbb{R}),Q) &...

**2**

votes

**2**answers

115 views

### is this process a Markov one?

Here is the problem I can't solve.
Let $\xi_n$ $(n=1,2,3,\dots)$ be a sequence of i.i.d. random variables on $\mathbb{R}$ with density $p(x)>0$, let $\eta_n=\sum_{i=1}^{n}\xi_i^2$. Define $$\...

**-1**

votes

**0**answers

30 views

### Stopping times about Brownian motion with draft

Assumet $M(t) = B(t) + \mu t$ where $B(t)$ is a standard Brownian Motion. Denote:
$$T_a := \inf \{ t \geq 0, \, M(t) = a\}, \quad T_b := \inf \{ t \geq 0, \, M(t) = b\}$$
The question asks to ...

**1**

vote

**1**answer

49 views

### Conditions for optimal stationary strategies in MDPs

I have a specific markov decision process (MDP) which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal ...

**0**

votes

**0**answers

14 views

### Calculate regime-switching correlation matrix without assumption on distribution

There's rich literature on Markov regime-switching dynamic correlation matrix. But most results seem to assume a certain kind of distribution and use MLE/EM. For example, some sort of multivariate ...

**6**

votes

**2**answers

500 views

### what is the number of paths returning to 0 on the hexagonal lattice

I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.
I can find plenty on references on self avoiding paths, but I am looking ...

**3**

votes

**0**answers

44 views

### Algebraic property of a transition matrix

Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...

**1**

vote

**0**answers

80 views

### Upper and lower bounds on the entries of a matrix power

Say I have a non-negative square $n\times n$ irreducible stochastic matrix $A$ (i.e., each column sums to 1), for which the following holds:
$$A_{ij} > 0 \iff A_{ji} > 0.$$
I know that no more ...

**0**

votes

**1**answer

44 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

291 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 same ...

**2**

votes

**1**answer

107 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

79 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

149 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

80 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

119 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

60 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

87 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

81 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

94 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

67 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

**0**answers

28 views

### Keeping track of the variance of a Metropolis-Hastings estimator

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces, $p,q$ be probability densities on $(E,\mathcal E,\lambda)$, and $\varphi:E'\to E$ be bijective and $(\mathcal E',\...

**0**

votes

**2**answers

121 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 ...

**1**

vote

**1**answer

115 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 ...

**0**

votes

**0**answers

18 views

### Continuous time-inhomogenous Markov chain from discrete TIMC

Cross-posting the question from math.stackexchange.com:
https://math.stackexchange.com/questions/3478043/continuous-time-inhomogenous-markov-chain-from-discrete-timc

**0**

votes

**1**answer

122 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. ...

**0**

votes

**0**answers

31 views

### V-Norm in Markov Chain Analysis Question

I had a question about the $V$-norm that I often see used in the Markov Chain analysis literature, where $V:X\to [1,\infty)$ is specified, and the norm $|\bullet|_V$ is defined as
$$
|f|_V = \sup_{x\...

**1**

vote

**1**answer

113 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

45 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

85 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

43 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

59 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 ...

**10**

votes

**0**answers

273 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 ...

**1**

vote

**1**answer

90 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

118 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

56 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)...

**0**

votes

**1**answer

79 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

68 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

85 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

**0**answers

34 views

### Derivation of a differential equation from a SDE

Suppose there is a non-homogeneous Markov process with state space $\mathbb{R}_{+}$
driven by this McKean-Vlasov-tipe SDE:
$$ dY_t = a \mathbb{E}[Y_t]\ dt - b\ Y_t\ dt - Y_t\ dN_{aY_t}$$
where $...

**0**

votes

**2**answers

108 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

**0**answers

30 views

### Minimize the asymptotic variance as in Tierney's theorem, but only for a single fixed function

Let $(\Omega,\mathcal E,\mu)$ be a probability space and $\kappa^{(i)}$ be a Markov kernel on $(E,\mathcal E)$. $\kappa^{(i)}$ can be considered as a contractive self-adjoint linear operator on $$L^...

**0**

votes

**1**answer

66 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**

votes

**1**answer

82 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

230 views

### Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?

In the following paper (extended version here), at the beginning of section 3, the authors give two axioms about $\mathcal{A}$. Axiom 1 is about $\mathcal{A}$ being an algebra. I do not see where this ...

**1**

vote

**0**answers

60 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)}\\
& =\...

**2**

votes

**1**answer

327 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

196 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

190 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

99 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 ...