# Average ratio of Manhattan distance to Euclidean distance

Suppose we've picked two points randomly from a uniform distribution over the Euclidean plane and we know that the Euclidean distance between them is $d$. What is the expected value of the Manhattan distance, $m$, between the two points, $E[m|d]$?

For context: I originally thought it was just a simple application of the Pythagorean theorem. But knowing that $a^2+b^2=c^2$ doesn't allow me to recover $a+b$ as a function of $c$, right? That function depends on factors other than the side lengths, and it's not immediately obvious to me as to how to proceed. For further context, I have haversine distances between pairs of points. I'd love a quick and dirty way to convert these to driving distances, for which Manhattan would work fine assuming a grid-like transportation network.

• If the question is not well-formulated, I'd appreciate guidance on how to correct it. Thanks! – Shane Aug 9 '18 at 17:24
• could you include some details of your thoughts so far? – Connor Harris Aug 9 '18 at 17:24
• Regardless, here's a hint: write the two points as $(x, y)$ and $(x + d \cos \theta, y + d \sin \theta)$ where $\theta$ is uniform in $[0, 2\pi)$. – Connor Harris Aug 9 '18 at 17:28
• Could you include some of those details in the question? They're relevant. – Connor Harris Aug 9 '18 at 17:31
• I think the assumption is that the angle between them is supposed to be of normal expected value (is it? how does one select a two points?) so manhatten distance will be the expected value of $d(|\sin \theta + \cos \theta|)$ – fleablood Aug 9 '18 at 17:38

## 3 Answers

Basic approach. Make the assumption that one point is at the origin, and the other point is uniformly distributed on the circle centered at the origin with radius $d$. Equivalently, the argument $\theta$ of that point is uniformly distributed on the interval $[0, 2\pi]$. Note that the Manhattan distance $m$ is $|d\sin\theta| + |d\cos\theta|$, so

$$E(m \mid d) = E(|d\sin\theta|)+E(|d\cos\theta|)$$

Simple integration should take you the rest of the way there—does that suffice, or could you use more direction?

• Neat. Just to be sure, your $E(m)$ is actually $E(m|d=1)$ right? And it takes me to $4/\pi$ as the average ratio. – Shane Aug 9 '18 at 17:35
• @Shane: Yeah. I'll edit my post. – Brian Tung Aug 9 '18 at 18:13

What you are asking is simply the average Manhattan distance of the points on a circle of radius $d$ to the center. By symmetry you can perform the computation in a single quadrant and evaluate the average abscissa and average ordinate, which are equal.

In polar coordinates and for a unit circle,

$$\frac\pi2 E(x)=\int_0^{\pi/2} x\,d\theta=\int_0^{\pi/2} \cos\theta\,d\theta=1.$$

Finally,

$$E(m)=\frac 4\pi d$$ where the factor is larger than one and smaller than the square root of two, as could be expected.

The Manhattan distance between the two points $$A, B$$ will have an intermediate point $$C$$ which has a right angle, as shown in the figure below: Note that we're trying to find $$\mathbb{E}[m|d]=\mathbb{E}[x+y|d]=\mathbb{E}[x|d]+\mathbb{E}[y|d]$$, by linearity of the expectation operator.

Notice that each choice of the angle $$\alpha$$ completely characterizes the solution, since $$x=d*cos(\alpha)$$ and $$y = d*sin(\alpha)$$.

To compute the avg. Manhattan distance we vary $$C$$ over the semi-circle, which corresponds to $$\alpha$$ having a uniform distribution over the interval $$[0,\frac\pi2]$$. Now, $$\mathbb{E}[x|d] = \int_{0}^{\pi/2}d*cos(\alpha)*\frac2\pi d\alpha = \frac2\pi d$$ and, $$\mathbb{E}[y|d] = \int_{0}^{\pi/2}d*sin(\alpha)*\frac2\pi d\alpha = \frac2\pi d$$ Finally,

$$\mathbb{E}[m|d] = \frac4\pi d$$

In words, the Manhattan distance (on average) inflates the actual distance by a factor of $$\frac4\pi$$ which is around $$1.27$$. This is expected, since we know from the triangle inequality that $$x + y \geq d$$.