0

I am trying to show that; If $X_n, ~ n = 0,1,...$ is a simple random walk on d-regular graph (finite or infinite) starts at $X_0$, after any even number of steps the most likely position is $X_0$.

I can see that since it is regular then the stationary distribution is $~Uniform~$ and I could prove the convergence to uniform distribution, but I don't see why the origin would have higher probability when we have uniform distribution on all vertices.

Can you help me showing that?

Thank you in advance.

Med Qadi
  • 51
  • We don't necessarily have a uniform distribution on the vertices. Consider a $4$-cycle. On even steps, the position is equally likely to be on node $0$ or $2$, and odd steps, it's equally likely to be on node $1$ or $3$. – saulspatz Apr 13 '21 at 16:42
  • a necessary condition for existence of stationary distribution in a finite graph is ergodicity, which means aperiodicity and positive recurrence. see here for example: https://math.stackexchange.com/questions/67516/conditions-for-stationary-distributions-in-markov-chains – Rahul Madhavan Apr 13 '21 at 17:51
  • @saulspatz shouldn't that mean it will be 1/2 probability for each step on each node, make the transition matrix and calculate the stationary distribution, it will be 1/4 for each node, meaning distribution uniform(4) – Med Qadi Apr 14 '21 at 12:20
  • @RahulMadhavan d-regular graphs are ergodic, more over doubly stochastic, in this question you can assume it is connected graph if you wish. – Med Qadi Apr 14 '21 at 12:29
  • how so? consider the example given by saulpatz - the 4 cycle. Label the vertices n the cycle as 0,1,2,3. Starting at 0, you can go to 1,3 in step 1. From 1,3, you can go to 0,2 in step 2. Generalizing, in the even steps, you can go to ${0,2}$, and in the odd steps you can go to ${1,3}$. This appears periodic to me (and therefore not ergodic). See here for example: https://en.wikipedia.org/wiki/Ergodicity#A_periodic_chain – Rahul Madhavan Apr 14 '21 at 13:30
  • @MedQadi Yes, it is uniform. The example shows that after an even numbers of steps, the chain is not necessary more likely to be at the origin than anywhere else, but at least as likely to be there. – saulspatz Apr 14 '21 at 15:17
  • @RahulMadhavan I got your points, thanks, still this may affect the uniqueness but the stationary distribution existed. – Med Qadi Apr 14 '21 at 15:23
  • @saulspatz So the statement above is wrong and cannot be proven!!! – Med Qadi Apr 14 '21 at 15:24
  • @MedQadi I wouldn't say that. I think it may be worded a little carelessly. Perhaps it should say, "a most likely position", or more explicitly, "After an even number of steps, the walk is at least as likely to be at the origin as in any other position." I've been trying to prove this by induction, but not getting anywhere. – saulspatz Apr 14 '21 at 15:30

0 Answers0