Random walk on lollipop graph

Question

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.

Answer 1

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$.

Answer 2

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.