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
2 answers

Pointless probability

POINTLESS is a BBC game show. Each night, four teams compete. If a team does not win, it comes back for a second night; but not a third night. Each night has 1, 2, 3 or 4 new teams. There are never 0 new teams because the previous night's winner…
Empy2
  • 50,853
1
vote
0 answers

recurrence time for transient state

I have the following transition matrix for a MC with state space $S = \{ 1,2,3,4,5,6,7,8 \}$ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.4 & 0 & 0 & 0 & 0.6 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 …
jim
  • 1,214
1
vote
1 answer

Markov Chains in a Casino

Consider an agent that enters a casino with an integer amount of money $y$ such that $0 < y \leq 5.$ The agent will stop gambling if the agent has either 0 dollars (in which case, the agent cannot play) or 5 dollars. When the agent has 1 or 2…
Hunter
  • 13
1
vote
1 answer

Recurrence of a Markov chain (lemma of Pakes)

For my course on Markov chains, we have to think about the following problem: Consider the irreducible Markov chain with $P$ on the state space $S={0,1,2,...}$, with $p_{0,1}=1$, $p_{n,n+1}=1/(n+1)^2$ and $p_{n,0}=1-p_{n,n+1}$ for $n\geq 1$…
1
vote
2 answers

A property of irreducible and aperiodic Markov chains

Let $P$ denote the $s\times s$ Markov transition matrix. We know that irreducibility and aperiodicity implies the following: There exists an integer $N\geq 1$, such that $[P^n]_{ij}>0$ for all $i,j$ and all $n\geq N$. Is the following property true…
1
vote
1 answer

How to solve for the n-step state probability vector for the Markov chain

Could you help me to solve for the $n$-step state probability vector for the Markov chain given below. Assume that the system starts in $S_1$ (the other two are $S_2$ and $S_3$). $$ \begin{bmatrix} 0.5 & 0.5 & 0 \\ 0 & 0 & 1…
1
vote
1 answer

Probability of absorption in Markov chain

Given the probability matrix $P$ with states $s_1...s_5$ where $s_1$ and $s_5$ are absorbing $$ P = \left[ \begin{matrix} 1 & 0.7 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0 & 0 \\ 0 & 0.3 & 0 & 0.65 & 0 \\ 0 & 0 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0.35 &…
C.T.
  • 187
1
vote
1 answer

A tricky conditional probability question on Markov chains

Let $X_1,X_2,\ldots,X_n$ be a time-homogeneous discrete-time ergodic Markov chain on a finite state space $\mathcal{S}.$ You can assume stationarity and time-reversibility as well, if you like. Fix $s_0\in\mathcal{S}.$ Let $A=\{1\leq i\leq n-1: X_i…
Hedonist
  • 1,401
1
vote
0 answers

Relaxation time and Mixing time of Markov chains

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite state space $S$ whose Markov kernel is $K$ and…
Hedonist
  • 1,401
1
vote
2 answers

When to stop checking if a transition matrix is regular?

The definition that I have of a Transition Matrix for a Markov Chain is: A transition matrix is regular if some power of it is positive. Doesn't this mean though that in theory, you could keep calculating powers forever, because at some point one…
1
vote
2 answers

Difficult to comprehend markov chain and its characteristics

If $Y_n$ is a sequence of independent random variables with $P(Y_n=0)=2/3,P(Y_n=1)=1/6,P(Y_n=2)=1/6$ and $X_n$ with $X_0=0$ is defined as $$X_{n+1}= \left\{ \begin{array}{lr} X_n-Y_n & : &X_n=3\\ X_n-1+Y_n &: &1\leq X_n\leq2\\ Y_n & :…
user235238
1
vote
3 answers

Markov chain: I don't understand how read this matrix

Consider a gambling game in which on any turn you win \$1 with the probability $p=0.4$ and you loose \$1 with the probability $p=0.4$. We have that $p(i,j)=p\{X_{n+1}=j\mid X_n=i\}$ and thus, for $N=5$, $$\big(p(i,j)\big)_{0\leq i,j\leq…
idm
  • 11,824
1
vote
1 answer

Can You Help Me With This Markov Chain Question?

For a birth and death process with birth rates, $\lambda_i$ and death rates $\mu_i$ $(i=0,1,2...)$ respectively. Show that the transition probabilities, $P_{i,j}(t)$ satisfy the following differential equations $P'_{0,j}(t) = -\lambda_{0}…
user211962
1
vote
1 answer

What does this question about classifying the states of this Markov chain mean?

If $X$ is a discrete Markov chain with state space $S=\{1,2\}$ and transition matrix \begin{equation*} P=\begin{pmatrix} 1-a& a\\ b& 1-b \end{pmatrix}. \end{equation*} I must answer the question "Classify the states of the chain". What is meant by…
user235238
1
vote
1 answer

Converting second order Markov chain into a first order Markov chain

I'm having some trouble converting a second order Markov chain into a first order Markov chain, namely I want to define some new random variables $Y_i$, that have the property $P(Y_i=b|Y_{i-1}=b_1,...Y_0 = b_n) = P(Y_i=b|Y_{i-1}=b_1)$, given random…
user82004