Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
538
questions
2
votes
0
answers
35
views
Including fixed-time transitions into a continuous time Markov chain system
I have system which is mostly described by a CTMC (Continuous-time Markov chain) with a single absorbing state and a large but tractable and sparse transition matrix. However, at a fixed set of "...
0
votes
0
answers
12
views
Understanding relation of 2 dependent, integral equations which are nested in a Bayesian Expectation
I'm trying hard to try understand the recursive nature between two equations in a recent macroeconomics paper, but my question mainly relates to how mathematically such recursive equations can depend ...
3
votes
0
answers
71
views
A stochastic matrix $B = \lambda(\lambda I - A)^{-1}$ such that $B-B^2$ has a non-negative diagonal
I apologize if this is too elementary a question, but I have not been able to make much progress.
Consider a real matrix $A$ with $A_{ij} >0$ for $i \ne j$ and $\sum_{j} A_{ij} = 0$ for each $j$. ...
0
votes
0
answers
19
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
81
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
86
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
61
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
45
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
232
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
3
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
101
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
70
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
143
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
216
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
108
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
70
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
173
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
148
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
51
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
111
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
140
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
150
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
71
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
219
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
157
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
712
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
36
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
118
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
86
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
224
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
48
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
33
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
93
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
97
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
66
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
71
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
104
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
51
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
341
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
83
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 ...
2
votes
1
answer
216
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 ...