All Questions
Tagged with pr.probability markov-chains
362 questions
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 ...
- 37.7k
3
votes
2
answers
973
views
How much larger than the relaxation time can the mixing time be?
The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.
Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
- 63.9k
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)=\...
- 188k
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 ...
- 6,045
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 ...
- 334
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 ...
- 14.2k
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/...
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 . ...
- 14.2k
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{...
- 61.9k
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
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
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 ...
- 128k
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 ...
- 188k
1
vote
0
answers
80
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\...
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, ...
- 3,937
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
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
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 ...
- 173
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
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 ...
- 34.7k
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$ ...
- 4,361
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 ...
- 128k
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 ...
- 30.1k
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 ...
- 10.3k
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 (...
- 128k
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$ ...
- 23.2k
17
votes
2
answers
953
views
Convexity of spectral radius of Markov operators, Random walks on non-amenable groups
Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$.
Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication.
Question
Under which conditions can we show that ...
- 4,361
1
vote
2
answers
307
views
Continuous family of Markov chains
Suppose I have a family of countable state-space, discrete-time Markov chains, indexed by a parameter $r \in \mathbb{R}$. The state space is the same for all values of $r$; the transition ...
- 101
1
vote
2
answers
2k
views
Does a irreducible set of states necessarily need to be closed in a Markov chain?
I have come across two different definitions for a 'irreducible set of states' of a Markov chain.
Definition 1: A subset of states $A$ of a Markov chain is irreducible if it is possible to access (...
- 101
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 ...
- 482
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-...
- 17k
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
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
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
$$ \...
- 406
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
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 ...
- 17.2k
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 ...
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 ...
CommunityBot
- 1
5
votes
0
answers
485
views
Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)
Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
- 1,127
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
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
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 ...
- 8,071