Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 151
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 ...
user avatar
  • 383
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 \...
user avatar
  • 53
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 ...
user avatar
  • 193
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. $...
user avatar
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 ...
user avatar
  • 3
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/...
user avatar
  • 395
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 185
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 ...
user avatar
  • 125
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$ ...
user avatar
  • 1
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 ...
user avatar
  • 1,058
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 ...
user avatar
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^...
user avatar
  • 13
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 21
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}+\...
user avatar
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 ...
user avatar
  • 103
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 ...
user avatar
  • 5,566
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'...
user avatar
  • 16.7k
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 ...
user avatar
  • 21
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_{...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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{...
user avatar
  • 703
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 143
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 ...
user avatar
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 ...
user avatar
  • 31
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 ...
user avatar
  • 61
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 ...
user avatar
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....
user avatar
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 ...
user avatar
  • 433
-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....
user avatar
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 ...
user avatar
  • 179
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 ...
user avatar
  • 3,668
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 ...
user avatar
  • 542
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)=\...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 703

1
2 3 4 5
10