Charlotte's New Web

A puzzle by Xavier Durawa for the week of 5/3.

The puzzle

Charlotte is building a web inside a circular frame. She picks a starting point on the boundary uniformly at random, picks a direction pointing into the disk uniformly at random, walks in a straight line, and lays down a strand of silk. When she reaches the boundary she reflects elastically, in exactly the way a billiard ball or a beam of light would, and lays down the next strand. New strands cross many of the earlier ones. On average, how many of the previous strands does the $n$-th strand cross?

That is the whole question. Getting to a clean answer takes about ten small steps, and we will spell out every one of them. The road runs through some elementary geometry of reflection, a change of variables that collapses two random choices into one, a piecewise integration, a symmetry argument with a satisfying twist, and a telescoping sum. The reward at the end is an exact closed form, simple enough to fit on a single line.

We work in the unit disk $\{(x, y) : x^2 + y^2 \leq 1\}$. Charlotte’s starting point is on the boundary circle and her initial direction is some unit vector pointing inward.

Step 1: every chord has the same length

Here is the first surprise. Every strand Charlotte lays down has exactly the same length, no matter where the bounces occur. The reflection law arranges this for free.

To see why, look at the very first bounce. Charlotte travels along a chord from $A$ to $B$, reflects, and continues along $BC$. We claim $|AB| = |BC|$.

Let $O$ be the centre of the disk. Triangle $OAB$ is isosceles, since the two sides $OA$ and $OB$ are radii of equal length. A standard fact about isosceles triangles is that their two base angles (the angles opposite the two equal sides) are equal. So $\angle OAB = \angle OBA.$ Call this common angle $\alpha$.

Now we need one fact from elementary plane geometry: at any point of a circle, the radius is perpendicular to the tangent line. Quick justification: the tangent line at $B$ touches the circle only at $B$, and any other point on the tangent line is outside the circle, i.e. at distance greater than $1$ from $O$. So $B$ is the closest point on the tangent line to $O$. The closest point on a line to a fixed external point is always the foot of the perpendicular dropped from that point, so $OB$ must meet the tangent at $B$ at a right angle.

Back to the bounce. The chord $BA$ leaves $B$ along a direction making angle $\alpha$ with the radius $OB$, so it makes angle $90° - \alpha$ with the tangent. The reflection law says the angle of incidence equals the angle of reflection, both measured against the tangent. So the outgoing chord $BC$ also makes angle $90° - \alpha$ with the tangent, just on the opposite side. That places $BC$ at angle $\alpha$ from the radius $OB$ on the opposite side. So $\angle OBC = \alpha$ as well.

We have arrived at two isosceles triangles with the same shape. Triangle $OAB$ has $OA = OB = 1$ and base angles $\alpha$; its apex angle at $O$ is therefore $180° - 2\alpha$ (since angles in a triangle sum to $180°$). Triangle $OBC$ has $OB = OC = 1$ and base angle $\alpha$ at $B$, hence by isosceles symmetry base angle $\alpha$ at $C$ too, and apex angle at $O$ also $180° - 2\alpha$.

The two triangles each have two unit sides separated by the same included angle, $180° - 2\alpha$. By side-angle-side, they are congruent. In particular the third sides match: $|BC| = |AB|$.

So every chord has the same length. Equivalently (by the law of cosines applied to $OAB$, which gives $|AB|^2 = 2 - 2\cos\angle AOB$), every chord subtends the same central angle. Call this constant central angle $\delta$. The boundary points $P_0,\ P_1,\ P_2,\ P_3,\ \dots$ where successive strands meet the circle therefore form an arithmetic progression of angles: if $P_0$ sits at angle $\theta_0$, then $P_k$ sits at angle $\theta_0 + k\delta$.

Step 2: the rotation $\delta$ is uniform on $(0, 2\pi)$

The puzzle hands us two pieces of randomness: a uniform starting point and a uniform inward direction. We have just seen that the entire web is determined by the single number $\delta$. So the next question is, what is the distribution of $\delta$?

The starting point itself does no work. The whole problem is rotationally symmetric, so we can place $P_0$ at $(1, 0)$ once and forever, and forget about it.

What is left is the random direction. Parametrise inward-pointing unit vectors at $(1, 0)$ by an angle $\vartheta \in (0, \pi)$ measured from the upward tangent. The tangent at $(1, 0)$ points in the $y$-direction, so the unit vector $\mathbf{v}(\vartheta) = (-\sin\vartheta,\ \cos\vartheta)$ points along the upward tangent at $\vartheta = 0$, along the inward normal $(-1, 0)$ at $\vartheta = \pi/2$, and along the downward tangent at $\vartheta = \pi$. The puzzle specifies the direction as uniform, so $\vartheta$ is uniform on $(0, \pi)$. (No Bertrand-style ambiguity here: the random ingredient is the direction at a fixed boundary point, not the chord.)

Charlotte then walks along the line $P(t) = (1, 0) + t\,\mathbf{v}(\vartheta) = (1 - t\sin\vartheta,\ t\cos\vartheta), \qquad t \geq 0.$ She bounces when she meets the boundary again, i.e. when $\|P(t)\|^2 = 1$:

(1 - t\sin\vartheta)^2 + (t\cos\vartheta)^2 &= 1 \\ 1 - 2t\sin\vartheta + t^2(\sin^2\vartheta + \cos^2\vartheta) &= 1 \\ t^2 - 2t\sin\vartheta &= 0 \\ t(t - 2\sin\vartheta) &= 0. \end{aligned}$$ The root $t = 0$ is the starting point. The other root, $t = 2\sin\vartheta$, is the next bounce. Substitute it back: $$P_1 = \bigl(1 - 2\sin^2\vartheta,\ 2\sin\vartheta\cos\vartheta\bigr) = (\cos 2\vartheta,\ \sin 2\vartheta),$$ where the last step uses the double-angle identities $\cos 2\vartheta = 1 - 2\sin^2\vartheta$ and $\sin 2\vartheta = 2\sin\vartheta\cos\vartheta$. So $P_1$ sits on the unit circle at angle $2\vartheta$. The central angle from $P_0$ to $P_1$ is $\delta = 2\vartheta$. Since $\vartheta$ is uniform on $(0, \pi)$, the rotation $\delta = 2\vartheta$ is uniform on $(0, 2\pi)$. Setting $$\beta = \frac{\delta}{2\pi},$$ we have a single random parameter $\beta$, uniform on $(0, 1)$, that determines the entire web. The whole problem is now parametrised by one number on the unit interval. ## Step 3: boundary positions on a circle of length 1 It will pay to forget about angles entirely and measure boundary positions as fractions of the circumference. The boundary becomes the interval $[0, 1)$ with the two endpoints glued together. Place $P_0$ at position $0$. The bounce point $P_k$ is then at position $$k\beta \bmod 1 = \text{the fractional part of } k\beta.$$ A note on the notation: for any real $x$, the symbol $x \bmod 1$ means the unique $y \in [0, 1)$ with $x - y \in \mathbb{Z}$. So $1.7 \bmod 1 = 0.7$, $2.5 \bmod 1 = 0.5$, $-0.3 \bmod 1 = 0.7$. The $k$-th strand (for $k \geq 1$) is the chord whose two boundary endpoints are $(k-1)\beta \bmod 1$ and $k\beta \bmod 1$. That is the picture we will work with from now on: a sequence of points marching around a length-1 circle in steps of $\beta$, with chords joining consecutive points. ## Step 4: when do two chords cross inside the disk? Two chords cross strictly inside the disk if and only if their four endpoints alternate around the boundary. The chord $ab$ separates the open disk into two pieces; a second chord crosses $ab$ iff its two endpoints lie on opposite arcs. Alternation is invariant under rotating the boundary, so we can shift strand $i$ to sit at $\{0, \beta\}$. For strand $j$ with $m = j - i \geq 1$, the endpoints become $$\{u,\ u + \beta \bmod 1\}, \qquad u = m\beta \bmod 1.$$ The chord $\{0, \beta\}$ cuts the boundary into two arcs: $A = (0, \beta)$ of length $\beta$, and $B = (\beta, 1)$ of length $1 - \beta$. Strands $i$ and $j$ cross iff exactly one of $\{u,\, u + \beta \bmod 1\}$ lies in each arc. <figure> <img src="/handout-figs/charlottes_web/cases_both.png" alt="A 2-by-3 grid of circle diagrams. Top row, β = 0.30 (case β < 1/2): three snapshots of the second chord as u sweeps through (0, β), (β, 1-β), (1-β, 1) — labelled cross, no cross, cross. Bottom row, β = 0.70 (case β > 1/2): three snapshots through (0, 1-β), (1-β, β), (β, 1) — labelled cross, no cross, cross. The first chord at endpoints {0, β} is shown in copper, the second chord at {u, u+β mod 1} in green, with intersection points highlighted." /> </figure> **Case $\beta < 1/2$ (top row).** Arc $A$ has length $\beta$ and is the shorter one. Three sub-cases for $u$: - $u \in (0, \beta)$: $u \in A$ and $u + \beta \in (\beta, 2\beta) \subset B$. **Cross.** - $u \in (\beta,\, 1 - \beta)$: $u \in B$ and $u + \beta \in (2\beta, 1) \subset B$. **No cross.** - $u \in (1 - \beta,\, 1)$: $u \in B$ and $u + \beta - 1 \in (0, \beta) = A$. **Cross.** The cross region is $u \in (0, \beta) \cup (1 - \beta, 1)$. **Case $\beta > 1/2$ (bottom row).** Now arc $B$ has length $1 - \beta$ and is the shorter one. Three sub-cases: - $u \in (0,\, 1 - \beta)$: $u \in A$ and $u + \beta \in (\beta, 1) = B$. **Cross.** - $u \in (1 - \beta,\, \beta)$: $u \in A$ and $u + \beta - 1 \in (0, 2\beta - 1) \subset A$. **No cross.** - $u \in (\beta,\, 1)$: $u \in B$ and $u + \beta - 1 \in (2\beta - 1, \beta) \subset A$. **Cross.** The cross region is $u \in (0, 1 - \beta) \cup (\beta, 1)$. **Both cases together.** In each case, the cross region consists of those $u$ whose circle-distance to the nearer of $\{0, 1\}$ is less than the length of the shorter arc. Writing the circle distance as $$d(x) = \min(x,\ 1 - x), \qquad x \in [0, 1),$$ the shorter-arc length is $d(\beta) = \min(\beta, 1 - \beta)$, and the criterion collapses to $$\boxed{\ \text{strands $i$ and $j$ cross}\ \iff\ d(m\beta \bmod 1) < d(\beta), \qquad m = j - i.\ }$$ The condition has nothing to do with $i$ or $j$ separately, only on the gap $m$ between their indices. That is the simplification we need. ## Step 5: the answer is a sum of probabilities For each $m \geq 1$, define $$P_m = \mathbb{P}\bigl(d(m\beta \bmod 1) < d(\beta)\bigr), \qquad \beta \sim \mathrm{Unif}(0, 1).$$ By Step 4, $P_m$ is the probability that any two strands whose indices differ by $m$ cross. Let $N_n$ be the number of previous strands that strand $n$ crosses. For each $k = 1, \dots, n - 1$, strand $n$ versus strand $k$ has $m = n - k$, so by linearity of expectation (which holds without any independence assumptions), $$\mathbb{E}[N_n] = \sum_{k=1}^{n-1} \mathbb{P}\bigl(\text{strand $n$ crosses strand $k$}\bigr) = \sum_{m=1}^{n-1} P_m.$$ The puzzle has reduced to a single problem: compute $P_m$. ## Step 6: a worked example, $P_2$ Let us compute $P_2 = \mathbb{P}(d(2\beta \bmod 1) < d(\beta))$ by hand. The trick is to chop $[0, 1]$ into pieces on which both $d(\beta)$ and $d(2\beta \bmod 1)$ are linear in $\beta$, and read off the answer piece by piece. The function $d(\beta)$ is a tent: it climbs linearly from $0$ at $\beta = 0$ up to $1/2$ at $\beta = 1/2$, then descends to $0$ at $\beta = 1$. Explicitly, $d(\beta) = \beta$ on $[0, 1/2]$, and $d(\beta) = 1 - \beta$ on $[1/2, 1]$. The function $d(2\beta \bmod 1)$ is the same shape, but at twice the frequency: two tents stacked side by side. A direct computation on each quarter-interval gives $$d(2\beta \bmod 1) = \begin{cases} 2\beta & \text{on } [0,\tfrac14], \\ 1 - 2\beta & \text{on } [\tfrac14, \tfrac12], \\ 2\beta - 1 & \text{on } [\tfrac12, \tfrac34], \\ 2 - 2\beta & \text{on } [\tfrac34, 1]. \end{cases}$$ <figure> <img src="/handout-figs/charlottes_web/p2_integration.png" alt="A plot on β ∈ [0, 1] showing two functions: the green tent d(β) = min(β, 1-β) climbing to 1/2 at β = 1/2 then descending, and the orange double-tent d(2β mod 1) with peaks at β = 1/4 and 3/4. Two shaded regions sit between β = 1/3 and 1/2, and between β = 1/2 and 2/3, where the orange function lies below the green. Total shaded length 1/3." /> </figure> The probability we want is the total length of the $\beta$-interval on which the orange tents (the high-frequency function) are below the green tent (the low-frequency one). Reading off each piece: $$\begin{aligned} \beta \in [0,\tfrac14]:\quad & 2\beta < \beta \iff \beta < 0.\quad \text{Empty.} \\ \beta \in [\tfrac14, \tfrac12]:\quad & 1 - 2\beta < \beta \iff \beta > \tfrac13.\quad \text{Length } \tfrac12 - \tfrac13 = \tfrac16. \\ \beta \in [\tfrac12, \tfrac34]:\quad & 2\beta - 1 < 1 - \beta \iff \beta < \tfrac23.\quad \text{Length } \tfrac23 - \tfrac12 = \tfrac16. \\ \beta \in [\tfrac34, 1]:\quad & 2 - 2\beta < 1 - \beta \iff \beta > 1.\quad \text{Empty.} \end{aligned}$$ Adding the four contributions, $P_2 = 0 + \tfrac16 + \tfrac16 + 0 = \tfrac13$. The same recipe works for general $m$: the function $d(m\beta \bmod 1)$ has $2m$ linear pieces, and on each piece the comparison with $d(\beta)$ is a single linear inequality whose solution set is an interval (or empty). Machine arithmetic with exact rationals can carry the calculation out to whatever $m$ we want. ## Step 7: a table for $P_m$ and a closed form Carrying out exactly that integration for $m = 1, 2, \dots, 12$ in exact rational arithmetic (the code is at the end of this article) gives $$P_1 = 0,\ P_2 = \tfrac{1}{3},\ P_3 = \tfrac{1}{2},\ P_4 = \tfrac{7}{15},\ P_5 = \tfrac{1}{2},\ P_6 = \tfrac{17}{35},\ P_7 = \tfrac{1}{2},\ P_8 = \tfrac{31}{63},\ P_9 = \tfrac{1}{2},\dots$$ Two patterns leap off the page. Every odd $m \geq 3$ gives $P_m = 1/2$ exactly. The even values $P_{2k}$ fit the formula $$P_{2k} = \frac{2k^2 - 1}{4k^2 - 1}.$$ Quick check: $P_2 = (2-1)/(4-1) = 1/3$ at $k = 1$; $P_4 = (8-1)/(16-1) = 7/15$ at $k = 2$; $P_6 = (18-1)/(36-1) = 17/35$ at $k = 3$. The pattern matches. Both patterns deserve a proof. The first has a slick one. The second needs more work. ### Why $P_m = 1/2$ for every odd $m \geq 3$ Here is the nice symmetry. The integral defining $P_m$ is invariant under the substitution $\beta \mapsto \beta'$, where $$\beta' := (\beta + \tfrac12) \bmod 1$$ is the antipode of $\beta$ on our length-1 circle. This substitution is a measure-preserving bijection of $[0, 1)$ to itself, so any probability over a uniform $\beta$ is the same as the corresponding probability over a uniform $\beta'$. What does the substitution do to our two circle distances? _First_, $d(\beta')$. Shifting by $1/2$ moves a point to its antipode. The antipode of a point at circle-distance $d(\beta)$ from $0$ sits at circle-distance $\tfrac12 - d(\beta)$ from $0$. (Check: if $\beta = 0.1$, then $\beta' = 0.6$, and $d(\beta') = 1 - 0.6 = 0.4 = 0.5 - 0.1 = 0.5 - d(\beta)$. If $\beta = 0.7$, then $\beta' = 0.2$, and $d(\beta') = 0.2 = 0.5 - 0.3 = 0.5 - d(\beta)$.) So $$d(\beta') = \tfrac12 - d(\beta).$$ _Second_, $d(m\beta' \bmod 1)$. Compute: $$m\beta' = m\beta + \tfrac{m}{2} = m\beta + \tfrac{m-1}{2} + \tfrac12.$$ For odd $m$, the term $(m-1)/2$ is an integer. Reducing modulo 1 kills the integer: $$m\beta' \bmod 1 = (m\beta + \tfrac12) \bmod 1.$$ So $m\beta' \bmod 1$ is the antipode of $m\beta \bmod 1$, and by the same antipode rule, $$d(m\beta' \bmod 1) = \tfrac12 - d(m\beta \bmod 1).$$ Now substitute everything into the inequality $d(m\beta \bmod 1) < d(\beta)$. After substitution it becomes $$\tfrac12 - d(m\beta \bmod 1) < \tfrac12 - d(\beta),$$ which simplifies to $$d(m\beta \bmod 1) > d(\beta).$$ The substitution flipped the direction of the inequality. So $$P_m = \mathbb{P}(d(m\beta \bmod 1) < d(\beta)) = \mathbb{P}(d(m\beta \bmod 1) > d(\beta)).$$ The equality case $d(m\beta \bmod 1) = d(\beta)$ has zero probability (it occurs on a finite set of $\beta$-values, which has Lebesgue measure zero), so the two complementary events have probabilities summing to 1. Each must be $1/2$. ### Why $P_{2k} = \tfrac{2k^2 - 1}{4k^2 - 1}$ The slick substitution above fails for even $m$, because the term $(m-1)/2$ is no longer an integer and so does not vanish modulo 1. We have to roll up our sleeves and integrate. The same piecewise-linear approach we used by hand for $m = 2$ goes through for general $m = 2k$; it is just longer. **Halve the interval by symmetry.** The substitution $\beta \mapsto 1 - \beta$ is a measure-preserving bijection of $[0, 1)$ to itself. It sends $\beta$ to its mirror image about $1/2$. Under it, $d(\beta) = \min(\beta, 1-\beta)$ is unchanged (since $\min(1-\beta, \beta) = \min(\beta, 1-\beta)$), and similarly $d(2k\beta \bmod 1)$ is unchanged (since $d$ is symmetric: $d(1-x) = d(x)$, and $2k(1-\beta) \bmod 1 = (-2k\beta) \bmod 1$). So the integral over $[0, 1]$ is twice the integral over $[0, 1/2]$. We compute the latter and double. **The structure of $d(2k\beta \bmod 1)$ on $[0, 1/2]$.** On $[0, 1/2]$, $d(\beta) = \beta$, the simpler of the two functions. The function $h(\beta) := d(2k\beta \bmod 1)$ has period $1/(2k)$ in $\beta$ (because adding $1/(2k)$ to $\beta$ shifts $2k\beta$ by 1, which is killed by $\bmod 1$). The interval $[0, 1/2]$ contains exactly $k$ full periods, indexed by $p = 0, 1, \dots, k - 1$. The $p$-th period is the interval $\bigl[\tfrac{p}{2k},\, \tfrac{p+1}{2k}\bigr]$, on which $h$ traces out a tent of height $1/2$. Within this period, the tent's left half is the interval $\bigl[\tfrac{p}{2k},\, \tfrac{2p+1}{4k}\bigr]$, where $h$ rises linearly from $0$ to $1/2$ with slope $2k$: $$h(\beta) = 2k\beta - p \quad \text{on the left half of the $p$-th period.}$$ The right half is $\bigl[\tfrac{2p+1}{4k},\, \tfrac{p+1}{2k}\bigr]$, where $h$ falls from $1/2$ to $0$ with slope $-2k$: $$h(\beta) = (p + 1) - 2k\beta \quad \text{on the right half of the $p$-th period.}$$ <figure> <img src="/handout-figs/charlottes_web/tent_period.png" alt="One period of the tent h(β) = ||2kβ|| over the interval [p/(2k), (p+1)/(2k)], peaking at 1/2 at the midpoint (2p+1)/(4k). The diagonal line y = β is overlaid. Two shaded regions where the tent dips below the diagonal: a left-cross sub-interval [p/(2k), p/(2k-1)] and a right-cross sub-interval [(p+1)/(2k+1), (p+1)/(2k)]." /> </figure> The diagonal $y = \beta$ has slope $1$, while the tent has slope $\pm 2k$. The tent crosses $y = \beta$ once on each half, so the cross region inside the period is two short intervals at the ends. **Integrating piece by piece.** We want, on each period, the set of $\beta$ where $h(\beta) < \beta$. _Left half of period $p$._ Solve $2k\beta - p < \beta$: $$(2k - 1)\beta < p, \quad\text{i.e.,}\quad \beta < \frac{p}{2k - 1}.$$ For $p = 0$ this gives $\beta < 0$, empty. For $p \geq 1$ we intersect with the left-half interval $\bigl[\tfrac{p}{2k},\, \tfrac{2p+1}{4k}\bigr]$. Note $\tfrac{p}{2k} < \tfrac{p}{2k-1}$ (denominators), so the lower bound is $p/(2k)$; and one can check $\tfrac{p}{2k-1} \leq \tfrac{2p+1}{4k}$ holds for $p \leq k - 1$ (cross-multiplying gives $4kp \leq (2p+1)(2k-1) = 4kp + 2k - 2p - 1$, equivalent to $2k - 2p - 1 \geq 0$, which is true for $p \leq k - 1$). So the upper bound is $p/(2k-1)$, and the contribution from the left half of period $p$ is $$\frac{p}{2k - 1} - \frac{p}{2k} = \frac{p \cdot \bigl(2k - (2k-1)\bigr)}{(2k - 1)(2k)} = \frac{p}{(2k - 1)(2k)}.$$ _Right half of period $p$._ Solve $(p + 1) - 2k\beta < \beta$: $$(2k + 1)\beta > p + 1, \quad\text{i.e.,}\quad \beta > \frac{p + 1}{2k + 1}.$$ Intersect with the right-half interval $\bigl[\tfrac{2p+1}{4k},\, \tfrac{p+1}{2k}\bigr]$. By a similar denominator check, $\tfrac{2p+1}{4k} < \tfrac{p+1}{2k+1}$ (cross-multiply: $(2p+1)(2k+1) = 4kp + 2k + 2p + 1$ vs. $4k(p+1) = 4kp + 4k$, difference $4k - 2k - 2p - 1 = 2k - 2p - 1 \geq 0$ for $p \leq k - 1$); and $\tfrac{p+1}{2k} \leq \tfrac12$ for $p \leq k - 1$ (with equality at $p = k - 1$, where the right end of the period is exactly $1/2$). So the contribution from the right half of period $p$ is $$\frac{p + 1}{2k} - \frac{p + 1}{2k + 1} = \frac{(p + 1)\cdot\bigl((2k+1) - 2k\bigr)}{(2k)(2k + 1)} = \frac{p + 1}{(2k)(2k + 1)}.$$ **Sum the periods.** Adding both halves over $p = 0, 1, \dots, k - 1$: $$\begin{aligned} \text{measure on } [0, \tfrac12] &= \sum_{p=0}^{k-1} \frac{p}{(2k - 1)(2k)} + \sum_{p=0}^{k-1} \frac{p + 1}{(2k)(2k + 1)} \\ &= \frac{1}{(2k - 1)(2k)} \sum_{p=0}^{k-1} p + \frac{1}{(2k)(2k + 1)} \sum_{p=0}^{k-1} (p + 1) \\ &= \frac{1}{(2k - 1)(2k)} \cdot \frac{(k - 1)k}{2} + \frac{1}{(2k)(2k + 1)} \cdot \frac{k(k + 1)}{2} \\ &= \frac{k - 1}{4(2k - 1)} + \frac{k + 1}{4(2k + 1)}. \end{aligned}$$ We used $\sum_{p=0}^{k-1} p = (k - 1)k/2$ and $\sum_{p=0}^{k-1} (p + 1) = \sum_{q=1}^{k} q = k(k + 1)/2$. Doubling, by the symmetry we opened with, $$P_{2k} = \frac{k - 1}{2(2k - 1)} + \frac{k + 1}{2(2k + 1)}.$$ Putting it on a common denominator $2(2k-1)(2k+1) = 2(4k^2 - 1)$, the numerator becomes $$(k - 1)(2k + 1) + (k + 1)(2k - 1).$$ Expand each piece: $(k-1)(2k+1) = 2k^2 + k - 2k - 1 = 2k^2 - k - 1$, and $(k+1)(2k-1) = 2k^2 - k + 2k - 1 = 2k^2 + k - 1$. Adding, $(2k^2 - k - 1) + (2k^2 + k - 1) = 4k^2 - 2$. So $$P_{2k} = \frac{4k^2 - 2}{2(4k^2 - 1)} = \frac{2k^2 - 1}{4k^2 - 1}.$$ _Sanity check._ At $k = 1$, $1/3$, matching $P_2$. At $k = 2$, $7/15$, matching $P_4$. At $k = 3$, $17/35$, matching $P_6$. ## Step 8: summing the $P_m$'s We now want to compute $\mathbb{E}[N_n] = \sum_{m=1}^{n-1} P_m$. Split the sum by the parity of $m$. Among the values $m = 1, 2, \dots, n-1$: - $m = 1$ contributes $0$. - The odd values $m = 3, 5, \dots$ each contribute $1/2$. There are $\lfloor n/2 \rfloor - 1$ of them (the odd numbers strictly between 1 and $n$). - The even values $m = 2, 4, \dots, 2K$ each contribute $P_{2k} = (2k^2 - 1)/(4k^2 - 1)$. Here $K = \lfloor (n-1)/2 \rfloor$, the number of even values among $\{1, 2, \dots, n-1\}$. So $$\mathbb{E}[N_n] = 0 + \bigl(\lfloor n/2 \rfloor - 1\bigr) \cdot \tfrac12 + \sum_{k=1}^{K} \frac{2k^2 - 1}{4k^2 - 1}.$$ The even-$m$ summand has a tidy rewrite: $$\frac{2k^2 - 1}{4k^2 - 1} = \frac{1}{2} - \frac{1}{2(4k^2 - 1)}.$$ Check: $\tfrac12 - \tfrac{1}{2(4k^2-1)} = \tfrac{(4k^2-1) - 1}{2(4k^2-1)} = \tfrac{4k^2 - 2}{2(4k^2-1)} = \tfrac{2k^2 - 1}{4k^2 - 1}$. ✓ Substituting, $$\mathbb{E}[N_n] = \bigl(\lfloor n/2 \rfloor - 1\bigr) \cdot \tfrac12 + \frac{K}{2} - \frac{1}{2} \sum_{k=1}^{K} \frac{1}{4k^2 - 1}.$$ The first two terms are just half the count of all $m$'s that contribute $1/2$ each. The total count of contributors of either parity is $n - 2$ (we have $n - 1$ values of $m$, of which one, namely $m = 1$, contributes $0$). So $$\bigl(\lfloor n/2 \rfloor - 1\bigr) + K = n - 2,$$ which means $$\bigl(\lfloor n/2 \rfloor - 1\bigr) \cdot \tfrac12 + \tfrac{K}{2} = \tfrac{n - 2}{2}.$$ A small sanity check at $n = 5$: odd $m \in \{3\}$ has count 1; even $m \in \{2, 4\}$ has count $K = 2$; total $1 + 2 = 3 = n - 2$. ✓ So $$\mathbb{E}[N_n] = \frac{n - 2}{2} - \frac{1}{2} \sum_{k=1}^{K} \frac{1}{4k^2 - 1}, \qquad K = \lfloor (n - 1)/2 \rfloor.$$ The only mystery left is the small tail sum. ## Step 9: telescope the sum The denominator factors: $$4k^2 - 1 = (2k - 1)(2k + 1).$$ Partial fractions then give $$\frac{1}{(2k-1)(2k+1)} = \frac{1}{2}\left(\frac{1}{2k-1} - \frac{1}{2k+1}\right).$$ _Quick check._ The right side equals $\tfrac12 \cdot \tfrac{(2k+1) - (2k-1)}{(2k-1)(2k+1)} = \tfrac12 \cdot \tfrac{2}{(2k-1)(2k+1)} = \tfrac{1}{(2k-1)(2k+1)}$. ✓ The point of partial fractions here is that the sum now telescopes: each negative term in one summand cancels the positive term in the next. Writing the first few out: $$\begin{aligned} \sum_{k=1}^{K} \frac{1}{4k^2 - 1} &= \frac{1}{2} \sum_{k=1}^{K} \left(\frac{1}{2k-1} - \frac{1}{2k+1}\right) \\ &= \frac{1}{2}\left[\left(\frac{1}{1} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{5}\right) + \left(\frac{1}{5} - \frac{1}{7}\right) + \cdots + \left(\frac{1}{2K-1} - \frac{1}{2K+1}\right)\right] \\ &= \frac{1}{2}\left(1 - \frac{1}{2K + 1}\right) \\ &= \frac{1}{2} - \frac{1}{2(2K + 1)}. \end{aligned}$$ The middle line is where the work happens: $-1/3$ from the first parenthesis kills the $+1/3$ from the second, $-1/5$ kills $+1/5$, and so on down the line. Only the very first $+1$ and the very last $-1/(2K+1)$ survive. Substituting back into Step 8, $$\mathbb{E}[N_n] = \frac{n - 2}{2} - \frac{1}{2}\left(\frac{1}{2} - \frac{1}{2(2K+1)}\right) = \frac{n - 2}{2} - \frac{1}{4} + \frac{1}{4(2K + 1)} = \frac{2n - 5}{4} + \frac{1}{4(2K + 1)}.$$ ## Step 10: the exact closed form The final job is to simplify $2K + 1$ in terms of $n$. Recall $K = \lfloor (n-1)/2 \rfloor$: - If $n$ is odd, $n - 1$ is even, $K = (n-1)/2$, so $2K + 1 = n$. - If $n$ is even, $n - 1$ is odd, $K = (n-2)/2$, so $2K + 1 = n - 1$. Define $n_\ast = n$ for $n$ odd, and $n_\ast = n - 1$ for $n$ even. We have proved $$\boxed{\ \mathbb{E}[N_n] = \frac{2n - 5}{4} + \frac{1}{4 n_\ast}.\ }$$ That is the answer. Two things are worth noticing. _First_, as $n \to \infty$ the residual $1/(4 n_\ast)$ vanishes and $\mathbb{E}[N_n] \to (2n - 5)/4 = \tfrac{n}{2} - \tfrac{5}{4}$. A plausible-looking guess might be that the $n$-th strand crosses "half of the previous ones," i.e. $(n-1)/2 = \tfrac{n}{2} - \tfrac12$. The true answer undershoots that guess by exactly $\tfrac34$ in the limit. The discrepancy comes from the fact that consecutive strands ($m = 1$) share a boundary endpoint and so never cross at all, which systematically depresses the count. _Second_, the residual $1/(4 n_\ast)$ decays like $1/(4n)$ but does so in pairs of equal height: $n = 3$ and $n = 4$ both give residual $1/12$; $n = 5$ and $n = 6$ both give $1/20$; and so on. Going from an odd $n$ to the next $n + 1$ does not move $n_\ast$ at all, so the residual stays put. ## Small-$n$ table | $n$ | $\mathbb{E}[N_n]$ exact | decimal | $(2n-5)/4$ | |-----|-------------------------|---------|------------| | 3 | $1/3$ | 0.3333 | 0.2500 | | 4 | $5/6$ | 0.8333 | 0.7500 | | 5 | $13/10$ | 1.3000 | 1.2500 | | 10 | $34/9$ | 3.7778 | 3.7500 | | 20 | $333/38$ | 8.7632 | 8.7500 | | 30 | $399/29$ | 13.7586 | 13.7500 | | 50 | $1164/49$ | 23.7551 | 23.7500 | | 100 | $9653/198$ | 48.7525 | 48.7500 | ## Monte Carlo verification <figure> <img src="/handout-figs/charlottes_web/convergence.png" alt="A plot of E[N_n] versus strand index n, with the (n-1)/2 heuristic line, the (2n-5)/4 asymptote, the exact closed-form curve, and 80,000-trial Monte Carlo dots overlaid. The dots sit on the closed-form line out to n = 100. An inset shows the exact residual 1/(4 n_*) decaying as 1/(4n) in pairs of equal height." /> </figure> Each dot is the average of 80,000 random $\beta$ draws. For each draw we build the boundary positions $\{0, \beta, 2\beta, \dots, 100\beta\} \bmod 1$ and, for each strand $n$, count by direct geometry how many of the previous $n - 1$ strands it crosses. The dots sit on the closed-form curve all the way out to $n = 100$. The inset shows the exact residual $\mathbb{E}[N_n] - (2n - 5)/4 = 1/(4 n_\ast)$, which is already about 0.0025 at $n = 100$ and decays as $1/(4n)$ in pairs of equal height. ## Python code ```python import numpy as np from fractions import Fraction def positions(n, beta): """Boundary positions of P_0, P_1, ..., P_n in [0, 1).""" return (np.arange(n + 1) * beta) % 1.0 def to_xy(pos): """Map a position in [0, 1) to its (x, y) on the unit circle.""" a = 2 * np.pi * pos return np.column_stack([np.cos(a), np.sin(a)]) def segments_cross(p1, p2, p3, p4, eps=1e-12): """Open segments p1-p2 and p3-p4 cross strictly inside the disk?""" d1, d2 = p2 - p1, p4 - p3 denom = d1[0]*d2[1] - d1[1]*d2[0] if abs(denom) < eps: return False diff = p3 - p1 t = (diff[0]*d2[1] - diff[1]*d2[0]) / denom s = (diff[0]*d1[1] - diff[1]*d1[0]) / denom return eps < t < 1-eps and eps < s < 1-eps def E_Nn_montecarlo(n_max=100, n_trials=80_000, seed=0): """Estimate E[N_n] for n = 2..n_max by Monte Carlo.""" rng = np.random.default_rng(seed) counts = np.zeros(n_max + 1) for _ in range(n_trials): beta = rng.uniform(0, 1) pts = to_xy(positions(n_max, beta)) for n in range(2, n_max + 1): a, b = pts[n-1], pts[n] counts[n] += sum( segments_cross(a, b, pts[k-1], pts[k]) for k in range(1, n) ) return counts / n_trials def exact_E_Nn(n): """Closed form: (2n-5)/4 + 1/(4 n_*) where n_* = n if n is odd, else n - 1.""" n_star = n if n % 2 == 1 else n - 1 return Fraction(2*n - 5, 4) + Fraction(1, 4 * n_star) ```