# Questions tagged [markov-chains]

The markov-chains tag has no usage guidance.

536
questions

0
votes

0
answers

16
views

### Proof that Component-wise MH algorithm is invariant w.r.t. target measure

consider a standard situation in Bayesian modelling,
given real vector parameter $\theta=(\theta_1,\dotsc,\theta_n)$ and observations $x$ we derive a posterior distribution $\pi$ with posterior ...

1
vote

0
answers

79
views

### Spectral gap of a Markov operator on $L^2$ with a symmetric $L^\infty$ kernel

Let $I$ be a compact interval, say $I:=(0,1)$, and $k\in L^\infty(I\times I)$ a symmetric Markov kernel, i.e. $k(x,y)=k(y,x)$ and
$$\int_I k(x,y) d y = 1\qquad\mbox{for almost all } x\in I.$$
Let $K:L^...

2
votes

0
answers

85
views

### Embedding a Markov chain in a Markov process

Let $X_{t\ge 0}$ be a Markov process with values in a metric space $(\mathcal{X},d)$ defined on a probabiltiy space $(\Omega,\mathcal{F},\mathbb{P})$ and let $(\tau_n)_{n=1}^{\infty}$ be a sequence of ...

3
votes

0
answers

54
views

### Second eigenvalue of primitive matrix

Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...

0
votes

0
answers

44
views

### Generator of sub-Markov semigroup induces generator of Markov semigroup

I have to show that for the generator $A:L^1 \rightarrow L^1$ of a sub-Markov semigroup and a non-negative $f_* \in L^1$ (with $L^1$ Set of Lebesgue-integrable functions) with $\int_{-\infty}^\infty ...

5
votes

0
answers

230
views

### How to play golf in one dimension?

One-dimensional golf is a function $g$ on $\mathbb R$ such that
$g(x)= 1+\min_\mu E[g(x+N(\mu,c\mu^2))]$ if $|x|>1$ and 0 if $|x|\le 1.$
Here $N$ is the normal distribution, whose mean $\mu$ you ...

10
votes

2
answers

2k
views

### Trace inequality for non-reversible Markov chain

Let $P \in \mathbb{R}^{d \times d}$ be the transition kernel for a Markov chain with stationary measure $\pi$ and define $P^\ast$ to be the time-reversed transition kernel defined by $P^\ast_{ij} := ...

2
votes

0
answers

99
views

### Find a function $f\geq 0$ such that $e^{-t[(x-\partial_x)\partial_x]^2} f$ is not non-negative for some $t\geq 0$

Consider the square of the Ornstein-Uhlenbeck operator $$A=[(x-\partial_x)\partial_x]^2=(x-\partial_x)\partial_x (x-\partial_x)\partial_x.$$ We know that $[(x-\partial_x)\partial_x]^2$ cannot be a ...

0
votes

1
answer

64
views

### Asymptotic variance for averages of trajectory functionals of Markov chain

I am looking for references on theory for convergence rates of ergodic averages of a Markov chain in the more general setting where the functional is over multiple states or even a whole trajectory, ...

0
votes

0
answers

46
views

### Reference needed for powers of semi-group generators

Let $\mathcal{L}$ be the infinitesimal generator of a Markov semi-group. I am looking for references that study powers of $\mathcal{L}$; i.e. $\mathcal{L}^n$, for $n\in\mathbb{N}$.
For example, if the ...

2
votes

1
answer

137
views

### Metropolis-Hastings kernel in measure theory

I'm facing difficulties in formulating the Metropolis-Hastings kernel for a specific problem where I need to sample from a probability distribution involving both discrete and continuous degrees of ...

1
vote

1
answer

214
views

### Question about the proof of Propp-Wilson algorithm in Olle Häggström's book

Update: Oops! This is a stupid question and should be closed. The definition of the probability space that contains events $A_i$ requires using a single random stream.
I have difficulties ...

0
votes

0
answers

105
views

### Calculating the expected hitting time of a specific birth and death chain

I am working with a specific birth and death chain, defined as follows.
Consider a set of states $X = \{0,1,2,...,n\}$, where $x^* \in (0,n)$ is a recurrent state. Transition probabilities are defined ...

3
votes

1
answer

69
views

### Rate of convergence for Markov chain in random environment

Let $(\Omega,\mathfrak{F},\mathbb{P})$ be a probability space and $\sigma:\Omega\to\Omega$ be an ergodic, invertible and measure preserving transformation. Consider a family of column stochastic ...

0
votes

0
answers

39
views

### Characterising optimal majorising Lyapunov function for Markov semigroup

Fix a space $\mathcal{X}$, a Markov process on that space with infinitesimal generator $L$, and a positive function $g : \mathcal{X} \to \mathbf{R}_+$. I don't want to assume too much more about the ...

2
votes

0
answers

170
views

### A few questions on Feller processes

Update. Most of my questions have been answered in the comments. I am adding these answers to the post.
There are at least three definitions of Feller semigroup and the corresponding processes: $C_0 \...

1
vote

0
answers

51
views

### Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph

Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...

2
votes

1
answer

72
views

### Conditions for absorption

Let $X$ be a Markov chain with countable state space $S$ and transition kernel $P$, and let $h \colon S \to [0,1]$ be a sub-harmonic or super-harmonic function. Assume that for all $\varepsilon >0$ ...

1
vote

1
answer

137
views

### Expected time to absorption for Markov chains

Let $X$ be a Markov chain with countable state space $S$ and transition kernel $P$, and let $ T = [ z \in S : \ P(z,z) = 1 ]$. Let $\tau = \inf [ k \geq 0 : X_k \in T ]$ and assume that $ \mathbb{E}^x ...

3
votes

0
answers

50
views

### Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce

Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation?
I've been unable ...

1
vote

1
answer

108
views

### Lipschitz-type inequalities for Markov kernels

Let $K(\cdot\mid\cdot)$ be a Markov kernel. For a measure probability $\mu$, denote by $\mu K$ the probability measure induced by $K$ and $\mu$, i.e. $(\mu K)(A):=\int_\Omega \mu(d\omega)K(A\mid\omega)...

0
votes

0
answers

136
views

### Markov process with time varying transition kernels

I cross post this question from StackExchange as it may be more appropriate.
I am interested in studying the evolution of a variable $\alpha_t\in [0,1]$ governed by the following stochastic dynamical ...

3
votes

0
answers

148
views

### Local dimension of stationary measures for iterated function systems with an expanding map

Consider the iterated function system (IFS) $X_n$ on $I = [0,1] $generated by the functions $\Phi = \{f_1,f_2,f_3\}$ and the probability vector $P = (p/2,p/2,1-p),$ where:
$f_1,f_2: I\to I$, where $...

2
votes

0
answers

73
views

### Expected number of steps until a queue of $n$ people has passed all $n$ ordered tests consecutively

We are given a queue of $n$ people $\{p_1, \ldots, p_n\}$. They each have to pass $n$ exams $\{t_1, \ldots, t_n\}$. For simplicity we can "draw" the setting in the following way:
$$[t_n,t_{n-...

1
vote

0
answers

70
views

### Bounding expectation of switching stochastic process

I am analyzing the behavior of an 1D stochastic dynamic system, where the state can vary randomly within a small magnitude. However, when the state deviates too much from zero, its expected magnitude ...

2
votes

0
answers

204
views

### Ball games: How to allocate $N$ balls into $M$ boxes so as to maximize the expected number of taken balls

Consider the following ball games, which looks like very intuitive and simple but I have tried for a long time.
Assuming we have $M$ identical boxes and $N$ identical balls, we distribute these $N$ ...

1
vote

0
answers

47
views

### Convergence of random variables based on shifts of a markov chain

Suppose we have a discrete time (not necessarily stationary) Markov chain $X=(X_0,X_1,X_2,\dots)$ on $(\Omega, F)$. We assume $X$ is Harris ergodic with an invariant distribution.
Suppose we have a ...

3
votes

1
answer

149
views

### Quantitative version of ergodic theorem in Markov chains

Consider an irreducible Markov chain $X_t$ with finite state space $E$, and unique invariant measure $\pi$. Fix a function $V:E\to\mathbb R$ such that $E_\pi[V]=0$. The ergodic theorem tells us that, ...

9
votes

2
answers

682
views

### Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain

I posted the following question on MSE, feeling that it perhaps isn't research level mathematics, but didn't get any bites. So, I am crossposting here.
The following ergodic theorem is well known.
...

1
vote

0
answers

35
views

### On a generator of a continuous-time Markov chain

Let $S$ be a countable set with discrete topology and let $X=(\{X_t\}_{t \ge 0},\{P_x\}_{x \in S})$ be a continuous-time Markov chain on $S$. We assume that each $x \in S$ is a exponential holding ...

2
votes

0
answers

111
views

### Can a diffusion process admit an invariant measure with a non-differentiable density?

The precise domain of the generator $A$ of an Itō diffusion on a Hilbert space $H$ (assume $H=\mathbb R^d$, if that's easier for you to work with) can usually not be determined explicitly$^1$. Usually,...

4
votes

1
answer

85
views

### The canonical path method for continuous-time Markov chains on a countable state space

I wonder if anyone knows a research article that uses the canonical path method (or congestion ratio) to show that a Poincare inequality holds (see the images below) for a continuous-time Markov chain ...

3
votes

1
answer

215
views

### "Ergodic theorem" for Markov kernels

Consider a discrete time Markov chain $(X_t)$ on a finite state space $\mathcal{S}$, with transition matrix $P$. Assume that the chain admits a stationary distribution $\pi$, which I will identify ...

-1
votes

1
answer

47
views

### Markov chain to solve a particle fusion problem

A sequence of elementary particles arrive at Poisson rate $r$ to a system. A pair of elementary particles can be fused into a level-$1$ particle. The fusion process succeeds with probability $p_0$. ...

0
votes

0
answers

32
views

### How to find lower bounds of a modified mixing time (defined below) with respect to spectral of a finite Markov chain?

I am focused on a time-homogeneous continuous-time Markov chain with a finite state space $\mathcal{X}$, whose Markov kernel is $K$ and the corresponding semigroup is $H_t=e^{-t(I-K)}$. The invariant ...

1
vote

1
answer

92
views

### Asymptotic behavior of a Markov process on the set of $\{0,1\}$-polynomials

This question is cross-posted from https://math.stackexchange.com/questions/4711799/asymptotic-behavior-of-a-markov-process-on-the-set-of-0-1-polynomials
I am trying to study the asymptotic behavior ...

1
vote

0
answers

93
views

### Concatenation of Markov processes and independence

In chapter 14 of Sharpe's General Theory of Markov Processes the concatenation of Markov processes $X^1$ and $X^2$ is described. I've posed the relevant part at the bottom of this post.
It is rather ...

1
vote

0
answers

64
views

### Reference for the asymptotic mixing time of the random walk on the cycle

In Diaconis's book Group Representations in Probability and Statistics, Chapter 3C, there are explicit computations for the mixing time of the random walk on the cycle graph $\mathbb{Z}_{p}$, with $p$ ...

1
vote

0
answers

70
views

### Time-inhomogeneous Krylov-Bogoliubov Existence Theorem

I am interested in what is known about the application of the Krylov-Bogoliubov existence theorem to the time-inhomogeneous case, especially as it relates to an underlying random dynamical system (...

3
votes

1
answer

98
views

### Comparison of time until absorption for two absorbing Markov chains

Let $\{X_t, t \geq 0\}$ and $\{X_t', t \geq 0\}$ denote two markov chains on the same state space $\{1, ..., n+1\}$ with transition probability matrices $P$ and $P'$ respectively. Suppose that both ...

0
votes

0
answers

73
views

### Convergence bounds for ergodic random walk

We are given a simple connected graph $G(V,E)$, where $V$ and $E$ denote the vertex and edge sets respectively. Let $G'(V,E')$ be the graph generated by $G$ by adding one self-loop edge for each ...

1
vote

0
answers

40
views

### Langevin dynamics or stochastic gradient flow for grand canonical ensemble

We know that for a measure exp(-U(X)) (canonical ensemble), we can use the dynamic dX=-DU(X)+ noise to sample the measure as t goes to infinity.
Is there any dynamic corresponding to the grand ...

0
votes

0
answers

50
views

### About cutoff for quasi-random graphs

In this paper by Hermon, Sly and Sousi about mixing time of a random walk on a random graph, there is a concept of $\textit{regeneration edges}$ which I'm trying to understand. This is defined in page ...

3
votes

1
answer

332
views

### Spectral Radius and Spectral Norm for Markov Operators

My question concerns differences between the spectral radius $\rho$ and norm $\| \cdot \|$ of Markov operators in infinite-dimensional Banach spaces. This is far from my area of expertise, that is ...

1
vote

0
answers

81
views

### Derive a closed-form expression of this recursive formula

$$\begin{equation}
S(r,k) = f(r)S(0,k-1) + g(r)S(r+1,k-1)
\end{equation}\ ,$$
where $r=0,1,2,\dots$ and $k=1,2,3,\dots$ . Also, $0<f(r)<1$ is an increasing function and $0<g(r)<1$ is a ...

0
votes

0
answers

31
views

### Prove the explicit form of the ratio function in a Markov Chain

Let $(A_M^{\mathbb{Z}_+}, \Omega, P, \lambda)$ be a Markov Shift where $A$ is a finite alphabet set, $M$ is the admissibility matrix, $P = [P_{i, j}]_{i, j\in A}$ is a stochastic matrix that is ...

2
votes

1
answer

215
views

### When is a stationary measure of a Markov chain "exponentially localized"?

Here exponentially localized can be thought in a non-rigorous manner as a measure that is mostly supported on a sparse number of nodes.
Some intuition can gained by thinking about a diffusion process, ...

0
votes

1
answer

46
views

### Diameter of the range of composition of random maps on the circle

My questions are related to the paper https://hal.science/hal-03933493v1 (accepted with corrections in Ergodic Theory and Dynamical Systems).
I fix an irrational number $\theta \in [0,1[$. I define ...

0
votes

0
answers

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

4
votes

1
answer

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