Problems · Max Moyle

1. Two random points

Pick two points uniformly at random in the unit square. What is the expected distance between them in the taxicab metric? What about in the ordinary Euclidean metric?

Solution

Write the points as $(X_1, Y_1)$ and $(X_2, Y_2)$ , and let $S = |X_1 - X_2|$ and $T = |Y_1 - Y_2|$ . These are independent, and each is distributed like $|U - V|$ for independent uniform $U, V$ on $[0, 1]$ , which has density $2(1 - s)$ on $[0, 1]$ .

Taxicab. The distance is $S + T$ , so by linearity of expectation its mean is $2\,\mathbb{E}\,S$ , where

\mathbb{E}\,S = \int_0^1 2s(1 - s)\,ds = \frac{1}{3}.

The answer is $\tfrac{2}{3}$ .

Euclidean. The distance is $\sqrt{S^2 + T^2}$ . The integrand is symmetric in $s$ and $t$ , so we can integrate over the half of the square where $t \le s$ and double the result. In polar coordinates that half is $0 \le \theta \le \pi/4$ , $0 \le r \le \sec\theta$ , so

\mathbb{E}\sqrt{S^2 + T^2} = 8\int_0^{\pi/4}\!\!\int_0^{\sec\theta} r^2 (1 - r\cos\theta)(1 - r\sin\theta)\,dr\,d\theta.

The inner integral is $\frac{\sec^3\theta}{12} - \frac{\sin\theta}{20\cos^4\theta}$ . Using $\int_0^{\pi/4} \sec^3\theta\,d\theta = \tfrac{1}{2}\big(\sqrt{2} + \ln(1 + \sqrt{2})\big)$ and $\int_0^{\pi/4} \frac{\sin\theta}{\cos^4\theta}\,d\theta = \tfrac{1}{3}\big(2\sqrt{2} - 1\big)$ , we get

\begin{aligned} \mathbb{E}\sqrt{S^2 + T^2} &= 8\left(\frac{\sqrt{2} + \ln(1 + \sqrt{2})}{24} - \frac{2\sqrt{2} - 1}{60}\right) \\ &= \frac{2 + \sqrt{2} + 5\ln(1 + \sqrt{2})}{15} \approx 0.5214. \end{aligned}

So on a grid you walk about 28% farther on average. That’s close to $4/\pi \approx 1.27$ , the average ratio of taxicab to Euclidean length for a step in a uniformly random direction.

2. Staying below the diagonal

You walk from $(0, 0)$ to $(n, n)$ on a grid by a uniformly random shortest route, so each of the $\binom{2n}{n}$ routes is equally likely. What is the probability that you never step strictly above the line $y = x$ ?

Solution

Call a route bad if it meets the line $y = x + 1$ . Since $y - x$ changes by exactly 1 at each step, these are exactly the routes that go above $y = x$ .

Given a bad route, reflect the portion after its first visit to $y = x + 1$ across that line. The reflection maps $(a, b)$ to $(b - 1, a + 1)$ , so the new route ends at $(n - 1, n + 1)$ instead of $(n, n)$ . Conversely, along any route from $(0, 0)$ to $(n - 1, n + 1)$ , the quantity $y - x$ starts at 0, ends at 2, and changes by 1 at each step, so the route meets $y = x + 1$ ; reflecting the portion after its first meeting gives back a bad route. These two maps are inverses, so bad routes correspond exactly to routes ending at $(n - 1, n + 1)$ , of which there are $\binom{2n}{n-1}$ . Therefore

P(\text{never above}) = \frac{\binom{2n}{n} - \binom{2n}{n-1}}{\binom{2n}{n}} = 1 - \frac{n}{n+1} = \frac{1}{n+1}.

The numerator is the Catalan number $C_n$ .

3. Turning up the shade

Heatwave’s Balanced mode picks the route that minimizes $T + \lambda S$ , where $T$ is the walking time, $S$ is the time spent in the sun, and $\lambda \ge 0$ says how much you mind the sun. Fastest is $\lambda = 0$ , and Coolest is the limit as $\lambda \to \infty$ .

Show that raising $\lambda$ never makes the chosen route sunnier or quicker. This should hold even when several routes tie and any of them might be chosen.
Call a route efficient if no other route is at least as quick and at least as shady, and strictly better in one of the two. Give an example of an efficient route that is never chosen, whatever $\lambda$ is.

Solution

Let $\lambda < \mu$ , and let $P$ and $Q$ be routes chosen for $\lambda$ and $\mu$ , with walking times $T_P, T_Q$ and sun times $S_P, S_Q$ . Since $P$ is optimal for $\lambda$ and $Q$ is optimal for $\mu$ ,
$T_P + \lambda S_P \le T_Q + \lambda S_Q \quad\text{and}\quad T_Q + \mu S_Q \le T_P + \mu S_P.$
Adding these and cancelling gives $(\mu - \lambda)(S_Q - S_P) \le 0$ , so $S_Q \le S_P$ . Substituting into the first inequality gives $T_P - T_Q \le \lambda (S_Q - S_P) \le 0$ , so $T_Q \ge T_P$ .
Suppose there are only three routes. $P$ takes 10 minutes with 8 in the sun, $Q$ takes 12 with 6 in the sun, and $R$ takes 14 with 2 in the sun. Each one is quicker or shadier than each of the others, so all three are efficient. For $Q$ to be chosen, we would need $12 + 6\lambda \le 10 + 8\lambda$ , so $\lambda \ge 1$ , and also $12 + 6\lambda \le 14 + 2\lambda$ , so $\lambda \le \tfrac{1}{2}$ . No $\lambda$ satisfies both.

Geometrically, if each route is plotted as the point $(T, S)$ , a weighted sum can only choose points on the lower-left edge of their convex hull, and $Q$ lies above the segment from $P$ to $R$ .

4. How long until a fall?

Model someone standing still as a random walk. The horizontal position of their center of mass starts at 0, every second it shifts one unit left or right, and they fall when it reaches $\pm k$ , the edge of their base of support.

If each shift is equally likely to go either way, show that the expected time until a fall is $k^2$ seconds.
Now suppose they correct themselves: whenever they’re off center, each shift moves them back toward the center with probability $\tfrac{2}{3}$ . From the center, they still go either way with probability $\tfrac{1}{2}$ . Show that the expected time until a fall is $2^{k+2} - 3k - 4$ seconds.

Solution

The walk is symmetric about 0, so only the distance $d$ from the center matters. Let $t_d$ be the expected time to first reach distance $d + 1$ , starting from distance $d$ . The expected time until a fall is $t_0 + t_1 + \cdots + t_{k-1}$ , and $t_0 = 1$ because the first shift always moves away from the center.

For $d \ge 1$ , let $p$ be the probability of a shift toward the center and $q = 1 - p$ . Condition on the first shift. With probability $q$ it reaches distance $d + 1$ in one second. With probability $p$ it moves to distance $d - 1$ , after which it takes $t_{d-1}$ seconds on average to return to distance $d$ , and then $t_d$ more. So

t_d = 1 + p\,(t_{d-1} + t_d), \qquad \text{or equivalently} \qquad t_d = \frac{1 + p\,t_{d-1}}{q}.

With $p = q = \tfrac{1}{2}$ , the recurrence is $t_d = t_{d-1} + 2$ , so $t_d = 2d + 1$ , and the expected time is $1 + 3 + \cdots + (2k - 1) = k^2$ .
With $p = \tfrac{2}{3}$ and $q = \tfrac{1}{3}$ , it is $t_d = 2t_{d-1} + 3$ . Then $t_d + 3 = 2(t_{d-1} + 3)$ , so $t_d = 2^{d+2} - 3$ , and the expected time is
$\sum_{d=0}^{k-1} \left(2^{d+2} - 3\right) = 2^{k+2} - 3k - 4.$

So a modest correction turns a quadratic expected time into an exponential one: with $k = 10$ , it goes from 100 seconds to 4,062. The same argument shows that for any correction probability $p > \tfrac{1}{2}$ , the expected time grows like $\big(p/(1 - p)\big)^k$ .