Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
137 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
1answer
92 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
2answers
115 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
votes
0answers
30 views

Stopping times about Brownian motion with draft

Assumet $M(t) = B(t) + \mu t$ where $B(t)$ is a standard Brownian Motion. Denote: $$T_a := \inf \{ t \geq 0, \, M(t) = a\}, \quad T_b := \inf \{ t \geq 0, \, M(t) = b\}$$ The question asks to ...
1
vote
1answer
49 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 ...
0
votes
0answers
14 views

Calculate regime-switching correlation matrix without assumption on distribution

There's rich literature on Markov regime-switching dynamic correlation matrix. But most results seem to assume a certain kind of distribution and use MLE/EM. For example, some sort of multivariate ...
6
votes
2answers
500 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
0answers
44 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
0answers
80 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
1answer
44 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}...
2
votes
3answers
291 views

Generations until fixation: A nontrivial generalization of a dice convergence problem

In spite of its "recreational" aspect, this question appears to me to be research-level and (I hope) clearly formulated and tagged. Edit 4/4/20: You can find a related question with the same ...
2
votes
1answer
107 views

Diagonalizable stochastic matrix that satisfies an equation

Given an arbitrary discrete probability distribution $a = (a_1, ..., a_n)$ and another arbitrary discrete probability distribution $b = (b_1, ..., b_n)$, what is the easiest known way to find a ...
2
votes
0answers
79 views

Gurevich's entropy and topological entropy in a countable Markov shift

Good afternoon, I understand that Gurevich's entropy and topological entropy coincide when the countable Markov shift is topologically mixing (right?) Does anyone know of an example or a reference ...
6
votes
1answer
149 views

Random walks on infinite directed regular graphs

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps). Assume that $\Gamma$ is bi-regular, that is ...
0
votes
1answer
80 views

Law of large numbers for Harris recurrent Markov chains

I'm trying to familiarize myself with the details of the proof that the Markov chains produce by the Metropolis-Hastings algorithm have a law of large numbers. I've found a half dozen or more ...
3
votes
3answers
119 views

A stopping time that gives the metric

Let $\Omega$ a finite metric space with $\forall x,y,z\in \Omega:d(x,y)<d(x,z)+d(z,y)$. Does there exists a continuous-time Markov process $X$ on $\Omega$ such that $$\mathbb{E}_x(T_y)=d(x,y)$$ for ...
2
votes
1answer
60 views

Concentration in Markov chains

Consider a discrete state space $\mathcal{X}$. The expander Chernoff inequality gives subgaussian concentration for the sample mean $\frac1n \sum_{t=1}^n f(X_t)$ for some function $f : \mathcal{X} \to ...
6
votes
1answer
87 views

Maximum eigenvalue of a doubly stochastic matrix with deleted row and column

Consider an $n \times n$ irreducible and reversible (in the sense of a Markov chain) stochastic matrix $P$; assume that it has uniform stationary distribution (so, by reversibility, the matrix is ...
2
votes
1answer
81 views

Sampling algorithms on convex polytopes

Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
1
vote
0answers
94 views

Showing existence of a solution to an underdetermined system of equations with non-negativity constraints

Let $K$ be a positive integer, let $p\in (0,1)$, and let $\{W(k,i),W^B(k,i), \varphi_k(i)\}_{1\leq i\leq k\leq K}$ be variables. I need to prove that there exists a solution to the following system ...
2
votes
1answer
67 views

Entropy rate problem of ergodic Markov process with non-ergodic joint

I have a problem with the entropy rate when two ergodic Markov processes who are independent of each other having a non-ergodic joint. More specifically let us consider two finite-state Markov ...
0
votes
0answers
28 views

Keeping track of the variance of a Metropolis-Hastings estimator

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces, $p,q$ be probability densities on $(E,\mathcal E,\lambda)$, and $\varphi:E'\to E$ be bijective and $(\mathcal E',\...
0
votes
2answers
121 views

Spectrum of a Markov kernel acting on $L^2$

Let $P$ be a Markov kernel on a measurable space $(E,\mathcal E)$ admitting an invariant probability measure $\pi$. $P$ acts on $L^2(\pi)$ via $$Pf:=\int\kappa(\;\cdot\;{\rm d}y)f(y).$$ The invariance ...
1
vote
1answer
115 views

Uniform upper bound on contraction coefficient w.r.t total-variation metric, of a certain set of block-diagonal Markov kernels

Disclaimer. This is related to another question I've asked on the TCS site https://cstheory.stackexchange.com/q/46097/44644. I'm new to information theory (and other relevant fields). It's even ...
0
votes
0answers
18 views

Continuous time-inhomogenous Markov chain from discrete TIMC

Cross-posting the question from math.stackexchange.com: https://math.stackexchange.com/questions/3478043/continuous-time-inhomogenous-markov-chain-from-discrete-timc
0
votes
1answer
122 views

Symmetric random walks - bounds on the amount of time spent in a subset $A$?

For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$? Let $S_n$ be a symmetric random walk on the integers. ...
0
votes
0answers
31 views

V-Norm in Markov Chain Analysis Question

I had a question about the $V$-norm that I often see used in the Markov Chain analysis literature, where $V:X\to [1,\infty)$ is specified, and the norm $|\bullet|_V$ is defined as $$ |f|_V = \sup_{x\...
1
vote
1answer
113 views

Distribution of non-overlapping words in randomly generated text

The question can be described in the following way: Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$. I have a string that is composed of a concatenated series of $n$ instances ...
1
vote
0answers
45 views

Reduce the asymptotic variance for a class of Metropolis-Hasting estimates

I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
1
vote
0answers
85 views

Show a Poincaré inequality for a Markov kernel and minimize the Poincaré constant

Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$ (see definitions ...
1
vote
0answers
43 views

Minimizing the rate of geometric ergodicity of a Metropolis-Hastings kernel depending on a parameter

Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$. I want to ...
1
vote
0answers
59 views

Is there any equivalent Foster-Lyapunov Theorem where expected Lyapunov drift is negative though not uniformly upper bounded by a negative number

I have a process $\{X_t\}_t$, where $x_t$ in $[0,1]$, and a Lyapunov function $V(x)=x$ such that the drift $$E[X_{t+1}|x_t] - x_t < -k(1-x_t)$$ for $x_t \in (1-\epsilon,1]$, where $k>0$. Thus ...
10
votes
0answers
273 views

Does Chu and Hough's solution to the mixing time of the 15-puzzle carry over to the Rubik's cube?

In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states: Here is a simplified version: Consider the blank as a $16$th ...
1
vote
1answer
90 views

Comparison of hitting probability of two Markov chains both with only one absorbing state version 3

Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_t\in N_n\}\big)_{t=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$. Define $p_{i,j}...
1
vote
1answer
118 views

Comparison of hitting probability of two Markov chains both with only one absorbing state version 2 under stronger condition

Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$. $\text{Pr}\...
1
vote
1answer
56 views

Comparison of hitting probability of two Markov chains both with only one absorbing state

Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have one absorbing state $1$. Pr$(X^{(1)}_{i+1}=1|X_i=1)...
0
votes
1answer
79 views

Stationary distribution of Markov Chain with departure

I have a Markov Chain of $N$ states. Such states represent the energy levels in a molecule. The states' connectivity is as follows: States $j\in\{0,\ldots,N\}$ transition to $k\in\{\max(j-M,0),...,\...
0
votes
1answer
68 views

In smooth stochastic dynamics, if a Lebesgue-like measure is both forward-time and reverse-time stationary, is the measure necessarily incompressible?

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact connected $C^\infty$-smooth manifold. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to ...
0
votes
1answer
85 views

If a probability measure is stationary in both forward time and reverse time, does this imply that the measure is incompressible?

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and let $X$ be a compact metric space. Let $F \colon \Omega \times X \to X$ and $\bar{F} \colon \Omega \times X \to X$ be measurable ...
0
votes
0answers
34 views

Derivation of a differential equation from a SDE

Suppose there is a non-homogeneous Markov process with state space $\mathbb{R}_{+}$ driven by this McKean-Vlasov-tipe SDE: $$ dY_t = a \mathbb{E}[Y_t]\ dt - b\ Y_t\ dt - Y_t\ dN_{aY_t}$$ where $...
0
votes
2answers
108 views

Markov with epsilon memory and Quantitative Strong Markov property

We have a process $\{X_{t}\}_{t\geq 0}$ ,with fixed parameter $\epsilon>0$, starting from zero that satisfies The process is strictly monotone $X_{t+r}-X_{t}>0$ with moments existing $p\in(-\...
0
votes
0answers
30 views

Minimize the asymptotic variance as in Tierney's theorem, but only for a single fixed function

Let $(\Omega,\mathcal E,\mu)$ be a probability space and $\kappa^{(i)}$ be a Markov kernel on $(E,\mathcal E)$. $\kappa^{(i)}$ can be considered as a contractive self-adjoint linear operator on $$L^...
0
votes
1answer
66 views

A question about positive operator pregenerator [closed]

Thank you for reading. My question was raised up when I tried to prove an example in the book of Liggett(1985), which is in P13 Example 2.3(a). Here is a link of the page: https://books.google.com/...
-1
votes
1answer
82 views

Coupling argument involved in the contracting and mixing properties of the Glauber dynamics for an Ising model

While doing a research work, I had to read about the Glauber dynamics for an Ising model. A wonderful account on this is given in the book Markov Chains and Mixing Times by Levin, Peres and Wilmer. ...
2
votes
0answers
230 views

Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?

In the following paper (extended version here), at the beginning of section 3, the authors give two axioms about $\mathcal{A}$. Axiom 1 is about $\mathcal{A}$ being an algebra. I do not see where this ...
1
vote
0answers
60 views

Convexity of conditional relative entropy for Markov distributions

Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is \begin{align} D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\ & =\...
2
votes
1answer
327 views

Markov chain and random iteration of functions

Could anyone give me some references for the convergence rate of Markov chain arising from the random iteration of Lipschitz functions which moves as follows: $$ X_{n+1}= f_{\omega_n}(X_n)$$ where $...
3
votes
0answers
196 views

Maximize an $L^p$-functional subject to a set of constraints

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces $f\in L^2(\lambda)$ $I$ be a finite nonempty set $\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
2
votes
1answer
190 views

Existence and uniqueness of a stationary measure

This same question was also posted on MSE https://math.stackexchange.com/questions/3327007/existence-and-uniqueness-of-a-stationary-measure. Recently I have posted the following question on MO ...
2
votes
0answers
99 views

Characterizing the relationship between element-wise Markov transitions and the full-conditionals of the stationary distribution

Consider a $p$ dimensional random variable with a discrete support. Consider a Markov transition kernel on the state space that is defined in terms of element-wise transition distributions. One can ...

1
2 3 4 5
9