All Questions
Tagged with pr.probability markov-chains
362 questions
1
vote
0
answers
81
views
Markov Chain that maximises the entropy creation rate
I am working on MERW (Maximal entropy random walk) for a project.
I want to show that given a graph G, there is $\textbf{only one}$ aperiodic markov chain on G that maximises the entropy creation rate ...
- 11
8
votes
1
answer
534
views
The cars problem, again
Consider the following simple problem: We are given $2n$ parking spots, labelled from 0 to $2n-1$. There are $n$ cars on the first $n$ spots, and the remaining $n$ spots are free. At every step, every ...
0
votes
1
answer
227
views
Constructing Markov chain
Let $(A_1,B_1)$ and $(A_2,B_2)$ be two random variables with the joint distributions $p_{A_1B_1}$ and $p_{A_2B_2}$, respectively. Moreover, we have
$$\mathbb{P}[(A_1,B_1)\neq (A_2,B_2)]=\alpha.$$
Then,...
CommunityBot
- 1
0
votes
1
answer
95
views
On the behaviour of individual random walks of a Markov Chain
My current research (on Probabilistic Automaton) brought me to the following question regarding Markov Chains. I state the definitions for the sake of clarity.
Let $M$ be a discrete-time finite Markov ...
- 232
1
vote
0
answers
41
views
Asymptotic mixing time and Euclidean probability distance for path graphs
We are given a simple path graph $P(V,E)$ with vertex set $V$ and edge set $E$, having $n=|V|$ nodes. Given an initial distribution $\mathbf{\mu}$ over $V$, let $d_t(\mathbf{\mu},\pi)$ be defined as $\...
- 1,677
2
votes
0
answers
124
views
dimensionality reduction of Markov chains
Suppose that $M$ is a time-homogeneous (and, for simplicity, stationary) Markov chain on $d$ states, which induces the probability measure $P$ on paths of length $n$. I seek a Markov chain $M'$ on $d'&...
- 6,541
0
votes
0
answers
66
views
Long-time conditioning for a Markov Chain
I am studying MERW and for some reasons, i would like to know if, if I have $(X_n)$ an irreducible Markov Chain, I can say that
$\mathbb{P}(X_1=x | X_0=a, X_n = b)$ goes to $\mathbb{P}(X_1=x | X_0=a)$ ...
- 11
3
votes
1
answer
373
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
CommunityBot
- 1
2
votes
1
answer
59
views
The ranked mass process associated with a Lambda-coalescent
I am reading a paper by Pitman (1999), and I am confused by his Corollary 7. First some notation so that I can explain my confusion:
$\mathcal{P}_\infty$ is the space of partitions of $\mathbb{N}$, $\...
- 3,937
0
votes
0
answers
85
views
Does a 2d random walk hit 0 for increasing distances AND time spans?
Question: For a simple symmetric random walk $(Z_t)_{t\geq 0}$ in $\mathbb{Z}^2$, does
$$\lim_{\beta\rightarrow 0}\mathbb{P}^{x_\beta}(Z_t=0\text{ for some }t\leq h(\beta)T)=0\quad (2.8)$$
where $|x_\...
- 31
2
votes
1
answer
123
views
Monotone grand coupling of Markov chains
A stochastic matrix $P$ on a finite poset $(\mathcal X,\preceq)$ is called monotone if $Pf$ is increasing whenever $f$ is. This property ensures the existence of a monotone coupling: specifically, ...
- 138
3
votes
0
answers
58
views
Infinitesimal generators of random evolutions
Consider two state spaces $X$ and $Y$ and infinitesimal generators of Markov processes $(A_y)_{y\in Y}$ and $B$, on $X$ and $Y$ respectively. We assume that $A_y$ share the same domain $D(A)$, and ...
- 31
1
vote
0
answers
114
views
An urn model with weighted objects and replacement
Consider the following game:
In an urn, there are $K$ balls, $x_0$ of them are blue and light (mass $m_0$), $x_1$ are blue and heavy ($m_1$), $x_2$ are red and light ($m_2$), the rest $x_3$ are red ...
- 31
5
votes
1
answer
192
views
Non-equivalent definitions of Markov process
As far as I know, there are three definitions of Markov processes (or of Markov chains).
DEFINITION 1 (WEAKER). A process $(X_t)_{t\in[0,\infty)}$ on $(\Omega,\mathcal{F},\mathbb{P})$ with values in ...
- 398
0
votes
0
answers
101
views
Simulation of Markov processes with exponential timestepping
Let $(Y_t)_{t\ge0}$ be a time-homogeneous Markov process with transition semigroup $(\kappa_t)_{t\ge0}$. Numerical simulation of $(Y_t)_{t\ge0}$ can be done in the following way:
Choose an initial ...
- 167
1
vote
2
answers
489
views
The limiting behavior of geometric random walk
I would like to know what the asymptotic limiting behavior is for the following random walk on $\mathbb Z^d$. By Donsker's invariance principle, I suspect that its behavior is diffusive, i.e., the ...
- 5,405
5
votes
2
answers
369
views
Markov process on a torus with prescribed invariant distribution
In Euclidean space, $\mathbb R^d$, the Langevin diffusion $${\rm d}X_t=b(X_t){\rm d}t+\sigma(X_t){\rm d}W_t\tag1,$$ where $\sigma:\mathbb R^d\to\mathbb R^{d\times k}$, $$b:=\frac{\Sigma+U}2\nabla\ln p+...
- 167
3
votes
2
answers
923
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 ...
1
vote
1
answer
345
views
Random walk on $\mathbb{Z}^3$. Expected number of visits and probability of return
I am working with the simple symmetric random walk on $\mathbb{Z}^3$. Using the Fourier identity I have been able to prove:
$$ P(S_n = 0) = \frac{1}{(2\pi)^3} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \...
- 34.7k
0
votes
0
answers
34
views
Does the definition of mixing time work for general non-Markovian processes?
A definition of the mixing time for Markov chains is given by
\begin{equation}
\tau_{\text{mix}}\equiv\inf{\{t>0: \sup_i\left\vert \frac{\boldsymbol{p}(t|p_j(0)=\delta_{ij})}{\boldsymbol{\pi}}-\...
- 31
0
votes
1
answer
182
views
Hidden Markov model with two hidden states?
I am currently studying what Markov models are, and have a question. If we have a hidden Markov model with 2 hidden states or observations, then how do we find the probability of just the main state ...
4
votes
2
answers
227
views
Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?
Note: I've entirely rewritten this question! Originally it was just the third formulation, take note of that when reading answers.
Let's say $S$ is a $b$-automatic set, and let's say $M$ is a DFA ...
- 2,585
6
votes
3
answers
460
views
Regarding Ricci curvature of Markov chains
In Ricci curvature of Markov chains on metric spaces Yann Ollivier, defines a coarse Ricci curvature for a Markov chain with transition kernels $\{m_x\}$ defined on a metric space $(X,d)$ as follows: ...
0
votes
0
answers
92
views
MDP Average Reward independent of Initial State
Consider a Markov Decision Process where the state space $S$ and the action space $A$ are continuous and compact.
In state $s$, if action $a$ is chosen and the next state becomes $s'$, the ...
- 115
1
vote
1
answer
121
views
Characterization of Fellerian kernels
This question concerns Feller Markov kernels, similar to Vanessa's question.
Terminology
By 'Markov kernel' $N:E\to F$, we adopt exactly the same definition as Vanessa, with the exception that $E,F$ ...
- 63.9k
2
votes
0
answers
54
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 "...
- 6,367
-2
votes
3
answers
2k
views
Convergence of a markov matrix
Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)
2- Not all ...
- 1,446
0
votes
0
answers
21
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 ...
- 31
2
votes
0
answers
112
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 ...
- 21
5
votes
0
answers
272
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 ...
- 19k
1
vote
1
answer
99
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, ...
- 51
3
votes
1
answer
190
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, ...
- 51
8
votes
4
answers
8k
views
Is there MDPs (Markov Decision Process) which have a non deterministic optimal policy?
I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...
- 4,219
1
vote
1
answer
259
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 ...
- 565
0
votes
0
answers
142
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
0
answers
241
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 \...
- 620
9
votes
2
answers
954
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.
...
- 165
2
votes
1
answer
74
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$ ...
- 63.9k
1
vote
1
answer
192
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 ...
- 128k
3
votes
0
answers
54
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 ...
- 56
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,...
- 12.9k
0
votes
0
answers
161
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 ...
17
votes
2
answers
2k
views
Random walk is to diffusion as self-avoiding random walk is to ...?
One can view a random walk as a discrete process whose continuous
analog is diffusion.
For example, discretizing the heat diffusion equation
(in both time and space) leads to random walks.
Is there a ...
- 2,175
7
votes
1
answer
391
views
Idempotent splitting for Markov kernels
Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation,
$$e(A|x) = \int_X e(...
- 6,406
1
vote
0
answers
72
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 ...
- 11
2
votes
0
answers
237
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$ ...
- 21
2
votes
0
answers
155
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,...
- 167
3
votes
1
answer
307
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 ...
- 17k
1
vote
0
answers
115
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 ...
- 167
1
vote
1
answer
96
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 ...
- 3,937