Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
MatEZ's user avatar
  • 31
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^...
Johny B's user avatar
  • 11
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 ...
user521485's user avatar
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 ...
Curious's user avatar
  • 143
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 ...
Mathhead123's user avatar
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 ...
domotorp's user avatar
  • 18.2k
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} := ...
Alex Damian's user avatar
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 ...
matilda's user avatar
  • 90
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, ...
itchidese's user avatar
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 ...
matilda's user avatar
  • 90
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 ...
Iris Allevi's user avatar
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 ...
zemora's user avatar
  • 505
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 ...
Roberto Rozzi's user avatar
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 ...
JayP's user avatar
  • 131
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 ...
πr8's user avatar
  • 688
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 \...
tsnao's user avatar
  • 462
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 ...
yy98's user avatar
  • 11
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$ ...
user avatar
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 ...
user avatar
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 ...
Eubos's user avatar
  • 56
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)...
Michele's user avatar
  • 313
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 ...
Francesco Bilotta's user avatar
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 $...
Matheus Manzatto's user avatar
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-...
Lucas's user avatar
  • 21
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 ...
pzr1988's user avatar
  • 11
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$ ...
koko's user avatar
  • 21
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 ...
hs12's user avatar
  • 11
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, ...
Tiago's user avatar
  • 59
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. ...
user24601's user avatar
  • 165
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 ...
sharpe's user avatar
  • 701
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,...
0xbadf00d's user avatar
  • 141
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 ...
IamHungry's user avatar
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 ...
Francesco Bilotta's user avatar
-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$. ...
lchen's user avatar
  • 459
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 ...
Richard Ben's user avatar
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 ...
Francesco Bilotta's user avatar
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 ...
0xbadf00d's user avatar
  • 141
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$ ...
Austin80's user avatar
  • 111
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 (...
Gregory V.'s user avatar
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 ...
user675763's user avatar
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 ...
Penelope Benenati's user avatar
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 ...
Hausdorff's user avatar
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 ...
Garfield's user avatar
  • 201
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 ...
Sam OT's user avatar
  • 550
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 ...
K. Bountrogiannis's user avatar
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 ...
Sanae Kochiya's user avatar
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, ...
Piyush Grover's user avatar
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 ...
Christophe Leuridan's user avatar
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\\ \...
Subhankar Ghosal's user avatar
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 ...
Hamid Enki's user avatar

1
2 3 4 5
11