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

Proof that state $i$ can reach state $j$ in $\leq M$ steps by induction on $M$

Problem: Prove that if the number of states in a Markov Chain is $M$, and if state $j$ can be reached from state $i$, then it can be reached in $M$ steps or less. I'm attempting to prove this by induction on $M$ (I realize there are other, perhaps,…
1
vote
1 answer

Markov jump process

Assume there is a radioactive material which emits particles according to a Poisson process at rate $\lambda$. Each particle stays alive for 1/μ time units (deterministic time). Define $X=\{X_t,t\geq0\}$ to be the number of live particles at time…
adamco
  • 413
1
vote
1 answer

Find a mapping such that $f\big((X_n)_{n=0,1,\ldots}\big)$ is not a markov chain

I have the following markov chain: Let $(X_n)_{n=0,1,\ldots}$ be the markov chain. For every bijective map $f: \{1,2,3\} \rightarrow \{a,b,c\}$, the map $f\big((X_n)_{n=0,1,\ldots}\big)$ is also a Markov chain. Find a mapping $f:…
Nullspace
  • 979
1
vote
1 answer

Markov Chain Converging in Single Step

I have a markov kernel K. From this I find the invariant probability $\pi$. The question is to design a "dream" matrix K*, that converges in one step. Such that $\lambda_{SLEM}=0$ (second largest eigen-value modulus). I am not sure how to go about…
skr
  • 394
1
vote
1 answer

Continuous time Markov chains with self-loops

CTMCs are normally defined with no self loops. That is, when in state $i$, you transition to state $j$ at a rate $Q_{ij}$. You never transition from $i$ to $i$, so we're free to choose $Q_{ii}$ such that the rows of $Q$ sum to zero, so that…
tomfelker
  • 21
  • 3
1
vote
1 answer

Markov Chains - Mice

I did the following exercise, but I really don't know if it's okay A mouse enters a box with 9 gaps as follows: The probability to go from one state to another is equally probable depending on the space in which it is. Additionally, in space 9…
1
vote
1 answer

Distribution of a Markov Chain

I'm having a very hard time understanding a theorem in my notes stating the Markov property. It says that for a Markov-chain $(X_n)_n$ with initial distribution $\mu$ and transition matrix $p$ we have: $\mathbb{P}((X_{m+n})_{n\geq0} \in…
1
vote
1 answer

Sufficient condition for a Markov chain with tridiagonal transition matrix to be null recurrent

Consider the random walk induced by the Markov matrix \begin{equation} \begin{Vmatrix}P_{ij}\end{Vmatrix}= \begin{Vmatrix} r_0 & p_0 & 0 & 0 & \cdots \\ q_1 & r_1 & p_1 & 0 & \cdots \\ 0 & q_2 & r_2 & p_2 & \cdots…
1
vote
1 answer

Why does the limit defining the transition rate for a Markov chain exist?

Background Let $S$ be a countable (finite or infinite) state space. The text I am reading defines a Markov process as a stochastic process $\{X(t)\}_{t\in\mathbb R_{\ge0}}$ with the Markov property: For any times $t_1<\cdots
1
vote
0 answers

Hidden Markov Model Coin Flips

Suppose in a system there are two possible states and each transition probability is decided by flipping a coin, e.g. transition probability from state 1 to 2 depends on outcome of the flip. How do you construct a MC in this problem to find…
eet
  • 393
1
vote
1 answer

Reversible Markov chain: aperiodicity and strictly positive self-loop probabilities, simplified proof?

Aperiodicity for Markov chains ensures that powers of self-loop probabilities $[P^{k}]_{ii}$ remain strictly positive from a certain power k onward (for the transition matrix $P$) The proof relies on generalizing Bezout's lemma to the following…
1
vote
1 answer

Continuous Markov Chain

Let $\left(\xi_n\right)_{n\geqslant1}$ be a sequence of independent identically distributed random variables with distribution $\mathcal{N}(0,1)$. Let $X_0$ be a random variable in $\mathbb{R}$ with distribution $\mu$, independent from the sequence…
Flewer47
  • 631
1
vote
0 answers

About mixing time of Markov chains and diffusive nature

Q1) May I know why for some Markov chains like a Markov chain on a line segment of length $n$, say started at $0$, the chain mixes by the time it reaches it's diameter i.e. state $n$ (which takes $O(n^2)$ time by Central limit theorem)? I am looking…
1
vote
1 answer

Expected time until different starting states will reach the same state in a Markov chain

Consider a Markov chain with $n$ states and transition probabilities $p_{ij}$. For a given pair of states $s_1$ and $s_2$, how can I express the expected time until a chain starting in $s_1$ and a chain starting in $s_2$ will reach the same state? I…
1
vote
2 answers

Why is the proof of Markov's property so roundabout?

We've defined a Markov chain as a sequence of random variables $(X_n)_{n\geq0}$ such that $P(X_{n+1}=i_{n+1}|X_0=i_0,\dots,X_n=i_n)=P(X_{n+1}=i_{n+1}|X_n=i_n).$ That is, $X_{a}$ and $X_{b}$ are independent for any $|a-b|>1.$ (This is my…
Zerkoff
  • 489