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

Simplifying calculations for hitting probabilities using communicating classes

When given a rather elaborate transition matrix for 6 state Markov chain, for example $$\begin{bmatrix} 0&0&\frac{1}{2}&0&0&\frac{1}{2} \\ \frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0\\ \frac{1}{3}&0&\frac{1}{3}&0&0&\frac{1}{3} \\…
1
vote
1 answer

Modelling problems using Markov chains.

A bucket contains four red and three green balls. The probability of picking a ball is equal. If a red ball is chosen, it is removed from the bucket and if a green ball is picked, it is placed back into the bucket. The game continues until all four…
thesmallprint
  • 3,636
  • 1
  • 16
  • 25
1
vote
0 answers

How Can I know if Something is a Markov Chain?

Given a state space of $\{1, 2, 3\}$, and probabilities to transition $p(1,2)$, etc (which are given), how would I know if $Y_n = X_{5n} or Z_n = X_{n+17}$ or $W_n = (X_n)^2$ are Markov chains? I get the feeling that, for $Y_n = X_{5n}$, I need to…
1
vote
1 answer

ergodicity in Markov Chains

I have a question regarding ergodicity in the context of Markov chains. I do understand that the intuition about it is that if it’s possible to get from any state to any other state you’ve got an ergodic chain, fine. My lecturer (who uses…
Fede C
  • 21
1
vote
1 answer

Probability to visit a node exactly n times in a markov chain

Markov chain.png Ok so we have the above Markov chain and all of the transitions coming out of a vertex are equal( $p_{12}=p_{11}=1/2, p_{21}=p_{23}=1/2, p_{31}=p_{32}=p_{34}=1/3 $ and $p_{41}=1 $ Ok so how can we find the probability to visit node…
1
vote
2 answers

Markov Chain and Expectation

A coin with probability of heads p is being tossed repeatedly. Consider the 4 state Markov chain given by the results of the previous toss and the toss before that. Using Markov chain hitting time arguments, find the expected time we need to wait…
1
vote
1 answer

Equilibrium Distribution of Reducible Markov Chain

Let's say a Markov chain has the state-space $S = \{A,B,C,D\}$ Transition Matrix as follows: $$ \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix} $$ This is NOT…
1
vote
1 answer

If a state is transient, then all states are transient.

I'm a bit confused by this theorem, not sure of the name in english but here are the details: Let the markov chain $X = (X_n)_{n\geq 0}$ with transition matrix $\mathbb{P}$ and state space $S$. Let $X$ be irreducible then, if a state in $S$ is…
Fainted
  • 181
1
vote
1 answer

Random shuffling as a Markov Chain

Consider the set of permutations (i.e. of a deck of cards). We can move from one permutation to another, by swapping two different cards in the permutation. let's assume $\mu$ is uniform distribution on those transpositions. Is $P_\mu$, the Markov…
Covvar
  • 257
1
vote
0 answers

Showing transience condition for this continuous markov chain

I have a markov chain with the following $Q$ matrix: $q_{n,n+1}= 1$, $q_{n, 0} = \delta_n$ for $n\neq0$. That is, for any $n\geq1$ we move to $n+1$ with rate $\delta_n$ or to $0$ with rate $\delta_n$, and we move to $1$ to $0$ with rate 1 with…
ocstat
  • 33
1
vote
1 answer

Efficient algorithm for finding period of Markov chain

What is the least time consuming way to find a period of state of irreducible Markov chain? I wondering if there is an algorithm which does not use matrix multiplication?
Hlib
  • 111
1
vote
1 answer

How does the sum of row in infinitesimal rate marix for Continous Time Markov Chain tend to zero?

i have a single question about the theory of infinitesimal rate or generator matix for CTMC. I have learned that the sum of row in infinitesimal rate or generator matrix have sum of zero. From many days, i have search many textbook and paper about…
Refan
  • 21
1
vote
3 answers

What is the expected time to absorption in a Markov Chain given that the system is absorbed to a specific recurrent state?

Consider the attached Markov Chain. I need to calculate the E[number of visits to State 2 | the system starts from 2 and gets absorbed to State 1]. More generally, I am interested in calculating the expected time to absorption given that the system…
Salivan
  • 397
1
vote
0 answers

A question about Markov kernel definition.

Here is the definition of Markov kernel I am reading from this paper, https://arxiv.org/pdf/1410.5110.pdf, it defines the Markov kernel as: A Markov kernel, $\tau$, is a map from an element of the sample space and the $\sigma$-algebra to a…
Fly_back
  • 123
1
vote
1 answer

How to solve the large state Markov Chain

I am solving a paper, in which there is a very large Markov chain. How can I find the steady state probability of a very large Markov chain since solving it through eigenvector process is proving to very difficult. I have attached the Markov chain…
SJa
  • 849