Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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