Taxicab metric *with stoplights*; does it ever give the Euclidean metric?

Solution 1:

Very interesting question. This is not an answer to your question; just a look into the "stoplight metric" you described.

How should the stoplight metric be defined?

I'll use $d$ to refer to the stoplight metric, and $d_1$ to refer to the standard taxicab metric.

Now let's consider two lattice points $x, y \in \mathbb{Z}^2$. If $x = y$ then of course we must set $d(x,y) = 0$.

Otherwise, there are either one or two lattice points $n \in \mathbb{Z}^2$ such that

1. $x$ and $n$ are adjacent
2. $d_1(n,y) < d_1(x,y)$

We can think of these as "useful neighbors" of $x$ (relative to $y$) – travelling to a useful neighbor gets you closer to $y$, and travelling to a non-useful neighbor gets you farther away from $y$, so we will define $d$ recursively by travelling only to useful neighbors. In the figure below, $x_1$ has only one useful neighbor relative to $y$, while $x_2$ has two useful neighbors relative to $y$.

Let's call the time it takes to travel between adjacent lattice points (with no interference) $\ell$, and the probability that a given direction is blocked $p$. WLOG the time it takes for a light to change/update is $1$.

Then the expected time to go from one lattice point to an adjacent lattice point is $$T := \sum_{n = 0}^\infty p^n(1-p)(n+\ell) = \frac{p+(1-p)\ell}{1-p}.$$

If $x$ has exactly one useful neighbor $x'$ relative to $y$, then the expected time to travel from $x$ to $y$ via useful neighbors must be $$d(x,y) = T + d(x',y).$$

Otherwise, if $x$ has exactly two useful neighbors $x',x''$ relative to $y$, then as soon as we can travel to at least one useful neighbor, we should travel to whichever available neighbor minimizes our expected remaining time to $y$.

Side Note: This strategy might not always be optimal. In some situations (depending on $p$ and $\ell$) it's best to be willing to wait longer for the "better neighbor". This seems to be the case when $\ell < 1$, as reflected in the plots below.

This gives an expected time of \begin{multline*} d(x,y) = \sum_{n=0}^\infty p^{2n}\left((1-p)^2(n+\ell+\min(d(x',y),d(x'',y))) + p(1-p)(n+\ell+d(x',y)) + p(1-p)(n+\ell+d(x'',y))\right)\\ = \frac{(1-p)^2\min(d(x',y),d(x'',y))+p(1-p)(d(x',y) + d(x'',y)) + (1-p^2)\ell + p^2}{1-p^2} \end{multline*}

It's horrible to look at, but this gives a complete recursive definition of $d$. I implemented this definition in Mathematica to produce the following visualizations of the balls of radius $50T$ for various values of $\ell$ and $p$:

Indeed, $p=1/2, \ell=1$ gives an octagon!

Solution 2:

Here are the scattered notes of a somewhat negative answer, from a probabilistic/combinatorial perspective.

Consider the lattice graph on $\mathbb Z^2$. For any edge $(x,x')$ of adjacent points $x$, $x' \in \mathbb Z^2$, there can be an associated "wait time" $\mathbf{W}(x,x')$, a random variable taking values in $[1,\infty)$ which we interpret as the amount of time to travel along the road from $x$ to $x'$ (enforced by stoplights and the like). We can assume that all the $\mathbf{W}(x,x')$ are independent and identically distributed to some common distribution $\mathbf W$.

Then, given arbitrary points $x$, $y\in \mathbb Z^2$, how to define the distance between them?

A lattice path from $x$ to $y$ is a sequence of points $p = (p_i)_{i=0}^\ell$ such that $p_0 = x$, $p_\ell = y$, and $(p_i, p_{i+1})$ is an edge for every $i < \ell$. The length of the path is the number of edges it spans, which is precisely $\ell$.

Let $|\cdot|_1$ denote the taxicab norm on $\mathbb Z^2$. As noted in the other answer, a realistic 'driver' going from $x$ to $y$ would only want to travel along the paths $p$ for which $|p_{i+1} - y|_1 \leq |p_i - y|_1$ for every $i < \ell$. These are precisely the paths of length $\ell = |x-y|_1$, which is the minimal length of any path from $x$ to $y$. Let $\mathcal P(x,y)$ denote the collection of all such paths. Each path $p \in \mathcal P(x,y)$ is constrained to the bounding rectangle of $x$ and $y$, of dimension $m \times n$ for some $m$, $n \in \mathbb N$. Observe that $m + n = |x - y|_1 = \ell$.

For a given path $p$ of length $\ell$, we can define the wait time of travel along $p$ by summing the wait times of the edges which $p$ spans; denote this by

$$\mathbf{W}(p) = \sum_{i=0}^{\ell-1} \mathbf{W}(p_i,p_{i+1}).$$

Finally, we can define the distance $\mathbf{D}(x,y)$ as the random variable taking values in $[1,\infty)$, given by

$$\mathbf{D}(x,y) = \min_{p\in \mathcal P(x,y)} \mathbf{W}(p).$$

The goal would then be to find the correct distribution $\mathbf{W}$ for which

$$\mathbb E\big(\mathbf{D}(x,y)\big) \sim |x-y|_2 \text{ as } |x-y|_1 \to\infty$$

where $|\cdot|_2$ is the euclidean norm. However, I have doubts as to whether this is possible (at least assuming the setup above, where each edge's wait time is IID and the metric is defined as the minimum wait time over all paths of length $|x-y|_1$).

Notice that $\mathbf{W}(p)$ is a sum of independent, identically distributed random variables. If the mean and variance of $\mathbf{W}$ are finite, then the central limit theroem says that the average $\mathbf{W}(p)/\ell$ tends to a normal distribution as $\ell \to \infty$. Therefore, when $\ell = |x-y|_1$ is large, $\mathbf{W}(p)$ is (approximately) distributed as $|x-y|_1 \cdot \mathbf{N}(\mu,\sigma)$ for some $\mu$, $\sigma$.

Since $\mathbf{D}(x,y)$ is the minimum of $\mathbf{W}(p)$ over all paths $p$ of length $\ell=|x-y|_1$, then $\mathbb{E}\big(\mathbf{D}(x,y)\big)$ is asymptotically $|x-y|_1$ multiplied by the expected value of the minimum of $N = |\mathcal{P}(x,y)|$ independent normal variables, each with some mean $\mu$ and variance $\sigma$. There is a formula for the expected value of the minimum of $N$ normal variables, which yields the final asymptote

$$\mathbb E\big(\mathbf{D}(x,y)\big) \sim |x-y|_1 \cdot\big(\mu - \sigma\sqrt{2\log N}\big)$$

where $N = |\mathcal P(x,y)|$ is the number of paths of length $|x-y|_1$ from $x$ to $y$. Recall, the goal was for this asymptote to be $|x-y|_2$.

It is the appearance of the $N$ which I think really throws things off, as its range is very wide, minimized when $x$ and $y$ are due north-south or east-west of each other, and maximized when $x$ and $y$ are due NE-SW or NW-SE of each other.

Indeed, how many paths of length $\ell = |x-y|_1$ are there from $x$ to $y$? The exact count is

$$|\mathcal{P}(x,y)| = \binom{m+n}{n} = \frac{(m+n)!}{m!n!}$$

where $m$ and $n$ are again the dimensions of the bounding rectangle between $x$ and $y$. So suppose the point $x$ is fixed and let $y$ wander around $x$ in a large circle, at a distance approximately $r = |x-y|_2$. When $y$ is due north of $x$, there is only one path in $\mathcal P(x,y)$. But when $y$ is due northeast, for instance, and $m = n \approx r/\sqrt{2}$, we have

$$|\mathcal P(x,y)| = \operatorname{CBC}(r/\sqrt{2}) \sim \frac{a}{\sqrt{r}} \cdot b^r$$

for constants $a > 0$ and $b> 2$, where $\operatorname{CBC}(n) = \binom{2n}{n}$ is the central binomial coefficient.

So, suppose one wants to force

$$|x-y|_1 \cdot \big(\mu - \sigma\sqrt{2\log |\mathcal P(x,y)|}\big) \sim |x-y|_2$$

as $|x-y|_1 \to \infty$. Let $m+n = |x-y|_1$ and $r = |x-y|_2$ and consider the case where $x$ and $y$ are due NE-SW of each other, in which case we have $m = n \approx r/\sqrt{2}$ and $|\mathcal P(x,y)| \sim (a/\sqrt{r})\cdot b^r$ for constants $a$, $b$. Then we have

$$\frac{|x-y|_1 \cdot \big(\mu - \sigma\sqrt{2\log |\mathcal P(x,y)|}\big)}{|x-y|_2}$$

is asymptotic to

$$\frac{(2r/\sqrt{2})\big(\mu - \sigma\sqrt{2\log(ab^r/\sqrt{r})}\big)}{r}$$

which cannot limit to $1$ as $r\to \infty$, as it actually grows roughly like $\sqrt{r}$ (identifying the dominant term $\sqrt{\log(b^r)}$ inside).

Edit: Upon further thought, I think I made a mistake above, as $\mu$ and $\sigma$ should not be constant, but they should be functions of $|x-y|_1$ (?). So there may yet be hope, if one chooses $\mathbf{W}$ so that $\mu$ and $\sigma$ grow at just the right rate for the above ratio to limit to $1$.

Even so, this may only handle the diagonal directions, and the limit may be $\neq 1$ in other directions (like the north/south direction, where the ratio actually simplifies to just $\mu\cdot 2/\sqrt{2}$).