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?

Improve this question
$\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$
    – Liviu Nicolaescu
    Commented 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
    Commented 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$
    – Aaron Meyerowitz
    Commented 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
    Commented 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$
    – Aaron Meyerowitz
    Commented Oct 22, 2016 at 3:51

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented Oct 21, 2016 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .