2
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    Please delete that last, absolutely incorrect, comment!2011-11-14