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.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  joriki Mar 23 '13 at 17:35
    
@joriki Good idea! I'll try to calculate it this way. –  Byron Schmuland Mar 23 '13 at 17:58
add comment

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.

share|improve this answer
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.