Random walk on lollipop graph Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, vertex $j$ be the vertex where the path and the clique meet, and $k$ be the vertex on the other end of the path. What is the $H(i,k)$ and $H(k,i)$. Result can be just asymptotic.
I know $H(i,k)=O(n^3)$ and $H(k,i)=O(n^2)$ but I dont know how to finish the proof. I know that $H(i,j)=n/2$ and when $t$ is the first vertex on the path, neighbor of $j$, then $H(i,t)=\frac{n/2}{P(j,t)}=\frac{n*(n+1)}{2}$ I guess.
But how can I finish the proof, and how can I prove $H(k,i)$. I know $H(k,j)=\frac{n^2}{4}$, but how can I make $H(k,i)$ out of it. Well I hope its understandable, any help appreciated. John.
 A: For  $H(i,k)$, the average hitting time of $k$ starting at $i$, there is 
a trick to simplify the calculations. 
All the states in the clique (except $j$) are equivalent and 
can be collapsed into one state. This gives a random walk on a linear 
graph with non-equal probabilities. 
I use $N$ instead of your $n/2$, and I relabel the collapsed graph 
as $\{-1,0,1,2,\dots, N\}$ so that the state $i$ is labelled $-1$, 
 state $j$ is $0$, and state $k$ is $N$.
We have $$H(-1,N)=H(-1,0)+H(0,1)+H(1,2)+\cdots +H(N-1,N),$$ 
and the terms on the right hand side are pretty easy to calculate. 
For a random walk on a clique we have $H(-1,0)=N-1$ (not $N$, as you wrote),
and the others can be calculated using 
$$H(i,i+1)=1+p(i,i-1)[H(i-1,i)+H(i,i+1)]\ \mbox{ for }\ 0\leq i<N,$$
and 
$$p(i,i+1)=\begin{cases}1/(N-1) & i=-1\\[5pt] 
                       1/N     & i=0\\[5pt]
                       1/2     & 1\leq i<N.\end{cases}
$$
If my calculations are correct, the end result is $$H(i,k)=H(-1,N)=N^3+N-1.$$ 
For example, here's the expected time to hit $k$ from each state, when $N=3$.


Added: Following joriki's suggestion, I have calculated $$H(k,i)=N^2+N+3.$$
For example, here's the expected time to hit $i$ from each state, when $N=3$.

A: Here is an alternative way to conclude about $H(i,k)$ based on the arguments formulated in John's question. As he mentioned, $H(i,t)=\Theta(n^2)$. Assuming the path between $t$ and $k$ is taken separately, the walk would then take another $\Theta(n)^2$ to reach $k$. But in our case, it will actually pass through $t$ and get back to the clique a number of times. Based on the return time for the endpoint of a path ($2m$), we can see this will happen $\Theta(n)$ times, whence $H(i,k)=\Theta(n^3)$.
This argument can be found on page 8 of Lovàsz's survey.
