3

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.

Shane
  • 1,325
  • If the question is not well-formulated, I'd appreciate guidance on how to correct it. Thanks! – Shane Aug 09 '18 at 17:24
  • could you include some details of your thoughts so far? – Connor Harris Aug 09 '18 at 17:24
  • 2
    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 09 '18 at 17:28
  • Could you include some of those details in the question? They're relevant. – Connor Harris Aug 09 '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 09 '18 at 17:38
  • I actually don't know the answer to this but: how are points universely distributed. Are the represented as $(a,b)$ coordinated pairs or as $(d,\theta)$ distance angle pairs? Will it make a difference? – fleablood Aug 09 '18 at 17:41

3 Answers3

5

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?

Brian Tung
  • 34,160
3

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.

1

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 \approx 1.27$. This is expected, since we know from the triangle inequality that $x + y \geq d$.

user3009798
  • 101