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.


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

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

an example

  • $\begingroup$ For $H(k,i)$, you can do the same linearization, but with the target state $i$ taken out of the clique, so $-1$ represents the $N-2$ nodes of the clique minus the connection state and the target state, and there's another label $-2$ representing the target state. You can reach $-2$ from $0$, but that makes the equations only slightly more complicated. $\endgroup$ – joriki Mar 23 '13 at 17:35
  • $\begingroup$ @joriki Good idea! I'll try to calculate it this way. $\endgroup$ – user940 Mar 23 '13 at 17:58

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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