Questions tagged [markov-chains]

Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

A Markov chain is a stochastic process on a discrete (finite or countably infinite) space in which the distribution of the next state depends only on the current state. These objects show up in probability and computer science both in discrete-time and continuous-time models. For Markov processes on continuous spaces please use .

A discrete-time Markov chain is a sequence of random variables $\{X_n\}_{n\geq1}$ with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states, i.e. $$\mathbb P(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\mathbb P(X_{n+1}=x\mid X_{n}=x_{n}),$$ if both conditional probabilities are well defined, i.e. if $\mathbb P(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

5938 questions
1
vote
2 answers

Period of Markov Chain when no chance of return

Everywhere I look I see that the period of a state $i$ in a Markov chain is given by $$ \gcd\{n>0 : P_{ii}^n>0 \} $$ but what do we mean if the set $\{n>0 : P_{ii}^n>0 \} = \emptyset$? For instance in a two state Markov chain with $P_{00}=1$ and…
nullUser
  • 27,877
1
vote
1 answer

Is it possible to find a new variable Y such that a non-Markovian random variable X becomes Markovian?

It is given that $$X_n = \min(X_{n-1}, X_{n-2}) + \epsilon_n \quad \forall n\ge2 $$ where $X_0=X_1=0$, and $\{\epsilon_n:n\ge2\}$ are i.i.d random variables equal to either -1 or 1 with probability $1/2$. The question asks if $(X_n:n\ge0)$ is a…
1
vote
1 answer

Proof of property of Markov chain

Given markov chain $X$, how to prove following property by markov property: $$P(X_{n+1} = s | X_{n_1} = x_{n_1}, X_{n_2} = x_{n_2}, ...,X_{n_k} = x_{n_k} ) = P(X_{n+1} = s | X_{n_k} = x_{n_k}) , \quad \forall 0 \le n_1 < n_2 < ...
1
vote
2 answers

Aperiodic but not irreductible Markov Chain

If I understood well, a Markov Chain with state space $E$ is said to be irreductible if for all $x,y\in E$ there is $n$ such that $$P^n(x,y)>0,$$ where $P$ is the transition matrix. Also, I know that a Markov chain is aperiodic if and only if for…
Gabriel
  • 4,513
1
vote
0 answers

Markov Chain -- Transient or Recurrent class?

Specify the classes of the Markov chain, and state whether they are recurrent or transient. \begin{align*} P_4= \begin{bmatrix} \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0\\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0…
mXdX
  • 571
  • 3
  • 14
1
vote
1 answer

In Markov Chains, what is the difference between null recurrent and positive recurrent?

Let $P$ be the transition probability matrix for the homogeneous Markov chain on the states $E=\{1, 2, 3 \}$. $$ P = \left[ \begin{array}{ccc} 2/3 & 1/3 & 0 \\ 1/3 & 1/3 & 1/3 \\ 0 & 0 & 1 \end{array} \right] $$ States $E=\{ 1 \}$ and $E=\{ 2 \}$…
eBopBob
  • 111
  • 1
  • 9
1
vote
1 answer

Limit distribution of a reducible Markov chain

I had a simple question yesterday when I was trying to solve an exercise on a reducible,aperiodic Markov Chain. The state spase S was $$S=\{1,...,7\}$$ and we could partition it into two closed classes $\{5,6,7\} \bigcup \{3,4\}$ but the class…
1
vote
1 answer

Explanation of Markov transition function

Here the definition of my course (in the picture below). Could someone explain me the Chapman-Kolomogorov equation ? I don't really understand what it mean. Also, I tried to make a parallel with discrete Markov chain, I don't see the link between…
1
vote
1 answer

Function of a Markov chain is a Markov chain

Given a Markov chain $X_n$ with it's states taking values in the set $S$. $f$ is a function, $f:S\rightarrow\mathbb{R}$. If a $f(X_n)$ is also a Markov chain, prove that either $f$ is injective or $f$ is constant. I'm totally clueless as to how I…
1
vote
1 answer

Difference between two definitions for recurrence

Let $\{X_n\}$ be a Markov chain on a state-space $E$. A state $i$ is recurrent if $$P(X_n = i\;\text{for some} \;n\geq 1|X_0=i) = 1\tag{Definition 1}$$ $$\text{for some}\; n\geq 1\; P(X_n=i|X_0=i)=1\tag{Definition 2}$$ Definition $2$ is supposed to…
mrnovice
  • 5,773
1
vote
0 answers

Existence of a reversible distribution for Markov chains with compact state space

Krylov–Bogolyubov theorem shows that for any Markov chain on a Polish space $S$ that satisfies suitable conditions, there exists a stationary probability measure. My question is that under what conditions there exists a stationary and reversible…
1
vote
1 answer

$\pi(x) P_x ( \tau_y < \tau_x^+) = \pi(y) P_y( \tau_x < \tau_y^+)$?

$P$ is the transition probability of a finite, irreducible and reversible Markov chain (i.e. a walk on a finite network$G$). $\pi$ is the stationary distribution.For $y \in G$, $\tau_y$ is hitting time of $y$, $\tau_y^+$ is first hitting time after…
Elle Najt
  • 20,740
1
vote
1 answer

Solving Backwards Chapman-Kolmogorov Questions

The question is A flea hops on the vertices A, B and C of a triangle. Each hop takes it from one vertex to the next and the times between successive hops are independent random variables, each with an exponential distribution with mean…
1
vote
0 answers

Counter Example on Markov Chain

I have a question on find a counter example of Markov Chain. The question states as follows: Suppose $X_0$, $X_1$ are the Markov chain whose state space is $\mathbb{Z}$, Since we know from Markov property, we know that $$ \mathbb{P}(X_n = i_n | X_1…
1
vote
0 answers

how to calculate limit of P(Xn = j | X0 = i) in markov chain?

1. in http://robotics.eecs.berkeley.edu/~wlr/126/w12.htm lim N ® ¥ [1{X1 = j} + 1{X1 = j} + … + 1{XN = j}]/N = 0 What is N? how it limit to zero? and what do 1 in 1{X1 = j} represent? /N must be 0, no other choice, any other example to show limit…
Scott
  • 65
  • 6