Does moving closer to the target reduce first passage time

Question

Given a finite graph $G$ and two vertices $v, w \in G$, denote the mean first passage time from $v$ to $w$ by $T(v, w)$. If $u$ is a neighbour of $v$ and $u$ is closer to $w$ than $v$ (in the sense of graph distance) is it true that $T(u,w) \leq T(v,w)$?

Answer 1

I presume you're talking about a simple random walk, where from a given vertex you go to any neighbour of that vertex with equal probabilities. Consider a situation like this:

Vertex $u$ is closer to the target $w$ than $v$, but if you go from $v$ to $u$ you're very likely to go next into the mess at the top of the picture and stay there for a very long time before you ever get to $w$, while if you go from $v$ to one of the vertices below it you have probability $1/2$ to get to $w$ on the next move. In fact, if the degree of $v$ is $d$, we have

$$T(v,w) = 1 + \dfrac{T(u,w)}{d} + \dfrac{d-1}{d} (1 + T(v,w)/2)$$

so that

$$T(v,w) = \dfrac{2 T(u,w)}{d+1} + \dfrac{4d-2}{d+1}$$

which is less than $T(u,w)$ if $T(u,w) > (4d-2)/(d-1)$.