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

Probability of extinction in branching process

Consider a branching process where the offspring distribution is given by $$P(X = k) = \frac{1}{2^{k+1}}$$ what is the probability that the process becomes extinct at exactly at the $n$th generation? The answer is supposed to be $\frac{1}{n(n+1)}$…
1
vote
1 answer

Use Discrete Markov Chain to predict n steps ahead

I modeled a Markov Chain with M states. Assuming that the process is homogeneous in time. But, each state has a differente resident time. Moreover, each state has a self-loop transition and a transition to other state. I assume that transition…
Gustavo
  • 13
1
vote
1 answer

Proving irreducibility of Markov chain

I have a Markov chain: state: a permutation of n cards transition: taking the top-most card and randomly choose one of the n possible positions for the card I know it is obviously irreducible because we can arrive at any permutation states from…
1
vote
1 answer

Definition of limiting distribution in a Markov chain -- why do we condition on the initial state?

Given a Markov chain $\{X_n \mid n \in \{0, 1, \ldots\}\}$ with states $\{0, \ldots, N\}$, define the limiting distribution as $$ \pi = (\pi_0, \ldots, \pi_N) $$ where $$ \pi_j = \lim_{n \to +\infty} \mathbb{P}\{X_n = j \mid X_0 = i\} $$ I am…
d125q
  • 2,370
  • 17
  • 19
1
vote
1 answer

Markov chain knowing future

I was wondering whether or not P(X1 = S1 | X0 = S0) and P(X1 = S1 | X0 = S0 and X2 = S2) are the same? What I mean is can we get some information from the future states? Thanks!
1
vote
1 answer

Every finite closed class is recurrent

Let $(X,E,P)$ denote a Markov chain, where $X=(X_n)_{n\in\mathbb{N}_0}$, $E$ is finite state space and $P$ is the transition matrix. Claim: Every finite closed class is recurrent. Here is how we proved that, where $$ H(i):=\inf\left\{n\geq 0:…
user34632
1
vote
0 answers

Why does a Markov chain with one irreductible class has a lower triangular transition matrix?

Given a Markov chain on an infinite and countable set of states, with one irreductible class that has a finite number of states, why can its transition matrix be put in a lower triangular form ? $\begin{bmatrix}D & 0\\R & Q\end{bmatrix}$ And then,…
1
vote
1 answer

Proof of "strong law of large numbers" in Markov Chains

I have been given a theorem stating an analogue of the strong law of large numbers for Markov chains. It states that if $X=(X_n)_{n\in\mathbb{N}}$ is a Markov chain with transition matrix $p$ and $\pi$ is its invariant probability and…
MickG
  • 8,645
1
vote
0 answers

Marcov Chain confirmation

I am currently having some problems on the following question: Given is the function $f(x)$: $f(x) = 0,1,2$ with probability $\frac{1}{3}$ for each. I have to give the state space, transition probability matrix and explain why independent successive…
Nedellyzer
  • 1,174
1
vote
1 answer

Transition probability matrix of Markov chain

Given that $g(x)=\begin{cases} 1/3 \quad\text{for } x=0\\ 1/3 \quad \text{for } x=1\\ 1/3 \quad \text{for } x=2\end{cases}$ Explain why independent draws $X_1,X_2,\dots$ from $g(x)$ give rise to a Markov chain. What is the state space and what…
aeswar
  • 23
1
vote
1 answer

Difference in markov chain persistense probability

I feel confused! Suppose that we are given a markov chain that has transition rates for each $q_{ij}$. So you can multiply the matrix $[p_1,p_2,\ldots,p_n] Q=0$ and solve the system. $p_1, p_2, \ldots$ in my notes are persistence state probabilties.…
GorillaApe
  • 1,071
1
vote
0 answers

Quasi-stationary distribution of a state in a birth-and-death MC

I need to find an expression for the first state in an MC with transition matrix $P$ with tridiagonal entries. The state space is $U={1,2,..n}$ with the last state being absorbing. Expressions for limiting distribution for the other states are given…
sigma.z.1980
  • 1,717
1
vote
1 answer

Is this stochastic process a Markov chain?

I have been struggling sometime now with the following question and I feel like I am stacked. Let $X_n : n= 0,1,\ldots$ be a sequence of iid discrete random variables with $$P(X_n=j)=a_j>0 \qquad \text{ for } j=0,1,2...$$ Is…
Wanderer
  • 927
1
vote
1 answer

How to show positive recurrence/ null recurrence?

Suppose that you have a Markov chain with state space $E$ containing $0$. Assume that $$ p_{00}^{(2n)}=\binom{2n}{n}\left(\frac{1}{2}\right)^{2n-1}~~~\text{ and }~~~p_{00}^{(2n-1)}=0~~~\text{ for }n\in\mathbb{N}. $$ Is $0$ transient,…
mathfemi
  • 2,631
1
vote
0 answers

Check if $(N_n)$ is a Markov chain

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ if }N_{n-1}=0\\X_{n,1}+\ldots+X_{n,N_{n-1}}, & \text{ if…
Salamo
  • 1,094