My question concerns Exercise 1.15 from the book "Markov Chains and Mixing Times" of Levin, Peres and Wilmer:

For a subset $A\subset \Omega$, define $f(x) = E_x(\tau_A)$. Show that

  1. $f(x) = 0$ for $x \in A$.
  2. $f(x) = 1 + \sum_{y\in\Omega}P(x, y)f(y)$ for $x \not\in A$.
  3. f is uniquely determined by 1. and 2.

Here $\tau_A$ is the hitting time of $A$.

Points 1. and 2. were discussed (in a different form) here. My question relates to point 3. I cannot see where the uniqueness comes from.

  • $\begingroup$ You have n linear equations in n unknowns. Study the matrix for this system. $\endgroup$ – Ian Dec 8 '15 at 10:57
  • $\begingroup$ Theorem 1.3.5 in the book by Norris "Markov Chains" (CUP, 1997) states the same result, but adds the condition that $f(x)$ should be the minimal non-negative solution of the linear system described by $1$ and $2$. $\endgroup$ – alezok Dec 8 '15 at 11:06
  • $\begingroup$ Yes, there can potentially be multiple solutions. For instance it could happen that $A$ is not reachable at all from some $x$, in which case one solution to the system would have $f(x)=+\infty$. $\endgroup$ – Ian Dec 8 '15 at 14:10
  • $\begingroup$ Thank you for your replies. I also think that the problem was badly formulated and that the reference from Norris' book is correct and makes sense. $\endgroup$ – DCPC Dec 9 '15 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.