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
2
votes
1 answer

$\psi$ irreducibility and ergodicity of Markov Processes

How is Markov chain splitting technique useful for inferring ergodicity of a Markov Chain?Assume that I am working with general state space (uncountable say $R^{N}$ but time is discrete. I want to show that the Markov Process is ergodic. I guess…
user24367
  • 1,286
2
votes
1 answer

Why is the mixing time defined with $\frac{1}{4}$?

Let $\{X_t\}_{t \in \mathbb{N}_0}$ be a discrete-time Markov chain with (countable) state space $\Omega$ and stationary distribution $\pi$. Let $x,y \in \Omega$ and $P^t(x,y)$ be the probability of moving to state $y$ in $t$ time steps, given that…
Babado
  • 1,306
2
votes
0 answers

Undefined Notation for Markov Chains In Durrett's Probability

Let $(S,\mathcal{S})$ be a measurable space (thought of as the state space of a Markov chain). In Durrett's probability, he defines a transition probability to be a function $p:(S,\mathcal{S}) \to \mathbb{R}$ such that For fixed $x \in S$,…
2
votes
1 answer

How to show random walk on semi-infinite line is null-recurrent

The figure shows the Markov chain with the transition probabilities. I need to prove that it is null recurrent by showing $$ \sum_n p_{00}^{(n)} \to \infty$$ Showing the above is enough as I can show it is not positive recurrent as no stationary…
Black Jack 21
  • 698
  • 6
  • 24
2
votes
1 answer

Why is the stationary distribution of a Markov Chain one over the mean sojourn time?

I am reading the book "Markov Chains and Mixing Times" by Levin et al. and i have a problem with proposition 1.14, page 12. There a stationary distribution is constructed by defining for fixed initial state z $$\tilde \pi(y):=\mathbf…
2
votes
2 answers

Limit theorem of Markov chains applied to higher order Markov chains

I have a second order Markov chain with 4 states {A,T,C,G} (the 4 DNA nucleotides). the transition matrix looks like this: A T C G AA[0.1, 0.6, 0.2, 0.1] AT[0.3, 0.1, 0.5, 0.1] AC[0.5, 0.3, 0, 0.2] AG[..., ..., ..., ...] TA[..., ...,…
2
votes
0 answers

Periodic and aperiodic Markov chains

Let $X$ be an irreducible homogeneous Markov chain $(\mu,P)$ with state space $S$. The following statements should be proved or disproved: a) If a $x\in S$ with $P(x,x)>0$ exists, then $X$ is aperiodic. b) If $X$ is aperiodic, then there exists a…
Tino
  • 137
  • 7
2
votes
0 answers

Prove $Y_k$ is a homogeneous markov chain

Let $(X_n)_{n\in\mathbb{N}_0}$ be a homogeneous markov chain with starting distribution $\mu$, transition matrix $P$ and $P(x,x)<1$ for all $x\in S$, and $\tau_0:=0$ and $\tau_{k+1}:=\inf\{n\geq \tau_k:X_n \neq X_{\tau k}\}$ for all $k\in…
mayme
  • 21
2
votes
1 answer

Is there a general procedure for finding the limit of a Markov chain?

To solve a problem at work, I need to write an algorithm that will find the limit of a user-submitted Markov chain. The Wikipedia page on Markov chains says Because there are a number of different special cases to consider, the process of finding…
awlman
  • 33
2
votes
1 answer

Markov chain with finite positive recurrent states

If I have a Markov chain with finite positive recurrent states $\in S$, then that means starting from a given state $y$, the expected number of steps to return to state $y$ is finite. Now, if I start at state $j\ne y$ where $y,j\in S$, then I am…
Solver
  • 173
2
votes
1 answer

Question about proof with doubly stochastic matrix. Why do we need the uniqueness of $\pi_j?$

A stochastic matrix is called doubly stochastic if its rows and columns sum to 1. Show that a Markov chain whose transition matrix is doubly stochastic has a stationary distribution, which is uniform on the statespace. I'm trying to under…
Parseval
  • 6,413
2
votes
0 answers

Markov Chain: Ehrenfest

Suppose we have two boxes, labeled 1,...,d balls Initially some of these balls are in box 1 and the remainder are in box 2. An integer is selected at random from {1,...,d}, and the ball labeled by that integer is removed from its box and placed in…
jaclynx
  • 121
2
votes
1 answer

General Markov property

Let $X_0,X_1,\ldots$ be a Markov chain with state space $\mathbb{Z}$. Now I found in a textbook that we have $$ \mathbb{P}(X_{n+1} \in A \mid X_n = i, (X_{0},X_1,\ldots,X_{n-1}) \in B) = \mathbb{P}(X_{n+1} \in A \mid X_n = i) $$ for all $n \in…
user562724
2
votes
1 answer

Markov Chains. How to find F with different shape of I and Q

First for all I want to say that I deal with Markov Chains only second day so I have some problems with terminology. Sorry for that. I need to solve following matrix: Now in I need to compute FR. In order to compute FR I need to find F first which…
2
votes
1 answer

Conditions under which a finite, irreducible Markov Chain does not converge to its stationary distribution

I understand that if all states of an irreducible Markov chain are non-null recurrent, then the MC has a unique stationary distribution if an irreducible Markov chain is finite, then all of its states are non-null recurrent. Therefore, an…
theQman
  • 1,097