Random Walk from the Centre of a Unit Square and Cube

Riddler Express

You start at the centre of the unit square and pick a random direction to move in, with all directions equally likely. You move along this direction until you reach a point on the perimeter of the square. On average, how far can you expect to have travelled?

Solution

Place the square with corners at $(0, 0)$, $(1, 0)$, $(1, 1)$, $(0, 1)$. By symmetry, the mean distance over all directions equals the mean over the triangle with vertices $(1/2, 1/2)$, $(1, 1/2)$, $(1, 1)$. Pick a direction $\theta \in [0, \pi/4]$; the distance to the right edge is $d = 1/(2 \cos \theta)$.

Weighting by the uniform density on the fundamental sector, $$\mathbb{E}[d] \;=\; \int_0^{\pi/4} \frac{1}{2 \cos \theta} \cdot \frac{4}{\pi} \, d\theta \;=\; \frac{2}{\pi} \int_0^{\pi/4} \sec \theta \, d\theta.$$ The antiderivative of $\sec \theta$ is $\ln|\sec \theta + \tan \theta|$, so $$\mathbb{E}[d] \;=\; \frac{2}{\pi} \, \ln(\sqrt 2 + 1) \;=\; \frac{\ln(3 + 2\sqrt 2)}{\pi} \;\approx\; \boxed{0.5611}.$$

Why the $\int \sec x \, dx$ step works: four derivations

Method 1: multiplication by a clever form of 1.

Multiply by $(\sec x + \tan x)/(\sec x + \tan x) = 1$: $$\int \sec x \, dx \;=\; \int \frac{\sec^2 x + \sec x \tan x}{\sec x + \tan x} \, dx.$$ With $u = \sec x + \tan x$, the numerator equals $du$, so the integral equals $\ln|u| + C = \ln|\sec x + \tan x| + C$.

Method 2: Weierstrass substitution.

With $t = \tan(x/2)$, the half-angle formulas give $\sin x = 2t/(1+t^2)$, $\cos x = (1-t^2)/(1+t^2)$, and $dx = 2 \, dt/(1+t^2)$. Then $$\int \sec x \, dx \;=\; \int \frac{2}{1 - t^2} \, dt \;=\; \ln\!\left|\frac{1 + t}{1 - t}\right| + C \;=\; \ln\!\left|\tan\!\bigl(\tfrac{\pi}{4} + \tfrac{x}{2}\bigr)\right| + C.$$

Method 3: complex exponentials.

Since $\cos x = (e^{ix} + e^{-ix})/2$, $$\int \sec x \, dx \;=\; \int \frac{2 \, e^{ix}}{e^{2ix} + 1} \, dx.$$ Substitute $u = e^{ix}$, giving $\int 2/(i(u^2 + 1)) \, du = -2i \arctan(e^{ix}) + C$, which on the real line reduces to $\ln|\sec x + \tan x| + C$.

Method 4: via hyperbolic functions.

Setting $x = it$, $\cos(it) = \cosh t$, so $$\int \sec x \, dx \;=\; i \int \operatorname{sech} t \, dt \;=\; 2i \arctan\bigl(\tanh(t/2)\bigr) + C,$$ which again equals $\ln|\sec x + \tan x| + C$ after substituting $t = -i x$.

Monte Carlo verification

import numpy as np

def simulate_random_walk_2d(num_simulations=1_000_000):
    """Simulate random walks from the centre of the unit square."""
    x0, y0 = 0.5, 0.5
    theta = np.random.uniform(0, 2 * np.pi, num_simulations)
    dx, dy = np.cos(theta), np.sin(theta)

    t_right  = np.where(dx > 0, (1 - x0) / dx, np.inf)
    t_left   = np.where(dx < 0,  -x0 / dx,     np.inf)
    t_top    = np.where(dy > 0, (1 - y0) / dy, np.inf)
    t_bottom = np.where(dy < 0,  -y0 / dy,     np.inf)

    return np.minimum(np.minimum(t_right, t_left),
                      np.minimum(t_top,   t_bottom))

np.random.seed(42)
exact = np.log(3 + 2 * np.sqrt(2)) / np.pi
d = simulate_random_walk_2d(10**6)
print(f"analytical: {exact:.6f}")
print(f"simulated:  {d.mean():.6f}")
# analytical: 0.561100
# simulated:  0.561103

Riddler Classic

Now, you start at the centre of the unit cube. Again, you pick a random direction to move in, with all directions being equally likely. You move along this direction until you reach a point on the surface of the cube. On average, how far can you expect to have travelled?

Solution

Place the cube with corners at $(0, 0, 0)$ and $(1, 1, 1)$. A random direction on the sphere is written as $\vec v = (\sin \varphi \cos \theta, \sin \varphi \sin \theta, \cos \varphi)$ with $\theta \in [0, 2\pi)$ and $\varphi \in [0, \pi]$; the uniform measure on the sphere is $(4\pi)^{-1} \sin \varphi \, d\varphi \, d\theta$. From the centre, the distance along $\vec v$ to the boundary is $$d \;=\; \frac{1}{2 \, m}, \qquad m \;=\; \max\bigl(|\sin \varphi \cos \theta|,\; |\sin \varphi \sin \theta|,\; |\cos \varphi|\bigr).$$

The cube’s direction sphere is cut into congruent pieces by its symmetries: $8$ octants from the sign choices, and within each octant $3$ regions according to which coordinate is largest in magnitude. Restrict to the region in the first octant where the $x$-component is largest (the $y$ and $z$ order is left free), which is therefore $\tfrac{1}{24}$ of the sphere: $$\theta \in \left[0, \tfrac{\pi}{4}\right], \qquad \varphi \in \left[\arctan(\sec \theta),\, \tfrac{\pi}{2}\right].$$ In this region, $d = 1/(2 \sin \varphi \cos \theta)$, and the $\sin \varphi$ in the measure cancels the $\sin \varphi$ in the denominator of $d$. Multiplying by $24$ and dividing by $4\pi$: $$\begin{aligned} \mathbb{E}[d] &\;=\; \frac{3}{\pi} \int_0^{\pi/4} \frac{\tfrac{\pi}{2} - \arctan(\sec \theta)}{\cos \theta} \, d\theta\\ &\;=\; \frac{3}{\pi} \int_0^{\pi/4} \frac{\arctan(\cos \theta)}{\cos \theta} \, d\theta, \end{aligned}$$ using $\arctan x + \arctan(1/x) = \pi/2$ for $x > 0$.

The integral does not collapse to elementary constants. Numerically, $$\int_0^{\pi/4} \frac{\arctan(\cos \theta)}{\cos \theta} \, d\theta \;\approx\; 0.63951,$$ giving $$\mathbb{E}[d] \;\approx\; \boxed{0.6106}.$$

Distance to each face

From the centre $(1/2, 1/2, 1/2)$, the distance to each face in direction $(\sin \varphi \cos \theta, \sin \varphi \sin \theta, \cos \varphi)$ is:

• right ($x = 1$): $t = 1 / (2 \sin \varphi \cos \theta)$ if $\sin \varphi \cos \theta > 0$

• left ($x = 0$): $t = 1 / (2 |\sin \varphi \cos \theta|)$ if $\sin \varphi \cos \theta < 0$

• front ($y = 1$): $t = 1 / (2 \sin \varphi \sin \theta)$ if $\sin \varphi \sin \theta > 0$

• back ($y = 0$): $t = 1 / (2 |\sin \varphi \sin \theta|)$ if $\sin \varphi \sin \theta < 0$

• top ($z = 1$): $t = 1 / (2 \cos \varphi)$ if $\cos \varphi > 0$

• bottom ($z = 0$): $t = 1 / (2 |\cos \varphi|)$ if $\cos \varphi < 0$

The actual distance travelled is the minimum of these six values.

Monte Carlo verification

import numpy as np

def simulate_random_walk_3d(num_simulations=1_000_000):
    """Simulate random walks from the centre of the unit cube."""
    x0, y0, z0 = 0.5, 0.5, 0.5

    theta = np.random.uniform(0, 2 * np.pi, num_simulations)
    u     = np.random.uniform(-1, 1, num_simulations)   # cos(phi), uniform
    s     = np.sqrt(1 - u * u)                          # sin(phi)
    dx, dy, dz = s * np.cos(theta), s * np.sin(theta), u

    t_right  = np.where(dx > 0, (1 - x0) / dx, np.inf)
    t_left   = np.where(dx < 0,  -x0 / dx,     np.inf)
    t_front  = np.where(dy > 0, (1 - y0) / dy, np.inf)
    t_back   = np.where(dy < 0,  -y0 / dy,     np.inf)
    t_top    = np.where(dz > 0, (1 - z0) / dz, np.inf)
    t_bottom = np.where(dz < 0,  -z0 / dz,     np.inf)

    return np.minimum.reduce([t_right, t_left, t_front,
                              t_back,  t_top,  t_bottom])

np.random.seed(42)
d = simulate_random_walk_3d(10**6)
print(f"simulated: {d.mean():.6f}")
# simulated: 0.610596

Convergence

Running Monte Carlo for varying sample sizes:

Comparison of the two answers

The expected distance grows only modestly (by about $9\%$) from $2$D to $3$D. Although an extra dimension opens longer “body-diagonal” directions (up to $\sqrt 3 / 2 \approx 0.866$), the cube’s six faces cut most rays off quickly, so the uniform-direction average is only a little above the inradius $0.5$.