All Questions
Tagged with pr.probability markov-chains
362 questions
2
votes
2
answers
237
views
is this process a Markov one?
Here is the problem I can't solve.
Let $\xi_n$ $(n=1,2,3,\dots)$ be a sequence of i.i.d. random variables on $\mathbb{R}$ with density $p(x)>0$, let $\eta_n=\sum_{i=1}^{n}\xi_i^2$. Define $$\...
- 21
2
votes
3
answers
376
views
Generations until fixation: A nontrivial generalization of a dice convergence problem
In spite of its "recreational" aspect, this question appears to me to be research-level and (I hope) clearly formulated and tagged.
Edit 4/4/20: You can find a related question with the ...
- 7,831
6
votes
1
answer
361
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
- 26k
0
votes
1
answer
203
views
Law of large numbers for Harris recurrent Markov chains
I'm trying to familiarize myself with the details of the proof that the Markov chains produce by the Metropolis-Hastings algorithm have a law of large numbers. I've found a half dozen or more ...
- 2,791
3
votes
3
answers
163
views
A stopping time that gives the metric
Let $\Omega$ a finite metric space with $\forall x,y,z\in \Omega:d(x,y)<d(x,z)+d(z,y)$. Does there exists a continuous-time Markov process $X$ on $\Omega$ such that $$\mathbb{E}_x(T_y)=d(x,y)$$ for ...
- 4,361
2
votes
1
answer
185
views
Entropy rate problem of ergodic Markov process with non-ergodic joint
I have a problem with the entropy rate when two ergodic Markov processes who are independent of each other having a non-ergodic joint. More specifically let us consider two finite-state Markov ...
- 333
0
votes
2
answers
244
views
Spectrum of a Markov kernel acting on $L^2$
Let $P$ be a Markov kernel on a measurable space $(E,\mathcal E)$ admitting an invariant probability measure $\pi$. $P$ acts on $L^2(\pi)$ via $$Pf:=\int\kappa(\;\cdot\;{\rm d}y)f(y).$$ The invariance ...
- 167
2
votes
1
answer
290
views
Uniform upper bound on contraction coefficient w.r.t total-variation metric, of a certain set of block-diagonal Markov kernels
Disclaimer. This is related to another question I've asked on the TCS site https://cstheory.stackexchange.com/q/46097/44644. I'm new to information theory (and other relevant fields). It's even ...
- 6,853
1
vote
1
answer
284
views
Symmetric random walks - bounds on the amount of time spent in a subset $A$?
For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$?
Let $S_n$ be a symmetric random walk on the integers. ...
user145350
1
vote
0
answers
73
views
Reduce the asymptotic variance for a class of Metropolis-Hasting estimates
I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
- 167
1
vote
0
answers
106
views
Show a Poincaré inequality for a Markov kernel and minimize the Poincaré constant
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$ (see definitions ...
- 167
1
vote
0
answers
56
views
Minimizing the rate of geometric ergodicity of a Metropolis-Hastings kernel depending on a parameter
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$.
I want to ...
- 167
1
vote
1
answer
143
views
Comparison of hitting probability of two Markov chains both with only one absorbing state version 2 under stronger condition
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$.
$\text{Pr}\...
- 2,239
1
vote
1
answer
119
views
Comparison of hitting probability of two Markov chains both with only one absorbing state
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have one absorbing state $1$.
Pr$(X^{(1)}_{i+1}=1|X_i=1)...
- 2,239
1
vote
1
answer
170
views
Stationary distribution of Markov Chain with departure
I have a Markov Chain of $N$ states. Such states represent the energy levels in a molecule.
The states' connectivity is as follows:
States $j\in\{0,\ldots,N\}$ transition to $k\in\{\max(j-M,0),...,\...
- 151
0
votes
1
answer
82
views
In smooth stochastic dynamics, if a Lebesgue-like measure is both forward-time and reverse-time stationary, is the measure necessarily incompressible?
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact connected $C^\infty$-smooth manifold. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to ...
- 708
0
votes
1
answer
95
views
If a probability measure is stationary in both forward time and reverse time, does this imply that the measure is incompressible?
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact metric space. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to X$ be measurable ...
- 708
0
votes
2
answers
128
views
Markov with epsilon memory and Quantitative Strong Markov property
We have a process $\{X_{t}\}_{t\geq 0}$ ,with fixed parameter $\epsilon>0$, starting from zero that satisfies
The process is strictly monotone $X_{t+r}-X_{t}>0$ with moments existing $p\in(-\...
- 5,474
0
votes
1
answer
80
views
A question about positive operator pregenerator [closed]
Thank you for reading.
My question was raised up when I tried to prove an example in the book of Liggett(1985), which is in P13 Example 2.3(a).
Here is a link of the page:
https://books.google.com/...
- 385
1
vote
1
answer
174
views
Coupling argument involved in the contracting and mixing properties of the Glauber dynamics for an Ising model
While doing a research work, I had to read about the Glauber dynamics for an Ising model. A wonderful account on this is given in the book Markov Chains and Mixing Times by Levin, Peres and Wilmer.
...
- 367
2
votes
0
answers
321
views
Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?
In Bobkov and Tetali - Modified Log-Sobolev Inequalities, Mixing and Hypercontractivity (extended version Modified Logarithmic Sobolev Inequalities in Discrete Settings), at the beginning of section 3,...
- 105
2
votes
1
answer
409
views
Existence and uniqueness of a stationary measure
This same question was also posted on MSE https://math.stackexchange.com/questions/3327007/existence-and-uniqueness-of-a-stationary-measure.
Recently I have posted the following question on MO ...
- 333
2
votes
0
answers
113
views
Characterizing the relationship between element-wise Markov transitions and the full-conditionals of the stationary distribution
Consider a $p$ dimensional random variable with a discrete support. Consider a Markov transition kernel on the state space that is defined in terms of element-wise transition distributions.
One can ...
- 2,791
1
vote
1
answer
173
views
Can we show that $\mathbb R^{\mathbb N}\ni x\mapsto\bigotimes_{n\in\mathbb N}\mathcal N_{x,\:\sigma^2}$ is a Markov kernel?
Let $\sigma>0$ and $\mathcal N_{x,\:\sigma^2}$ denote the normal distribution with mean $x\in\mathbb R$ and variance $\sigma^2$. From the Ionescu-Tulcea theorem, we know that $$\kappa(x,\;\cdot\;):=...
- 167
1
vote
4
answers
272
views
Probability of traversing all other states and finally landing on one state
This is a cross-post from math.stackexchange.com. There has been no response there.
Given a Markov chain of finite states with constant transition probabilities, what is the method to compute the ...
- 2,239
0
votes
0
answers
83
views
A closed form of mean-field equations
Assume that a system at time t, for example number of costumers in a line at time $t$ which is denoted by $q(t)$, follows a Markov chain with these dynamics (probabilities)
$$P(q(t+\Delta t)-q(t)=1)=\...
user135936
7
votes
2
answers
259
views
Slowest initial state for convergence of finite birth-and-death Markov chains
Consider the continuous-time birth-and-death Markov chain on $\{1,\cdots,n\}$ with all rates equal to $1$. Is it true that the convergence to equilibrium, in total variation distance, is slowest when ...
- 4,653
5
votes
1
answer
199
views
Reference request: When is the variance in the central limit theorem for Markov chains positive?
I'm looking for a reference which gives sufficient conditions for the variance to be positive in the central limit theorem for Markov chains (cf https://en.wikipedia.org/wiki/...
- 153
3
votes
0
answers
88
views
Joint drunkard walks
The drunkard walk is a game where two players have $a$ and $b$ dollars, respectively, and they play a series of fair games (both risking one dollar in each game) until one of them goes broke.
My ...
- 131
0
votes
2
answers
306
views
Lower bounds on discrete time finite Markov chains hitting probabilities
I am interested in some general theorems related to lower bounds on discrete time finite Markov chains hitting probabilities (preferably ergodic chains , but not necessarily ), with references . ...
3
votes
1
answer
226
views
Total offspring of Poisson multitype branching process
A normal branching process $Z_n$ initialized with $Z_0=1$ and offspring generated from $Pois(p),p<1,$ has a total progeny / total off spring distribution
$$X=\sum_{n=0}^\infty Z_n$$
$X\in \mathbb{...
- 315
2
votes
1
answer
994
views
Comparing mixing time of lazy and non-lazy Markov chains
Suppose we have a probability distribution $\pi : X \rightarrow [0,1]$ where $X$ is finite and let $Q : X \times X \rightarrow [0,1]$ be a Markov kernel that is reversible with respect to $\pi$. That ...
- 123
2
votes
0
answers
70
views
If $X^n$ is a sequence of càdlàg processes whose FDDs converge to a continous process $X$, does $X^n$ converge to $X$ in the Skorohod topology?
Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space, $E$ be a complete locally compact separable metric space, $(X^n_t)_{t\ge0}$ be an $E$-valued càdlàg process on $(\Omega,\mathcal A,\...
- 167
2
votes
0
answers
37
views
Exclusion processes from point of view of a tagged particle
I'm interested in the simple exclusion processes on $Z^d$ and the ergodic theorems that can be proved from the point of view of the particle. Ellen Saada proved the following in 1987 (Annals of Prob): ...
- 941
3
votes
1
answer
236
views
Mixing time and spectral gap for a special stochastic matrix
Consider the following dimension stochastic matrix,
\begin{bmatrix}
p & q & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 &...
- 103
4
votes
2
answers
206
views
Reference on a markov chain / Queue
Im looking for a reference that treats the Markov Chain defined by
$$W_i=(W_{i-1}-1)\vee X_i$$
where $X_i\geq 0$ are i.i.d discrete variables. In particular im interested in a reference that treats ...
- 315
0
votes
1
answer
204
views
How is the Cauchy-Schwarz inequality used in the proof of Lyapunov's criterion in the book "Analysis and Geometry of Markov Diffusion Operators"
Let $(E,\mu,\Gamma)$ be a full Markov triple (see definition below), $J\in\mathcal A$ with $J\ge1$ and $g\in\mathcal A_0$. In the proof of Theorem 4.6.2 of the book "Analysis and Geometry of Markov ...
- 167
1
vote
1
answer
305
views
Existence of a Lyapunov function for a log-concave measure
Let $d\in\mathbb N$, $f:\mathbb R^d\to\mathbb R$ be convex with $$\int e^{-f(x)}\:{\rm d}x<\infty\tag1$$ and $\mu$ denote the measure with density $e^{-f}$ with respect to the Lebesgue measure on $\...
- 167
4
votes
5
answers
7k
views
Proof of Bellman optimality equation for finite Markov Decision Processes
This question has already been posed in Cross Validated without receiving a correct formal answer, so I reformulate it here to gain attention of mathematicians. I am referring to chapter 3 of Sutton ...
- 171
1
vote
0
answers
81
views
If $\text P\left[X_2\in B_2\mid X_1\right]=\kappa(X_1,B_2)$ a.s. for all $B_2$, can we select a common null-set over all $B_2$?
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E_i,\mathcal E_i)$ be a measurable space
$X_1:\Omega\to E_1$
$X_2:\Omega\to E_2$ be $(\mathcal A,\mathcal E_2)$-measurable
$\kappa$ ...
- 167
-1
votes
1
answer
370
views
What's the probability of two independent events in time domain?
Suppose there are two independent events A and B. The probability that A or ...
- 29
1
vote
0
answers
79
views
Discrete Markov process on finite interval
Consider an contiguous array of $N$ states, numbered from $1$ to $N$.
At every time step $t$, the process should transition to an adjacent state.
The probability of moving to the right (from state $n\...
2
votes
0
answers
416
views
How can we treat the generator of a discrete-time Markov chain as the generator of a Markov-jump process?
In the popular paper Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms by Roberts, Gelman and Gilks, the authors state (see below) that "in the Skorokhod topology, it does not ...
- 167
3
votes
2
answers
264
views
Probability of one species reaching zero before the other in a Markov process on a 2d lattice
$\textbf{Background}$: Say we've got a two-variable system of stochastic chemical reactions, with quantities $\vec{x}(t) = (x_1(t),x_2(t)) \in \mathbb{N}^2$ evolving according to the following system, ...
- 41
1
vote
0
answers
149
views
Construction of Feller's pseudo-poisson process
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$(Y_n)_{n\in\mathbb N_0}$ be a $(E,\mathcal E)$-valued time-homogeneous Markov chain on $(\...
- 167
3
votes
2
answers
1k
views
Non-backtracking random walk in regular (finite) graphs
I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
- 1,561
1
vote
0
answers
120
views
Existence of Time-Reversed Markov Kernels
Suppose I have a probability measure $\pi$ and a Markov kernel $q$ which leaves $\pi$ invariant, in the sense that
\begin{align}
\int_x \pi(dx) q(x \to dy) = \pi(dy)
\end{align}
Then, a (the) time-...
- 801
1
vote
2
answers
302
views
how to derive stationary distribution of maximal entropy random walk
I was reading the paper 0810.4113v2, burda, which analyzed the stationary distribution maximal entropy random walk on the irregular lattice. I am confused on some of the steps.
Description:
The ...
- 211
2
votes
0
answers
37
views
Reference request: semimarkov processes
What are some good modern introductions to the theory of semimarkov processes? To be clear, by a semimarkov processes, I mean a Markov chain, together with "waiting times" between transitions, the ...
- 505
3
votes
1
answer
97
views
Bounds on $\|(P+\Delta)^n - P^n\|_F$ for stochastic matrices
Let us suppose that $P$ is a stochastic matrix (non-negative matrix with $P \mathbf{1} = \mathbf{1}$).
Let $\Delta$ such that $P + \Delta$ is a stochastic matrix (which means $P + \Delta$ is non-...
- 113