All Questions
Tagged with pr.probability markov-chains
362 questions
0
votes
0
answers
72
views
Invariant measures for a renewal process driven by Interarrival times bounded away from zero
Good morning, I apologize in advance if my question sounds too basic but after some research I was unable to come up with satisfactory answers to my doubts.
I am currently studying a model which ...
- 277
2
votes
0
answers
74
views
Random contractions and contractions on the space of measures
Let $(S,d)$ be some separable and complete metric space, and let $\mathbb{F}$ be some collection of functions from $S$ to $S$. Endow $\mathbb{F}$ with a suitable sigma algebra such that everything I ...
3
votes
2
answers
436
views
Central limit theorem for weak dependent bernoulli random variables
Suppose $\epsilon_1,\epsilon_2,...$ are i.i.d bounded random variables with compact support. Let $X_k=g_k(\epsilon_k,...,\epsilon_1)$ be Bernoulli random variables with the covariance between $X_i$ ...
- 339
1
vote
1
answer
65
views
Transition of probability in duality and its properties
Let $(E,\mathscr{E})$ be a measurable space. Two transition of probabilities
$p, q\colon E\times\mathscr{E}\to [0,1]$ are said to be in duality relative to
a probability measure $m$ if for every ...
- 95
4
votes
2
answers
261
views
Probability question about random shuffling of piles of rocks
I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...
- 41
3
votes
1
answer
343
views
Positive and Null recurrence of Markov Chains on a General State Space
Suppose $X_n$ is an irreducible, aperiodic and Harris recurrent Markov chain. It is well known that in this case, $X_n$ has a stationary distribution $\pi$.
Are there any conditions that are ...
- 339
1
vote
1
answer
75
views
Measurability of kernel on generating set
Suppose $(X, \Sigma_X)$ and $(Y, \Sigma_Y)$ are measurable spaces such that $\Sigma_Y$ is generated by a set $B$.
Suppose $k : X \times \Sigma_Y \to [0, 1]$ has the property that $k(x, -)$ is a (...
- 239
6
votes
0
answers
608
views
'Permutation Coupling' for Markov Chains
Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a doubly stochastic matrix $P$. The double-stochasticity guarantees that ...
- 801
2
votes
1
answer
187
views
Stationary distribution for a Markov Chain on an uncountable space
Suppose $X_n$ are i.i.d. random variables on $\mathbb{R}$ with compact support, and define the Markov chain $Y_n=X_n +\frac{1}{Y_{n-1}}$ on $\Omega=\mathbb{R}\cup \{\infty\}$. Does the chain $Y_n$ ...
- 339
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}=\{\...
- 133
2
votes
1
answer
167
views
Concentration of emperical conditional probability
Assume sequence $(X_1,X_2, X_3, \ldots)$ is a first-order Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define emperical ...
- 33
1
vote
1
answer
198
views
Does marginal Markov sequences imply jointly Markov property?
Assume sequence $(X_1,X_2, X_3, \ldots)$ is Markov sequence of real random variables where $X_i \in \mathcal{X}$ for some alphabet $\mathcal{X}$ of finite size $k$. Define random variable $Y_i = (X_{i-...
- 33
3
votes
0
answers
106
views
Find the generator of a markov process with constant decay and exponential jumps
Suppose we have a continuous time Markov process $(X_t)_{t\in [0,\infty)}$. This Markov process represents the queue length in amount of work left, therefore its state space is given as $S = [0,\infty)...
- 277
2
votes
1
answer
232
views
If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?
Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
- 2,185
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 ...
- 1,037
3
votes
2
answers
140
views
Extinction of a Markov process with strong drift towards (a neighbourhood of) the absorbing state
Let $(X_t)_{t\in\mathbb{R}\geqslant 0}$ be a Markov Jump Process on a discrete state space $S\cup \{0\}$, with $0$ an absorbing state. If $T_0$ is the hitting time of $0$, I want to prove that
$$ \...
- 203
3
votes
3
answers
2k
views
Proof of the existence of an optimal MDP with a stochastic reward signal?
I'm following Sutton's book on Reinforcement Learning, and he casually states that "There is always at least one policy that is better than
or equal to all other policies" for a given finite MDP. This ...
- 133
0
votes
0
answers
169
views
Behaviour of a Markov Chain, given a Lyapunov condition
I'm reading this notes from Martin Hairer about convergence of Markov Processes (on a discrete state space $S$ and in continuous time). On page 12, before presenting the so-called "Harris Theorem", ...
- 203
1
vote
1
answer
561
views
What do you call a Markov kernel continuous w.r.t. the weak topology?
Let $X$ and $Y$ be Polish spaces and $K$ a Markov kernel from $X$ to $Y$. That is, $K$ is a mapping $X \times \mathcal{B}_Y \rightarrow [0,1]$ (where $\mathcal{B}_Y$ is the $\sigma$-algebra of Borel ...
- 1,368
9
votes
0
answers
239
views
Is the P.M.F. of the first return time of a random walk monotone?
Suppose $X_1,X_2,\ldots$ are i.i.d. $\mathbb Z$-valued random variables such that the random walk
$$S_n=\sum_{i=1}^nX_i$$
is recurrent with some period $k\geq1$ (i.e., $\Pr[S_n=0]>0$ if and only if ...
- 891
2
votes
0
answers
102
views
Verifying if Markov process's dependency on time is not random
I am simulating two objects on a grid, and checking how long they can run until the two objects meet. The two objects move randomly, and choose any block (up, down, left, right) randomly. If the side ...
- 21
1
vote
1
answer
127
views
Almost certain extinction for a Markov Jump Process
I'm studying a simplification of a biological neuron model with $n$ neurons. We are describing the evolution of the membrane potential of each neuron. Let $(X_t)_{t\geq 0}$ be a Markov Jump Process in ...
- 203
4
votes
1
answer
176
views
Random Walk with "Forward Dependency"
Let $\{X_t\}_{t=-\infty}^{\infty}$ be a sequence of random variables. We are interested in a "random walk" (or more generally, a random field) that can be characterized by
$$
X_t ~|~ X_{t-k}, \ldots, ...
- 1,127
3
votes
0
answers
115
views
Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position
I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees.
Consider a 1D random walk on the integers, starting at the origin, ...
- 101
4
votes
0
answers
589
views
Optimal transport between two distributions in a Markov chain
In a previous question, given an ergodic Markov chain, I'm interesting in sampling as short a path as possible with prescribed distributions for its endpoints. In a comment, I propose that the ...
- 6,853
2
votes
0
answers
159
views
Distribution of path probabilities for a finite absorbing Markov chain
I am interested in the distribution of path probabilities for a finite
absorbing (but otherwise well behaved) Markov chain. Has this topic
been considered in the literature?
A bit of Googling ...
- 15.4k
1
vote
1
answer
404
views
Does Irreducibility holds for the Ergodic non-stationary Markov chain?
In the stationary case, I know that if the chain is irreducible and aperiodic, it is Ergodic. But in the non-stationary case, i can not comprehend the content deeply. I want to know if Irreducibility ...
- 121
3
votes
1
answer
143
views
Markov chain dichotomy
Suppose $X$ is a complete separable metric space, and there is a continuous map $x \mapsto \mu_x$ associating to each point in $X$ a probability measure on $X$ (where we use the weak topology on the ...
- 4,304
0
votes
0
answers
75
views
Drunkards Uphill Walk revisited
We want to help the poor git...
Old Question
...with a bias to speed up things. We replace step 1
1. Draw ball, memorize color, throw it back.
with
1a-c. Draw ball, memorize color, throw it back. ...
- 4,829
3
votes
1
answer
182
views
Superlinear Convergence of a Markov Chain
Suppose that we have a Markov process $\{Z_t\}_{t=0}^\infty$, where $Z_t \geq 0$ for any $t$. Assume that, conditioning on $Z_t = z_t$, we have
$
\mathbb{E}\{Z_{t+1}|Z_t = z_t\} \leq \kappa z_t^2
$. ...
- 1,127
3
votes
0
answers
182
views
Spectral radius of infinite substochastic upper triangular matrix
Let $M$ be a Markov chain on $\{0, 1, 2, \dots\} \cup \{\delta\}$, where $\Pr(i \to j) > 0$ for $i, j \in \mathbb{N}$ only if $j > i$, and $\Pr(\delta \to \delta) = 1$. This represents a birth-...
- 131
1
vote
0
answers
336
views
Existence of solution for Poisson equation in Markov chain
Consider $X_n\in \mathcal{X}$ a controlled Markov chain taking value in a compact set $\mathcal{X}$ with action $a\in \mathcal{A}$, where the action set $|\mathcal{A}|$ is finite.
(In particular, we ...
- 185
1
vote
0
answers
265
views
Time-inhomogeneous and state dependent Markov chain
We look at an inhomogeneous Markov chain $X_{n}$ that evolves according to the following transition probabilities:
$$
P(X_{n+1}=k+1|X_{n}=k)=\frac{f(k)}{n+1}\\
P(X_{n+1}=k|X_{n}=k)=\frac{n-f(k)}{n+1}\\...
- 11
3
votes
0
answers
112
views
Conditional expectation with respect to paths of a Markov jump process
I'm having some trouble detangeling how the conditional expectation in equation (2.13) in the article https://arxiv.org/abs/cond-mat/9811220 (Lebowitz, Spohn) is defined.
The context is as follows: ...
- 53
3
votes
1
answer
281
views
Drunkards Uphill Walk
An urn is filled with n black and n white balls. Do the following Markov process: 1. Draw ball, memorize color, throw it back. 2. Draw another ball (might be the same!), color it with memorized color, ...
- 4,829
1
vote
1
answer
2k
views
Simple finite random walks with reflective boundaries
Let us take the 1D case: for an n-step random walk on a line confined between two boundaries at positions t and s, can we determine the average time (number of steps) the walker spends off the ...
user88381
3
votes
1
answer
139
views
Show that $\mbox{Var}(\sum_{k=0}^{\infty} \delta\{L_{t-k} > k\}) \leq \mbox{Var}(L)$
General Statement
Suppose we have a sequence of identically distributed but dependent random variables $(X_n)_{n\in \mathbb{N}}$ which take values on $\{0,\dots,m\}$ for some $m \in \mathbb{N}$ (...
- 277
1
vote
1
answer
431
views
Properties of moment generating function of random walk on unit sphere
Question in brief
Let $a$ and $b$ be unit vectors in $\mathbb{R}^d$. Let $f$ be the $1-step$ transition function of a random walk on the $d$ dimensional unit sphere.
I am interested in evaluating $\...
- 720
2
votes
0
answers
440
views
Hitting time of a specific Markov chain using martingale approach (or otherwise)
Let $0 < c < 1$. Consider the Markov chain $(X_i)$ on $\{0, 1, \dots, n\}$, with transition probabilities
$$ P(k,k+1) = \left(1 - \tfrac {k}{n} \right)(1-c), \quad k = 0, \dots, n-1, $$
$$ P(k,...
- 985
1
vote
1
answer
140
views
Reference request: Cover times, Mixing Times and DGFF applied in statistics?
I am trying to find if in active research in statistics, there is interest in mixing times, cover times of graphs, and/or the discrete Gaussian free field?
I haven't found anything so far for the ...
- 11
2
votes
0
answers
32
views
$\mbox{Var}(\sum \delta\{X_n > i_n\} )$ i.f.o. correlation of $(X_n)_n$
Question
Suppose we have an ergodic positive stochastic process $(X_n)_{n \in \mathbb{N}}$ (in particular I'm mainly interested in the case where $(X_n)_n$ is an aperiodic, irreducible, positive ...
- 277
0
votes
0
answers
78
views
Core of direct product of Markov processes
Let $X$ and $Y$ be two diffusion processes. Suppose they have generators $G_X$ and $G_Y$ with domains $D(G_X)$ and $D(G_Y)$ and cores $C(G_X)$ and $C(G_Y)$. Let $Z$ be the product diffusion with ...
- 43
3
votes
2
answers
922
views
On representing a continuous time Markov chain by a stochastic integral of a Poisson random measure
Let $Q=(q_{ij})$ be the transition rate matrix of a continuous time Markov chain $\{ X_t \}$ with countable state space $M$. Let $q_i = -q_{ii}=\sum_{j \neq i}q_{ij}$, and let $\Gamma_{ij}$ be defined ...
- 31
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
1
vote
1
answer
276
views
Number of deaths in birth-death process conditioned on start and end points
Say I have a simple linear continuous time birth-death process with state space the non-negative integers, where there are parameters $b$ and $d$, with the rate (as you'd see in a $Q$ matrix) of going ...
- 11
2
votes
0
answers
74
views
Literature/Book on counting processes
I seek literature that makes a rigorous treatment of counting processes. In particular im interested in a precise treatment of the conditional intensity $\lambda_t$ which is often informally defined ...
- 315
1
vote
1
answer
4k
views
First passage time of a 1D simple random walk in a discrete time infinite markov chain [closed]
If we consider a simple Random Walk on the positive integers (discrete Markov chain), with symmetric transition probabilities. We start at time $0$ at the integer $i_0 = m$ and at each time step $P(...
- 53
4
votes
1
answer
126
views
Dynamic site percolation of independent random walkers on 2-dimensional square lattice
I am stuck in a part of my research which I am not expert in.
I have a 2-dimensional square lattice with periodic boundary conditions(torus). I am placing one walker at each node at the beginning. It ...
- 53
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 ...
- 708
1
vote
1
answer
377
views
Ergodicity of the product Markov chain
$\def\P{\mathsf{P}}$
Let $(X_n)_{n\in\mathbb{Z}_+}$ be a Markov chain with a transition kernel $P(x,dy)$. Consider now a product Markov chain $(X^1_n,X^2_n)_{n\in\mathbb{Z}_+}$ with the transition ...
- 21