<p>The cover time of a random walk on an undirected graph is the expected time for the walk to visit all vertices of the graph (starting from an arbitrary vertex). It is well known that any connected graph with <span class="math-container">$n$</span> vertices has cover time <span class="math-container">$O(n^3)$</span>.</p>
<p>I'm looking for a similar result, perhaps with a much worse upper bound, for random walks on directed graphs that are connected <strong>but not necessarily strongly connected</strong>. To guarantee that the walk will be able to visit every vertex without getting stuck in a strongly connected component, we assume the following features.</p>
<ol>
<li>That the walk starts at a node <span class="math-container">$v$</span> that can reach any other vertex in the graph. So we assume that such a vertex exists.</li>
<li>We add a stack to the walk. More precisely, the walk starts at a vertex <span class="math-container">$v$</span> and <span class="math-container">$v$</span> is the only vertex at the stack. At each time step, given that <span class="math-container">$v$</span> is at the top of the stack, the walk either moves to a neighbor <span class="math-container">$u$</span> of <span class="math-container">$v$</span>, and <span class="math-container">$u$</span> is added to the top of the stack, or the walk pops <span class="math-container">$v$</span> from the top of the stack and moves to the vertex just below it in the stack (a backtrack move). If the stack has at least two vertices, then moving to a neighbour <span class="math-container">$u$</span> happens with probability <span class="math-container">$1/2\delta(v)$</span>, while backtracking happens with probability <span class="math-container">$1/2$</span>. If <span class="math-container">$v$</span> is the only vertex in the stack, then moving to a neighbor <span class="math-container">$u$</span> happens with probability <span class="math-container">$1/\delta(v)$</span> (no backtracking is allowed).</li>
</ol>
<p><strong>Questions:</strong></p>
<ol>
<li>What is the correct name for the type of random walk described above. I'm having a hard time finding references about it, but I'm sure it has been studied somewhere.</li>
<li>Is there any non-trivial upper bound on the cover time for such a walk? In particular, is there an upper bound for directed graphs with constant (or bounded) out-degree graphs?</li>
</ol>
<p><strong>Obs:</strong> I have found some material on random walks on strongly connected graphs (which do not need a stack). There are examples of such graphs with exponential cover time (see <a href="https://cstheory.stackexchange.com/questions/2908/cover-time-of-directed-graphs">this question</a>). But the examples I found have some vertex with very large maximum degree (linear in <span class="math-container">$n$</span>). Additionally, I have the impression that the addition of a stack may help, reducing the time in the bounded out-degree case (I may be wrong here).</p>

CC BY-SA 4.0
2020-12-17T00:21:35.130Z
This should be undefined. Let $G$ be the graph $u \leftarrow v → a \leftrightarrow b$. Starting at $v$, the walk has a $1/8$ chance of starting out with the sequence $v → a → b → a$, sans backtracking. At this point, there is some nonzero probability that the walk avoids $v$ for all time: the depth of $v$ in the stack is itself a (non-backtracking) biased random walk with probability $2/3$ of increasing and probability $1/3$ of decreasing. Whatever the avoidance probability $p$ of that walk is ($1/2?$), there is at least a $p/8 > 0$ probability of not returning to $v$ and hitting $u$ at all.
Yonatan N
CC BY-SA 4.0
2020-12-17T01:36:04.280Z
@YonatanN  I have corrected a small mistake in the question. The vertex $v$ currently being visited is always the one at the top of the stack. In any case, I didn't really get your argument. Even if there was a probability of p/8 of never returning to v, there is a probability of 1-p/8 of returning to v. So why would this cause the walk to not visit u?
Springberg
CC BY-SA 4.0
2020-12-17T02:51:07.397Z
In the above example, $u$ cannot be visited until the walk returns to $v$. So, with some positive probability, it is never visited. The cover time of a graph is the expected number of steps taken until each node is visited for the first time. It's not clear what this means when not every vertex is (almost surely) visited at all.
Yonatan N
CC BY-SA 4.0
2020-12-17T08:41:56.320Z
What Yonatan’s example suggests is that to make the problem well defined, you should change the definition of the random walk so that the probability of backtracking is $1/2$, and the probability of moving to each neighbour is $1/(2\delta(v))$.
Emil Jeřábek
CC BY-SA 4.0
2020-12-17T11:14:46.100Z
@EmilJeřábek thanks for the suggestion. And Yonatan, thanks for the explanation. I'm changing the transition probabilities as suggested by Emil.
Springberg
CC BY-SA 4.0
2020-12-18T04:10:21.053Z
Isn't the natural example a path of length n going from left to right, where the $i$th vertex is connected back to the first vertex. Since every vertex has two outgoing edges,and backtracking happens with probability half at each step, it seems that it would take $4^n$ steps before the walk visits all the vertices, even as the graph is low degree (every vertex has at most two outgoing edges...
Sariel Har-Peled
<randomized-algorithms><random-walks>
Cover Time of Random Walks with Backtracking on Directed Graphs
Springberg
# Cover Time of Random Walks with Backtracking on Directed Graphs

(Asked by: username_0 on 2020-12-16)

The cover time of a random walk on an undirected graph is the expected time for the walk to visit all vertices of the graph (starting from an arbitrary vertex). It is well known that any connected graph with $n$ vertices has cover time $O(n^3)$.

I'm looking for a similar result, perhaps with a much worse upper bound, for random walks on directed graphs that are connected **but not necessarily strongly connected**. To guarantee that the walk will be able to visit every vertex without getting stuck in a strongly connected component, we assume the following features.

1. That the walk starts at a node $v$ that can reach any other vertex in the graph. So we assume that such a vertex exists.
2. We add a stack to the walk. More precisely, the walk starts at a vertex $v$ and $v$ is the only vertex at the stack. At each time step, given that $v$ is at the top of the stack, the walk either moves to a neighbor $u$ of $v$, and $u$ is added to the top of the stack, or the walk pops $v$ from the top of the stack and moves to the vertex just below it in the stack (a backtrack move). If the stack has at least two vertices, then moving to a neighbour $u$ happens with probability $1/2\delta(v)$, while backtracking happens with probability $1/2$. If $v$ is the only vertex in the stack, then moving to a neighbor $u$ happens with probability $1/\delta(v)$ (no backtracking is allowed).

**Questions:**

1. What is the correct name for the type of random walk described above. I'm having a hard time finding references about it, but I'm sure it has been studied somewhere.
2. Is there any non-trivial upper bound on the cover time for such a walk? In particular, is there an upper bound for directed graphs with constant (or bounded) out-degree graphs?

**Obs:** I have found some material on random walks on strongly connected graphs (which do not need a stack). There are examples of such graphs with exponential cover time (see [this question](https://cstheory.stackexchange.com/questions/2908/cover-time-of-directed-graphs)). But the examples I found have some vertex with very large maximum degree (linear in $n$). Additionally, I have the impression that the addition of a stack may help, reducing the time in the bounded out-degree case (I may be wrong here).

**Tags:** randomized-algorithms, random-walks
> **Comments:**
> **username_1**: This should be undefined. Let $G$ be the graph $u \leftarrow v → a \leftrightarrow b$. Starting at $v$, the walk has a $1/8$ chance of starting out with the sequence $v → a → b → a$, sans backtracking. At this point, there is some nonzero probability that the walk avoids $v$ for all time: the depth of $v$ in the stack is itself a (non-backtracking) biased random walk with probability $2/3$ of increasing and probability $1/3$ of decreasing. Whatever the avoidance probability $p$ of that walk is ($1/2?$), there is at least a $p/8 > 0$ probability of not returning to $v$ and hitting $u$ at all.  
> **username_0**: @YonatanN  I have corrected a small mistake in the question. The vertex $v$ currently being visited is always the one at the top of the stack. In any case, I didn't really get your argument. Even if there was a probability of p/8 of never returning to v, there is a probability of 1-p/8 of returning to v. So why would this cause the walk to not visit u?  
> **username_1**: In the above example, $u$ cannot be visited until the walk returns to $v$. So, with some positive probability, it is never visited. The cover time of a graph is the expected number of steps taken until each node is visited for the first time. It's not clear what this means when not every vertex is (almost surely) visited at all.  
> **username_2**: What Yonatan’s example suggests is that to make the problem well defined, you should change the definition of the random walk so that the probability of backtracking is $1/2$, and the probability of moving to each neighbour is $1/(2\delta(v))$.  
> **username_0**: @EmilJeřábek thanks for the suggestion. And Yonatan, thanks for the explanation. I'm changing the transition probabilities as suggested by Emil.  
> **username_3**: Isn't the natural example a path of length n going from left to right, where the $i$th vertex is connected back to the first vertex. Since every vertex has two outgoing edges,and backtracking happens with probability half at each step, it seems that it would take $4^n$ steps before the walk visits all the vertices, even as the graph is low degree (every vertex has at most two outgoing edges...  

---

## 0 answers

