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

Basic identity from introductory lecture notes intp discrete Markov chains

Can someone please tell me, how from these lecture notes, on pp. 6, equation (1) is derived (where the joint probabilities $$P(X_0=i_0,\ldots,X_n=i_n)$$of a Markov chain $(X_n)_{n\in \mathbb{N}}$ is computed)? I have to somehow use Lemma 1 but I…
user17793
0
votes
2 answers

Markov chain, Q matrix, jump matrix and invariant distribution

For the following Q matrix i want to find the jump matrix and the invariant distribution. \[ Q= \begin{pmatrix} -2 &1 &1 &0\\ 2 & -4 &1 &1\\ 1 &0 &-1 &0\\ 1 &1 &0 &-2 \end{pmatrix}\] I can find the jump matrix but am not sure how to…
Johnny Byr
  • 35
  • 5
0
votes
1 answer

Lower bound of mixing times

I want to prove that for any Markov Chain we have $t_{mix}>\max_{x,A}\left(\pi(A)-\displaystyle\frac{1}{4}\right)E_x(\tau_A)$ I wanted to used that if $P_x(\tau_A\leq t)\geq \alpha $ for any $x$ in the state space then $E(\tau_x)>t_0/\alpha $.…
EQJ
  • 4,369
0
votes
0 answers

A question onMarkov chain

The diffusion of electrons and holes across a potential barrier in an electronic devise is modelled as follows. There are $m$ black balls (electrons) in urn $A$ and $m$ white balls (holes) in urn $B$. We perform independent trials, in each of which…
0
votes
0 answers

Formal definition of: "The event $A$ is determinated by $X_0, \ldots, X_T$"

Given an event $A \subset \Omega$, a Markov chain $(X_n)$ on $\Omega$ and stopping time $T$ what is the formal definition of: "The event $A$ is determinated by $X_0, \ldots, X_T$". I have found this in the proof of Markov property and Strong Markov…
0
votes
1 answer

Markov Chain Matrix

Can any make Markov chain matrix of this problem? We can model the educational journey of a student using a Markov chain. In our model there are 4 states, representing whether a student is registered in year 1, year 2, has taken their exam or has…
0
votes
0 answers

Hitting time , Marcov chain probability of two different absorbing states

My question is: Starting in state 1 what is the probability on ending up in state 3 resp. state 4? The transition matrix T= \begin{bmatrix} 0& 0.8& 0&0.2\\ 0&0.2&0.6&0.2\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix} Both state 3 and 4 are…
S.n
  • 145
0
votes
1 answer

Markov chain in Jukes-Cantor model

This question concerns the Jukes-Cantor model with respect to DNA nucleotides (ACGT). In any DNA string, consider a single nucleotide subject to mutation with a rate P for some time period. I'm tasked to derive the probability equation that the…
0
votes
1 answer

Mean time spent in transient states /inverse of (I-P)

For transient states $i$ and $j$ , let $s_{ij}$ denote the expected number of time periods that the Markov chain is in state $j$, given that it starts in state $i$. Let $\delta_{i,j}= \begin{cases} 1,&\text{when $i=j\quad$ and}\\ 0,&…
0
votes
0 answers

Proof of markov property : "The future depends on the past through the present"

I took recently my first class, but I don't quite understand how can I prove the equality. Show that for every $i_0$, $i_1$, . . . , $i_{n−1}$, $i_n$, $j_1$, $j_2$ ∈ E and n ∈ $N_0$ the following below is valid. P($X_{n+2}$ = $j_2$, $X_{n+1}$ =…
Oleg
  • 499
0
votes
1 answer

CTMC stationary distribution vs. embedded DTMC stationary distribution

This is merely a concept question. I have an inclination, unfortunately with no proof, that the stationary distribution of a Continuous Time Markov Chain and its embedded Discrete Time Markov Chain should be if not the same very similar. Discrete…
0
votes
1 answer

Limiting distribution of non-irreducible markov chain

In an excercise I'm given the following matrix of a markov chain $\begin{pmatrix} 0&1&0 \\ 1/2 &1/2 & 0 \\ 0 & 1/2 &1/2 \end{pmatrix}$. It has the stationary distribution $\pi=(1/3,2/3,0)$ (which I think is unique). In the answer to the problem it…
0
votes
0 answers

Verifying that limiting distribution of Markov Chain is stationary

A markov chain has an initial distribution $u^{(0)}$ = {1/6 1/2 1/3} and the following transition matrix P= $\left(\begin{matrix}0&&0.5&&0.5\\0.5&&0&&0.5\\0.5&&0.5&&0\end{matrix}\right)$ Find its stationary distribution. Is it unique? Verify…
SAK
  • 529
0
votes
0 answers

Intuitive example of The Renewal Reward Theorem with Markov Chains.

So I'm trying to study som Markov Chains. And I've stumbled across "The Renewal Reward Theorem" or "The elementary renewal theorem", it seems to have different names. The theorem basically says: $lim_{t\to \infty} \frac{1}{t} m(t) =…
almar
  • 1
0
votes
1 answer

Markov Chain Transition Matrix Question

Ok, so my question is pretty simple, the question states: A spider web is only big enough to hold 2 flies at a time. Assuming that the flies fly into the web independently: -The probability that no flies will fly into her web on any given day is…