1
$\begingroup$

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?

$\endgroup$
5
  • $\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$ Oct 21, 2016 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, 2016 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$ Oct 21, 2016 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, 2016 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$ Oct 22, 2016 at 3:51

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\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, 2016 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, 2016 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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