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

Parrondo's Paradox: Show that base games are losing games

I am currently working through (at least I'm trying to) Parrondos' Paradox. Specifically the following instance: Game 1: unfair coin flip with winning probability $\frac{1}{2} - \varepsilon$, where $\varepsilon = 0.005$. Game 2: If the current…
lphil
  • 126
4
votes
1 answer

Sojourn time of a CTMC

Soujourn time of a CTMC at time $t$ is defined as : $$T(t)= \inf\{ s > 0 : X(t+s) \neq X(t)\}$$ My question is why "inf", not min ? Here $T(t)$ belongs to the set $\{ s > 0 : X(t+s) \neq X(t)\}$. Then we can write minimum. Is this correct ?
user21982
4
votes
1 answer

Return time of a markov chain

I'm having trouble deriving the return time for a Markov chain. The graph has $n$ vertices and is connected by $n - 1$ edges. So we can draw this as a horizontal line of nodes with node $1$ all the way to the left and node $n$ all the way to the…
Ricky
  • 53
4
votes
1 answer

Probability distribution of markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 2/3 & 0 & 0 & 0 \\ 0 & 1/4 & 1/4 & 1/4 & 1/4 \\ 0 & 0 …
Henry
  • 93
4
votes
2 answers

Calculating conditional probability for markov chain

I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below: $$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\\ 1/3 & 2/3 & 0 & 0 & 0 \\\ 0 & 1/4 & 1/4 & 1/4 & 1/4 \\\ 0 & 0 & 0 & 3/4 & 1/4 \\\ 0 & 0 & 0 & 1/5 & 4/5\…
Henry
  • 93
3
votes
2 answers

Irreducible and aperiodic Markov chain : $P^t(x,y)>0$

Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$. Which of the following statement is true? If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, \forall x,y\in\Omega$. If $X$ is irreducible and…
user14108
3
votes
0 answers

Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition $r_{ij}$ stored in matrix $R$. For example if we…
rwolst
  • 741
3
votes
1 answer

Are there open questions in Markov chains?

I would be curious to know if there's still open question about discrete markovian chains
3
votes
1 answer

Identifying states in Markov chains

I just started learning about Markov processes and got the following homework question. Classify all the states as recurrent or transient for the Markov chain below $$\begin{matrix} {}&s_1&s_2&s_3&s_4&s_5\cr s_1&1/4 & 3/4 & 0 & 0 & 0\cr s_2&1/2…
JP83
  • 81
3
votes
1 answer

Mean return time of king on chess board

I am trying to find the stationary distribution of the markov chain of a king on a chess board, where a king can uniformly choose between any of its legal moves. I have potential approaches, first, finding the transition matrix P for the entire…
SinByCos
  • 133
3
votes
1 answer

expected hitting time with two absorbing states

Consider a Markov chain in a finite space and with two absorbing states, each of which is accessible from the other, transient states. Is the expected number of transitions to reach any single absorbing state infinite?
antonio
  • 31
3
votes
0 answers

Kolmogorov backward and forward equations for a discrete-time Markov chain?

I found Kolmogorov backward equations and forward equations for diffusion processes, and for continuous time Markov chains in Wikipdia. I was wondering what Kolmogorov backward and forward equations are like for a discrete-time Markov chain?…
Tim
  • 47,382
3
votes
1 answer

Ergodic Markov Chain vs Regular Markov Chain

I am trying to understand the difference between regular Markov Chain and Ergodic Markov Chain. According to https://math.dartmouth.edu/archive/m20x06/public_html/Lecture15.pdf: A Markov chain is called an ergodic chain if it is possible to go…
3
votes
1 answer

Find the probability of the following Markov chain

A Markov chain with 3 states: $S = \left \{1,2,3\right\}$ has the following transition matrix: $P = \begin{pmatrix} 0.65 & 0.28 & 0.07\\ 0.15 & 0.67 & 0.18\\ 0.12 & 0.36 & 0.52 \end{pmatrix}$ Knowing that the initial state is $2$, what is the…
Ghost
  • 1,105
3
votes
1 answer

Finding the steady state Markov chain?

I have drawn a certain Markov chain with a weird transition matrix. Here's the drawing: And here's the transition matrix: My problem is that I don't quite know how to calculate the steady state probabilities of this chain, if it exists. I need a…
1
2
3
30 31