# Solved – Expected value in Markov chains

Let \$left{X_{n}right}_{ngeq0}\$ be a homogeneous markov chain with state space E and transition matrix P. Let \$tau\$ be the first time n for which \$X_{n}\$ \$neq\$ \$X_{0}\$, where \$tau=+infty\$ if \$X_{n}=X_{0}\$ for all \$ngeq0\$. We need to compute \$E[tau|X_{0}=i]\$ in terms of \$p_{ii}\$

My solution

For any \$l>0\$ let \$l\$ be the first for which \$X_{n}\$ \$neq\$ \$X_{0}\$ which means that \$forall\$ \$m\$ such that \$1leq m <l\$ the value of \$X_{m}=X_{0}\$ but \$X_{i} neq X_{0}\$. The probability of this happening is the product of probability of \$P_{ii}^{m}\$ for all \$m\$ multiplied by \$(1-P_{ii}^{l})\$. The resulting product is then again multiplied by the value of \$l\$ and then summed over for all possible values of \$l\$ i.e from 1 to \$infty\$ to find expectation

The expected value therefore is \$(1-P_{ii}^{1})+2(1-P^{2}_{ii})P_{ii}^{1}+3(1-P_{ii}^{3})P_{ii}^{2}P_{ii}^{1}+…..=sum_{j=1}^{infty}(j(1-P^{j}_{ii})prod_{k=0}^{j-1}P^{k}_{ii})\$ where \$P^{0}_{ii}=1\$

Is this correct ?

Contents

You are thinking along the right lines but it seems your notation is obscuring things (see bottom of this answer).

The event \$tau = k\$ means we remain in state \$X_0\$ for \$k-1\$ steps (which has probability \$p_{ii}^{k-1}\$) and then jump to another state on step \$k\$ (which has probability \$1-p_{ii}\$). Consequently, \$\$ mathbb{P}(tau = k) = p_{ii}^{k-1}(1-p_{ii}). \$\$

This "waiting for an event to happen (in a time homogenous setting)" time distribution is called the geometric distribution.

The expectation can be evaluated with a "differentiate under the integral" trick:

\$\$ mathbb{E}[tau] = sum_k k p_{ii}^{k-1}(1-p_{ii}) \ = (1-p_{ii})sum_k frac{d}{dp} left. p^k right|_{p=p_{ii}} \ = (1-p_{ii})frac{d}{dp}left. sum_k p^k right|_{p=p_{ii}} \ = frac{1}{1-p_{ii}}, \$\$ the differentiation in the infinite series being ok because all terms are non-negative. Also we used the formula for a geometric series.

• Usually "homogeneous" means time homogeneous for Markov chains.
• With the usual notation for transition matrices \$P = (p_{ij})_{i,j in mathcal{S}}\$, \$P^k\$ is the \$k\$-step transition probability (just the matrix power). You appear to use \$P^k\$ for the transition probability at time step \$k\$ (which is different to the usual convention).

With this understanding, taking \$P^j_{ii}=p_{ii}\$ (in your notation) makes your attempt look right.

Rate this post