<p>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.</p>

CC BY-SA 3.0
2015-11-19T20:12:11.537Z
2015-11-19T20:12:11.537Z
David Eppstein
<p>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$. </p>

<p>For what family of graphs is the <em>minimum</em> of all expected hitting times as large as it can be? </p>

CC BY-SA 3.0
2015-11-17T11:31:09.650Z
Take a look at my question about [mean hitting time](http://cstheory.stackexchange.com/q/32848/36007). 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)$)?
arekolek
CC BY-SA 3.0
2015-11-17T11:55:29.220Z
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.
arekolek
CC BY-SA 3.0
2015-11-18T09:35:51.717Z
I don't remember the source, but I read somwhere that the lollipop graph maximizes the hitting time.
Lamine
CC BY-SA 3.0
2015-11-18T19:33:46.473Z
@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.
aellab
CC BY-SA 3.0
2015-11-18T19:35:22.893Z
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.
aellab
CC BY-SA 3.0
2015-11-19T01:09:27.800Z
Why does it make sense to start uniformly at random? Wouldn't the stationary distribution be a better choice?
David Eppstein
CC BY-SA 3.0
2015-11-19T18:26:01.320Z
@DavidEppstein Thank you for your comments. Maybe my choice of distribution is a little arbitrary. In the toy problem I am considering, we have non-identical "signals" that are randomly traversing the graph whose vertices are processors, and the initial placement of a signal is simply the processor which decided to send it. Each processor's decision to send or not send a starting signal is independent of the structure of the graph, so I thought the uniform distribution better represents that.

With that said I would be very interested in an analysis for the stationary distribution as well! :-)
aellab
<graph-theory><pr.probability><randomness><random-walks>
Graph that maximizes minimum hitting time?
aellab
# Graph that maximizes minimum hitting time?

(Asked by: username_0 on 2015-11-15)

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?

**Tags:** graph-theory, pr.probability, randomness, random-walks
> **Comments:**
> **username_1**: Take a look at my question about [mean hitting time](http://cstheory.stackexchange.com/q/32848/36007). 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)$)?  
> **username_1**: 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.  
> **username_2**: I don't remember the source, but I read somwhere that the lollipop graph maximizes the hitting time.  
> **username_0**: @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.  
> **username_0**: 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.  
> **username_3**: Why does it make sense to start uniformly at random? Wouldn't the stationary distribution be a better choice?  
> **username_0**: @DavidEppstein Thank you for your comments. Maybe my choice of distribution is a little arbitrary. In the toy problem I am considering, we have non-identical "signals" that are randomly traversing the graph whose vertices are processors, and the initial placement of a signal is simply the processor which decided to send it. Each processor's decision to send or not send a starting signal is independent of the structure of the graph, so I thought the uniform distribution better represents that.  With that said I would be very interested in an analysis for the stationary distribution as well! :-)  

---

## 1 answers

### Answer by username_3 on 2015-11-19. Score: 10 | Accepted answer

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.


---

