Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
538
questions
1
vote
1
answer
179
views
Factorizing the doubly stochastic matrix where all entries are equal such that the factors are all convex combinations of few permutation matrices
Let $N_{n}=(1/n)_{i=1,j=1}^{n}$ be the $n\times n$-matrix where all the entries are equal.
Suppose $n>0$. Let $\delta_{n}$ be the least natural number such that $N_{n}$ can be factored as $N_{n}=A_{...
2
votes
1
answer
236
views
How quickly can irreducible aperiodic convex combinations of permutation matrices converge to the stationary distribution?
Recall that a doubly stochastic matrix is a square matrix with non-negative entries where the sum of each row and the sum of each column is 1. The Birkhoff-von Neumann theorem states that every doubly ...
2
votes
0
answers
325
views
Convex combinations $A$ of $n\times n$ permutation matrices such that every entry in $A^{k}$ is $1/n$
Recall that a doubly stochastic matrix is a square matrix $A$ with non-negative entries such that the sum of each row is $1$ and the sum of each column is $1$. The Birkhoff-von Neumann theorem states ...
1
vote
0
answers
308
views
Markov chains with drift
We consider a Markov process $X$ on a finite set $\mathcal{X} (\neq \emptyset)$. Basically, $X$ is associated with a generator of the following form
\begin{align*}
Af(x)=\lambda(x)\sum_{ y\in \mathcal{...
2
votes
1
answer
91
views
Preservation of the Markov Property under Conditioning
Let $(X_t,Z_t)_t$ be an $\mathbb{R}^{n}\times \mathbb{R}^m$-valued time-homogeneous Markov process on a filtered probability space $(\Omega,\mathcal{F},(\mathcal{F}_t)_t,\mathbb{P})$ with transition ...
0
votes
1
answer
116
views
How to detect, track and map a Markov chain
You are receiving a time series whose elements belong to a finite set. Assume the time series is distributed as a Discrete-Time Markov Chain. You receive one element at each time step.
For each time ...
2
votes
0
answers
75
views
Pagerank Markov chain reductions
In short: if a Markov chain models a (generalized) pagerank, is it always possible to remove any of its state and obtain a Markov chain that models a pagerank close to the initial one?
Full details.
...
3
votes
2
answers
535
views
Random walk on $n$-dimensional cube
Consider a symmetric random walk along the edges of an $n$-dimensional unit cube. At each time step, a particle located at a particular vertex $(a_1, \ldots, a_n)$ moves to an adjacent neighbor each ...
0
votes
0
answers
107
views
Methods to find the spectrum of an operator
Suppose we have a bounded, self-adjoint operator $T$ on a set of functions $\mathcal{F}$. What kinds of methods are there to find the spectrum of $T$?
Here is the setting I'm wondering about: consider ...
1
vote
0
answers
62
views
The rate of convergence of Markov chain to stationary distribution
Let $X_t$ is Markov chain with transition rates $c: G \times G \rightarrow [0: +\infty)$, where $c(x, y) > 0$, $c(x, x) = -\sum_y c(x, y)$ for $x \neq y$. If $\mu_t(x)$ is the distribution of chain ...
3
votes
0
answers
79
views
Rate of convergence of sojourn times of Markov chains
Let $(X_0,X_1,\dots)$ be a time-homogeneous Markov chain with finite state space $\Omega$.
Assume that $(X_0,X_1,\dots)$ is irreducible and aperiodic and let $\pi$ be its stationary distribution.
By ...
1
vote
0
answers
74
views
Stationary distribution of a Memoryless 2-type priority queue
I have come across the following priority queue, which seems quite natural to me.
A single queue with 2 types of costumers, independent Poisson arrivals and Poisson services.
First class costumers ...
2
votes
1
answer
126
views
The reference on Markov chains uncovering the power of the subject in a better way for a working macro-economist
This is by no means a research question. But asking here I hope for the most expert opinion.
A friend of mine, who is a working economist, asked me for advice about a book which uncovers wealth and ...
6
votes
1
answer
234
views
Perron-Frobenius and Markov chains on countable state space
The following question naturally arises in the theory of Markov chains with countable state space to which I would be curious to know the answer:
Let $A:\ell^1 \rightarrow \ell^1$ be a contraction, i....
1
vote
2
answers
212
views
Is a linear combination of Markov generator a Markov generator?
Let $X$ be a compact metric set and $\mathcal{C}(X)$ be the set on continuous real functions over $X$ endowed with the supremum norm $\|\cdot\|_{\infty}$. Let $\Omega_1$ and $\Omega_2$ be two Markov ...
-2
votes
1
answer
149
views
Stationary distribution of a weighted directed acyclic graph
Is there any way to calculate the equilibrium (stationary) distribution for a weighted directed acyclic graph?
Some references emphasized adjacency matrix to be symmetric.
https://arxiv.org/abs/1012....
1
vote
0
answers
184
views
Stationary distributions of convex combination of stochastic matrices
Consider two irreducible finite state Markov chains with transition matrices $A,B\in\mathbb{R}^{n\times n}$.
Let $x$ and $y$ be the unique stationary distributions of $A$ and $B$, respectively.
Now ...
1
vote
0
answers
35
views
Markov chains with “clustered” stationary distributions
Are there any canonical or well-known Markov chains whose stationary distributions are basically clustered into two or more components? Obviously, it is easy to create one, but I’m wondering if there ...
1
vote
0
answers
34
views
Estimation of probability matrix from samples at different time intervals
I am given discrete-time Markov chain that evolves on a finite subset $\{1,\dots,n\}$. This Markov chain is time-homogeneous and has a transition matrix $P$ that I want to estimate.
Let $X_t$ be the ...
2
votes
1
answer
163
views
Monotonicity of Dirichlet form of Markov chain
Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E,
$$Lf(x)=\...
0
votes
0
answers
77
views
Constrained MDP
I have a question that is an extension of this one.
My question is: Can we say that for every policy, there exists a deterministic policy in case of a finite-state, finite-action infinite-horizon ...
1
vote
0
answers
135
views
Harnack inequalities for Markov chains
We consider a (continuous time) Markov chain $X=(\{X_t\}_{t \ge 0},\{P_x\}_{x \in V})$ on a finite set $V$. We assume moreover that $V$ is embedded into $\mathbb{R}^d$. The generator $\mathcal{L}$ of $...
0
votes
1
answer
108
views
Sets of invariant measures of Markov operators
A family of Markov operators $P_i \colon C \to C, i \in I$ is given. Let $V_i$ be the set of the $P_i$-invariant measures. Is there any result in the literature about a necessary and sufficient ...
0
votes
0
answers
78
views
If $W$ is a Markov chain and $N$ is a Poisson process, then $\left(W_{N_t}\right)_{t\ge0}$ is Markov
Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space, $(E,\mathcal E)$ be a measurable space, $(W_n)_{n\in\mathbb N_0}$ be a time-homogeneosu Markov chain on $(\Omega,\mathcal A,\...
1
vote
1
answer
151
views
If $L_t=\sum_{i=1}^{N_t}Y_i$ is a compound Poisson process, then $\left|\left\{s\in[0,t]:\Delta L_s\in B\right\}\right|=\sum_{i=1}^{N_t}1_B(Y_i)$
Let $H$ be a $\mathbb R$-Hilbert space, $\mu$ be a finite measure on $\mathcal B(H)$ with $\mu(\{0\})=0$ and $(L_t)_{t\ge0}$ be a $H$-valued càdlàg Lévy process on a probability space $(\Omega,\...
1
vote
0
answers
248
views
Path dependent Markov property
Let's consider a function $\Psi\in \mathcal{C}_B(\mathcal{C}[t,T])$ continuous and bounded
\begin{align*}
\Psi \colon \mathcal{C}[t,T] \longrightarrow [0,+\infty)
\end{align*}
Then my question is:...
1
vote
1
answer
174
views
finiteness of moments of the stationary distribution of a Markov chain
I have a Markov chain $\{X_k\}_{k\geq 0}$ on $\mathbb{R}$. The corresponding probability density functions satisfy
$$
f_{k+1}(t) = \int_{-\infty}^\infty \Psi(t,\tau)f_k(\tau)\,d\tau,\qquad k=0,1,2,\...
1
vote
0
answers
44
views
Chernoff-type Bounds for Continuous-space Markov Chains
Let $X_1, X_2, \dots, X_n$ be $n$ samples from a discrete-time continuous-space Markov Chain.
Are there any good references who have provided a Chernoff-type bound regarding the behaviour of the ...
2
votes
1
answer
729
views
Defining measures through products of Markov kernels
I am quite puzzled by the expression given in equation 21 (page 10) in this paper,
https://arxiv.org/pdf/1802.09188.pdf
Its LHS seems to be a measure $\nu_n^N$ and hence I guess it takes as argument ...
3
votes
0
answers
60
views
Mixing times for the exclusion process with rejection
Consider the following Markov chain on $k$-subsets of $\{1,\ldots, L\}$, equivalently, sequences $x\in \{0,1\}^L$ with $k$ 1's.
Let $p_1,\ldots, p_L\in (0,1)$ and $q_i=1-p_i$.
At each step, choose an ...
2
votes
1
answer
104
views
Strong Data Processing Inequality for capped channels
Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$.
Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=...
1
vote
0
answers
73
views
SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?
the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs.
Another popular approach to obtain efficient ...
1
vote
0
answers
54
views
Convergence of empirical measure to Mc-Kean Vlasov equation for mean-field model with jumps
I am interested in the following mean-field model introduced in the reference below:
There are $N$ particles. At each instant of time, a particle's state is a particular value taken from the finite ...
2
votes
0
answers
153
views
Representing a continuous time-inhomogeneous Markov chain by a stochastic integral
I am interested in the following mean-field model introduced in the reference below:
There are $N$ particles. At each instant of time, a particle's state is a particular value taken from the finite ...
1
vote
1
answer
180
views
If a Markov semigroup is eventually contractive, can we conclude that it admits a unique invariant measure?
Let $E$ be a separable $\mathbb R$-Banach space, $\rho$ be a complete separable metric on $E$, $\operatorname W_\rho$ denote the Wasserstein metric of order $1$ associated to $\rho$, $\mathcal M_1(E)$ ...
1
vote
1
answer
163
views
Spectral gap of a Markov chain on the nonnegative integers
Let $\lambda_k,\mu_k\in\mathbb R_{\ge0}$ $(k\ge1)$ be nonnegative real numbers such that $\sum_{k=1}^\infty k\lambda_k<\infty,$ let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, let $T=\mathbb ...
1
vote
1
answer
274
views
English translation of a Russian paper by Gordin and Lifšic
Unfortunately I can't read Russian, I was wondering if there is an English translation of this paper
“The central limit theorem for stationary Markov processes”, Dokl. Akad. Nauk SSSR, 239:4 (1978), ...
2
votes
2
answers
299
views
Of all probability matrix $P$ having stationary distribution $\pi$, find the one having smallest diagonal
I am requesting your help today trying to solve a somewhat odd problem. Is there a way to find through some numerical algorithm such as Newton's method the stochastic matrix $\boldsymbol{P}$ having ...
1
vote
2
answers
230
views
Extension of spectral gap inequality in Wasserstein distance
Let $E$ be a separable $\mathbb R$-Banach space, $\rho_r$ be a metric on $E$ for $r\in(0,1]$ with $\rho_r\le\rho_s$ for all $0<r\le s\le1$, $\rho:=\rho_1$, $$d_{r,\:\delta,\:\beta}:=1\wedge\frac{\...
2
votes
0
answers
40
views
If a stochastic flow is Fréchet differentiable in the spatial parameter, does the induced transition semigroup preserve differentiability?
Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space, $(E,\mathcal E)$ be a measurable space, $X:\Omega\times[0,\infty)\times E\to E$ be $(\mathcal A\otimes\mathcal B([0,\infty))\otimes\...
3
votes
0
answers
81
views
How does one define the gradient of a Markov semigroup?
In the context of functional inequalities for Markov semigroups $(\mathcal P_t)_{t\ge0}$, what is one denoting by $\nabla\mathcal P_tf$? For example, I've found the following assumption in this paper:
...
1
vote
1
answer
168
views
Existence of Markov chain on nonnegative integers with specified rates
Let $\lambda_k,\mu_k\in\mathbb R_{\ge0}$ $(k\ge1)$ be nonnegative real numbers, let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, let $T=\mathbb R_{\ge0}$ be the nonnegative real numbers and ...
2
votes
1
answer
749
views
Calculate Radon-Nikodym derivative
For the laws of two pure-jump Markov processes $\mu_1$ and $\mu_2$ on $\mathbb R^n$, which generators are
$H_1f(x)=\int h(x,dy) (f(y)-f(x))$
and $H_2f(x)=\int e^{-g(x,y)} h(x,dy) (f(y)-f(x))$ (...
2
votes
1
answer
184
views
Eigenspace of Gaussian Markov operator
Consider the (one-dimensional) Gaussian distribution $Q := N(\nu,\tau^2)$ and the (Gaussian) Markov operator
\begin{equation*}
\begin{array}{rccc}
R : & L_1(\mathbb{R},\mathcal{B}(\mathbb{R}),Q) &...
2
votes
2
answers
222
views
is this process a Markov one?
Here is the problem I can't solve.
Let $\xi_n$ $(n=1,2,3,\dots)$ be a sequence of i.i.d. random variables on $\mathbb{R}$ with density $p(x)>0$, let $\eta_n=\sum_{i=1}^{n}\xi_i^2$. Define $$\...
1
vote
1
answer
138
views
Conditions for optimal stationary strategies in MDPs
I have a specific Markov decision process (MDP) which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal ...
7
votes
2
answers
825
views
what is the number of paths returning to 0 on the hexagonal lattice
I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.
I can find plenty on references on self avoiding paths, but I am looking ...
3
votes
0
answers
60
views
Algebraic property of a transition matrix
Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...
1
vote
0
answers
331
views
Upper and lower bounds on the entries of a matrix power
Say I have a non-negative square $n\times n$ irreducible stochastic matrix $A$ (i.e., each column sums to 1), for which the following holds:
$$A_{ij} > 0 \iff A_{ji} > 0.$$
I know that no more ...
0
votes
1
answer
67
views
Friedrich's extension of the generator of a continuous time markov chaoin
Consider the infinitesimal generator $G$ of a Markov chain with state space $\mathbb{Z}$ such that it is symmetric with respect to a measure $\mu$ on $\mathbb{Z}$. Then, the operator $(G,C_c(\mathbb{Z}...