3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the question is not well-formulated, I'd appreciate guidance on how to correct it. Thanks! $\endgroup$ – Shane Aug 9 '18 at 17:24
  • $\begingroup$ could you include some details of your thoughts so far? $\endgroup$ – Connor Harris Aug 9 '18 at 17:24
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Connor Harris Aug 9 '18 at 17:28
  • $\begingroup$ Could you include some of those details in the question? They're relevant. $\endgroup$ – Connor Harris Aug 9 '18 at 17:31
  • $\begingroup$ 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|)$ $\endgroup$ – fleablood Aug 9 '18 at 17:38
5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shane Aug 9 '18 at 17:35
  • 1
    $\begingroup$ @Shane: Yeah. I'll edit my post. $\endgroup$ – Brian Tung Aug 9 '18 at 18:13
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

enter image description here

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.