# Questions tagged [markov-chains]

The markov-chains tag has no usage guidance.

467
questions

4
votes

1
answer

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

2
votes

0
answers

63
views

### Chow's theorem for time one flows

Chow's theorem gives a criterion for the reachable set of the points of a manifold $M$ to be full. Specifically, if we have a distribution $D$ whose iterated commutators span the tangent bundle then ...

4
votes

1
answer

119
views

### About non-reversible Metropolis Hastings Markov chain

I am reading a paper about constructing a non-reversible Metropolis Hastings Markov chain from a reversible one as described at a high level in paragraph $3$ of page $1$.
But I don't understand how, ...

0
votes

0
answers

39
views

### Can we describe the transition affected by the measurement of a quantum mechanical observable in the language of probability theory?

Consider a quantum mechanical system $S$ with the state space being given by a $\mathbb C$-Hilbert space $H$. It is assumed each physically measurable quantity $\mathcal A$ is described by an ...

3
votes

1
answer

141
views

### Harmonic function and Markov chain

Let $X=(X_k)_{k \in \mathbb{N}}$ be a Markov chain with countable countable state space $S$ and transition matrix $P.$
Let $\mathcal{T}$ be the tail $\sigma$-field of $X:\mathcal{T}=\bigcap_{k \in \...

1
vote

1
answer

72
views

### Stationary and limiting distributions

Consider a CT Markov Process $X=(X_t)_{t\geq0}$ with state space $E\in\mathbb{R}^N$. Are there any general conditions under which a stationary distribution $\pi$ for $X$ is also a limiting ...

0
votes

0
answers

19
views

### Does the best stochastic stationary policy has the same optimal cumulative reward of an finite horizon MDP as a deterministic stationary policy?

I have this question when reading Gergely et al (2014)'s paper.
Let me define the question.
Definition: A online learning in MDP problem up to time $T$ consists of $(S,A,P,d_1,R)$
$S$: state space. $...

0
votes

1
answer

37
views

### Recurrence criterion for non-reversible random walks on general infinite (locally finite) graph with unequal edge weights

Can someone please provide a reference (starting point) for analysing recurrence/transience of random walks on graphs with general edge weights? Looking into random walks that are known to be NOT ...

1
vote

0
answers

67
views

### Birth and death process $M/M/\infty$

I was reading about continuous time Markov chains, when I met for the first time the theory of queue processes. In particular, I considered the following situation which I found on Wikipedia, called M/...

3
votes

1
answer

119
views

### Concentration of very dependent Markov chains

Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...

1
vote

0
answers

75
views

### Understanding the statements of Theorem 5.5 and Lemmas 5.6, 5.7 and 5.8 from a French paper by Yves Guivarc’h and Émile Le Page

I would like to understand the statement and the proof Theorem 5.5 just for the special case when $X$ is a single point from the paper “Simplicité de spectres de Lyapounov et propriété d’isolation ...

1
vote

0
answers

327
views

### how could we calculate numerically $\hat{v} = α_{0}(I −P)^{-1}$, as the limit of the recurrence $v(t +1) = v(t)P +α_{0}$?

I'm working with my colleague to introduce a potential therapeutic model. We use the framework of adaptive dynamics. But we are stuck at some steps of the continuous-time Markov chain.
In the appendix ...

1
vote

1
answer

158
views

### Identity for special case of Markov chain

Consider $P(X,Y)$ discrete and $Z = f(Y)$ with $f$ deterministic. The function $f$ identifies a partition of the elements of the alphabet $\mathcal{Y}$ of $Y$. Each outcome $z \in \mathcal{Z}$ is a ...

3
votes

1
answer

221
views

### Probability that two walkers will meet on a graph

Consider two independent continuous random walks on a graph $G$ with adjacency matrix $A$. I am interested in the probability that the two walkers will ever meet.
When the graph is a $k$-regular ...

0
votes

0
answers

21
views

### $\varphi$-irreducibility of random walk on a half line

The book "Markov chain and stochastic stability" states the following proposition:
The discrete-time random walk $\Phi=\{\Phi_n\}$ on the half line $[0,\infty)$ with increment variable $W$ ...

8
votes

1
answer

610
views

### Probabilistic proof for derivative of invariant distribution of a Markov chain

Let $P$ be an irreducible Markov matrix, and $\pi$ its stationary distribution. Let $D$ be a perturbation matrix which is zero except for two entries in row $r$:
$$D_{rg}=+1 \qquad D_{r\ell}=-1.$$
Let ...

2
votes

0
answers

88
views

### Probability of a finite cylinder set in a free group

Let $\mathbb{F}_n$ be the free group (each elemen is in its reduced form) generated by the set $\Sigma_n = \{a_1, a_2, \cdots, a_n, a_1^{-1}, a_2^{-1}, \cdots, a_n^{-1}\}$ and let $e$ denote the ...

0
votes

2
answers

178
views

### Convergence of stationary distributions of a sequence of Markov Chains

I fairly new in the field of Stochastic Processes and Markov Chains so excuse my ignorance.
My question is: If we have a sequence of Markov chains such that each one has a stationary distribution $\pi^...

1
vote

1
answer

252
views

### Occupation times for two-state Markov processes

Consider a two-state Markov process in continuous time, with states labelled $A$ and $B$. The transition rates for going from state $A$ to $B$, and state $B$ to $A$ are $\alpha$ and $\beta$ ...

0
votes

0
answers

80
views

### Canonical Markov process and abstract Markov process

I have the following question:
Why do some books work with the canonical Markov process instead of just the abstract one, as from my point of view they both share exactly the same properties in terms ...

2
votes

0
answers

39
views

### Covariance of an exclusion process

In Erhard and Hairer's recent paper, they say that the covariance of exclusion process is given by the discrete Heat Kernel (page 61, paragraph following equation 4.11). I have not been able to make ...

1
vote

1
answer

170
views

### Random walks on Galton–Watson trees

I am working on a paper of Elie Aidekon : ‘Speed of the biased random walk on a Galton–Watson tree’ and have a question about one transformation in a proof:
\begin{align}
& 1+\frac{1}{1-\lambda}+\...

0
votes

1
answer

86
views

### Mixing time for random walk on graph with $k$ loops on each vertex

I try to find an upper bound for the mixing time of a random walk $S$ on a connected graph $L=(V,E)$ which has $k<\min_{v\in V}d(v)$ loops at every vertex. The transition probabilities of this ...

1
vote

0
answers

120
views

### Random walk on 2d lattice with obstacles

Consider a random work on $L=\mathbb Z^2$ endowed with obstacles (i.e each cell $(x,y)$ of $L$ may contain a obstacle, i.e the random walk halts whenever it hits such a cell). Let $P(x,y) = 1$ if cell ...

8
votes

3
answers

378
views

### All two-point correlations equal to $0$, three-point correlation not $0$?

Let $a_1,a_2,a_3,\dotsc \in \{-1,1\}$ be a sequence. Suppose that, for all $j>0$ and all
$\epsilon, \epsilon'\in \{-1,1\}$, the proportion of $n\geq 1$ such that $(a_n,a_{n+j}) = (\epsilon,\epsilon'...

0
votes

0
answers

41
views

### Concentration of function of Markov frequencies

Let $S=\{1,2,...,n\}$ be a finite set of states and $\{X_t,1\le t\le T\}\subset S$ be a Markov chain with stationary distribution $\pi=(\pi_1,...,\pi_n)$. For $1\le i\le n$, denote by $F_i$ the number ...

1
vote

1
answer

104
views

### Factorizing the doubly stochastic matrix where all entries are equal such that the factors are all convex combinations of few permutation matrices

Let $N_{n}=(1/n)_{i=1,j=1}^{n}$ be the $n\times n$-matrix where all the entries are equal.
Suppose $n>0$. Let $\delta_{n}$ be the least natural number such that $N_{n}$ can be factored as $N_{n}=A_{...

2
votes

1
answer

163
views

### How quickly can irreducible aperiodic convex combinations of permutation matrices converge to the stationary distribution?

Recall that a doubly stochastic matrix is a square matrix with non-negative entries where the sum of each row and the sum of each column is 1. The Birkhoff-von Neumann theorem states that every doubly ...

2
votes

0
answers

167
views

### Convex combinations $A$ of $n\times n$ permutation matrices such that every entry in $A^{k}$ is $1/n$

Recall that a doubly stochastic matrix is a square matrix $A$ with non-negative entries such that the sum of each row is $1$ and the sum of each column is $1$. The Birkhoff-von Neumann theorem states ...

0
votes

0
answers

78
views

### Is there a Feller Markov process without ergodic measure?

It is a well known fact that a Markov process with the Feller property $\{ x_m\}_m$ whose state space $X$ is compact admits at least one stationary measure (Krilov-Bogoliubov).
It is also known that ...

1
vote

0
answers

227
views

### Markov chains with drift

We consider a Markov process $X$ on a finite set $\mathcal{X} (\neq \emptyset)$. Basically, $X$ is associated with a generator of the following form
\begin{align*}
Af(x)=\lambda(x)\sum_{ y\in \mathcal{...

0
votes

0
answers

32
views

### Finding the stable state of a Markov-chain using unequal sampling

Given a set of $N$ states that each have a probability of moving from one state to another state (or even back into the same state), we can construct a 2 dimensional matrix of size $N\times N$, where ...

2
votes

1
answer

61
views

### Preservation of the Markov Property under Conditioning

Let $(X_t,Z_t)_t$ be an $\mathbb{R}^{n}\times \mathbb{R}^m$-valued time-homogeneous Markov process on a filtered probability space $(\Omega,\mathcal{F},(\mathcal{F}_t)_t,\mathbb{P})$ with transition ...

0
votes

1
answer

102
views

### How to detect, track and map a Markov chain

You are receiving a time series whose elements belong to a finite set. Assume the time series is distributed as a Discrete-Time Markov Chain. You receive one element at each time step.
For each time ...

2
votes

0
answers

63
views

### Pagerank Markov chain reductions

In short: if a Markov chain models a (generalized) pagerank, is it always possible to remove any of its state and obtain a Markov chain that models a pagerank close to the initial one?
Full details.
...

3
votes

2
answers

307
views

### Random walk on $n$-dimensional cube

Consider a symmetric random walk along the edges of an $n$-dimensional unit cube. At each time step, a particle located at a particular vertex $(a_1, \ldots, a_n)$ moves to an adjacent neighbor each ...

0
votes

0
answers

66
views

### Methods to find the spectrum of an operator

Suppose we have a bounded, self-adjoint operator $T$ on a set of functions $\mathcal{F}$. What kinds of methods are there to find the spectrum of $T$?
Here is the setting I'm wondering about: consider ...

1
vote

0
answers

43
views

### The rate of convergence of Markov chain to stationary distribution

Let $X_t$ is Markov chain with transition rates $c: G \times G \rightarrow [0: +\infty)$, where $c(x, y) > 0$, $c(x, x) = -\sum_y c(x, y)$ for $x \neq y$. If $\mu_t(x)$ is the distribution of chain ...

3
votes

0
answers

74
views

### Rate of convergence of sojourn times of Markov chains

Let $(X_0,X_1,\dots)$ be a time-homogeneous Markov chain with finite state space $\Omega$.
Assume that $(X_0,X_1,\dots)$ is irreducible and aperiodic and let $\pi$ be its stationary distribution.
By ...

1
vote

0
answers

70
views

### Stationary distribution of a Memoryless 2-type priority queue

I have come across the following priority queue, which seems quite natural to me.
A single queue with 2 types of costumers, independent Poisson arrivals and Poisson services.
First class costumers ...

2
votes

1
answer

119
views

### The reference on Markov chains uncovering the power of the subject in a better way for a working macro-economist

This is by no means a research question. But asking here I hope for the most expert opinion.
A friend of mine, who is a working economist, asked me for advice about a book which uncovers wealth and ...

6
votes

1
answer

168
views

### Perron-Frobenius and Markov chains on countable state space

The following question naturally arises in the theory of Markov chains with countable state space to which I would be curious to know the answer:
Let $A:\ell^1 \rightarrow \ell^1$ be a contraction, i....

1
vote

2
answers

151
views

### Is a linear combination of Markov generator a Markov generator?

Let $X$ be a compact metric set and $\mathcal{C}(X)$ be the set on continuous real functions over $X$ endowed with the supremum norm $\|\cdot\|_{\infty}$. Let $\Omega_1$ and $\Omega_2$ be two Markov ...

-2
votes

1
answer

70
views

### Stationary distribution of a weighted directed acyclic graph

Is there any way to calculate the equilibrium (stationary) distribution for a weighted directed acyclic graph?
Some references emphasized adjacency matrix to be symmetric.
https://arxiv.org/abs/1012....

1
vote

0
answers

82
views

### Stationary distributions of convex combination of stochastic matrices

Consider two irreducible finite state Markov chains with transition matrices $A,B\in\mathbb{R}^{n\times n}$.
Let $x$ and $y$ be the unique stationary distributions of $A$ and $B$, respectively.
Now ...

1
vote

0
answers

33
views

### Markov chains with “clustered” stationary distributions

Are there any canonical or well-known Markov chains whose stationary distributions are basically clustered into two or more components? Obviously, it is easy to create one, but I’m wondering if there ...

1
vote

0
answers

24
views

### Estimation of probability matrix from samples at different time intervals

I am given discrete-time Markov chain that evolves on a finite subset $\{1,\dots,n\}$. This Markov chain is time-homogeneous and has a transition matrix $P$ that I want to estimate.
Let $X_t$ be the ...

2
votes

1
answer

141
views

### Monotonicity of Dirichlet form of Markov chain

Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E,
$$Lf(x)=\...

0
votes

0
answers

63
views

### Constrained MDP

I have a question that is an extension of this one.
My question is: Can we say that for every policy, there exists a deterministic policy in case of a finite-state, finite-action infinite-horizon ...

1
vote

0
answers

100
views

### Harnack inequalities for Markov chains

We consider a (continuous time) Markov chain $X=(\{X_t\}_{t \ge 0},\{P_x\}_{x \in V})$ on a finite set $V$. We assume moreover that $V$ is embedded into $\mathbb{R}^d$. The generator $\mathcal{L}$ of $...