Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 1

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

 
discard

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.