# Drunkards walk on a sphere.

I simulated the following situation on my pc. Two persons A and B are initially at opposite ends of a sphere of radius r. Both being drunk, can take exactly a step of 1 unit(you can define the unit, i kept it at 1m) either along a latitude at their current location, or a longitude. A and B are said to meet, if the arc length distance between A and B becomes less than equal to 1km.

Note: the direction of possible motion of each man is fixed w.r.t thr axis of the globe. Either latitude or longitude. Assume such a coordinate system exists before hand(just like the 2d analog on a plane, moving in x or y only and not absolutely randomly).

The simulation returned results, which i could not comprehend fully. The average time to meet, was about 270 years for a sphere of radius 100km!. Can someone shed some light on how i can proceed with proving this result. I want the expected time of meeting given the radius and step length, given that each move requires 1 sec. I tried considering a spehrical cap of arc length √n, after n steps, in analogy with the 2d model. But then,i cant calculate the expected time. If possible please help or suggest some related articles.

• Does your program allow for therm to make steps that undo themselves? for example can drunk A step forward along a line of latitude and then step backwards along the same line of latitude? From the little bit you have explained of this it seems to have parallels with the Banach-Tarski paradox, not in the paradox itself but in the way you define movement about a sphere. Perhaps that may be worth looking into? Apologies I cannot help further. – Danish Sep 20 '16 at 3:06
• Yes, it is exactly like the 2d analog on a sphere. A can also take the next step backward after moving one step forward. – Lelouch Sep 20 '16 at 3:28
• The ability to be able to retrace one's steps makes your problem quite a bit harder, because if you are using a random seed of some sort to determine their next move you will have an infinite set of sequences that result in returning to the origin. As such it looks like your solution is a probability curve - something I have very little experience in. Sorry I can't help you further, best of luck with the problem though. – Danish Sep 20 '16 at 3:58
• Thanks for your help. I also figured it will be a probabilty curve, and cam get the expection value, if i can find that curve, alternatively. – Lelouch Sep 20 '16 at 4:04
• My experience is that when drunkards attempt to walk on a sphere, they don't get very far! – user247327 Sep 26 '16 at 0:59

## 2 Answers

For now, I will give a reformulation of this problem in terms that should make it easier to attack with analytic methods (at least to get results on the asymptotic behavior) and greatly simplify simulations. In a second time, I will maybe also attempt to solve it, but I don't guarantee any kind of success.

My reformulation of this problem is based on the following two remarks:

1. On spheres, it is always easier to work with angles than with distances. Therefore, we will always work on a sphere of radius $r=1$, define an angle $\epsilon$ corresponding to one unit, and say that $A$ and $B$ meet if the angle between them is less than or equal to some angle $\beta$.
2. If possible, it is better to have only one thing moving around. Therefore we will change our point of view and fix ourselves in the reference system of one of the two people, say person $B$. We will take this point to be the north pole (for the spherical coordinates we'll find ourselves in). In light of the first observation, the only variable of interest to us will be the latitude $A$ finds itself on.

For the mathematical details:

First we have to fix our coordinate system. Let $\phi$ be the longitude (this variable will be useful for calculations, but irrelevant in the end), and $\theta$ be the latitude. We put the north pole $B$ at latitude $\theta = 0$, and the south pole is at $\theta = \pi$. We'll denote positions by coordinates $(\theta,\phi)$.

Notice that by spherical symmetry, $A$ and $B$ bot taking a step is the same as $B$ staying put and $A$ taking two steps. Let's start by seeing what happens when $A$ takes one step. Let's say that $A$ starts in position $(\theta,\phi)$. We are only interested in the probability of $A$ landing at latitude $\theta'$. Notice that $P[A\text{ lands at }\theta'\le\theta_0]$ is given by the ration of the circumference of the circle at angle $\epsilon$ from $A$ below the meridian at $\theta_0$. To find this, I refer you to this answer by @Aretino, giving $$P[A\text{ lands at }\theta'\le\theta_0] = 1 - \frac{1}{\pi}\arccos\left(\frac{\cos\theta' - \cos\epsilon\cos\theta}{\sin\epsilon\sin\theta}\right)$$ whenever the term in the brackets is in $[-1,1]$, and $0$ or $1$ else (depending on $\theta'$). The distribution function $f_\theta(\theta')$ giving the probability to land at $\theta'$ after one step starting at $\theta$ can then be found as usual by differentiating this probability: \begin{align} f_\theta(\theta') = & \frac{\partial}{\partial\theta'}\left(1 - \frac{1}{\pi}\arccos\left(\frac{\cos\theta' - \cos\epsilon\cos\theta}{\sin\epsilon\sin\theta}\right)\right)\\ = & \frac{\sin\theta'}{\sqrt{1 - \left(\frac{\cos\theta' - \cos\epsilon\cos\theta}{\sin\epsilon\sin\theta}\right)^2}}\\ = & \frac{\sin\epsilon\sin\theta\sin\theta'}{\sqrt{\cos\theta'(2\cos\epsilon\cos\theta - \cos\theta') + \sin^2\theta - \cos^2\epsilon}}, \end{align} and $0$ outside the domain of definition of the original function. The probability of landing at $\theta'$ after two steps starting at $\theta$ is therefore given by $$F_\theta(\theta') = \int_0^\pi f_\theta(\theta'')f_{\theta''}(\theta')d\theta''.$$ I have some doubts this can be done analytically, but maybe some approximation can give something useful.

Given this data, we can have a hope to be able to do something at least to find asymptotic bounds for when $\epsilon\to0$, and if not, it will at least greatly simplify simulations, as we are reduced to simulating a walk on a line (parametrized by $\theta$) with a non-uniform probability to move to nearby points.

• A step of a fixed distance east on the equator results in a different change in your longitude then near the poles. It doesn't look like you take account of this. – Q the Platypus Sep 26 '16 at 3:07
• @QthePlatypus Yes, it does. At the pole we have in fact that $f_\pi(\theta') = \delta(\theta'-\epsilon)$ (it is one of the special cases), while at the equator $$f_{\frac{\pi}{2}}(\theta') = \frac{\sin\epsilon\sin\theta'}{\sin^2\theta' - \cos^2\epsilon}$$ for $-\epsilon \le \theta'-\frac{\pi}{2}\le\epsilon$. – Daniel Robert-Nicoud Sep 26 '16 at 11:38
• I can see that its already quite simplified. So i'll try getting ahead with this. Meanwhile any more updates are very welcome. Thanks for your efforts. – Lelouch Sep 26 '16 at 13:08
• @Lelouch You're welcome :) let me know your progress (simulations, conjectures, results...) Oh, and maybe check the details of what I've done. I'm prone to errors sometimes... – Daniel Robert-Nicoud Sep 26 '16 at 13:19

As stated in Daniel's answer, it is easier to think about the problem if we say only one of the two people is moving. Suppose person $B$ stays at the North pole and person $A$ starts at the South pole, and each time step, $A$ moves 1m either longitudinally or latitudinally.

If $A$ moves latitudinally, then $A$'s distance from the North pole remains the same. Therefore, we ignore these latitudinal movements and say instead that $A$ has a 50% chance of not moving and a 50% chance of taking a 1 meter step along a great circle containing the North and South pole. We parameterize this circle by $x = 0$ at the South pole, $x = 1$ one meter in one direction from the South pole, $x = -1$ one meter in the opposite direction, and so on.

If the radius of the sphere is 100000m, and $A$ needs to be 1000m from the North pole to see $B$, then $A$ will see $B$ if the distance of $A$ from the South Pole is $$\pi 100000m - 1000m \approx 313159m$$

If $f(x)$ is the expected number of remaining time steps when $A$ is at position $x$ then $f$ satisfies $$f(x) = \frac{f(x-1) + 2f(x) + f(x+1)}{4} + 1$$ And $$f(313159) = f(-313159) = 0$$ We see that this is satisfied by $$f(x) = 2(313159)^2 - 2x^2$$

So $$f(0) = 2(313159)^2 = 1.9 \times 10^{11}$$ So if the time steps are half seconds (since two movements happen each second - one for each person), the expected time should be 3108 years.

• But dont we need to consider the longitudinal movements in the end? – Lelouch Sep 26 '16 at 7:34
• You don't consider possible "diagonal" movement (i.e. not longitudinal, but not on a great circle through the north pole either). That's why I had to compute all that stuff with probability distributions etc. in my answer, instead of keeping it simple. – Daniel Robert-Nicoud Sep 26 '16 at 11:41
• Yes, it is indeed possible in the original problem that the two people can move in a "diagonal" direction to each other, so this answer is really only an estimate. – Bolton Bailey Sep 26 '16 at 17:23