Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
44 questions from the last 365 days
0
votes
0
answers
36
views
Markov chain on the real line: Numerical methods for evaluating the stationary distribution
Consider a Markov chain on the real line with transition probabilities
$$
p(x_0,x)=\mathbf 1_{\{x\geq x_0+\alpha\,\cup\,x\leq x_0-\beta\}}\phi(x)+\delta(x-x_0)\left(\Phi(x_0+\alpha)-\Phi(x_0-\beta)\...
1
vote
0
answers
78
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
0
votes
1
answer
71
views
Limit distribution of this discrete time Markov chain is standard normal?
Consider a discrete time, uncountable state space Markov chain with one-step transition density
$$
p^{(1)}(z_0,z)=\mathbf 1_{\{z\leq z_0-\theta\lor z\geq z_0+\theta\}}\phi(z)
+\delta(z-z_0)\left(\Phi(...
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
41
views
Approximate the adjoint generator of the discretization of an SDE
Let
$d\in\mathbb N$;
$\sigma\in\mathbb R^{d\times d}$;
$p\in C^1(\mathbb R^d)$ be positive with $$c:=\int p(x)\;{\rm d}x<\infty\tag1$$ and $$b:=\frac12\Sigma\nabla\ln p;$$
$(X_t)_{t\ge0}$ denote ...
- 167
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
2
votes
0
answers
41
views
Why has the random Koopman matrix $ G_{xx}^{(-)} G_{yx} $ only eigenvalues on the complex unit circle?
Let U be a $\Bbb{R}^{(n+1)(n+1)} $ matrix with entries drawn from a independent normal distribution,
e.g.
$$ U_{i j} \sim N(0,1) \quad \quad i,j=1,...n+1$$
Let $ G=U U^* $ be a Gram matrix where $ U^* ...
- 253
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
0
votes
0
answers
74
views
Bayesian updating as a Markov process
I am struggling with the following exercise (Exercise 10.5) from some notes on stochastic processes I am currently studying. It reads as follows.
Let $\theta:(\Omega,\mathcal{F})\to (\Theta,2^\Theta)$...
- 1,149
2
votes
1
answer
153
views
What conditions on the rate matrix $Q$ ensure unique convergence in continuous-time Markov chains?
In the study of discrete-time Markov chains, the conditions under which all initial distributions converge to a unique stationary distribution are well-understood. Specifically, if the transition ...
- 807
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
2
votes
1
answer
201
views
Mean ergodic theorem in $L^p$ for infinite measure spaces
The mean ergodic theorem in $L^p$ can be stated as follows:
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $\theta:\Omega\to \Omega$ be a measure-preserving map, then for all $p\...
- 1,149
4
votes
0
answers
328
views
Convergence to unique stationary distribution for SDEs and Markov processes
I am interested in understanding the behavior of solutions to stochastic differential equations (SDEs) and continuous-time Markov processes with constant coefficients. Specifically, I would like to ...
- 807
6
votes
1
answer
287
views
Determinantal inequality for difference of substochastic matrices
Let $A=(A_{ij})_{1\le i,j\le n}$ be a square matrix with nonnegative real entries. Recall that $A$ is called a substochastic matrix if
$$
\forall i,\ \ \sum_j A_{ij}\le 1\ .
$$
In the course of my ...
1
vote
0
answers
19
views
Metropolis-Hastings in mini-batch setting
I would like to ask the following question : I have seen papers such as Stochastic gradient Langevin dynamics (link) and Stochastic gradient Hamiltonian monte-carlo (link) which could be used to train ...
- 11
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
1
vote
1
answer
69
views
Conditions for reversibility of higher order Markov chains
Consider a discrete time dynamical system on states $\{0, 1, 2 \}$. The one step transitions are not Markovian, but the 3rd order transitions from triples of states $(s_{t-2}, s_{t-1}, s_{t}) \...
- 13
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
14
views
Understanding relation of 2 dependent, integral equations which are nested in a Bayesian Expectation
I'm trying hard to try understand the recursive nature between two equations in a recent macroeconomics paper, but my question mainly relates to how mathematically such recursive equations can depend ...
3
votes
0
answers
83
views
A stochastic matrix $B = \lambda(\lambda I - A)^{-1}$ such that $B-B^2$ has a non-negative diagonal
I apologize if this is too elementary a question, but I have not been able to make much progress.
Consider a real matrix $A$ with $A_{ij} >0$ for $i \ne j$ and $\sum_{j} A_{ij} = 0$ for each $j$. ...
- 251
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
1
vote
0
answers
118
views
Spectral gap of a Markov operator on $L^2$ with a symmetric $L^\infty$ kernel
Let $I$ be a compact interval, say $I:=(0,1)$, and $k\in L^\infty(I\times I)$ a symmetric Markov kernel, i.e. $k(x,y)=k(y,x)$ and
$$\int_I k(x,y) d y = 1\qquad\mbox{for almost all } x\in I.$$
Let $K:L^...
- 11
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
3
votes
0
answers
74
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
- 143
0
votes
0
answers
56
views
Generator of sub-Markov semigroup induces generator of Markov semigroup
I have to show that for the generator $A:L^1 \rightarrow L^1$ of a sub-Markov semigroup and a non-negative $f_* \in L^1$ (with $L^1$ Set of Lebesgue-integrable functions) with $\int_{-\infty}^\infty ...
- 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.8k
10
votes
3
answers
3k
views
Trace inequality for non-reversible Markov chain
Let $P \in \mathbb{R}^{d \times d}$ be the transition kernel for a Markov chain with stationary measure $\pi$ and define $P^\ast$ to be the time-reversed transition kernel defined by $P^\ast_{ij} := ...
- 101
2
votes
0
answers
103
views
Find a function $f\geq 0$ such that $e^{-t[(x-\partial_x)\partial_x]^2} f$ is not non-negative for some $t\geq 0$
Consider the square of the Ornstein-Uhlenbeck operator $$A=[(x-\partial_x)\partial_x]^2=(x-\partial_x)\partial_x (x-\partial_x)\partial_x.$$ We know that $[(x-\partial_x)\partial_x]^2$ cannot be a ...
- 90
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
0
votes
0
answers
49
views
Reference needed for powers of semi-group generators
Let $\mathcal{L}$ be the infinitesimal generator of a Markov semi-group. I am looking for references that study powers of $\mathcal{L}$; i.e. $\mathcal{L}^n$, for $n\in\mathbb{N}$.
For example, if the ...
- 90