1

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). 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).

Springberg
  • 636
  • 3
  • 14
  • 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. – Yonatan N Dec 17 '20 at 00:21
  • @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 Dec 17 '20 at 01:36
  • 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. – Yonatan N Dec 17 '20 at 02:51
  • 1
    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 Dec 17 '20 at 08:41
  • 1
    @EmilJeřábek thanks for the suggestion. And Yonatan, thanks for the explanation. I'm changing the transition probabilities as suggested by Emil. – Springberg Dec 17 '20 at 11:14
  • 1
    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 Dec 18 '20 at 04:10

0 Answers0