Expected value in Markov chains Let $\left\{X_{n}\right\}_{n\geq0}$ 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 $n\geq0$. 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 $1\leq 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 ?
 A: 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.
