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

What is strictly periodic cycle

In AI book by Norvig and Russell ergodic Markov Chains are defined as follows: Every state is reachable from every other. There are no strictly periodic cycles in it. Can someone explain what is strictly periodic cycle or give any reference?
1
vote
0 answers

Expected Value of Placards

Let us say we have 10 placards with numbers from (-5 to 5 excluding zero) laid in a circular fashion. In each round, you perform a swap such that you switch the position of two adjacent placards . Find the expected number of swaps such that no two…
1
vote
1 answer

Markov chains exercise

Let the transition matrix be defined as follows The state space is defined as follow $E$={1,2,3,4} $$ \begin{bmatrix} 0&1/2&1/2&0\\ 1/4&1/2&0&1/4\\ 2/3&0&0&1/3\\ 0&2/3&1/3&0\\ \end{bmatrix} $$ What is the probability of getting from state 1 to…
Ashtart
  • 123
1
vote
1 answer

How to prove $\mathbb P [X_{n} = x_{n} |X_m = x_m, \ldots, X_0=x_0] = \mathbb P [X_{n} = x_{n} |X_m = x_m]$?

Let $S$ be a countable set and $(X_n)$ an $S$-valued discrete Markov chain. Then $$ \mathbb P [X_{n+1} = x_{n+1} |X_n = x_n, \ldots, X_0=x_0] = \mathbb P [X_{n+1} = x_{n+1} |X_n = x_n] $$ for all $x_0, \ldots, x_{n+1} \in S$. This is called the…
Akira
  • 17,367
1
vote
1 answer

Markov chains and biased coin

An unfair coin turns up heads with probability 0.2. It is tossed repeatedly. What is the expected number of tosses until there are two heads in a row? How can one use Markov chains to solve this problem?
kshah99
  • 19
1
vote
1 answer

Count of visits to a given state of a Markov chain.

While studying Markov processes, I faced to the following task. Please help to solve. We have the Markov Chain with two states. This Markov chain is shown here: The probabilities of transitions $p$ and $q$ are known. The initial state is $1$ with…
ets_ets
  • 19
1
vote
0 answers

Inverse Markov chain and functions

Consider $X_1$ discrete with finite alphabet $\mathcal{X_1}$. A chain of deterministic functions $f_i: \mathcal{X}_1 \rightarrow \mathcal{X}_{i+1}$ for $i=1, \dots, N$ identifies a Markov chain $X_1 \rightarrow X_2 \rightarrow \dotsc \rightarrow…
Cesare
  • 346
1
vote
2 answers

Can I define recurrent/transient states through number of visits in a Markov chain

I'm trying to appropriate myself some notions related to Markov chains (for which I'm not at all a specialist) and I have this question about the notion of "number of visits" in a certain state. Let $(X_t)_{t \in \mathbb{N}}$ be a homogeneous Markov…
Andrew
  • 483
1
vote
0 answers

Markov Chain Expected value of first Hitting Time

i am struggling with this task: Let X be a Markov chain on {0,1,..,N} with $\mathbb{P}$($X_k$ = n |$X_{k-1}$ = m) = $\frac{1}{N-m}$, if n > m (0 else). I have to compute $E_0(T_N)$ (the mean of the first hitting time of N if X starts in…
Troete
  • 11
1
vote
1 answer

Is this an absorbing Markov chain?

I started to study Markov chains and one of the exercices that I found on the internet is the following one: A forest consists of two types of trees: those that are 0-5 ft and those that are taller than 5 ft. Every year, 40% of all 0-5 ft tall…
Alfonso_MA
  • 49
  • 10
1
vote
0 answers

$\sum_{l=0}^{\infty} A^l $ for sub stochastic matrix

Let $A$ be a sub stochastic matrix (sum of rows is less or equal to 1) and also we know that the sum of at least one row is strictly less than 1. Ho do I show that $$ \sum_{l=0}^{\infty} A^l = (I - A)^{-1} $$ I think I can do it if all eigenvalues…
Tomer
  • 434
1
vote
2 answers

Markov Chain Contest Problem

Five cards labeled 1, 3, 5, 7, 9 are laid in a row in that order, forming the five-digit number 13579 when read from left to right. A swap consists of picking two distinct cards, and then swapping them. After three swaps, the cards form a new…
1
vote
0 answers

Toss a coin $X_0 = 5$ times. Let $X_1 =\text{ No. of heads}$. Toss the coin $X_1$ times. Let $X_2 = \text{No. of heads}$, and so on.

Toss a coin $X_0 = 5$ times. Let $X_1 = \text{No. of heads}$. Toss the coin $X_1$ times. Let $X_2 = \text{No. of heads}$, and so on. Find $P(X_2 = 2 \mid X_4=1)$. (Using Markov chain) If I define the states as the number of heads in each toss, I can…
Ram Zi
  • 67
1
vote
0 answers

Absorbing discrete time Markov chain with pure death-like structure

I consider a state space $X$ with a partition $X=\bigcup_{i=0}^n X_i$. Assume we have a transition matrix $P=(p_{x,y})_{x,y\in S}$ which has the structure $$P=\begin{pmatrix}Q_0 & R_{0,1} & 0 & 0 &... \\ 0 & Q_1 & R_{1,2} & 0 & ... \\ \vdots & 0 &…
Jfischer
  • 1,239
1
vote
1 answer

Markov chain transition between sets

I have a transition matrix $P=(p_{x,y})_{x,y\in S}$ which defines some Markov chain $X$ on some state space $S$. Now, I consider for $A,B\subset S$, $A\cap B=\emptyset$ the probability that $X$ transitions in one step from $A$ to $B$, i.e.,…
Jfischer
  • 1,239