Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
100 views

On the exponentiation of a stochastic matrix where the exponent is a function of matrix size

In this question, I asked about any arbitrary stochastic matrix $A(n)$ of the particular form $$A(n) = \begin{pmatrix} 1 & 0 & \cdots & 0\\ x_{21} & x_{22} & \cdots & 0\\ \...
Subhankar Ghosal's user avatar
4 votes
1 answer
242 views

Random walk visiting a cylinder infinitely often

I wonder whether a $d$-dimensional random walk $S_n$, generated by the infinite i.i.d. copies of X given by: $X=e_1=(1, 0, 0, ..., 0)$ (with probability $p_1$) $X=e_2=(0, 1, 0, ..., 0)$ (with ...
Hamid Enki's user avatar
8 votes
7 answers
999 views

One observation of special type of square matrix exponentiation

I was studying the following type of matrices, $$ A = \begin{pmatrix} 1 & x_{12} & \cdots &x_{1n}\\ 0 & x_{22} & \cdots &x_{2n}\\ \vdots\\ 0&\cdots&0&x_{nn} \end{...
Subhankar Ghosal's user avatar
1 vote
0 answers
46 views

Sample complexity of estimating a doubly stochastic matrix

Let $P\in\mathbb{R}^{n\times n}$ be a doubly-stochastic matrix. That is: $$P(x,y)\geq 0,\quad \sum_xP(x,y)=1,\quad \sum_yP(x,y)=1.$$ I would like to know if lower and upper bounds on the sample ...
user134977's user avatar
2 votes
0 answers
84 views

Training an energy-based model (EBM) using MCMC

I'm reading this paper about training energy-based models (EBMs) and don't understand the parameters that we are training for? The part that is relevant to the question is in pages 1-4. Here is the ...
Garfield's user avatar
  • 201
3 votes
1 answer
326 views

Importance resampling with exponential weighting

Suppose that we have $$ \frac{p(x)}{q(x)} \propto \exp(\tau f(x)), $$ where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...
Minkov's user avatar
  • 1,117
3 votes
2 answers
234 views

Is there something like a "self-avoiding Markov chain" on a continuous space?

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants. However, as far as I can see they are ...
0xbadf00d's user avatar
  • 161
0 votes
0 answers
127 views

Approximate range of Radon-Nikodym derivative in a dynamical system

Suppose $(X, G, \Omega, \mu)$ is a dynamical system where $(X, \Omega, \mu)$ is a Borel measure space and $G$ is acting on $X$ such that each group action $x\mapsto g\cdot x$ defines a measurable ...
Sanae Kochiya's user avatar
2 votes
1 answer
161 views

Joint irreducibility and aperiodicity of two independent Markov chains

Let $(X_i)_i, (Y_i)_i$ be two independent Markov chains on Polish state spaces $\mathcal{X}, \mathcal{Y}$ and with kernels $P, Q$. Suppose that they are both $\psi$-irreducible and aperiodic and have ...
Dasherman's user avatar
  • 203
0 votes
1 answer
142 views

Inhomogeneous Markov chains and the product-integral as a solution to the Kolmogorov forward equation

We have a inhomogeneous continous $K$-State Markov chain $X(t)$ with transition intensity matrix $Q(t)$. Therefore its entries are: $$q_{ij}(t)= \lim_{\delta \to 0} \frac{1}{\delta} \mathbb{P}(X(t+\...
Bloble's user avatar
  • 3
0 votes
1 answer
81 views

Skip-free random walks: recurrence and transience

Let us define a one dimensional random walk: for all $n\in\mathbb{N}$ $$ X_n:=\sum_{i=1}^nZ_i $$ with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...
lulli_'s user avatar
  • 1
1 vote
0 answers
26 views

How slowly can one be absorbed in the absorbing phase of the directed percolation universality class?

In absorbing state transitions on a lattice, one often considers "active" and "inactive" sites, with update rules describing how activity spreads or decays. When the lattice sites ...
user196574's user avatar
2 votes
1 answer
107 views

On the distance to the stationary distribution

A Markov Chain $M$ has only one stationary distribution $q$. For distribution $p$, with $D_{TV}(p,Mp)=x$, can we bound $D_{TV}(p,q)$? Clearly, $x=0$ implies $D_{TV}(p,q)=0$. Does general bound hold? ...
gondolf's user avatar
  • 1,483
2 votes
0 answers
48 views

Right spectral gap of vector of two independent Markov chains

Let $(X_i)$ be a stationary Markov chain on $S$ (a potentially uncountable space with a Borel sigma algebra) with stationary distribution $\pi$ and transition kernel $P$. Let $(Y_i)$ be a stationary ...
Dasherman's user avatar
  • 203
2 votes
2 answers
278 views

Polynomial time mixing Markov chain for multimodal distribution

Is there a discrete space Markov chain, starting from a fixed state, whose stationary distribution is a multimodal distribution and that mixes in polynomial time? For example, Ising model on say a ...
Garfield's user avatar
  • 201
1 vote
0 answers
32 views

If $(\kappa_t)_{t\ge0}$ is a Markov semigroup with invariant measure $μ$, under which assumption is $t\mapsto\kappa_tf$ measurable for $f\in L^p(μ)$?

Let $(E,\mathcal E)$ be a measurable space; $(\kappa_t)_{t\ge0}$ be a Markov semigroup on $(E,\mathcal E)$; $\mu$ be a finite measure on $(E,\mathcal E)$ which is subinvariant with respect to $(\...
0xbadf00d's user avatar
  • 161
6 votes
1 answer
362 views

Idempotent splitting for Markov kernels

Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation, $$e(A|x) = \int_X e(...
Tobias Fritz's user avatar
  • 5,775
1 vote
2 answers
204 views

Connection between invariant measure and positive recurrence for continuum state space markov chain

Let $\{ X_n(\omega,x)\}_{n \ge 0}$ be a Markov chain with and underlying probability space $(\Omega,\Sigma,\mathbb{P})$ and state space $X= \mathbb{S}^1$. Suppose this markov chain admits unique ...
Giuseppe Tenaglia's user avatar
6 votes
1 answer
425 views

Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
0 votes
1 answer
92 views

What is the significance of Blumenthal and Getoor's result on the boundedness of paths of a standard Markov process?

In the book Markov processes and Potential Theory of Blumenthal and Getoor we can find the following result: I don't understand the significance of this result. If I don't misinterpret the assertion, ...
0xbadf00d's user avatar
  • 161
4 votes
0 answers
164 views

Random walk on hexagonal lattice. First return to the origin

I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $2n$ that start at the origin $O$ and go back to $O$ but doing so for the first time at step $2n$ (...
A. G's user avatar
  • 245
0 votes
0 answers
55 views

If $\kappa$ is a Markov kernel with density $p$, does it generally hold $p(x,z)=\int p(x,y)p(y,z)\:{\rm d}y$?

Let $(E,\mathcal E)$ be a measurable space and $\kappa$ be a Markov kernel on $(E,\mathcal E)$. Assume that $$\kappa(x,B)=\int_Bp(x,y)\:\lambda({\rm d}y)\;\;\;\text{for all }(x,B)\in E\times\mathcal E$...
0xbadf00d's user avatar
  • 161
0 votes
1 answer
164 views

Constructing Markov chain

Let $(A_1,B_1)$ and $(A_2,B_2)$ be two random variables with the joint distributions $p_{A_1B_1}$ and $p_{A_2B_2}$, respectively. Moreover, we have $$\mathbb{P}[(A_1,B_1)\neq (A_2,B_2)]=\alpha.$$ Then,...
Math_Y's user avatar
  • 311
2 votes
1 answer
173 views

If $X$ is a Markov process, can we find a mild assumption ensuring that $\frac1t\operatorname E_x\left[\int_0^tc(X_s)\:{\rm d}s\right]\to c(x)$?

Let $(E,\mathcal E)$ be a measurable space with $\{x\}\in\mathcal E$ for all $x\in E$ $\mathcal E_b:=\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\}$ $(\kappa_t)_{t\ge0}$ ...
0xbadf00d's user avatar
  • 161
0 votes
1 answer
259 views

Construction of a Markov process with prescribed local behavior and state-dependent jump distribution

Let $(E,\mathcal E)$ be a measurable space $\mathcal E_b:=\left\{f:E\to\mathbb R\mid f\text{ is bounded and }\mathcal E\text{-measurable}\right\}$ $(\kappa_t)_{t\ge0}$ be a Markov semigroup on $(E,\...
0xbadf00d's user avatar
  • 161
1 vote
1 answer
309 views

How can we determine the generator of this Markov process (at least formally)?

Let $(\Omega,\mathcal A)$ be a measurable space; $(E,\mathcal E)$ be a measurable space with $\{x\}\in\mathcal E$; $(Y_t)_{t\ge0}$ be an $(E,\mathcal E)$-valued time-homogeneous Markov process on $(\...
0xbadf00d's user avatar
  • 161
1 vote
0 answers
47 views

What's the autocovariance of 2 concurrent hidden states of a stochastic gaussian walk, using the Kalman filter?

A latent variable evolves as $x_t = x_{t-1} + e_t$ where $e_t$ has a gaussian distribution with 0 mean and a variance which defines the volatility of the overall process. Let $o_t$ be the noisy ...
Nick Gregory's user avatar
3 votes
1 answer
165 views

Carne-Varopoulos bound and stationary measure

Let $\Gamma$ denote the Cayley graph for a finitely generated group $G$, and let $p_n(x, y)$ denote the transition probability that a random walk starting at $x$ reaches $y$ at time $n$. A famous &...
user482846's user avatar
4 votes
1 answer
180 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 ...
user196574's user avatar
2 votes
0 answers
71 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 ...
Clement Moreno's user avatar
4 votes
1 answer
258 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, ...
Garfield's user avatar
  • 201
3 votes
1 answer
370 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 \...
john's user avatar
  • 53
1 vote
1 answer
84 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 ...
Max's user avatar
  • 203
0 votes
1 answer
86 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 ...
Sounak's user avatar
  • 15
1 vote
0 answers
97 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/...
rime's user avatar
  • 435
3 votes
1 answer
300 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 ...
Yihan Zhang's user avatar
1 vote
0 answers
85 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 ...
tattwamasi amrutam's user avatar
1 vote
0 answers
442 views

How could we calculate numerically $\hat{v} = \alpha_{0}(I−P)^{-1}$, as the limit of the recurrence $v(t+1) = v(t)P + \alpha_{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 ...
Ahmed Ibrahim's user avatar
1 vote
1 answer
193 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 ...
Cesare's user avatar
  • 189
4 votes
1 answer
438 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 ...
Matt's user avatar
  • 97
8 votes
1 answer
676 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 ...
Ben Golub's user avatar
  • 1,058
2 votes
0 answers
123 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 ...
Sanae Kochiya's user avatar
0 votes
2 answers
548 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^...
dimoik's user avatar
  • 13
1 vote
1 answer
343 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$ ...
StatisticalMechanic's user avatar
0 votes
0 answers
203 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 ...
Oli Bernet's user avatar
2 votes
0 answers
47 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 ...
Usama's user avatar
  • 21
1 vote
1 answer
212 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}+\...
toni_iva's user avatar
0 votes
1 answer
214 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 ...
Jens Fischer's user avatar
1 vote
0 answers
161 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 ...
dohmatob's user avatar
  • 6,706
8 votes
3 answers
399 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'...
H A Helfgott's user avatar
  • 19.3k

1
2
3 4 5
11