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?

  • $\begingroup$ 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$. $\endgroup$ – Liviu Nicolaescu Oct 21 '16 at 15:08
  • $\begingroup$ 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. $\endgroup$ – emme Oct 21 '16 at 16:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Aaron Meyerowitz Oct 21 '16 at 16:36
  • $\begingroup$ 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). $\endgroup$ – emme Oct 21 '16 at 21:13
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Aaron Meyerowitz Oct 22 '16 at 3:51

[no right to comment, so I post this as an answer]

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.

| cite | improve this answer | |
  • $\begingroup$ 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$. $\endgroup$ – emme Oct 21 '16 at 16:07
  • 2
    $\begingroup$ Then you talk about the probability to visit a new state at time t+1; this prrobability is a function of your state at time t, and certainly not (in general) a constant .... perhaps the best would be that you rephrase your question? $\endgroup$ – Olivier Oct 21 '16 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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