1
$\begingroup$

$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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I see. $E(N\mid X_1 \neq X_0) = 1$ + number of steps needed from $X_1$ to $X_0$. Thanks! $\endgroup$
    – gnohz
    Sep 19, 2019 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.