$X\_i$ iid with $P(X\_i=j)=p\_j$, $j=1, \dots, m$.
$\sum\_{j=1}^m p\_j = 1$.
Define $N = \min\{n>0:X\_n = X\_0\}$, compute $E(N)$.


I have two solutions, but different answers:


**Solution 1**


$E(N) = E(N\mid X\_1=X\_0)P(X\_1=X\_0) + E(N\mid X\_1\neq X\_0)P(X\_1\neq X\_0)$


So $x = 1\cdot y + (1+x)(1-y)$, where $x = E(N), y = P(X\_1=X\_0) = \sum\_{j=1}^m p\_j^2$, and thus


$E(N) = 1/y = 1/\sum\_{j=1}^m p\_j^2$.


**Solution 2**


$E(N) = \sum\_{j=1}^m E(N\mid X\_0=j)P(X\_0=j) = \sum\_{j=1}^m 1/p\_j \times p\_j = m$


I cannot see where is wrong.
Any help?



Expected minimum number
Solution 2 is correct. 


In Solution 1, you are assuming that $E(N|X\_1\ne X\_0)=1+EN$, which is not true in general. Indeed, $N$ is the time needed to return to $i$ from a state $i$ -- whereas, on any event of the form $\{X\_0=i\ne j=X\_1\}$, $N-1$ is the time needed to get to state $i$ from $j\ne i$. 


