# Random walks cover time in random regular graphs

Let $G=(V,E)$ be a random $r$-regular graph on $n$ nodes. Perform a random walk on $G$, starting from a node chosen according to the walk stationary distribution (i.e. chosen uar from $V$).

Claim. If $U \subset V$ and the walk is at vertex $u \in U$ at a certain moment in time then the chance that the walk will still be inside $U$ at the next step is $|U|/|V|$.

The claim is wrong (cause otherwise the expected cover time for random cubic graphs would be $|V| \times \log|V|$, and i know it is slightly larger than that) ... but why? What wrong assumption am I making? What is the exact chance of staying in a given set of nodes?

• Heisenberg used to say that "one can say almost everything about nothing, and almost nothing about everything". The question is too general to expect a precise answer. If $U$ consists of vertices not connected by edges that the answer is zero. If $U=V$ then the answer is $1$. You have to be more specific. In any case the answer depends on $u\in U$. – Liviu Nicolaescu Oct 21 '16 at 15:08
• Assume that $U$ is the set of nodes visited so far, and look at the next step of the walk. I am also only interested in $U \subset V$ in the strict sense. – emme Oct 21 '16 at 16:09
• The wrong assumption is that the claim is true. At time $t=2$ also $|U|=2$ and the chance of staying in $U$ is $\frac{1}{r}$ which is probably not equal to $\frac{2}n.$ Assuming that the graph is connected, the walk stationary distribution is to be at any particular vertex with probability $1/n.$ If you are particularly interested in $U$ being the already visited vertices than periodicity is not a problem. One can arrange for an expected cover time of $O(n^2)$ by making a cycle of almost complete graphs (remove an edge from each one). That isn't random of course. – Aaron Meyerowitz Oct 21 '16 at 16:36
• Never said that the claim is true. I just want to get a deeper understanding of the problem, in the specific context of random regular graphs. Actually, then, $|U|/|V|$ is the chance of being in one of the vertices in $U$ at step $t+1$. Using your example, at step $t=2$ the chance of staying in $U$ is $1/r$, but then the chance of being in $U$ at the end of this step is $2/n$ (assuming, as i am, that the walk has mixed). – emme Oct 21 '16 at 21:13
• When the walk is (nearly) mixed we will have $U=V.$ For a more extreme case consider time $t=1$ when $|U|=1.$ Say that $U$ contains vertex $73.$ The chance of being in $U$ at the end of step $2$ is $0$ and not $1/n.$ If you ask "what is the chance that a random walk is at vertex $73$ at step $2?$" the answer is $1/n.$ But if you ask what is the chance that this random walk which already started will be at vertex $73$ at step $2?$ the answer is $0.$ – Aaron Meyerowitz Oct 22 '16 at 3:51

By the strong Markov property, what you seem to imply is equivalent to the following: starting at time 0 from the (uniform) stationary distribution restricted on $U$, $\pi(\cdot \cap U)/\pi(U)$, the chain is distributed according $\pi$ at time 1. This is wrong in general (see the previous comment by Liviu): you need more time to reach $\pi$.
(Aperiodic) example: for the 2 regular graph $\mathbb Z/n\mathbb Z$, $n$ even, if you take $U$ to be the set of odd/even numbers, then the probability to stay in U the next step after entering it is 0. On the other hand, if you choose $U=\{n/2,...,n-1\}$, then the probability to stay in $U$ the next step after entering it at a strictly positive time is $1/2$, and this coincides with $\pi(U)$. This means the boundary of U matters.
• Thanks. My fault. Let's assume $U$ is the set of nodes visited up to time $t$, and focus on the transition at time $t+1$. – emme Oct 21 '16 at 16:07