Library · The Fiddler: Solutions · Chapter 89
Can You Spin the Graph?
You graph , but it is rotated about the origin by a uniformly random angle in . What is the probability the rotated graph still passes the vertical line test (still defines as a function of )?
The Fiddler, Zach Wissner-Gross, January 31, 2025(original post)
Solution
The graph is two rays from the origin, apart, initially pointing at and . A pair of rays passes the vertical line test exactly when the two rays lie on opposite sides of the vertical axis: if both rays had a horizontal component of the same sign, a vertical line just past the origin would cross both. Writing the rays after rotation as and , we need and to have opposite signs, i.e. , i.e. . That holds for half of all , so
The computation
Spin the actual graph: pick a random rotation, point both rays through it, and check whether their horizontal components disagree in sign (the vertical line test). The pass rate is one half.
import numpy as np
rng = np.random.default_rng(0)
phi = rng.uniform(0, 360, 2_000_000) * np.pi / 180
a, b = np.radians(45) + phi, np.radians(135) + phi
print((np.cos(a) * np.cos(b) < 0).mean()) # 0.5000
Extra Credit
In a more advanced course you sketch the 3D graph of , and a bout of dizziness rotates it randomly in space: the true -axis is equally likely to point towards any point of the unit sphere (and the -axis is then equally likely to point in any direction perpendicular to it). What is the probability that the result is still a function, with a function of and ?
Solution
Being a function means passing the vertical line test: every line parallel to the new -axis meets the graph at most once. Only the direction of the new -axis matters, and it is uniform on the sphere.
The graph is the surface of the solid region above it, an upside-down square pyramid that goes on for ever. This region is a convex cone, and that is the key. Convex means that a line meets in a single stretch, possibly empty, possibly endless. Cone means that if contains a point , it also contains for every whenever the direction itself lies in .
If points into the cone. Take any line that meets . Once on the line inside , moving further in direction never leaves it, so the stretch inside runs off to infinity in one direction. Going the other way, the line eventually leaves , and the graph is crossed exactly once. The same holds if points into the cone (the picture is simply upside down), and this is the case the main puzzle also counted: there, remained a function both right way up and upside down.
Otherwise. Take a line in direction through a point inside . Its stretch inside cannot run to infinity in either direction, because that would need or to point into the cone. So the stretch is bounded, the line enters and leaves, and it meets the graph twice. The test fails.
So the probability is the fraction of all directions lying in or in , which is , where is the solid angle of the cone. The cone’s edges point along and , and its axis splits it into four congruent spherical triangles with corners , , . For a spherical triangle with unit corner vectors, the formula of Van Oosterom and Strackee gives So , and (The official extra-credit value is paywalled; this is my own.)
The computation
The check performs the vertical line test itself instead of using the cone argument. For each random direction of the new -axis it takes eight lines in that direction, through points chosen at random inside the region above the graph (any line that meets the graph twice must pass through that region), and counts how often each line crosses the surface. Along a line, the height above the surface is a straight-line function of the position except where or changes sign, so its zeros can be counted exactly from its values at those two points and far out at each end. A direction passes if no test line crosses more than once.
import numpy as np
rng = np.random.default_rng(1)
def crossings(p, u, T=1e6):
"""Number of times the line p + t*u meets the surface z = |x| + |y|."""
g = lambda t: (p[..., 2] + t*u[..., 2]) - np.abs(p[..., 0] + t*u[..., 0]) \
- np.abs(p[..., 1] + t*u[..., 1])
# g is linear between the parameters where x or y changes sign
t1 = -p[..., 0]/u[..., 0]; t2 = -p[..., 1]/u[..., 1]
ts = np.sort(np.stack([np.full_like(t1, -T), t1, t2, np.full_like(t1, T)]), axis=0)
ts = np.clip(ts, -T, T)
vals = np.stack([g(t) for t in ts])
return (np.sign(vals[1:]) != np.sign(vals[:-1])).sum(axis=0)
def inside_points(n):
"""Random points strictly inside the region above the graph, below z = 2."""
pts = []
while len(pts) < n:
q = rng.uniform([-2, -2, 0], [2, 2, 2])
if q[2] > abs(q[0]) + abs(q[1]): pts.append(q)
return np.array(pts)
N, K = 200_000, 8
u = rng.normal(size=(N, 3)); u /= np.linalg.norm(u, axis=1, keepdims=True)
P = inside_points(K)
worst = np.zeros(N, int)
for p in P: # K test lines per rotation
worst = np.maximum(worst, crossings(np.broadcast_to(p, (N, 3)), u))
ok = worst <= 1
print("still a function: %.4f +- %.4f" % (ok.mean(), np.sqrt(ok.mean()*(1-ok.mean())/N)))
It prints
still a function: 0.2173 +- 0.0009
within about one standard error of the boxed . (Eight test lines can very occasionally miss a failure close to the cone’s edge, which can only push the estimate up.)