Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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_{...
Joseph Van Name's user avatar
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 ...
Joseph Van Name's user avatar
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 ...
Joseph Van Name's user avatar
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{...
sharpe's user avatar
  • 701
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 ...
Joe_Affine's user avatar
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 ...
Diego Méndez's user avatar
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. ...
Matthieu Latapy's user avatar
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 ...
user avatar
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 ...
lady gaga's user avatar
  • 153
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 ...
Max Babich's user avatar
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 ...
ffx's user avatar
  • 31
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 ...
gidi's user avatar
  • 61
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 ...
Evgeny Kuznetsov's user avatar
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....
Landauer's user avatar
  • 173
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 ...
G. Panel's user avatar
  • 557
-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....
Mehdi Nmz's user avatar
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 ...
jonem's user avatar
  • 179
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 ...
Tom Solberg's user avatar
  • 3,910
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 ...
N. Gast's user avatar
  • 552
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)=\...
Tiago's user avatar
  • 59
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 ...
user812951's user avatar
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 $...
sharpe's user avatar
  • 701
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 ...
Miklos Pinter's user avatar
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,\...
0xbadf00d's user avatar
  • 161
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,\...
0xbadf00d's user avatar
  • 161
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:...
defex95's user avatar
  • 149
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,\...
Laurent Lessard's user avatar
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 ...
bolzano's user avatar
  • 143
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 ...
gradstudent's user avatar
  • 2,136
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 ...
Holden Lee's user avatar
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)=...
Thomas Dybdahl Ahle's user avatar
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 ...
user134977's user avatar
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 ...
SID A's user avatar
  • 31
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 ...
SID A's user avatar
  • 31
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)$ ...
0xbadf00d's user avatar
  • 161
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 ...
xFioraMstr18's user avatar
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), ...
Eduardo's user avatar
  • 757
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 ...
RSMax's user avatar
  • 23
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{\...
0xbadf00d's user avatar
  • 161
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\...
0xbadf00d's user avatar
  • 161
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: ...
0xbadf00d's user avatar
  • 161
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 ...
xFioraMstr18's user avatar
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))$ (...
Ivan Petrov's user avatar
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) &...
Henning's user avatar
  • 123
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 $$\...
I.Kiaan's user avatar
  • 21
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 ...
TPaul's user avatar
  • 31
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 ...
kaleidoscop's user avatar
  • 1,268
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} := \...
D. Thomine's user avatar
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 ...
Enric Florit's user avatar
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}...
Ribhu's user avatar
  • 271

1 2
3
4 5
11