Stop the Alien Invasion

A pair of hostile aliens land at two random locations on a spherical planet, each carrying half of a doomsday weapon. They race, at equal speed, to their meeting point, the spot on the surface exactly halfway between them along the shortest path, where they will assemble the weapon. A guardian starts at her own random location on the surface and can stop the attack if she reaches the aliens before they meet. Her speed is $20$ times the aliens’. What is the probability she saves the planet?

The Riddler, FiveThirtyEight(original post)

Solution

The first move makes the geometry tractable: because the guardian is faster than the aliens, she wins exactly when she can reach the aliens’ meeting point before they do. If she gets to that rendezvous first, she simply waits or steps toward an arriving alien and catches him; if she cannot, the aliens combine the weapon and it is over. So the race is guardian-to-rendezvous against alien-to-rendezvous.

Work in angles measured from the planet’s centre, with radius $R$ and alien speed $v$. Let $\theta$ be the angular separation of the two aliens. Their meeting point $M$ sits halfway along the connecting arc, an angular distance $\theta/2$ from each alien, so an alien reaches $M$ after travelling an arc of length $R\theta/2$, taking time $R\theta/(2v)$. Let $\varphi$ be the angular distance from the guardian’s start to $M$. She moves at $20v$, so she reaches $M$ after time $R\varphi/(20v)$. The planet is saved when she arrives first: $$\frac{R\varphi}{20v} < \frac{R\theta}{2v} \qquad\Longleftrightarrow\qquad \varphi < 10\,\theta .$$

Now the one fact that does the real work. For two independent points placed uniformly at random on a sphere, the angle $\psi$ between them (as seen from the centre) has probability density $$f(\psi) = \tfrac12 \sin\psi, \qquad 0 \le \psi \le \pi .$$ This is just the surface area of a thin ring at polar angle $\psi$: fix the first point as a pole, and the second point’s colatitude has density proportional to $\sin\psi$, normalised to $\tfrac12\sin\psi$. Two consequences follow. First, $\theta$ has this density. Second, the meeting point $M$ is itself a uniformly random point on the sphere (nothing in its construction prefers any direction), and the guardian is an independent uniform point, so $\varphi$, the angle between guardian and $M$, has the very same density and is independent of $\theta$.

So $\theta$ and $\varphi$ are independent, each with density $\tfrac12\sin$ on $[0,\pi]$, and we want $\Pr(\varphi < 10\theta)$. Integrate over $\theta$, and for each $\theta$ let $\varphi$ run up to $\min(\pi, 10\theta)$, using $\int_0^m \tfrac12\sin\varphi\,d\varphi = \tfrac12(1-\cos m)$: $$P = \int_0^{\pi} \tfrac12\sin\theta \cdot \tfrac12\bigl(1 - \cos(\min(\pi,10\theta))\bigr)\,d\theta .$$ The cap $10\theta = \pi$ at $\theta = \pi/10$ splits the range. For $\theta \ge \pi/10$ the inner factor is $\tfrac12(1-\cos\pi) = 1$, so that piece is $$\int_{\pi/10}^{\pi} \tfrac12\sin\theta\,d\theta = \tfrac12\bigl(1 + \cos\tfrac{\pi}{10}\bigr).$$ For $\theta < \pi/10$ the inner factor is $\tfrac12(1-\cos 10\theta)$, giving $\tfrac14\int_0^{\pi/10}(\sin\theta - \sin\theta\cos 10\theta)\,d\theta$. Writing $\sin\theta\cos 10\theta = \tfrac12(\sin 11\theta - \sin 9\theta)$ and using $\cos\tfrac{11\pi}{10} = \cos\tfrac{9\pi}{10} = -\cos\tfrac{\pi}{10}$, that last integral collapses to $-\tfrac1{99}\bigl(1+\cos\tfrac{\pi}{10}\bigr)$, so the small-$\theta$ piece is $$\tfrac14\!\left[\Bigl(1-\cos\tfrac{\pi}{10}\Bigr) + \tfrac1{99}\Bigl(1+\cos\tfrac{\pi}{10}\Bigr)\right].$$ Let $c = \cos(\pi/10)$ and add the two pieces over a common denominator of $396$: $$\begin{aligned} P &= \frac{198(1+c) + 99(1-c) + (1+c)}{396} = \frac{298 + 100c}{396}\\ &= \boxed{\dfrac{149 + 50\cos(\pi/10)}{198}} \approx 0.99269 . \end{aligned}$$ The guardian saves the planet about $99.27\%$ of the time. The same argument with a speed multiplier $k$ in place of $20$ just moves the split point to $\theta = \pi/k$; the lone slow case left is when the aliens land almost on top of each other and the guardian is far away.

The computation

Re-run the scene at random. Drop two aliens and a guardian uniformly on the unit sphere, build the aliens’ meeting point as the normalised average of their positions, and check whether the guardian’s angle to it is less than $10$ times the aliens’ separation.

import random, math
random.seed(0)

def rand_sphere():
    z = random.uniform(-1, 1)
    t = random.uniform(0, 2 * math.pi)
    r = math.sqrt(1 - z * z)
    return (r * math.cos(t), r * math.sin(t), z)

def angle(a, b):
    d = max(-1.0, min(1.0, sum(a[i] * b[i] for i in range(3))))
    return math.acos(d)

def saved(k=20):
    A, B, G = rand_sphere(), rand_sphere(), rand_sphere()
    m = [(A[i] + B[i]) / 2 for i in range(3)]
    norm = math.sqrt(sum(c * c for c in m))
    if norm < 1e-12:          # antipodal aliens, no defined midpoint
        return None
    M = tuple(c / norm for c in m)
    theta, phi = angle(A, B), angle(G, M)
    return phi / k < theta / 2          # guardian reaches rendezvous first

trials = [saved() for _ in range(400_000)]
hits = [s for s in trials if s is not None]
print("simulated :", round(sum(hits) / len(hits), 5))
print("formula   :", round((149 + 50 * math.cos(math.pi / 10)) / 198, 5))
# simulated : 0.99267
# formula   : 0.99269