Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current vertex's neighbors uniformly at random. The expected hitting time for a vertex $v$ is the time it takes, on average, for the walk to reach $v$.

For what family of graphs is the minimum of all expected hitting times as large as it can be?

  • $\begingroup$ Take a look at my question about mean hitting time. There are some links to articles that might answer your question. Also, you could improve your question: Is bidirectional the same as undirected? Is the starting vertex chosen uniformly or from a stationary distribution? Are you asking about expected hitting time or mean hitting time? There is a difference, see my question. Are you asking for graphs maximizing the lower bound ($\Omega(\cdot)$), as opposed to my question where I asked about maximizing the upper bound ($O(\cdot)$)? $\endgroup$
    – arekolek
    Nov 17 '15 at 11:31
  • $\begingroup$ If you ask about minimum expected hitting time, then picking starting vertex at random does not matter, since you actually want to pick two vertices that have the minimum hitting time among all pairs in the graph. $\endgroup$
    – arekolek
    Nov 17 '15 at 11:55
  • $\begingroup$ I don't remember the source, but I read somwhere that the lollipop graph maximizes the hitting time. $\endgroup$
    – Lamine
    Nov 18 '15 at 9:35
  • $\begingroup$ @arekolek: Thank you for your comments. I think I did address most of the issues you brought up in the question statement: I am talking about bidirectional graphs, selecting the starting vertex uniformly, and talking about expected hitting time. Just to clarify: yes, I am talking about graphs maximizing the lower (Omega) bound. $\endgroup$
    – mich
    Nov 18 '15 at 19:33
  • $\begingroup$ The lollipop graph indeed maximizes the mean hitting time, but I am interested in a graph such that no matter what vertex we are talking about, the expected time until a walk that starts somewhere on the graph at random hits that vertex is as high as it can be. Let me know if there is anything else I should clarify. $\endgroup$
    – mich
    Nov 18 '15 at 19:35

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the far clique from that vertex, after which it will take $\Omega(n^3)$ time in expectation before you traverse the connecting path to your chosen vertex.


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.