All Questions
Tagged with pr.probability markov-chains
362 questions
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. ...
CommunityBot
- 1
3
votes
1
answer
498
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 ...
- 234
0
votes
1
answer
205
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+\...
2
votes
1
answer
228
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, ...
- 2,281
60
votes
10
answers
14k
views
"Surprising" examples of Markov chains
I am looking for examples of Markov Chains which are surprising in the following sense: a stochastic process $X_1,X_2,...$ which is "natural" but for which the Markov property is not obvious at first ...
- 12.3k
4
votes
1
answer
247
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 ...
- 1,897
3
votes
1
answer
340
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_{...
- 1,127
1
vote
0
answers
48
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 ...
- 111
0
votes
1
answer
96
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, ...
CommunityBot
- 1
3
votes
2
answers
277
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 ...
- 8,992
2
votes
1
answer
201
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 ...
- 128k
2
votes
2
answers
302
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 ...
- 6,045
2
votes
0
answers
57
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 ...
- 203
1
vote
0
answers
37
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 $(\...
- 167
9
votes
2
answers
3k
views
Is this a situation where triple mutual information is always non-negative?
Suppose I have three identically-distributed homogeneous continuous-time discrete state space Markov chains $X_1(t), X_2(t), X_3(t)$, $t\geq 0$. They evolve independently but share a common random ...
- 4,713
0
votes
1
answer
262
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,\...
- 167
6
votes
1
answer
482
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$, ...
- 850
0
votes
0
answers
72
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$...
- 167
1
vote
1
answer
337
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 $(\...
- 6,045
1
vote
1
answer
170
views
Comprehensive reference for lumped or projected markov chains
Consider a Markov chain $X_n$ taking values in finite countable set $\mathcal{X}$ with transition matrix $P$. Consider a function $f:\mathcal{X}\to\mathcal{Y}$ inducing a partition $\mathcal{Y}=\{\...
- 105
3
votes
1
answer
220
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 &...
- 2,090
4
votes
1
answer
186
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 ...
- 14.2k
2
votes
1
answer
266
views
Upper bound lemma implies the ergodic theorem for random walks on groups?
Cross-Posted from Math Stackexchange.
Ergodic theorem. A random walk on a finite group $G$ driven by a probability $\nu\in M_p(G)$ is ergodic if $\operatorname{supp}(\nu)$ is not concentrated
on a ...
- 63.9k
6
votes
1
answer
509
views
Approximating Markov chains by Brownian motion
I would like a result along the following lines to be true, but haven't been able to locate it in the literature; pointers would be welcome.
Let $X_{t}$ be a finite-state, irreducible, aperiodic ...
- 1,503
1
vote
1
answer
88
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 ...
CommunityBot
- 1
4
votes
1
answer
276
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, ...
- 6,367
3
votes
1
answer
476
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 \...
- 14.2k
1
vote
0
answers
110
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/...
- 12.9k
1
vote
0
answers
89
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 ...
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 ...
- 128k
8
votes
1
answer
691
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 ...
- 1,989
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 ...
- 307
1
vote
1
answer
410
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$ ...
0
votes
2
answers
804
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^...
- 14.2k
1
vote
1
answer
233
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}+\...
- 14.2k
10
votes
1
answer
1k
views
Bounds on $\|P^{k+1} - P^k\|$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k\gg n$
The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
CommunityBot
- 1
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 ...
- 1
1
vote
0
answers
181
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 ...
- 6,853
8
votes
3
answers
404
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'...
- 14.2k
1
vote
0
answers
332
views
Markov chains with drift
We consider a Markov process $X$ on a finite set $\mathcal{X} (\neq \emptyset)$. Basically, $X$ is associated with a generator of the following form
\begin{align*}
Af(x)=\lambda(x)\sum_{ y\in \mathcal{...
- 721
2
votes
1
answer
101
views
Preservation of the Markov Property under Conditioning
Let $(X_t,Z_t)_t$ be an $\mathbb{R}^{n}\times \mathbb{R}^m$-valued time-homogeneous Markov process on a filtered probability space $(\Omega,\mathcal{F},(\mathcal{F}_t)_t,\mathbb{P})$ with transition ...
- 128k
4
votes
2
answers
835
views
Reference on continuous-time finite state filtering
Problem: I'm working in reliability field and have seen papers written on the topic like process of failures when systems are functioning under unobservable (or observable) Markov-like environment, i....
- 63.9k
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 $$\...
CommunityBot
- 1
4
votes
2
answers
683
views
Random walk on $n$-dimensional cube
Consider a symmetric random walk along the edges of an $n$-dimensional unit cube. At each time step, a particle located at a particular vertex $(a_1, \ldots, a_n)$ moves to an adjacent neighbor each ...
- 8,992
1
vote
0
answers
75
views
Stationary distribution of a Memoryless 2-type priority queue
I have come across the following priority queue, which seems quite natural to me.
A single queue with 2 types of costumers, independent Poisson arrivals and Poisson services.
First class costumers ...
- 14.2k
2
votes
1
answer
134
views
The reference on Markov chains uncovering the power of the subject in a better way for a working macro-economist
This is by no means a research question. But asking here I hope for the most expert opinion.
A friend of mine, who is a working economist, asked me for advice about a book which uncovers wealth and ...
- 774
1
vote
2
answers
228
views
Is a linear combination of Markov generator a Markov generator?
Let $X$ be a compact metric set and $\mathcal{C}(X)$ be the set on continuous real functions over $X$ endowed with the supremum norm $\|\cdot\|_{\infty}$. Let $\Omega_1$ and $\Omega_2$ be two Markov ...
- 1,989
2
votes
1
answer
176
views
Monotonicity of Dirichlet form of Markov chain
Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E,
$$Lf(x)=\...
- 695
-2
votes
1
answer
181
views
Stationary distribution of a weighted directed acyclic graph
Is there any way to calculate the equilibrium (stationary) distribution for a weighted directed acyclic graph?
Some references emphasized adjacency matrix to be symmetric.
https://arxiv.org/abs/1012....
0
votes
1
answer
109
views
Sets of invariant measures of Markov operators
A family of Markov operators $P_i \colon C \to C, i \in I$ is given. Let $V_i$ be the set of the $P_i$-invariant measures. Is there any result in the literature about a necessary and sufficient ...
CommunityBot
- 1