6
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 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$
    – aellab
    Nov 18, 2015 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$
    – aellab
    Nov 18, 2015 at 19:35

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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