Return to Answer

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote of $0.71 \sqrt{n}$ leaves a substantial component of the distribution in the left tail, to the left of the asymptote. Depending on whether you are interested in large or small values of $n$, an exercise such as the above will provide a simple way to select your desired $c$, to minimise any left-tail probability.

It is also apparent that using the distribution (or simulated distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths), which is what most of the literature seems to do. For instance, the following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$

... but, for your problem, you really should be looking at the distribution ... not just the first moment.

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote of $0.71 \sqrt{n}$ leaves a substantial component of the distribution in the left tail, to the left of the asymptote. Depending on whether you are interested in large or small values of $n$, an exercise such as the above will provide a simple way to select your desired $c$, to minimise any left-tail probability.

It is also apparent that using the distribution (or simulated distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths), which is what most of the literature seems to do. For instance, the following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$

... but, for your problem, you really should be looking at the distribution ... not just the first moment.

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote leaves a substantial component of the distribution in the left tail. Depending on whether you are interested in large or small values of $n$, an exercise such as the above provides a simple way to select your desired $c$, to minimise any left-tail probability.

Using the distribution (or empirical distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths). For instance, the following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote of $0.71 \sqrt{n}$ leaves a substantial component of the distribution in the left tail, to the left of the asymptote. Depending on whether you are interested in large or small values of $n$, an exercise such as the above will provide a simple way to select your desired $c$, to minimise any left-tail probability.

It is also apparent that using the distribution (or simulated distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths), which is what most of the literature seems to do. For instance, the following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$

... but, for your problem, you really should be looking at the distribution ... not just the first moment.

The question states asymptotic results, namely that as $n$ becomes large, the shortest path $L_n$ through $n$ points satisfies

$$L_n \to \sqrt{n} \beta \quad \text{ where } \quad \beta \approx 0.71~$$

Based on a quick play, what does seem clear is that the stated asymptotic result of $0.71 \sqrt{n}$ does, in fact, do a very poor job for your desired purpose, when $n$ is not large, or indeed even when $n$ is moderately large, such as $n= 50$.

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote leaves a substantial component of the distribution in the left tail ... that is inconsistent with your desired goal of placing some "very small" probability on same.

The following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

• $n = 3$:

• $n = 20$:

• $n = 50$:

• $n = 100$:

Even when $n = 100$, the stated asymptote leaves a substantial component of the distribution in the left tail. Depending on whether you are interested in large or small values of $n$, an exercise such as the above provides a simple way to select your desired $c$, to minimise any left-tail probability.

Using the distribution (or empirical distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths). For instance, the following diagram compares:

• Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

• Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

• The actual expected shortest path [ round dots ]

• The OP's stated asymptote: $.71 \sqrt{n}$