Take the 2-minute tour ×

Let $G$ be a connected graph on at least 3 vertices in which the vertex $v$ has only one neighbor, namely $w$. Let $(X_t)_{t \ge 0}$ be a simple random walk on $G$, where $X_t$ is the current vertex at time $t$. Show  

$$E_vT_w \ne E_wT_v$$

where $T_x=\min\limits_{t \ge 0} \{X_t=x\}$ is the hitting time of vertex $x$ and $E_xT_y=E(T_y|X_0=x)$.

I've attempted the following, but without success.

Starting from $v$, the walk must do it first step to $w$. Hence $E_vT_w=1$. Let $n$ be the number of vertices connected to $w$. By conditioning on the first step

$$E_wT_v=E_w(T_v|X_1=v){1 \over n} + {1 \over n}\sum\limits_{x \ne \{v,w\}}E_w(T_v|X_1=x).$$

Using the Markov property of the walk and the fact that $E_w(T_v|X_1=v)=1$

$$E_wT_v={1 \over n} +  {1 \over n}\sum\limits_{x \ne \{v,w\}}E_x(T_v).$$

I can't go further.

This is exercise 10.3 from Markov Chains and Mixing Times, 2009, Levin, Perez, Wilmer.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Since $P_w(T_v\geq 1)=1$, the equation $E_wT_v=1$ would imply $P_w(T_v=1)=1$. Connectivity and the third vertex make this impossible.

share|improve this answer
Yep, me stupid. Thanks. –  Did Nov 14 '11 at 20:22
Please delete that last, absolutely incorrect, comment! –  Byron Schmuland Nov 14 '11 at 20:25
add comment

Your Answer


