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

Does the stationary distribution of this Markov Chain exist?

To find the stationary distribution of a Markov Chain, I believe I must solve for $\vec{s} = \langle s_0, s_1 \rangle$ in $\vec{s} = \vec{s}Q$, where $Q$ is the transition matrix. $Q$, in my case, is $$ \left( \begin{array}{cc} p & 1-p \\ 1-q & q…
David Faux
  • 3,425
2
votes
0 answers

A Markov Chain Question

Problem I am working on is as follows ; Suppose that whenever the Washington Wizards win a game, they will also win the next one with probability 0.75 and lose it with probability 0.25. However, if the team loses a game, then they win the next one…
EGE
  • 77
  • 3
2
votes
0 answers

Variance of first return time markov chain

I have the following Markov Chain \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 \\ 0 & 0 & 0 & 1 \\ \frac{3}{5} & 0 & 0 & \frac{2}{5}\\ \end{bmatrix} Now the question is. Let T be the time to, for the first time,…
Jasper
  • 145
2
votes
2 answers

Expected amount of time until Markov chain pattern appears

Gary can be Cheerful $(1)$, So-so $(2)$, or glum $(3)$. The following transition matrix describes the Markov chain that records Gary's mood changes. $$P=\begin{bmatrix}0.5 & 0.4 & 0.1\\0.3 & 0.4 & 0.3\\0.2 & 0.3 & 0.5\end{bmatrix}$$ With stationary…
GuPe
  • 7,318
2
votes
0 answers

Is a random walk with symmetric and non-lattice increments always irreducible?

Let $\xi$ be a random variable with symmetric and non-lattice distribution. In other words, there dose not exists $\delta > 0$ such that $\mathrm P\{\xi \in \delta \mathbb Z\} = 1$. Define a random walk $S_n = \sum_{i=1}^n \xi_i$ where $\xi_i \sim…
2
votes
0 answers

Continuous Time Markov Chain - probability of moving from i to j taking into consideration not hitting state k

Assume we have a generator $Q$ describing the transitions between four states $A,B,C,D$. $Q$ is a valid generator and all non-diagonal elements are strictly positive hence no absorbing states. I am interested in the transition probability of moving…
2
votes
1 answer

Limit of transition probabilities of an infinite Markov chain

I have a Markov chain with state space $S = \left\{ 1,2,\dots \right\}$ with transition matrix as follows $\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & \dots \\ 0 & 0 & 1 & 0 & 0 & 0 & \dots \\ 0 & 0 & \frac{2}{3} & \frac{1}{3} & 0 & 0 &…
lllll
  • 409
2
votes
0 answers

Task about post office

There is a small town with strange post office. People use it to send letters, alright... In this town there are $N$ people. Let's think that everybody have a letter to send according to exponential distribution. I mean that $P(T_{s} + T_{new\…
user324463
2
votes
1 answer

Method of Generating function - Markov Chain

The question relates to using method of generating function for finding $n$th power of a transition matrix $P$ In the Text Book the generating function has been defined as: $P(s)= 1+sP+s^2P^2+s^3P^3+\cdots +s^n P^n$ where $|s|<1$ ($s$ is a…
SAK
  • 529
2
votes
3 answers

Expected number of unique states visited in Markov process

Is there a way to calculate the expected number of unique states visited in a Markov chain after n steps? For example, say I have 4 states {A,B,C,D} with transition probabilities 1/4 across the board; i.e., the transition matrix is uniformly 1/4.…
2
votes
0 answers

Random Walk on $N\times N$ grid

I would appreciate any help (answers, pointers to the literature etc.) on the following problem. Consider a (discrete time) random walk on an N-by-N grid which has two absorbing nodes, namely $(1,1)$ and $(N,N)$. Random walk means that the walker…
2
votes
1 answer

On the Markov chain defined by $X_n=U_nU_{n+1}$, where $(U_n)$ is i.i.d. symmetric Bernoulli

I came across this problem in homework: $U_n$ are i.i.d random variables with $P[Un=1]=P[Un=−1]=0.5$. a) Show that $X_n=U_nU_{n+1}$ is a Markov Chain. b) Show that $X_n=(U_n+U_{n+1})/2$ is not a Markov Chain. I don't know how to start the proof.…
Harel
  • 23
2
votes
1 answer

Markov property for the gambler's ruin problem

Let $(X_n)_{n\ge 0}$ be a simple asymmetric random walk on states $0,1,\dots,M$, where $0$ and $M$ are absorbing. Initial state is $i\neq 0,M$. Let $(X_n^*)_{n\ge 0}$ be the process $(X_n)$ conditional on event $A:=\{X_m=M\text{ finally }\}$. That…
vince
  • 31
2
votes
1 answer

Show that a function of a markov chain is not a markov chain

How do you show that a function, $Y(n)=g(X(n))$ if some Markov chain $X(n)$ cannot be a Markov chain?
2
votes
1 answer

Find expected time to reach a state in a Markov chain

Consider a Markov chain $ (X_n)_{n\geq 0} $ with state space $E$, initial distribution $p(0)$ and transition probability matrix $P$ given by $E = \{0, 1, 2\}, p(0) = [1\;\; 0\;\; 0]$ and $$ P= \begin{bmatrix}1/2 & 1/3 & 1/6\\0 & 2/3 & 1/3 \\0 &…
JKnecht
  • 6,543