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

If $X_0,X_1,X_2,...$ be a Markov chain then why $Z_n=X_0X_1...X_n$ is also a Markov chain?

If $X_0,X_1,X_2,...$ is a Markov chain then why is $Z_n=X_0X_1...X_n$ also a Markov chain? Could you explain briefly? Many thanks**
hatban
  • 11
  • 3
1
vote
0 answers

How to calculate the expect value in the question below and its limit?

Question: Consider the two-state Markov chain with P01 = p and P10 = q, with initial distribution αi = P(X0 =i)for i=0,1, as discussed in class. Assume that p+q̸=0,2. (a) Determine the expected value E(Xn) and its limit as n → ∞. (b) Compare the…
DANNY
  • 11
  • 1
1
vote
0 answers

Ergodic markov chain and irreducible

I have been reading about ergodic markov chain. Does ergodic markov chain has to be irreducible and aperiodic? Is it sufficient to satisfy irreducibility?
1
vote
1 answer

Is whether or not a Markov Chain is periodic dependent on the initial distribution?

I know that whether or not a MC is irreducible does not depend on the initial distribution (it depends only on the transitional matrix). But is the same (independence) true for periodicity?
ajfbiw.s
  • 375
1
vote
1 answer

Markov Chain and Steady States

I've been given the following problem and I want to know if the answer that I found makes sense. A student center cafeteria has three fast-food centers - serving burgers, tacos, and pizza.A survey of students found the following information…
Allison
  • 145
1
vote
1 answer

Markov chain application Gambler's Ruin Problem

Could anyone please explain me why you must assume to be win at i+1 and lose at i-1 in order to get to the highlighted lines? Thanks a lot. .
1
vote
0 answers

Solve Variable Order Markov Chain(VOMC)

I am using VOMC in order to implement a real-time system. The Loop of the system is the following: LOOP{ 1)Get Input and Train VOMC according to it 2)Get output from Markov Chain } With the above description I am want to show that in every iteration…
1
vote
1 answer

Is any subchain of Markov chain also a Markov chain?

Suppose $X_i$ is a Markov chain, which is defined by $$p(X_1,X_2,\ldots,X_n) = p(X_1)p(X_1\mid X_2)p(X_2\mid X_3)\ldots p(X_{n-1}\mid X_n)$$ For arbitrary subchain $X_{\alpha_k}$, where $1\le \alpha_1 < \alpha_2 < \cdots < \alpha_m \le n$, is it a…
1024
  • 565
1
vote
0 answers

When does a markov chain become independent of initial state

IF we are given a markov chain probability matrix represented by $$P = \left(\begin{matrix} a&&b&&c\\d&&e&&f\\g&&h&&i\end{matrix}\right)$$ and $a+b+c=d+e+f=g+h+i=1$ with an initial state $(x, y, z)$ Is there a way to know whether after how many …
SAK
  • 529
1
vote
0 answers

How to solve stationary disribution with higher dimension?

I have a problem with stationary disribution for Markov chain. Let say we have $\pi P=\pi$ where P is $n\times n$ transition matrix and $\pi$ is $n\times 1$ vector. Then, we have $\pi (P-I)=0$. If we have $n=3$, then we can solve this problem…
Wan
  • 11
1
vote
1 answer

Long-run fraction Markov Chains

A machine has three critical parts (1,2,3) but can function as long as two of these parts are functional. When two are broken, they are replaced and the machine is functional the next day. The state space is the parts that are broken…
Becky
  • 11
1
vote
2 answers

Help on some results with Markov chains

I currently have a markov chain represented by the following matrix: $$\left[\begin{array}{ccc} 0&1&0 \\ .99&0&.01 \\ 0&0&1 \end{array}\right],$$ i.e. a row-stochastic matrix, with uniform probability on the initial state distribution. I am trying…
Samantha
  • 174
1
vote
1 answer

Is this a valid proof for recurrence time?

The following is a well known result of Markov chain: Given a Markov chain $(X_t)_{t \ge 0}$, if $T_{ii}$ denote the time of the first return to state $i$ when starting at state $i$, then we have $$ E[T_{ii}] = \frac 1 {\pi_i}, $$ where $\pi$ is…
1
vote
0 answers

Finite irreducible Markov chain

The question I have is stated as follows: Show that for any finite-state irreducible Markov chain $$\max_{i,j}\mathbb E_iT_j\le C$$where the constant $C$ only depends on the number of states and $\min\lbrace P(i,j):P(i,j)>0\rbrace$. Here $T_j:=\inf…
vince
  • 31
1
vote
1 answer

Expected absorption time in modified Markov Chain

Consider a Markov Chain $\{X_n\}$ on $S=\{0,1,\dots,d\}$ where $0,d$ are absorbing states and all other are transient. Also consider any transient state leads to every state. Let the transition probabilities be denoted by $p_{ij}$. Consider a…
shadow10
  • 5,616