2
$\begingroup$

Suppose a sphere is partitioned by a latitude-longitude grid, with grid quadrilaterals $\Delta \times \Delta$. All grid nodes have degree $4$, while the North & South poles have degree $2 \pi / \Delta$, with incident grid triangles.

Let a random walk from any grid node $p$ take one step along each an incident arc, each with equal probability. Here is a $1000$-step random walk starting from the North pole, with $\Delta = 10^\circ$.


          RandWalkSphere1000
In this example, the north pole is visited $20$ times. My question is:

Q. What is the distribution of visits to the grid nodes (as a function of $n$, the number of steps, and $\Delta$)?

Qa. Specifically, how many visits to each pole can be expected (starting anywhere)?

Qb. Are the nodes closer to the poles (excluding the poles themselves) visited more frequently than those near the equator?

Clearly the poles are visited frequently. In a trial of $n{=}10000$ steps, $\Delta = 10^\circ$, the north pole was visited $195$ times. Although I expected the answer to Qb to be Yes, I am not observing clear evidence of such a bias.

$\endgroup$
10
$\begingroup$

According to the general theory any irreducible finite state space Markov chain has a unique stationary measure, and the empirical frequencies along a.e. sample path converge to this measure. The chain you consider is what is called the simple random walk on the constructed graph (the transition probabilities are equidistributed among neighbors), and its stationary measure is proportional to vertex degrees, which are $2\pi/\Delta$ for the poles and 4 for all other vertices.

Alternatively, one can obtain this measure from looking at the "latitudinal part" of the random walk, which is just the random walk on the integer interval $[0,\pi/\Delta]$ with the transition probabilities $p(i,i\pm 1)=1/4, p(i,i)=1/2$ and reflecting barriers at the endpoints. The stationary measure is then obtained by normalizing the vector $(1,4,4,\dots,4,4,1)$.

So, in your example with $\Delta=\pi/18$ the asymptotic frequency of the North pole should be $1/[2+4\cdot 17]=1/70$, which, for some reason, is much less than your empirical frequency $195/10000$.

$\endgroup$
  • $\begingroup$ I am seeing at the poles roughly about $36/4=9$ times the mean excluding the poles ($36 = 360^\circ/\Delta$). So I think that one quoted simulation may be misleading. A 2nd $10^4$ run led to $159$ & $117$ at the two poles, very close to $1/70$. $\endgroup$ – Joseph O'Rourke May 19 '15 at 0:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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