All Questions
Tagged with pr.probability markov-chains
362 questions
1
vote
0
answers
79
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
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 ...
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
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}$, $\...
- 203
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
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 ...
- 1,149
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
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} \...
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
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
180
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 ...
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, ...
- 234
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
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
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$ ...
- 235
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 "...
- 21
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
111
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
271
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 ...
- 18.9k
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
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
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$ ...
user514580
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 ...
user514580
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
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 ...
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
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, ...
- 59
9
votes
2
answers
953
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
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 ...
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 ...
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
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 ...
- 560
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
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 ...
- 91
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
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
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 ...
- 167
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 ...
- 203
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+\...
- 3
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
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 ...
- 201