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

Question

This question is not terribly formal in nature, but please bear with me: what I’m looking for is a model of traveling via taxi on a grid of streets where the “metric” in some sense becomes the standard Euclidean metric in a limit, for non-trivial reasons. I’ll elaborate below:

Recall the taxicab metric in the plane, where $d(x, y) = |x_1 - x_2| + |y_2 - y_2|$. I'm interested in looking at restricting this to $\mathbb{Z}^2$, and using that as a basis for a model in which we imagine taxis traveling on actual streets, where we then add complexity to the model (in ways that plausibly model car traffic, though it need not be actually realistic—extreme idealization is okay).

For example, one could imagine that on each lattice point, for each direction there is a $50\%$ chance it is blocked by a red light for $1$ unit of time; perhaps we also let traveling cost $1$ unit of time between lattice points when not stopped by a light. In this model, the expected time to get to two points depends on more than just the taxicab metric; you’d rather be $10$ units north and $10$ units west of your destination than $20$ units north, since in the former case when one of your ways is stopped, you have the choice of making progress in the other direction rather than having to stop and wait. (In fact, even if both ways are open, you want to move in the way that keeps how far you have to move south vs east as “balanced” as possible—I’ve made choices in real life based on this).

As a result of this, the “balls” around where you start are no longer diamond-shaped as in the taxicab metric (of course, we don't really have a metric, but a probabilistic model, where one can think in terms of expected times, and take approximate level sets of this and see the limiting shape: I’m intentionally informal here as I’m open to answers that take this in different directions). In fact, if I recall, I believe this forms an octagon, in some sense!

What I would like is model in the spirit of the above, devised so that the “balls” in some expected sense form a Euclidean circle. That is, for larger $r$, the expected time to move approximately $r$ in any given direction (not just north and south; just look at lattice points near $r$ in some direction) is the same as $r$ goes to infinity.

One reason one might be hopeful such a model exists is because there are examples of things defined on a grid where in the limit, Euclidean symmetry is recovered (see Brownian motion defined as a limit of random walks on a grid as an example of this).

I’m open to various creative things leading to this behavior, such as other cars, weird stoplight systems, etc, though ideally there is some degree of elegance to the model and it doesn’t immediately feel cooked up to give a Euclidean result.

Answer 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!

Answer 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}$).