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
3
votes
3 answers

Markov Chain problem from Grimmett and Stirzaker Ex 6.1.2.a

Problem 2 in section 6.1 of Grimmett and Stirzaker (G+M) asks: a die is rolled repeatedly which of the following are Markov chains, and supply the transition matrix for those that are: a.) the largest number up to the nth role I'm stuck on the…
Bazman
  • 899
3
votes
1 answer

Proof about Steady-State distribution of a Markov chain

Consider $A$ as a matrix, that when normalized represents an finite-state time-homogeneous Markov chain $M$ with entries $0\leq p_{i,j}\leq 1$, where each row sums up to $1$. We can also assume that $M$ is irreducible and aperiodic, hence it has an…
Nejc
  • 143
3
votes
0 answers

How to prove Detailed Balance Condition?

Given a Markov chain with a stationary distribution $\mathbf{\pi}$ and a transition matrix P, it satisfies the Detailed Balance Condition if: $$ \pi_i P_{ij}= \pi_j P_{ji}, \quad \forall i,j $$ My question is, how to derive this equation? I have…
Lynten
  • 131
3
votes
2 answers

States visit order in a Markov chain

Ok so we have a labyrinth with 6 possible states plus the exit position and we want to visit the state number 5, but not the death trap(6) and then exit the labyrinth through exit state, starting state is 1 as shown. The transition probabilities…
3
votes
2 answers

a theorem on transient and recurrent state in a DTMC

Is the following statement true: In a finite Markov chain, if $i$ is a transient state then there is at least one recurrent state $j$ such that $j$ is reachable from $i$.
user21982
3
votes
1 answer

How to tackle markov chains with transition cost?

A simple example would be: I have 3 states, A,B,C The transition matrix for the chain is: A B C A 0.1 0.3 0.6 B 0.4 0.2 0.4 C 0.5 0.2 0.3 and the transition cost matrix is: A B C A 3 5 1 B …
colinfang
  • 807
3
votes
1 answer

Computing the n-step transition probability of a Markov chain with repeated eigenvalues

I have a problem understanding a passage in Norris' book. If you have access to it, it's page 8. Here is the relevant text: More generally, the following method may in principle be used to find a formula for $p^{(n)}(i,j)$ for any $M$-state chain…
user68080
  • 47
  • 4
3
votes
2 answers

When is a Markov chain null recurrent?

Are there any necessary and sufficient conditions for a Markov chain to be null recurrent? What about sufficient conditions? Naturally, I am not looking for tautological statements, e.g., a Markov chain is null recurrent if and only if it is…
robinson
  • 1,918
3
votes
1 answer

How to "look back" in a Markov chain?

Imagine I have a discrete-time, discrete-space Markov chain with some transition matrix $B$ and stationary distribution $\pi$. If I know what state I'm in at some time $t$, how can I calculate $p ( X_{t-1} \mid X_t)$, the probability that I came…
Zack
  • 31
3
votes
2 answers

Show that if a Markov chain is irreducible and has a state $s_i$ such that $P_{ii}>0$, then it is also aperiodic.

Show that if a Markov chain is irreducible and has a state $s_i$ such that $P_{ii}>0$, then it is also aperiodic. Proof: Let $X=(X_0, X_1, X_2, \dots)$ be an irreducible Markov chain with a state $s_i$ such that $P_{ii}>0$. Recall a Markov chain…
3
votes
2 answers

Example of a markov chain that has a distribution that converges to some limit.

Can someone give me an example of a Markov chain that has a distribution that converges to some limit which depends on the initial distribution?
3
votes
1 answer

Given two biased coins, the probability of obtaining heads on the $i^\text{{th}}$ toss using the following strategy?

We are given two coins: A and B with probability of obtaining heads being: $\alpha$ and $\beta$ respectively. The following sampling rule is used for i=1,2,...: If the $i^{\text{th}}$ toss results in heads, stick to the same coin for the…
selz
  • 33
3
votes
3 answers

Random Walk on a Cube

A particle performs a randowm walk on the vertices of a cube. At each step it remains where it is with probability 1/4, or moves to one of its neighbouring vertices each having probability 1/4. Let A and D be two diametrically opposite vertices.…
JKnecht
  • 6,543
3
votes
0 answers

Markov chain monte carlo

The target is to simulate a discrete random variable $Z$ with mass function satisfying $\mathbb{P}(Z=i)\propto \pi_i$, for $i\in S$ and $S$ countable. Let $X$ be an irreducible Markov chain with state space $S$ and transition matrix $P=(p_{i,j})$…
user235238
3
votes
1 answer

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it when the transition probabilites change with time…
Josi
  • 33
1 2
3
30 31