Gilles

This is also a nice one to just simulate, and simulating it is more convincing than any of the above.

Generate ten thousand points, compute nearest neighbours, count components. Repeat a few times. The average settles down quickly and you will see the constant emerge.

Doing that alongside the derivation is worthwhile, because it is easy to make an error in the mutual-pair probability and a simulation catches it immediately.

Worth connecting it to the version most people meet first, because they look unrelated and are the same statement.

The probability version — that a random variable is far from its mean with probability bounded by variance over distance squared — comes from applying exactly this inequality to the squared deviation. The measure is probability, the function is the squared distance from the mean, and its integral is the variance.

So the abstract measure-theoretic statement is the general one, and the familiar probability result is one substitution away.

The same move generates a whole family: apply it to different functions of the variable and you get different tail bounds, including the exponential ones used everywhere in concentration inequalities. All of them are the rectangle argument with a different curve.

The arc length of a parabola has a closed form, and inverting it does not — which is the whole difficulty.

For y = a x², the arc length from the origin to x is an integral of the square root of (1 + 4a²x²). That integral evaluates in terms of a square-root term plus an inverse hyperbolic sine. Writing t = 2ax makes it tidy: the length is proportional to

t·√(t² + 1) + sinh⁻¹(t)

divided by 4a.

So given a and x you get L directly. What you want is the reverse — given L and a new a, solve for t. That equation mixes a polynomial term with an inverse hyperbolic one, and there is no closed-form inverse.

So the honest answer is: the forward direction is exact, the backward direction is numerical.

The practical method, which converges very fast:

1. Compute L once from the original curve using the closed form.
2. For the new coefficient, define k = 4·a_new·L and solve k = t·√(t²+1) + sinh⁻¹(t) for t.
3. Recover the point from x = t / (2·a_new).

For step 2, a good starting guess is t₀ = √k, which comes from noticing that for large t the expression is dominated by the t² term. From there, Newton's method converges in a handful of iterations because the function is smooth and strictly increasing.

Strict monotonicity is worth noting: the right-hand side increases without bound as t increases, so there is exactly one solution and no ambiguity about which root you found. That makes even a crude bisection perfectly reliable if you would rather not differentiate anything.