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

Finding Markov chain transition matrix using mathematical induction

Let the transition matrix of a two-state Markov chain be $$P = \begin{bmatrix}p& 1-p\\ 1-p& p\end{bmatrix}$$ Questions: a. Use mathematical induction to find $P^n$. b. When n goes to infinity, what happens to $P^n$? Attempt: i'm able to find…
Michael
  • 11
1
vote
0 answers

Markov Chain Lumpability conditions not met but reduced state space transition probabilities are equal to the lumpability method for calculation.

I have a Markov chain with a state space $S$ and its transition probability matrix generated mathematically as $P$. I have created another Markov chain with a reduced state space $S_r$ made by partitioning $S$. The transition of this reduced state…
prash
  • 141
1
vote
1 answer

Upper bound of first return probability of Markov chain

I only have problem about (b). My efforts: Consider the special case in which all transition probabilities are 1. Then the first return probabilities are $f^n_{jj}=1$ when $n=r$ and $f^n_{jj}=0$ when $n\neq r$. Since the problem requires $n>r$, any…
1
vote
0 answers

Continuous Time Markov Chain Remaining in a State

I am faced with the following question: given a Markov Chain with three possible states, $1,2,3$, and transition rates: $$\alpha(1,2)=\alpha(2,3)=1,\:\alpha(2,1)=\alpha(3,2)=4$$ and the assumption that $X_0=1$, what is the probability that $X_t=3$…
scoopfaze
  • 976
1
vote
2 answers

What is this period of this Markov chain?

We have the following markov matrix. \begin{bmatrix}0&1&0\\1/2&0&1/2\\0&1&0\end{bmatrix} So we have states 1, 2, and 3. State 2 always return to 2 in 2 steps. States 1 and 3 can return to themselves in a multiple of 2 steps. So I am assuming that…
1
vote
1 answer

A simple case of random walk

$\forall n \in \mathbb{N}$ we can either move from state $S_n$ to state $S_{n+1}$ with probability $p$ or to state $S_{n-1}$ with probability $q=1-p$. Also we move from state $S_0$ to state $S_{1}$ with probability $p$ or stay at state $S_{0}$ with…
Pranasas
  • 1,370
1
vote
1 answer

Markov Chains, Assistance will be much appreciated!

1) In the Markov chain linked below, in the long run, what fraction of the time does the chain spend in state 3? https://i.stack.imgur.com/tntbj.png 2) Find the probabilities of states 1 , 2 , and 4 in the stationary distribution of the Markov…
1
vote
1 answer

Calculate the average number of times transition states are visited given known absorption state

Given a transition matrix like the one below I am trying to find out how many states it passes through given that we reach state 4 in the end. State 4 and Out are my two absorption states. Taking the upper left side as matrix Q and finding the…
1
vote
1 answer

Proving a Markov Chain is Recurrent

Space $=S=\{0,1,2,\cdots\}$ Transition probabilities $P(n,n+1)=p, P(n,0)=1-p$ $T_n$ is the first time the Random Variable returns to $n$ I want to show that $P_n(T_n<\infty)=P(T_n<\infty|X_0=n)=1\,\,\forall n\in\mathbb N$ I was able to show…
Anvit
  • 3,379
1
vote
2 answers

How to find $\lim _{n\to \:\infty }P^n$ without calculating $P^n$?

Given the discrete time markov chain P= $\begin{pmatrix}0.6&0.4&0&0\\ 0.2&0.8&0&0\\ 0&0&0.6&0.4\\ 0&0&0.4&0.6\end{pmatrix}$ How do I find $\lim _{n\to \:\infty }P^n$ without calculating $P^n$? I know it has something to do with the fact that this…
1
vote
1 answer

Triangle Markov Chain question

A triathlon consists of $3$ disciplines: swimming, cycling and running. A triathlete does a training session every day. However he doesn’t want to pay for professional coaching advice so instead his strategy for training is to choose the next day’s…
user634512
1
vote
1 answer

Markov Chain with dice rolling board game

Simple board game. S---1---2---3---4---5---H You start at S. Each turn, your roll a standard six-sided die, and move forward that number of spaces. Your goal is to reach H. You can only get to H on an exact roll; if you roll a number that would…
1
vote
1 answer

Markov chain - recurrence and transience

Does a Markov chain with infinitely many recurrent states and infinitely many transient states exist? I believe it doesn't exists but I'm not sure how can I prove it. Thanks guys! :D
Manko
  • 145
1
vote
0 answers

Higher order developing Markov chains?

Are there Markov chains, possibly conventionally defined higher order Markov chains, whose state space is developing, I.e. number of states are changing and transition matrix are changing, e. G., by application some dynamic operator to it. Maybe…
TomR
  • 1,313
1
vote
0 answers

The relationship of Markov chain properties

I'm trying to understand the Metropolis-Hastings algorithm and its theoretical background Markov Chain properties. Is there something wrong with this diagram for the time-homogeneous, finite state Markov chains? (Not sure if it requires to be…
hotohoto
  • 111
  • 4