1
vote
2answers
82 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
2
votes
1answer
75 views

convergence rate of occupation measure of ergodic Markov Chain

Given an ergodic Markov chain $(X_n)_{n\geq 1}$ in $R^d$with $\pi$ as the invariant distribution of the transition kernel, under good conditions we have that the empirical occupation measure converges ...
1
vote
0answers
44 views

forward algorithm Hidden Markov Model

I am studying the the forward-backward algorithm used in Hidden Markov Models. I understand that that you are trying to propagate through a sequence (and the available states) to find the most ...
3
votes
0answers
74 views

Nonlinear Markov process

Consider the following nonlinear $\mathbb{R}$-valued stochastic recursive sequence: $ X_{n+1} = F(X_n) + W_{n+1}, \quad (W_n)_{n\ge1} \stackrel{ \scriptsize \mathrm{i.i.d.} }{ \sim } \phi. $ How can ...
0
votes
0answers
63 views

An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...
-1
votes
1answer
183 views

Generating independent random variable from two correlated random variables

Suppose two random variables $X$ and $V$ are given. I am wondering what kind of condition we need to impose on joint distribution of $V$ and $X$ to make sure that there exists a random variable $Z$ ...
1
vote
0answers
58 views

CLT for a Markov Renewal Process

Suppose $(X,T)=\{(X_n,T_n)\}_{n\geq0}$ is a Markov renewal process, where $X$ is a finite-state, discrete-time Markov chain with state space $\{1,2,...,R\}$. $T$ is the additive component, more ...
1
vote
1answer
38 views

Quasi-stationary distribution for a death process

In the paper, Survival in a quasi-death process by van Doorn and Pollett, the quasi-stationary distribution of a transient CTMC is discussed and QSD for a simple death process is derived. Consider a ...
2
votes
1answer
95 views

Transition probabilities in coupled CTMCs

I know that for a CTMC, the probability of transition from time $0$ to $t$ is given by $P(t)=e^{Q(t)t}$. I have a system of $N$ interdependent CTMCs evolving simultaneously. Each of the $N$ CTMCs can ...
1
vote
1answer
51 views

Minimal variance for phase-type distributions?

Let $\mathcal{D}(m)$ be the set of phase-type distributions constructed from $m+1$-state Markov chains. Recall that the coefficient of variation of a distribution $D$ is the ratio of the standard ...
3
votes
0answers
148 views

Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
3
votes
0answers
40 views

Relative vulnerabilities in SIS epidemic model

Consider the SIS model of epidemic spreading. There is a finite graph $G(V,E)$, link infection rates $\lambda_{ij}$ and node recovery rates $\mu_i$. There are a few initial nodes which are infected at ...
4
votes
1answer
134 views

Log-likelihood in regime switching

Not sure if this question is too simple to be asked here... In the following paper Cho, Jin Seo, and Halbert White. "Testing for regime switching." Econometrica 75.6 (2007): 1671-1720. doi: ...
1
vote
0answers
122 views

An optimization in Markov Chain

We are given two correlated random variables $V$ and $X$ supported over a finite alphabets $\mathcal{V}$ and $\mathcal{X}$. Suppose the marginal $P_V$ and conditional distribution $P_{X|V}$ are ...
0
votes
1answer
185 views

Stationary distribution in general Markov Chains

This is just a reference request for a result which is very general, useful and should be well-known, but I've failed to find a good reference to cite. The problem is to define the "most natural" ...
6
votes
1answer
179 views

Finding cohesive (low exit probability) sets in a Markov process

The following is a fact about Markov chains that came up in a game theory paper. The purpose of this question is to ask if related notions or similar results are found elsewhere in probability, or are ...
0
votes
0answers
72 views

Supremum in a Markov chain model

A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach ...
3
votes
4answers
290 views

Does the variance of a continuous time, time homogeneous, Markov process starting from one point necessarily not decrease?

Let $x_t$ be a zero mean, time homogeneous Markovian process (chiefly look at the case where the value is in $1$ dimension) over time $t$ starting from $x_0=0$. Is it necessary that, in continuous ...
1
vote
0answers
128 views

The problem of the drunkard in a valley [closed]

We consider a Markov chain on a subset of positive integers S = {0, 1, 2, 3, .......N}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. p(i, j) ...
5
votes
2answers
202 views

Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think. I am interested in anything (ideas, references) related to the following problem: Suppose that $A ...
4
votes
0answers
66 views

Best convergence rate for convolutions on $\mathbb{Z}_p$

Suppose, that we have sequence of i.i.d variables $X_1,\ldots,X_n$ taking values in $\mathbb{Z}_p$ such that $d_{TV}(X_1,U) < \delta$. How fast, in terms of $\delta$ and $n$ does the sum ...
7
votes
2answers
290 views

Convergence rate of the convolution of almost uniform measures on $\mathbb{Z}_p$

Statement Given a finite abelian group $G$ and two independent random variables $X,Y$ taking values in $G$ and satisfying $d_{TV}(X,U_G)\leqslant \delta$ and $d_{TV}(Y,U_G)\leqslant \delta$ (where ...
3
votes
0answers
173 views

Generalized Markov Processes on CW complexes of dimension > 1

Markov processes have a large variety of applications to physics and chemistry (as well as many other fields). Such processes are formulated on graphs, i.e., CW complexes of dimension one. It is ...
0
votes
3answers
406 views

Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...
2
votes
0answers
103 views

Kullback-Leibler Divergence of Stationary Distributions of Markov chains

Consider two finite Markov chains on the same state space, both assumed to be irreducible, with transition matrices $P$ and $Q$ and associated stationary distributions $\pi$ and $\tilde \pi$. Is it ...
1
vote
1answer
133 views

Optimum control of a probabilistic automaton

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to ...
2
votes
0answers
257 views

Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k. For example, the terminating sequence could be ...
1
vote
1answer
140 views

Regarding Ricci curvature of Markov chains

In Ricci curvature of Markov chains on metric spaces Yann Ollivier, defines a coarse Ricci curvature for a Markov chain with transition kernels $\{m_x\}$ defined on a metric space $(X,d)$ as follows: ...
0
votes
1answer
207 views

Markov Chain: state reduction

Hi I am trying to understand a proof in a paper (written by Isaac Sonin), I don't know if anyone could give me a clarification on the following: Firstly we have a Markov chain $\{Y_k\}$ with finite ...
2
votes
0answers
131 views

Markov operators and existence of ergodic measures

My question refers to the yesterday's question (see here) of John Learner and goes as follows: Can we deduce the existence of an ergodic measure if we know that an invariant measure exists, but the ...
2
votes
0answers
58 views

iterated mutinomial and hitting time

Let $N,k \geq 1$ be two integers and consider the following Markov chain on $[0,k\times N]^k$. It starts at $X^0=(N, N, \ldots, N)$ and $X^{n+1}$ is the realisation of a multinomial distribution with ...
0
votes
0answers
101 views

Inequality relating stationary probabilities and transition probabilities

Let $P$ be the transition probability matrix of a aperiodic irreducible DTMC and let $\pi$ be its stationary distribution. I would like to know if there is any literature on types of Markov chains ...
8
votes
0answers
102 views

Functions between Markov chains that preserve local harmonicity

Given two Markov chains with respective state-spaces $S$ and $T$, say that a function $\phi$ from $S$ to $T$ is holomorphic iff for all states $t \in T$, every real-valued function $f$ on $T$ that is ...
3
votes
1answer
131 views

Markov Chains based on sampled transition probabilities [closed]

If I have a process that transitions between states with some set, unknown probability, I can sample to find the transition probability. This probability is a sample average, with a well understood ...
1
vote
1answer
132 views

Is anything known about Large Deviation Principle for non additive functionals on Markov chains?

Let $\Sigma$ be a finite set of cardinality $|\Sigma |$ and $$\Pi = \{ \pi(i,j)\}_{i,j = 1}^{|\Sigma|}$$ a stochastic matrix (ie a matrix whose elements are non negative and such that each row sum ...
0
votes
1answer
112 views

A basic question on necessary and sufficient condition for positive recurrence

If state $j$ is recurrent and the following holds can it be called as positive recurrent ? $$\lim_{n -> \infty}\frac{1}{n}\sum_{k=1}^{n}p_{jj}^{(k)} > 0$$ I know that this a necessary ...
2
votes
1answer
223 views

The first eigenvalue of a branching process matrix

Let $M$ be the real square matrix of a typed branching process, such that $M_{ij}$ is the expected value of offspring of type $j$ emanating from type $i$. We know that if the first eigenvalue if $M$ ...
1
vote
1answer
83 views

Empirical distribution of a collection of iid Markov chains

Suppose we have $N$ independent 2-point Markov chains each having a rate matrix $Q = [-1,1;1,-1]$ and stationary distribution $\pi = [0.5,0.5]$. At time $t=0$, we initiate the chains so that the ...
1
vote
1answer
469 views

Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...
1
vote
1answer
225 views

Equivalent Markov Random Fields

Hi, Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ? Thanks!
1
vote
2answers
213 views

The limiting behavior of geometric random walk

I would like to know what the asymptotic limiting behavior is for the following random walk on $\mathbb Z^d$. By Donsker's invariance principle, I suspect that its behavior is diffusive, i.e., the ...
1
vote
1answer
358 views

How to prove ergodic property from aperiodicity and positive recurrence

How to prove that in case of an irreducible, aperiodic and positive recurrent Markov Chain time average along sample paths is equal to the ensemble average ? i.e. $$\lim_{n\to \infty ...
0
votes
1answer
130 views

Hidden Markov: representing joint probability for set of observations as a product of two subset probabilities.

Good day to everyone! My question concerns Hidden Markov Models and is pretty basic. In one of the books ("Introduction to Machine Learning" by Ethem Alpaydin, 2nd Edition, p.373), I get the ...
4
votes
1answer
195 views

Approximating a hitting time for some state using the stationary distribution?

Provided a random walk on a bounded interval, with step probabilities, $p$ and $q$ and a stationary distribution $\pi$, how "bad" of an approximation is to assume that the hitting time for a position ...
0
votes
1answer
226 views

Estimates for the mixing time of a Markov Chain with biased initiation

Imagine I have some Markov process consisting of a biased random walk on the integers, over some interval $[0, L]$, with $+1$ and $-1$ step probabilities of $p$ and $q$, respectively, s.t. $(p + q) = ...
1
vote
0answers
260 views

a problem on DTMC

For a Markov chain $\lbrace X_n, n\ge0\rbrace$ with transition probabilities $P_{i,j}$, consider the conditional probability that $X_n = m$ given that the chain started at time $0$ in state $i$ and ...
10
votes
2answers
2k views

Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves

In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a 3x3x3 Rubik's cube, starting in an arbitrary configuration, can strictly be ...
4
votes
1answer
177 views

Practical way to check for geometric convergence

Target distribution is multimodal, 24 dimensions, continuous state space. For MCMC integration (MH sampler) I use a manually tuned proposal distribution. When I measure the convergence rate ...
0
votes
1answer
273 views

Simple markov chain problem

I know this is an easy problem, but I can't figure it out. A particle takes discrete steps $σ_1,σ_2,σ_3,…,σ_n$ which take on values +1 or −1. However, $P(σ_i=+1)=p$ and $P(σ_i=−1)$ will be $1-p$. ...
2
votes
1answer
1k views

Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid

Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability ...