∎

# Euclidean traveling salesman problem with location dependent and power
weighted edges

Ghurumuruhan Ganesan

Institute of Mathematical Sciences E-Mail<EMAIL_ADDRESS>HBNI  Chennai

###### Abstract

Consider $n$ nodes $\\{X_{i}\\}_{1\leq i\leq n}$ independently distributed in
the unit square $S,$ each according to a distribution $f$ and let $K_{n}$ be
the complete graph formed by joining each pair of nodes by a straight line
segment. For every edge $e$ in $K_{n}$ we associate a weight $w(e)$ that may
depend on the _individual locations_ of the endvertices of $e$ and is not
necessarily a power of the Euclidean length of $e.$ Denoting $TSP_{n}$ to be
the minimum weight of a spanning cycle of $K_{n}$ corresponding to the
travelling salesman problem (TSP) and assuming an equivalence condition on the
weight function $w(.),$ we prove that $TSP_{n}$ appropriately scaled and
centred converges to zero a.s. and in mean as $n\rightarrow\infty.$ We also
obtain upper and lower bound deviation estimates for $TSP_{n}.$

Key words: Traveling salesman problem, location dependent edge weights,
deviation estimates.

AMS 2000 Subject Classification: Primary: 60J10, 60K35; Secondary: 60C05,
62E10, 90B15, 91D30.

##  1 Introduction

The Traveling Salesman Problem (TSP) is the study of finding the minimum
weight cycle containing all the nodes of a graph where each edge is assigned a
certain weight. Often, the location of the nodes by itself is random and the
edge weights are taken to be the Euclidean distance between the nodes. Thus
the edge weight is a metric and for such models, there is extensive literature
dealing with various properties of the TSP including the variance, deviation
and almost sure convergence. Beardwood et al (1959) use subadditive techniques
to determine a.s. convergence of the TSP length appropriately scaled to a
constant $\beta_{TSP}$ and recently Steinberger (2015) has obtained improved
bounds for $\beta_{TSP}.$ We refer to the books by Gutin and Punnen (2006),
Steele (1997) and Yukich (1998) and papers by Steele (1981), Rhee (1993) and
references therein for various other aspects of TSP like the variance and
complete convergence.

In this paper, we assume that the edge weight function is not necessarily a
metric and in fact might depend on the location of the endvertices of the
edge. This arises for example, in broadcasting problems of wireless ad-hoc
networks where each node is constrained to broadcast any received message at
most once. The cost of transmitting a message from a node might depend on the
geographical conditions surrounding and the node and the goal is therefore to
minimize the total cost incurred in sending packets to all nodes of the
network.

In the rest of this section, we briefly describe the model under consideration
and state our result Theorem 1 regarding the deviation estimates for the TSP
length.

### Model Description

Let $f$ be any distribution on the unit square $S$ satisfying such that

$\epsilon_{1}\leq\inf_{x\in S}f(x)\leq\sup_{x\in S}f(x)\leq\epsilon_{2}$ (1.1)

for some constants $0<\epsilon_{1}\leq\epsilon_{2}<\infty.$ Throughout all
constants are independent of $n.$

Let $\\{X_{i}\\}_{i\geq 1}$ be independently and identically distributed
(i.i.d.) with the distribution $f(.)$ defined on the probability space
$(\Omega,{\cal F},\mathbb{P}).$ For $n\geq 1,$ let
$K_{n}=K(X_{1},\ldots,X_{n})$ be the complete graph whose edges are obtained
by connecting each pair of nodes $X_{i}$ and $X_{j}$ by the straight line
segment $(X_{i},X_{j})$ with $X_{i}$ and $X_{j}$ as endvertices.

A path ${\cal P}=(Y_{1},\ldots,Y_{t})$ is a subgraph of $K_{n}$ with vertex
set $\\{Y_{j}\\}_{1\leq j\leq t}$ and edge set $\\{(Y_{j},Y_{{j+1}})\\}_{1\leq
j\leq t-1}.$ The nodes $Y_{1}$ and $Y_{t}$ are said to be _connected_ by edges
of the path ${\cal P}.$

Let $Y_{1},\ldots,Y_{t}\subset\\{X_{k}\\}_{1\leq k\leq n}$ be $t$ distinct
nodes. The subgraph ${\cal C}=(Y_{1},Y_{2},\ldots,Y_{t},Y_{1})$ with vertex
set $\\{Y_{j}\\}_{1\leq j\leq t}$ and edge set $\\{(Y_{j},Y_{{j+1}})\\}_{1\leq
j\leq t-1}\cup\\{(Y_{t},Y_{1})\\}$ is said to be a _cycle_. If ${\cal C}$
contains all the nodes $\\{X_{i}\\}_{1\leq i\leq n},$ then ${\cal C}$ is said
to be a _spanning cycle_ of $K_{n}.$

In what follows we assign weights to edges of the graph $K_{n}$ and study
minimum weight spanning cycles.

### Travelling Salesman Problem

For points $x,y\in S,$ we let $d(x,y)$ denote the Euclidean distance between
$x$ and $y$ and let $h:S\times S\rightarrow(0,\infty)$ be a deterministic
measurable function satisfying

$c_{1}d(x,y)\leq h(x,y)=h(y,x)\leq c_{2}d(x,y)$ (1.2)

for some positive constants $c_{1},c_{2}.$ For $\alpha>0$ a constant and for
$1\leq i<j\leq n$ we let $h^{\alpha}(X_{i},X_{j})=h^{\alpha}(e)$ denote the
_weight_ of the edge $e=(X_{i},X_{j}),$ with exponent $\alpha.$ We remark here
that unlike the Euclidean distance function $d,$ the edge weight function $h$
is not necessarily a metric. Also throughout, the quantity $\alpha$ appears in
the superscript of any term only as an exponent.

The weight of a cycle ${\cal C}$ in the graph $K_{n}$ is defined to be the sum
of the weights of the edges in ${\cal C};$ i.e.,

$W({\cal C}):=\sum_{e\in{\cal C}}h^{\alpha}(e).$ (1.3)

Let ${\cal C}_{n}$ be a spanning cycle of the graph $K_{n}$ satisfying

$TSP_{n}=W({\cal C}_{n}):=\min_{{\cal C}}W({\cal C}),$ (1.4)

where the minimum is taken over all spanning cycles ${\cal C}.$ We refer to
${\cal C}_{n}$ as the _travelling salesman problem_ (TSP) cycle with
corresponding weight $TSP_{n}.$ If there is more than one choice for ${\cal
C}_{n},$ we choose one according to a deterministic rule.

Let $\epsilon_{1},\epsilon_{2}$ be as in (1.1) and set
$\delta=\delta(\alpha)=\epsilon_{1}$ if the edge weight exponent is
$\alpha\leq 1$ and $\delta=\epsilon_{2}$ if $\alpha>1.$ Recalling that $c_{1}$
and $c_{2}$ are the bounds for the edge weight function $h$ as in (1.2), we
define for $A>0$ the terms
$C_{1}(A)=C_{1}(A,\epsilon_{1},\epsilon_{2},\alpha)$ and
$C_{2}(A)=C_{2}(A,\epsilon_{1},\epsilon_{2},\alpha)$ as

$\displaystyle C_{1}(A)$ $\displaystyle:=$
$\displaystyle\frac{(c_{1}A)^{\alpha}}{A^{2}}(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\text{
and }$ $\displaystyle C_{2}(A)$ $\displaystyle:=$
$\displaystyle(2c_{2}A)^{\alpha}\left(1+\frac{1}{A^{2}}\left(\mathbb{E}\tilde{T}^{\alpha}+\mathbb{E}\hat{T}^{\alpha}\right)\right),$
(1.5)

where $\tilde{T}$ is a geometric random variable with success parameter
$p=1-e^{-\delta A^{2}}\left(1+\delta A^{2}+\frac{\delta^{2}A^{4}}{2}\right);$
i.e., $\mathbb{P}(\tilde{T}=k)=(1-p)^{k-1}p$ for all integers $k\geq 1$ and
$\hat{T}$ is a geometric random variable with success parameter $1-p.$ We have
the following result.

###### Theorem 1

Let $\alpha>0$ be the edge weight exponent. For every $A>0$ and every integer
$k\geq 1$ and all $n\geq
n_{0}(A,k,\epsilon_{1},\epsilon_{2},\alpha,c_{1},c_{2})$ large,

$\mathbb{P}\left(TSP_{n}\geq
C_{1}(A)n^{1-\frac{\alpha}{2}}\left(1-\frac{4\sqrt{A}}{n^{1/4}}\right)\right)\geq
1-e^{-n^{1/3}},$ (1.6) $\mathbb{P}\left(TSP_{n}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{2}{n^{1/16}}\right)\right)\geq
1-\frac{1}{n^{2k}}$ (1.7)

and so

$C_{1}^{k}(A)\left(1-\frac{37k\sqrt{A}}{n^{1/4}}\right)\leq\mathbb{E}\left(\frac{TSP^{k}_{n}}{n^{k\left(1-\frac{\alpha}{2}\right)}}\right)\\\
\leq C^{k}_{2}(A)\left(1+\frac{3k}{n^{1/16}}\right).$

For the lower deviation estimates we determine the probability of favourable
configurations that ensure a large enough number of relatively long edges in
the TSP. To prove the upper deviation estimate, we tile the unit square into
small subsquares and join nodes within these subsquares to form an overall
spanning cycle. We then estimate the length of this cycle via stochastic
domination by homogenous processes (see Section 2).

### Remarks on Theorem 1

From Theorem 1, we see that the weights of the TSP in the location dependent
case, is of the same order $n^{1-\frac{\alpha}{2}}$ as in the location
independent case (see Steele (1988)). Using (1) we get that the normalized TSP
weight $\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}$ in fact satisfies

$c_{1}^{\alpha}\cdot\beta_{low}(\alpha)\leq\liminf_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\frac{\mathbb{E}MST_{n}}{n^{1-\frac{\alpha}{2}}}\leq
c_{2}^{\alpha}\cdot\beta_{up}(\alpha),$ (1.8)

where

$\beta_{low}(\alpha)=\beta_{low}(\alpha,\epsilon_{1},\epsilon_{2}):=\sup_{A>0}\frac{A^{\alpha}}{A^{2}}(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}},$
(1.9)
$\beta_{up}(\alpha)=\beta_{up}(\alpha,\epsilon_{1},\epsilon_{2}):=\inf_{A>0}(2A)^{\alpha}\left(1+\frac{\mathbb{E}{T_{a}}^{\alpha}+\mathbb{E}T_{b}^{\alpha}}{A^{2}}\right),$
(1.10)

and $T_{a}$ is a geometric random variable with success parameter $p$ and
$T_{b}$ is a geometric random variable with success parameter $1-p$ (see
(1.5)).

For the case of homogenous distribution $\epsilon_{1}=\epsilon_{2}=1$ we get

$\beta_{down}(\alpha)=\sup_{A>0}A^{\alpha-2}(1-e^{-A^{2}})e^{-8A^{2}}>0$
(1.11)

and

$\beta_{up}(\alpha)=\inf_{A>0}(2A)^{\alpha}\left(1+\frac{\mathbb{E}T_{a}^{\alpha}+\mathbb{E}T_{b}^{\alpha}}{A^{2}}\right)<\infty,$
(1.12)

where $T_{a}$ is a geometric random variable with success parameter
$p=1-e^{-A^{2}}\left(1+A^{2}+\frac{A^{4}}{2}\right)$ and $T_{b}$ is a
geometric random variable with success parameter $1-p.$ For illustration, we
plot $\beta_{down}(\alpha)$ and $\beta_{up}(\alpha)$ as a function of $\alpha$
in Figures 2 and 1, respectively. As we see from the figures
$\beta_{up}(\alpha)$ increases with $\alpha$ and $\beta_{down}(\alpha)$
decreases with $\alpha.$

Figure 1: Plot of $\beta_{up}(\alpha)$ as a function of $\alpha$ for the
homogenous case $\epsilon_{1}=\epsilon_{2}=1.$ Figure 2: Plot of
$\beta_{down}(\alpha)$ as a function of $\alpha$ for the homogenous case
$\epsilon_{1}=\epsilon_{2}=1.$

As a final remark, we provide a simple upper bound for $\mathbb{E}T^{\alpha}$
for a geometric random variable $T$ with success parameter $p,$ in order to
obtain quick evaluations of $\beta_{up}(\alpha)$ in (1.10). Using
$\mathbb{P}(T\geq k)=(1-p)^{k-1}\leq e^{-p(k-1)}$ we see that relation (7.6)
in Appendix is satisfied and so letting $r$ be the smallest integer greater
than or equal $\alpha$ we have from (7.7) that

$\mathbb{E}T^{\alpha}\leq\mathbb{E}T^{r}\leq\frac{r!}{(1-e^{-p})^{r}}.$

Plugging this estimate into (1.10) provides an upper bound for
$\beta_{up}(\alpha).$

The paper is organized as follows. In Section 2, we prove the deviation
estimates in Theorem 1. In Section 3 we obtain the variance upper bounds for
$TSP_{n}$ and in Section 4, we obtain the variance lower bounds for $TSP_{n}.$
Combining the bounds we get that the variance grows roughly of the order of
$n^{1-\alpha}$ for the case $0<\alpha<1.$ Next in Section 5, we prove the a.s.
convergence for $TSP_{n}$ (Theorem 7), appropriately scaled and centred and
finally in Section 6, we obtain bounds for the scaled TSP weight when the
nodes are uniformly distributed in the unit square (Theorem 9).

##  2 Proof of Theorem 1

To prove the deviation estimates, we use Poissonization and let ${\cal P}$ be
a Poisson process in the unit square $S$ with intensity $nf(.).$ We join each
pair of nodes by a straight line segment and denote the resulting complete
graph as $K^{(P)}_{n}.$ We let $TSP_{n}^{(P)}$ be the TSP of $K^{(P)}_{n}$ by
an analogous definition as in (1.4). We first find deviation estimates for
$TSP_{n}^{(P)}$ and then use dePoissonization to obtain corresponding
estimates for $TSP_{n},$ the TSP for the Binomial process as defined in (1.4).

For a real number $A>0,$ we tile the unit square $S$ into small
$\frac{A(n)}{\sqrt{n}}\times\frac{A(n)}{\sqrt{n}}$ squares $\\{R_{i}\\}_{1\leq
i\leq\frac{n}{A^{2}(n)}}$ where $A(n)\in\left[A,A+\frac{1}{\log{n}}\right]$ is
chosen such that $\frac{\sqrt{n}}{A(n)}$ is an integer. This is possible since

$\frac{\sqrt{n}}{A}-\frac{\sqrt{n}}{A+(\log{n})^{-1}}=\frac{\sqrt{n}}{\log{n}}\cdot\frac{1}{A(A+(\log{n})^{-1})}\geq\frac{\sqrt{n}}{2A^{2}\log{n}}$
(2.1)

for all $n$ large. For notational simplicity, we denote $A(n)$ as $A$
henceforth and label the squares as in Figure 3 so that $R_{i}$ and $R_{i+1}$
share an edge for $1\leq i\leq\frac{n}{A^{2}}-1.$

Figure 3: Tiling the unit square into $N=\frac{n}{A^{2}}$ smaller
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ squares $\\{R_{l}\\}_{1\leq
l\leq\frac{n}{A^{2}}}.$

### Lower deviation bounds

For $1\leq i\leq\frac{n}{A^{2}}$ let $E(R_{i})$ denote the event that the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square $R_{i}$ is occupied i.e.,
contains at least one node of ${\cal P},$ and all squares sharing a corner
with $R_{i}$ are empty. If $E(R_{i})$ occurs, then there are at least two
edges in the TSP of $K^{(P)}_{n}$ with one endvertex in $R_{i}$ and other
endvertex in a square not sharing a corner with $R_{i}.$ Each such edge has a
Euclidean length of at least $\frac{A}{\sqrt{n}}$ and so a weight of at least
$\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}$ (see (1.2)). Consequently

$TSP^{(P)}_{n}\geq\frac{1}{2}\cdot\sum_{i=1}^{\frac{n}{A^{2}}}2\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}1{1}(E(R_{i}))=\left(\frac{c_{1}A}{\sqrt{n}}\right)^{\alpha}\cdot
G_{\alpha},$ (2.2)

where $G_{\alpha}:=\sum_{i=1}^{\frac{n}{A^{2}}}1{1}(E(R_{i}))$ and the factor
$\frac{1}{2}$ occurs, since each edge is counted twice in the summation.

To estimate $G_{\alpha},$ we would like to split it into sums of independent
r.v.s using the following construction. For a square $R_{i},$ let ${\cal
N}(R_{i})$ be the set of all squares sharing a corner with $R_{i},$ including
$R_{i}.$ If $R_{i}$ does not intersect the sides of the unit square $S,$ then
there are $9$ squares in ${\cal N}(R_{i})$ and if $R_{j}$ is another square
such that ${\cal N}(R_{i})\cap{\cal N}(R_{j})=\emptyset,$ then the
corresponding events $E(R_{i})$ and $E(R_{j})$ are independent, by Poisson
property. We therefore extract nine disjoint subsets $\\{{\cal
U}_{l}\\}_{1\leq l\leq 9}$ of $\\{R_{i}\\}$ with the following properties:
$(A)$ If $R_{i},R_{j}\in{\cal U}_{l},$ then $\\#{\cal N}(R_{i})=\\#{\cal
N}(R_{j})=9$ and ${\cal N}(R_{i})\cap{\cal N}(R_{j})=\emptyset.$
$(B)$ The number of squares $\\#{\cal
U}_{l}\geq\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}$ for each $1\leq l\leq 9.$
This is possible since there are at most
$\frac{4\sqrt{n}}{A}-4<\frac{4\sqrt{n}}{A}$ squares in $\\{R_{k}\\}$
intersecting the sides of the unit square $S$ and the total number of squares
in $\\{R_{k}\\}$ is $\frac{n}{A^{2}}.$

We now write
$G_{\alpha}=\sum_{i=1}^{\frac{n}{A^{2}}}1{1}(E(R_{i}))\geq\sum_{l=1}^{9}\sum_{R_{i}\in{\cal
U}_{l}}1{1}(E(R_{i})),$ where each inner summation on the right side is a sum
of independent Bernoulli random variables, which we bound via standard
deviation estimates. Indeed for $1\leq l\leq 9$ and $R_{i}\in{\cal U}_{l},$
the number of nodes $N(R_{i})$ is Poisson distributed with mean
$n\int_{R_{i}}f(x)dx\in[\epsilon_{1}A^{2},\epsilon_{2}A^{2}]$ (see (1.1)) and
so $R_{i}$ is occupied with probability at least $1-e^{-\epsilon_{1}A^{2}}.$
Also each of the eight squares sharing a corner with $R_{i}$ is empty with
probability at least $e^{-\epsilon_{2}A^{2}},$ implying that
$\mathbb{P}(E(R_{i}))\geq(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}.$
Using the deviation estimate (7.2) in Appendix with
$\mu_{1}=(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}},m=\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}$
and $\epsilon=\frac{1}{m^{1/4}}$ we then get that

$\mathbb{P}_{0}\left(\sum_{R_{i}\in{\cal
U}_{l}}1{1}(E(R_{i}))\geq(1-\epsilon)\left(\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}\right)(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\right)\geq
1-e^{-D_{1}\epsilon^{2}n}$ (2.3)

for some constant $D_{1}>0$ not depending on $l.$ Since
$m^{1/4}<\left(\frac{n}{9A^{2}}\right)^{1/4},$ we get that
$D_{1}\epsilon^{2}n\geq 2D_{2}\sqrt{n}$ for some constant $D_{2}>0$ and since
$m^{1/4}>\left(\frac{n}{10A^{2}}\right)^{1/4}$ for all $n$ large, we have

$(1-\epsilon)\left(\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}\right)\geq\frac{n}{9A^{2}}-\frac{4\sqrt{n}}{A}-\frac{n}{A^{2}m^{1/4}}\geq\frac{n}{9A^{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)$

for all $n$ large.

Letting

$E_{low}:=\left\\{G_{\alpha}\geq(1-e^{-\epsilon_{1}A^{2}})e^{-8\epsilon_{2}A^{2}}\frac{n}{A^{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)\right\\},$

we get from (2.3) that $\mathbb{P}_{0}(E_{low})\geq 1-9e^{-2D_{2}\sqrt{n}}$
and moreover, from (2.2) we also get that

$TSP^{(P)}_{n}1{1}(E_{low})\geq\Delta_{n}:=C_{1}(A)n^{1-\frac{\alpha}{2}}\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right),$

where $C_{1}(A)$ is as defined in (1.5). From the estimate for the probability
of the event $E_{low}$ above we therefore get
$\mathbb{P}_{0}\left(TSP_{n}^{(P)}\geq\Delta_{n}\right)\geq
1-9e^{-2D_{2}\sqrt{n}}$ for all $n$ large. To convert the estimate from
Poisson to the Binomial process, we let
$E_{P}:=\left\\{TSP_{n}^{(P)}\geq\Delta_{n}\right\\},E:=\left\\{TSP_{n}\geq\Delta_{n}\right\\}$
and use the dePoissonization formula ((Bradonjic et al. 2010), also proved
below)

$\mathbb{P}(E)\geq 1-D\sqrt{n}\mathbb{P}(E^{c}_{P})$ (2.4)

for some constant $D>0$ to get that $\mathbb{P}(E)\geq
1-D\sqrt{n}e^{-2D_{2}\sqrt{n}}\geq 1~{}-~{}e^{-D_{2}\sqrt{n}}$ for all $n$
large. This proves (1.6) and so using

$\mathbb{E}TSP^{k}_{n}\geq\mathbb{E}TSP^{k}_{n}1{1}\left(MST_{n}\geq\Delta_{n}\right)\geq\Delta^{k}_{n}\left(1-e^{-D_{2}\sqrt{n}}\right)$

and

$\left(1-\frac{36\sqrt{A}}{n^{1/4}}\right)^{k}(1-e^{-D_{2}\sqrt{n}})\geq\left(1-\frac{36k\sqrt{A}}{n^{1/4}}\right)(1-e^{-D_{2}\sqrt{n}})\geq
1-\frac{37k\sqrt{A}}{n^{1/4}}$

for all $n$ large, we also obtain the lower bound on the expectation in (1).

To see that (2.4) is true, we let $N_{P}$ denote the random number of nodes of
${\cal P}$ in all the squares $\\{S_{j}\\}$ so that $\mathbb{E}_{0}N_{P}=n$
and $\mathbb{P}_{0}(N_{P}=n)=e^{-n}\frac{n^{n}}{n!}\geq\frac{D_{1}}{\sqrt{n}}$
for some constant $D_{1}>0,$ using the Stirling formula. Given $N_{P}=n,$ the
nodes of ${\cal P}$ are i.i.d. with distribution $f(.)$ as defined in (1.1);
i.e., $\mathbb{P}_{0}(E_{P}^{c}|N_{P}=n)=\mathbb{P}(E^{c})$ and so

$\mathbb{P}_{0}(E_{P}^{c})\geq\mathbb{P}_{0}(E_{P}^{c}|N_{P}=n)\mathbb{P}_{0}(N_{P}=n)=\mathbb{P}(E^{c})\mathbb{P}_{0}(N_{P}=n)\geq\mathbb{P}(E^{c})\frac{D_{1}}{\sqrt{n}},$

proving (2.4).

### Upper deviation bounds

As before, we consider the Poisson process ${\cal P}$ and first upper bound
$TSP^{(P)}_{n}.$ Intuitively, we would like to first connect all the nodes
within each square $R_{j}$ to get a cycle and then merge all these cycles
together to get an overall spanning cycle. However, it might so happen that
some of the squares in $\\{R_{i}\\}$ may contain only one or two nodes and
therefore, we take a slightly different approach. First we consider squares
containing at least three nodes and join all these nodes to form a path. We
then consider all the squares containing one or two nodes and connect these
nodes together by a separate path and finally merge the two paths to get a
spanning cycle.

Say that a square $R_{i}$ is a _dense square_ if it contains at least three
nodes of ${\cal P}$ and _sparse_ otherwise and let $E_{bas}$ be the event that
there are at least two sparse and at least two dense squares. To estimate the
probability of the event $E_{bas}$ we use the fact that the number of nodes
$N(R_{i})$ in the square $R_{i}$ is Poisson distributed with mean
$\mathbb{E}_{0}N(R_{i})=n\int_{R_{i}}f(x)dx\in[\epsilon_{1}A^{2},\epsilon_{2}A^{2}]$
(see bounds for $f(.)$ in (1.1)). Therefore there are constants $p_{0}$ and
$p_{1}$ not depending on $i$ such that

$0<p_{0}\leq p_{low}\leq p_{up}\leq p_{1}<1,$ (2.5)

where $p_{low}=\min\left(\mathbb{P}_{0}(R_{i}\text{ is
dense}),\mathbb{P}_{0}(R_{i}\text{ is sparse})\right)$
and $p_{up}=\max\left(\mathbb{P}_{0}(R_{i}\text{ is
dense}),\mathbb{P}_{0}(R_{i}\text{ is sparse})\right).$ Since the Poisson
process is independent on disjoint sets, there is at most one dense square
among the $\frac{n}{A^{2}}$ squares in $\\{R_{i}\\}$ with probability at most

$(1-p_{low})^{\frac{n}{A^{2}}}+\frac{n}{A^{2}}(1-p_{low})^{\frac{n}{A^{2}}-1}\leq(1-p_{low})^{\frac{n}{4}-1}(n+1),$

using $1\leq A\leq 1+\frac{1}{\log{n}}\leq 2.$ The same estimate holds for the
event that there is at most one sparse square and so we have that

$\mathbb{P}_{0}(E_{bas})\geq 1-e^{-q_{0}n}$ (2.6)

for some constant $q_{0}=q_{0}(\epsilon_{1},\epsilon_{2},A)>0.$

Henceforth we assume that $E_{bas}$ occurs and let
$R_{i_{1}},R_{i_{2}},\ldots,R_{i_{Q}},1\leq
i_{1}<i_{2}<\ldots<i_{Q}\leq\frac{n}{A^{2}},2\leq Q\leq\frac{n}{A^{2}}$ be all
the dense squares. For $1\leq j\leq Q,$ let ${\cal P}_{i_{j}}$ be any spanning
path containing all the nodes of $R_{i_{j}}$ and for $1\leq j\leq Q-1$ let
$e_{j+1}$ be any edge joining some node in $R_{i_{j}}$ and some node in
$R_{i_{j+1}}$ so that the union ${\cal P}_{dense}:=\cup_{1\leq j\leq Q}{\cal
P}_{i_{j}}\cup\cup_{2\leq l\leq Q}\\{e_{l}\\}$ is a path containing all the
nodes in the dense squares.

For $1\leq j\leq Q,$ there are $N(R_{i_{j}})$ nodes of the Poisson process in
the square $R_{i_{j}}$ and any two such nodes are connected by an edge of
Euclidean length at most $\frac{A\sqrt{2}}{\sqrt{n}}.$ Therefore the spanning
path ${\cal P}_{i_{j}}$ has a total weight of at most
$N(R_{i_{j}})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha},$
using (1.2). The edge $e_{j+1}$ that connects some node in $R_{i_{j}}$ with
some node of $R_{i_{j+1}}$ has a Euclidean length of at most
$\frac{2T_{j+1}A}{\sqrt{n}}$ where $T_{j+1}:=i_{j+1}-i_{j}$ and therefore has
a weight of at most $\left(\frac{2c_{2}T_{j+1}A}{\sqrt{n}}\right)^{\alpha},$
again using (1.2). Setting $T_{1}:=i_{1}-1,T_{Q+1}:=\frac{n}{A^{2}}-i_{Q}$ and
$S_{\alpha}:=\sum_{j=1}^{Q+1}T_{j}^{\alpha}$ we then get

$\displaystyle W\left({\cal P}_{dense}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{Q}N(R_{i_{j}})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha}+\sum_{j=2}^{Q}\left(\frac{2c_{2}T_{j}A}{\sqrt{n}}\right)^{\alpha}$
(2.7) $\displaystyle\leq$
$\displaystyle\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(\sum_{j=1}^{Q}N(R_{i_{j}})+S_{\alpha}\right).$

Suppose now that $R_{m_{1}},\ldots,R_{m_{L}},1\leq
m_{1}<m_{2}<\ldots<m_{L}\leq\frac{n}{A^{2}},2\leq L\leq\frac{n}{A^{2}}$ are
all the sparse squares. As before we connect the nodes in all these squares
together to form a path ${\cal P}_{sparse}$ whose weight is

$W\left({\cal
P}_{sparse}\right)\leq\sum_{l=1}^{L}N(R_{m_{l}})\cdot\left(\frac{c_{2}A\sqrt{2}}{\sqrt{n}}\right)^{\alpha}+\sum_{l=2}^{L}\left(\frac{2c_{2}U_{l}A}{\sqrt{n}}\right)^{\alpha},$

where $U_{l+1}:=m_{l+1}-m_{l}$ for $1\leq l\leq L-1.$ Setting
$U_{1}:=m_{1}-1,U_{L+1}:=\frac{n}{A^{2}}-m_{L}$ and
$V_{\alpha}:=\sum_{l=1}^{L+1}U_{j}^{\alpha}$ we then get

$W\left({\cal
P}_{sparse}\right)\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(\sum_{l=1}^{L}N(R_{m_{l}})+V_{\alpha}\right).$
(2.8)

Adding (2.7) and (2.8) we get

$W({\cal P}_{dense})+W({\cal
P}_{sparse})\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(\sum_{j=1}^{Q}N(R_{i_{j}})+S_{\alpha}+\sum_{l=1}^{L}N(R_{m_{l}})+V_{\alpha}\right)$

and using the fact that the squares $\\{R_{i_{j}}\\}\cup\\{R_{m_{l}}\\}$
contain all the nodes of the Poisson process ${\cal P},$ we then get

$W({\cal P}_{dense})+W({\cal
P}_{sparse})\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(N_{tot}+S_{\alpha}+V_{\alpha}\right),$
(2.9)

where $N_{tot}:=\sum_{i=1}^{\frac{n}{A^{2}}}N(R_{i})$ is the total number of
nodes of ${\cal P}$ in the unit square $S.$

The path ${\cal P}_{dense}$ has one endvertex $u_{1}$ in the square
$R_{i_{1}}$ and the other endvertex $u_{2}$ in the square $R_{i_{Q}}.$
Similarly, the path ${\cal P}_{sparse}$ has one endvertex $v_{1}$ in the
square $R_{m_{1}}$ and the other endvertex $v_{2}$ in the square $R_{m_{L}}.$
Since the event $E_{bas}$ occurs, there are at least two dense and two sparse
squares and so the vertices $u_{1},u_{2},v_{1},v_{2}$ are all distinct. We
join $u_{1}$ and $v_{1}$ by an edge $f_{1}$ and $u_{2}$ and $v_{2}$ by an edge
$f_{2}$ so that the union ${\cal C}_{tot}={\cal P}_{dense}\cup{\cal
P}_{sparse}\cup\\{f_{1},f_{2}\\}$ is a spanning cycle containing all the nodes
of the Poisson process ${\cal P}.$

Using the bounds for the edge weight function $h$ in (1.2), the weight of the
edge $f_{1}$ is at most
$\left(\frac{2c_{2}|i_{1}-m_{1}|A}{\sqrt{n}}\right)^{\alpha}$ and the weight
of $f_{2}$ is at most
$\left(\frac{2c_{2}|i_{Q}-m_{L}|A}{\sqrt{n}}\right)^{\alpha}.$ Therefore from
(2.9) we get that

$\displaystyle W({\cal C}_{tot})$ $\displaystyle\leq$ $\displaystyle W({\cal
P}_{dense})+W({\cal
P}_{sparse})+\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\cdot Z_{\alpha},$
(2.10) $\displaystyle\leq$
$\displaystyle\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(N_{tot}+S_{\alpha}+V_{\alpha}+Z_{\alpha}\right),$

where $Z_{\alpha}:=|i_{1}-m_{1}|^{\alpha}+|i_{Q}-m_{L}|^{\alpha}.$ From (2.10)
and the fact that $TSP^{(P)}_{n}\leq W({\cal C}_{tot}),$ we get that

$TSP^{(P)}_{n}1{1}(E_{bas})\leq\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(N_{tot}+S_{\alpha}+V_{\alpha}+Z_{\alpha}\right).$
(2.11)

We evaluate each of the four terms in (2.11) separately. The first term
$N_{tot}$ is a Poisson random variable with mean $n$ since this denotes the
total number of nodes of the Poisson process in the unit square. From the
deviation estimate (7.1) in Appendix with $m=1,\mu_{2}=n$ and
$\epsilon=\frac{\log{n}}{\sqrt{n}},$ we have that

$\mathbb{P}_{0}\left(N_{tot}\leq
n\left(1+\frac{\log{n}}{\sqrt{n}}\right)\right)\geq 1-e^{-C(\log{n})^{2}}$
(2.12)

for some constant $C>0.$ Setting $E_{node}:=\left\\{N_{tot}\leq
n\left(1+\frac{\log{n}}{\sqrt{n}}\right)\right\\},$ we get from (2.10) that

$\displaystyle TSP_{n}^{(P)}1{1}(E_{bas}\cap E_{node})$
$\displaystyle\;\;\;\;\;\leq\;\;\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{\log{n}}{\sqrt{n}}\right)+S_{\alpha}+V_{\alpha}+Z_{\alpha}\right).$
(2.13)

The following Lemma estimates $Z_{\alpha},S_{\alpha}$ and $V_{\alpha}.$

###### Lemma 2

Let $m\geq 2$ be any even integer constant. There exists a constant
$D=D(m,\epsilon_{1},\epsilon_{2},\alpha)>0$ such that

$\mathbb{P}_{0}\left(Z_{\alpha}\leq D\left(\log{n}\right)^{\alpha}\right)\geq
1-\frac{4}{n^{m}},$ (2.14)
$\mathbb{P}_{0}\left(S_{\alpha}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}{T}_{a}^{\alpha}\right)\geq
1-\frac{D}{n^{7m/16}}$ (2.15)

and

$\mathbb{P}_{0}\left(V_{\alpha}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}{T}_{b}^{\alpha}\right)\geq
1-\frac{D}{n^{7m/16}}.$ (2.16)

where ${T}_{a}$ is a geometric random variable with success parameter

$p_{dense}=1-e^{-A^{2}\delta}\left(1+A^{2}\delta+\frac{A^{4}\delta^{2}}{2}\right)$

and ${T}_{b}$ is a geometric random variable with success parameter

$p_{sparse}=1-p_{dense}=e^{-\delta
A^{2}}\left(1+A^{2}\delta+\frac{A^{4}\delta^{2}}{2}\right).$

We prove Lemma 2 at the end. Assuming Lemma 2, we complete the proof of
Theorem 1.

Setting $E_{Z}=\\{Z_{\alpha}\leq D\left(\log{n}\right)^{\alpha}\\}$ we then
get from (2.13) that

$\displaystyle TSP_{n}^{(P)}1{1}(E_{bas}\cap E_{node}\cap E_{Z})$
$\displaystyle\;\;\;\;\leq\;\;\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{\log{n}}{\sqrt{n}}\right)+D_{0}(\log{n})^{\alpha}+S_{\alpha}+V_{\alpha}\right),$
$\displaystyle\;\;\;\;\leq\;\;\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{2\log{n}}{\sqrt{n}}\right)+S_{\alpha}+V_{\alpha}\right)$
(2.17)

for all $n$ large.

Letting $E_{SV}$ be the intersection of the events in the left hand sides of
(2.15) and (2.16), we have from the estimate (2.17) that

$\displaystyle TSP_{n}^{(P)}1{1}(E_{bas}\cap E_{node}\cap E_{Z}\cap E_{SV})$
$\displaystyle\;\;\;\;\;\leq\;\;\left(\frac{2c_{2}A}{\sqrt{n}}\right)^{\alpha}\left(n\left(1+\frac{2\log{n}}{\sqrt{n}}\right)+n\left(1+\frac{1}{n^{1/16}}\right)\frac{1}{A^{2}}(\mathbb{E}{T}_{a}^{\alpha}+\mathbb{E}{T}^{\alpha}_{b})\right).$

Using $\frac{2\log{n}}{\sqrt{n}}\leq\frac{1}{n^{1/16}}$ for all $n$ large, we
then get

$\displaystyle TSP_{n}^{(P)}1{1}(E_{bas}\cap E_{node}\cap E_{Z}\cap
E_{SV})\leq C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right),$
(2.18)

where $C_{2}(A)$ is as in (1.5). From (2.18) and the estimates for the events
$E_{bas},E_{node},E_{Z}$ and $E_{SV}$ from (2.6),(2.12) and (2.14) and (2.15),
respectively, we have

$\displaystyle\mathbb{P}_{0}\left(TSP_{n}^{(P)}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)\right)$
$\displaystyle\;\;\;\;\;\;\geq\;\;\;\;1-e^{-q_{0}n}-e^{-D_{5}(\log{n})^{2}}-\frac{1}{n^{m}}-\frac{D_{5}}{n^{7m/16}}$
$\displaystyle\;\;\;\;\;\;\geq\;\;\;\;1-\frac{2D_{5}}{n^{7m/16}}$ (2.19)

for all $n$ large and some constant $D_{5}>0.$

From (2.19) and the dePoissonization formula (2.4), we obtain

$\mathbb{P}\left(TSP_{n}\leq
C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)\right)\geq
1-\frac{D_{6}\sqrt{n}}{n^{7m/16}}$ (2.20)

for some constant $D_{6}>0.$ Choosing $m$ large enough such that
$\frac{7m}{16}-\frac{1}{2}\geq k,$ we obtain the estimate in (1.7). For
bounding the expectation, we let
$\Delta_{n}=C_{2}(A)n^{1-\frac{\alpha}{2}}\left(1+\frac{1}{n^{1/16}}\right)$
and write $\mathbb{E}TSP_{n}^{k}=I_{1}+I_{2},$ where

$I_{1}:=\mathbb{E}TSP^{k}_{n}1{1}(TSP_{n}\leq\Delta_{n})\leq\Delta^{k}_{n}\leq
C_{2}^{k}(A)n^{k\left(1-\frac{\alpha}{2}\right)}\left(1+\frac{2k}{n^{1/16}}\right),$
(2.21)

using $\left(1+\frac{1}{n^{1/16}}\right)^{k}\leq e^{k/n^{1/16}}\leq
1+\frac{2k}{n^{1/16}}$ for all $n$ large and
$I_{2}:=\mathbb{E}TSP^{k}_{n}1{1}(TSP_{n}>\Delta_{n}).$

To evaluate $I_{2},$ we use the estimate $TSP_{n}\leq
n\cdot\left(c_{2}\sqrt{2}\right)^{\alpha}$ by (1.2), since there are $n$ edges
in the spanning cycle and each such edge has an Euclidean length of at most
$\sqrt{2}.$ Letting $\theta_{m}=\frac{7m}{16}-\frac{1}{2}-\frac{\alpha k}{2}$
and using the probability estimate (2.20) we therefore get that

$I_{2}\leq\left(n\cdot\left(c_{2}\sqrt{2}\right)^{\alpha}\right)^{k}\cdot\frac{D_{6}\sqrt{n}}{n^{7m/16}}=n^{k\left(1-\frac{\alpha}{2}\right)}\frac{D_{7}}{n^{\theta_{m}}},$
(2.22)

for some constant $D_{7}>0.$ Adding (2.21) and (2.22) we get

$\mathbb{E}TSP^{k}_{n}\leq
C^{k}_{2}(A)n^{k\left(1-\frac{\alpha}{2}\right)}\left(1+\frac{2k}{n^{1/16}}+\frac{D_{7}}{n^{\theta_{m}}}\right)$

and choosing $m$ larger if necessary so that $\theta_{m}\geq 1>\frac{1}{16},$
we obtain the expectation upper bound in (1).

_Proof of ( 2.14) in Lemma 2_: We write
$Z_{\alpha}=|i_{1}-m_{1}|^{\alpha}+|i^{\prime}_{1}-m^{\prime}_{1}|^{\alpha},$
where $i^{\prime}_{1}=\frac{n}{A^{2}}-i_{Q}$ and
$m^{\prime}_{1}=\frac{n}{A^{2}}-m_{L}.$ Using $(a+b)^{\alpha}\leq
2^{\alpha}(a^{\alpha}+b^{\alpha})$ for all $a,b,\alpha>0,$ we get
$Z_{\alpha}\leq
2^{\alpha}(i_{1}^{\alpha}+m_{1}^{\alpha}+\left(i^{\prime}_{1}\right)^{\alpha}+\left(m^{\prime}_{1}\right)^{\alpha}).$
The term $i_{1}$ denotes the index of the first dense
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square in $\\{R_{i}\\}.$ Since
each square is independently dense with probability at least $p_{0}$ (see
(2.5)), we get that $\mathbb{P}_{0}(i_{1}>l)\leq(1-p_{0})^{l}.$ Setting
$l=-\frac{m\log{n}}{\log(1-p_{0})}$ where $m$ is an even integer constant to
be determined later, we get
$\mathbb{P}_{0}(i_{1}^{\alpha}>l^{\alpha})\leq\frac{1}{n^{m}}.$ Analogous
estimates hold for $m_{1},i^{\prime}_{1}$ and $m^{\prime}_{1}$ and so we get
(2.14).

_Proof of ( 2.15) and (2.16) in Lemma 2_: The quantities $S_{\alpha}$ and
$V_{\alpha}$ are not i.i.d. sums and in what follows we evaluate $S_{\alpha}$
and an analogous analysis holds for $V_{\alpha}.$ The term $S_{\alpha}$ is
defined for all configurations $\omega\in E_{bas}$ which contain at least two
dense squares. We first extend the definition of $S_{\alpha}$ for all
configurations $\omega$ as follows. If $\omega$ is such that there is exactly
one dense square $R_{i_{1}},1\leq i_{1}\leq\frac{n}{A^{2}},$ then we set
$S_{\alpha}(\omega)=(i_{1}-1)^{\alpha}+\left(\frac{n}{A^{2}}-i_{1}\right)^{\alpha}.$
If $\omega$ is such that there is no dense square, we set
$S_{\alpha}(\omega)=\left(\frac{n}{A^{2}}-1\right)^{\alpha}.$ With this
extended definition, we now show that $S_{\alpha}(\omega)$ is monotonic in
$\omega$ in the sense that adding more nodes increases $S_{\alpha}$ if
$\alpha\leq 1$ and decreases $S_{\alpha}$ if $\alpha>1.$ This then allows us
to use coupling and upper bound $S_{\alpha}$ by simply considering homogenous
Poisson processes.

_Monotonicity of $S_{\alpha}$_: Let $\omega$ be any configuration and suppose
$\omega^{\prime}=\omega\cup\\{x\\}$ is obtained by adding a single extra node
at $x\in R_{j_{0}}$ for some $1\leq j_{0}\leq\frac{n}{A^{2}}.$ If
$N(R_{j_{0}},\omega)$ and $N(R_{j_{0}},\omega^{\prime})$ respectively denote
the number of nodes of $\omega$ and $\omega^{\prime}$ present in the square
$R_{j_{0}},$ then $N(R_{j_{0}},\omega^{\prime})=N(R_{j_{0}},\omega)+1.$

If $N(R_{j_{0}},\omega)\leq 1,$ then $N(R_{j_{0}},\omega^{\prime})\leq 2$ and
so $R_{j_{0}}$ is not a dense square in the configuration $\omega^{\prime}$ as
well. This implies that $S_{\alpha}(\omega^{\prime})=S_{\alpha}(\omega).$
Analogous argument holds if $N(R_{j_{0}},\omega)\geq 3$ so that $R_{j_{0}}$ is
already a dense square in the configuration $\omega.$ If on the other hand
$N(R_{j_{0}},\omega)=2,$ then $N(R_{j_{0}},\omega^{\prime})=3$ and so
$R_{j_{0}}$ is a dense square in the configuration $\omega^{\prime}$ but not
in $\omega.$

To compute $S_{\alpha}(\omega^{\prime})$ in terms of $S_{\alpha}(\omega),$
suppose first that $\omega$ contains at least one dense square and let $1\leq
i_{1}(\omega)<\ldots<i_{Q}(\omega)\leq\frac{n}{A^{2}}$ be the indices of all
the dense squares in $\\{R_{l}\\}.$ Setting $i_{0}(\omega):=1$ and
$i_{Q+1}(\omega):=\frac{n}{A^{2}},$ we then get that
$S_{\alpha}(\omega)=\sum_{j=0}^{Q}(i_{j+1}(\omega)-i_{j}(\omega))^{\alpha}.$
There are only three possibilities for the index $j_{0}:$ Either $j_{0}=1$ or
$j_{0}=\frac{n}{A^{2}}$ or there exists $0\leq a\leq Q$ such that
$i_{a}(\omega)<j_{0}<i_{a+1}(\omega).$ If $j_{0}\in\\{1,\frac{n}{A^{2}}\\},$
then again $S_{\alpha}(\omega)=S_{\alpha}(\omega^{\prime}).$ Else,
$i_{a}(\omega)<j_{0}<i_{a+1}(\omega)$ and so

$S_{\alpha}(\omega^{\prime})=S_{\alpha}(\omega)+(i_{a+1}(\omega)-j_{0})^{\alpha}+(j_{0}-i_{a}(\omega))^{\alpha}-(i_{a+1}(\omega)-i_{a}(\omega))^{\alpha}.$
(2.23)

If $\omega$ does not contain any dense square, then
$S_{\alpha}(\omega)=\left(\frac{n}{A^{2}}-1\right)^{\alpha}$ and
$S_{\alpha}(\omega^{\prime})=(j_{0}-1)^{\alpha}+\left(\frac{n}{A^{2}}-j_{0}\right)^{\alpha}$
so that (2.23) is again satisfied with $i_{a}(\omega)=1$ and
$i_{a+1}(\omega)=\frac{n}{A^{2}}.$ For $\alpha\leq 1$ we then use
$y^{\alpha}+z^{\alpha}\geq(y+z)^{\alpha}$ for positive numbers $y,z$ in
(2.23), to get that $S_{\alpha}(\omega^{\prime})\geq S_{\alpha}(\omega).$ If
$\alpha>1$ then $y^{\alpha}+z^{\alpha}\leq(y+z)^{\alpha}$ and so
$S_{\alpha}(\omega^{\prime})\leq S_{\alpha}(\omega).$ This monotonicity
property together with coupling allows us to upper bound $S_{\alpha}$ as
follows. Letting $\delta=\epsilon_{2}$ if $\alpha\leq 1$ and
$\delta=\epsilon_{1}$ if $\alpha>1,$ we let ${\cal P}_{\delta}$ be a
homogenous Poisson process of intensity $\delta n$ on the unit square $S,$
defined on the probability space $(\Omega_{\delta},{\cal
F}_{\delta},\mathbb{P}_{\delta}).$

Say that a square $R_{i}$ is a $\delta-$dense square if $R_{i}$ contains at
least three nodes of ${\cal P}_{\delta}$ and let $F_{\delta}$ denote the event
that there is at least one $\delta-$dense square. As before we set
$S^{(\delta)}_{\alpha}:=\left(\frac{n}{A^{2}}-1\right)^{\alpha}$ if there is
no $\delta-$dense square. Suppose now that $F_{\delta}$ occurs and let
$\\{i^{(\delta)}_{j}\\}_{1\leq j\leq Q_{\delta}}$ be the indices of the
$\delta-$dense squares in $\\{R_{j}\\}.$ As in the definition of $S_{\alpha},$
we define $T^{(\delta)}_{j+1}:=i^{(\delta)}_{j+1}-i^{(\delta)}_{j}$ for $1\leq
j\leq Q_{\delta}-1$ and set $T^{(\delta)}_{1}:=i^{(\delta)}_{1}-1$ and
$T^{(\delta)}_{Q_{\delta}+1}:=\frac{n}{A^{2}}-i^{(\delta)}_{Q_{\delta}}.$
Defining
$S^{(\delta)}_{\alpha}:=\sum_{j=1}^{Q_{\delta}+1}\left(T^{(\delta)}_{j}\right)^{\alpha},$
we have for any $x>0$ that

$\mathbb{P}_{\delta}\left(S^{(\delta)}_{\alpha}<x\right)\leq\mathbb{P}_{0}\left(S_{\alpha}<x\right).$
(2.24)

The proof follows by standard coupling techniques and for completeness, we
have a proof in the Appendix.

To estimate $S^{(\delta)}_{\alpha}$ we let $N^{(\delta)}(R_{i}),1\leq
i\leq\frac{n}{A^{2}},$ be the random number of nodes of ${\cal P}_{\delta}$ in
the square $R_{i}.$ The random variables $\\{N^{(\delta)}(R_{i})\\}$ are
i.i.d. Poisson distributed each with mean $A^{2}\delta.$ For
$i\geq\frac{n}{A^{2}}+1,$ we define $N^{(\delta)}(R_{i})$ to be i.i.d. Poisson
random variables with mean $A^{2}\delta,$ that are also independent of
$\\{N^{(\delta)}(R_{i})\\}_{1\leq i\leq\frac{n}{A^{2}}}.$ Without loss of
generality, we associate the probability measure $\mathbb{P}_{\delta}$ for the
random variables $\\{N^{(\delta)}(R_{i})\\}_{i\geq\frac{n}{A^{2}}+1}$ as well.

Let $\tilde{T}_{1}:=\min\\{j\geq 1:N^{(\delta)}(R_{j})\geq 3\\}$ and for
$j\geq 2,$ let
$\tilde{T}_{j}:=\min\\{k\geq\tilde{T}_{j-1}+1:N^{(\delta)}(R_{k})\geq
3\\}-\tilde{T}_{j-1}.$ The random variables $\\{\tilde{T}_{i}\\}$ are nearly
the same as $\\{T^{(\delta)}_{i}\\}$ in the following sense: We recall from
discussion prior to (2.24) that $F_{\delta}$ denotes the event that there
exists at least one $\delta-$dense square in $\\{R_{i}\\},$ containing at
least three nodes of ${\cal P}_{\delta}.$ If $F_{\delta}$ occurs, then $1\leq
Q_{\delta}\leq\frac{n}{A^{2}}$ and so
$T^{(\delta)}_{1}=\tilde{T}_{1}-1,T^{(\delta)}_{j}=\tilde{T}_{j}$ for $2\leq
j\leq Q_{\delta}$ and $T^{(\delta)}_{j}\leq\tilde{T}_{j}$ for
$j=Q_{\delta}+1.$ Consequently

$S_{\alpha}^{(\delta)}1{1}(F_{\delta})\leq\sum_{i=1}^{Q_{\delta}+1}\tilde{T}^{\alpha}_{i}1{1}(F_{\delta})\leq\sum_{i=1}^{\frac{n}{A^{2}}+1}\tilde{T}^{\alpha}_{i}$
(2.25)

since $Q_{\delta}\leq\frac{n}{A^{2}}.$ Also, arguing as in the proof of the
estimate (2.6) for the event $E_{bas}$ we have that

$\mathbb{P}_{\delta}\left(F_{\delta}\right)\geq 1-e^{-qn}$ (2.26)

for some constant $q>0.$

The advantage of the above construction is that $\\{\tilde{T}_{i}\\}$ are
i.i.d. geometric random variables with success parameter
$p_{dense}=1-e^{-A^{2}\delta}\left(1+A^{2}\delta+\frac{A^{4}\delta^{2}}{2}\right)$
and so all moments of $\tilde{T}_{i}^{\alpha}$ exist. Letting
$\beta_{i}=\left(\tilde{T}_{i}^{\alpha}-\mathbb{E}_{\delta}\tilde{T}_{i}^{\alpha}\right)$
and $\beta_{tot}=\sum_{i=1}^{\frac{n}{A^{2}}+1}\beta_{i}$ we obtain for an
even integer constant $m$ (to be determined later) that

$\mathbb{E}_{\delta}\beta_{tot}^{m}=\mathbb{E}_{\delta}\sum_{(i_{1},\ldots,i_{m})}\beta_{i_{1}}\ldots\beta_{i_{m}}.$
(2.27)

For a tuple $(i_{1},\ldots,i_{m})$ let $\\{j_{1},\ldots,j_{w}\\}$ be the
distinct integers in $\\{i_{1},\ldots,i_{m}\\}$ with corresponding
multiplicities $l_{1},\ldots,l_{w}$ so that

$\mathbb{E}_{\delta}\beta_{i_{1}}\ldots\beta_{i_{m}}=\mathbb{E}_{\delta}\beta_{j_{1}}^{l_{1}}\ldots\beta_{j_{w}}^{l_{w}}=\prod_{k=1}^{w}\mathbb{E}_{\delta}\beta_{j_{k}}^{l_{k}}.$

If $l_{k}=1$ for some $1\leq k\leq w,$ then
$\mathbb{E}_{\delta}\beta_{i_{1}}\ldots\beta_{i_{m}}=0$ and so for any non
zero term in the summation in (2.27), there are at most $\frac{m}{2}$ distinct
terms in $\\{i_{1},\ldots,i_{m}\\}.$ This implies that

$\mathbb{E}_{\delta}\beta_{tot}^{m}\leq D(m){n\choose m/2}\leq D(m)n^{m/2}$

for some constant $D(m)>0.$ For $\epsilon>0$ we therefore get from Chebychev’s
inequality that

$\mathbb{P}_{\delta}\left(|\beta_{tot}|>\epsilon\left(\frac{n}{A^{2}}+1\right)\mathbb{E}_{\delta}\tilde{T}_{1}^{\alpha}\right)\leq
D_{1}\frac{\mathbb{E}_{\delta}(\beta_{tot}^{m})}{n^{m}\epsilon^{m}}\leq\frac{D_{2}}{n^{m/2}\epsilon^{m}}$

for some constants $D_{1},D_{2}>0.$ Setting $\epsilon=\frac{1}{n^{1/16}}$ and
using
$\epsilon\left(\frac{n}{A^{2}}+1\right)\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}$
for all $n$ large, we then get

$\mathbb{P}_{\delta}\left(\sum_{i=1}^{\frac{n}{A^{2}}+1}\tilde{T}^{\alpha}_{i}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}\tilde{T}_{1}^{\alpha}\right)\geq
1-\frac{D_{2}}{n^{7m/16}}.$ (2.28)

From (2.25) and the estimate (2.26) for the event $F_{\delta},$ we further get

$\mathbb{P}_{\delta}\left(S^{(\delta)}_{\alpha}\leq\left(1+\frac{1}{n^{1/16}}\right)\frac{n}{A^{2}}\mathbb{E}\tilde{T}_{1}^{\alpha}\right)\geq
1-\frac{D_{2}}{n^{7m/16}}-e^{-qn}\geq 1-\frac{D_{3}}{n^{7m/16}}$

for all $n$ large and some constant $D_{3}>0.$ Using the monotonicity relation
(2.24) we finally get (2.15). An analogous analysis yields (2.16).

##  3 Variance upper bound

In this section, we obtain the variance upper bound for the overall TSP length
$TSP_{n}$ as defined in (1.4). We have the following result.

###### Theorem 3

Suppose the edge weight exponent is $0<\alpha<2.$ For every
$\epsilon>\frac{(2-\alpha)(1+\alpha)}{2+\alpha},$ there is a constant
$D_{1}=D_{1}(\epsilon,\alpha,\epsilon_{1},\epsilon_{2})>0$ such that

$var(TSP_{n})\leq D_{1}n^{\epsilon}$

for all $n$ large.

The desired bound is obtained via the martingale difference method that
estimates the change in TSP lengths after adding or removing a single node.

We perform some preliminary computations.

### One node difference estimates

As in (1.4), let $TSP_{n+1}=W({\cal C}_{n+1})$ be the weight of the TSP ${\cal
C}_{n+1}$ formed by the nodes $\\{X_{k}\\}_{1\leq k\leq n+1}$ and for $1\leq
j\leq n+1,$ let $TSP_{n}(j)=W({\cal C}_{n}(j))$ be the weight of the TSP
${\cal C}_{n}(j)$ formed by the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}.$
In this subsection, we find estimates for $|TSP_{n+1}-TSP_{n}(j)|,$ the change
in the length of the TSP upon adding or removing a single node.

Suppose $v_{j}$ and $v_{j+1}$ are the neighbours of the node $X_{j}$ in the
TSP ${\cal C}_{n+1}$ so that the edges $(v_{j},X_{j})$ and $(X_{j},v_{j+1})$
both belong to ${\cal C}_{n+1}.$ Removing the edges $(v_{j},X_{j})$ and
$(X_{j},v_{j+1})$ and adding the edge $(v_{j},v_{j+1}),$ we get a spanning
cycle containing the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ and so

$TSP_{n}(j)\leq TSP_{n+1}+h^{\alpha}(v_{j},v_{j+1})\leq
TSP_{n+1}+c_{2}^{\alpha}d^{\alpha}(v_{j},v_{j+1}),$ (3.1)

using (1.2).

By the triangle inequality we have that $d(v_{j},v_{j+1})\leq
d(X_{j},v_{j})+d(X_{j},v_{j+1})$ and so using $(a+b)^{\alpha}\leq
2^{\alpha}(a^{\alpha}+b^{\alpha})$ for all $a,b,\alpha>0$ we get that

$d^{\alpha}(v_{j},v_{j+1})\leq
2^{\alpha}\left(d^{\alpha}(X_{j},v_{j})+d^{\alpha}(X_{j},v_{j+1})\right)=2^{\alpha}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}d^{\alpha}(X_{j},v),$

where ${\cal N}(X_{j},{\cal C}_{n+1})$ denotes the set of neighbours of
$X_{j}$ in the spanning cycle ${\cal C}_{n+1}.$ Thus

$TSP_{n}(j)\leq TSP_{n+1}+g_{1}(X_{j}),$ (3.2)

where $g_{1}(X_{j}):=(2c_{2})^{\alpha}\sum_{v\in{\cal N}(X_{j},{\cal
C}_{n+1})}d^{\alpha}(X_{j},v).$

To get an estimate in the reverse direction, we would like to identify edges
of the TSP ${\cal C}_{n}(j)$ with small length that are close to the (yet to
be added) node $X_{j}.$ Recalling that
$\epsilon>\frac{(2-\alpha)(1+\alpha)}{2+\alpha},$ we let $\theta>0$ be such
that

$0<\theta<\frac{\alpha}{2(2+\alpha)}\text{ and
}1-\epsilon<2\theta\alpha<\frac{\alpha}{2}.$ (3.3)

To see such a $\theta$ exists, we use
$\epsilon>\frac{(2-\alpha)(1+\alpha)}{2+\alpha}$ and choose $\theta>0$
sufficiently close to but less than $\frac{\alpha}{2(2+\alpha)}$ so that
$\epsilon>1-2\theta\alpha>1-2\left(\frac{\alpha}{2(2+\alpha)}\right)\alpha=\frac{(2-\alpha)(1+\alpha)}{2+\alpha}.$
Fixing such a $\theta$ we use $\alpha<2$ to get that
$\theta<\frac{\alpha}{2(2+\alpha)}<\frac{1}{4}$ and therefore that
$2\theta\alpha<\frac{\alpha}{2}.$

Let $E_{good}(\theta)$ be the event that there is an edge $(u,v)\in{\cal
C}_{n}(j)$ such that each edge in the triangle formed by the nodes $X_{j},u$
and $v$ has Euclidean length at most $\frac{1}{n^{\theta}}.$ If
$E_{good}(\theta)$ occurs, then removing the edge $(u,v)$ and adding the edges
$(X_{j},u)$ and $(X_{j},v),$ we obtain a spanning cycle containing all the
nodes $\\{X_{k}\\}_{1\leq k\leq n+1}.$ The Euclidean length of each added edge
is at most $\frac{1}{n^{\theta}}$ and so the weight of each added edge is at
most $\left(\frac{c_{2}}{n^{\theta}}\right)^{\alpha},$ by (1.2).

If $E_{good}(\theta)$ does not occur, we then remove the shortest edge
$(u_{1},v_{1})\in{\cal C}_{n}(j)$ in terms of Euclidean length and add the
edges $(X_{j},u_{1})$ and $(X_{j},v_{1}).$ The Euclidean length of each of
these newly added edges is at most $\sqrt{2}$ and so the corresponding weights
are at most $(c_{2}\sqrt{2})^{\alpha},$ each. Thus we get from the above
discussion that $TSP_{n+1}\leq TSP_{n}(j)+g_{2}(X_{j}),$ where

$g_{2}(X_{j}):=2\left(\frac{c_{2}}{n^{\theta}}\right)^{\alpha}1{1}(E_{good}(\theta))+2(c_{2}\sqrt{2})^{\alpha}1{1}(E^{c}_{good}(\theta)).$

Combining with (3.2), we get

$|TSP_{n+1}-TSP_{n}(j)|\leq g_{1}(X_{j})+g_{2}(X_{j}).$ (3.4)

The following Lemma collects properties regarding $g_{1}$ and $g_{2}$ used
later.

###### Lemma 4

There is a constant $D>0$ such that for all $n$ large,

$\sum_{j=1}^{n+1}\mathbb{E}g_{1}(X_{j})=(n+1)\mathbb{E}g_{1}(X_{n+1})\leq
Dn^{1-\frac{\alpha}{2}},$ (3.5) $g_{1}^{2}(X_{j})\leq D\sum_{v\in{\cal
N}(X_{j},{\cal
C}_{n+1})}d^{\alpha}(X_{j},v),\sum_{j=1}^{n+1}\mathbb{E}g_{1}^{2}(X_{j})=(n+1)\mathbb{E}g_{1}^{2}(X_{1})\leq
2Dn^{1-\frac{\alpha}{2}},$ (3.6) $\mathbb{P}(E_{good}(\theta))\geq
1-\frac{1}{n^{2\theta\alpha}}\text{ and }\max_{1\leq j\leq
n+1}\mathbb{E}g_{2}^{2}(X_{j})\leq\frac{D}{n^{2\theta\alpha}}.$ (3.7)

Moreover,

$\mathbb{E}|TSP_{n+1}-TSP_{n}|\leq\frac{2D}{n^{1-\epsilon}}.$ (3.8)

The proof of (3.8) follows from (3.4) since

$\mathbb{E}|TSP_{n+1}-TSP_{n}|\leq\mathbb{E}g_{1}(X_{j})+\mathbb{E}g_{2}(X_{j})\leq\frac{D}{n^{\frac{\alpha}{2}}}+\frac{D}{n^{2\theta\alpha}}\leq\frac{2D}{n^{1-\epsilon}},$

since both $\frac{\alpha}{2}$ and $2\theta\alpha$ are at least $1-\epsilon,$
by our choice of $\theta$ in (3.3).

_Proof of ( 3.5) in Lemma 4_: Using (1.2), we have that

$g_{1}(X_{j})=(2c_{2})^{\alpha}\sum_{v\in{\cal N}(X_{j},{\cal
C}_{n+1})}d^{\alpha}(X_{j},v)\leq\left(\frac{2c_{2}}{c_{1}}\right)^{\alpha}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}h^{\alpha}(X_{j},v)$

and so

$\sum_{j=1}^{n+1}\mathbb{E}g_{1}(X_{j})\leq\left(\frac{2c_{2}}{c_{1}}\right)^{\alpha}\left(\sum_{j=1}^{n+1}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}h^{\alpha}(X_{j},v)\right).$ (3.9)

The final double summation in (3.9) is simply twice the weight of the TSP
cycle containing all the $n+1$ nodes and so using the expectation upper bound
(1), we get the desired estimate in (3.5).

_Proof of ( 3.6) in Lemma 4_: There are two edges containing $X_{j}$ as an
endvertex in the cycle ${\cal C}_{n+1}$ and so using $(a+b)^{2}\leq
2(a^{2}+b^{2})$ we first get that

$g_{1}^{2}(X_{j})\leq 2(2c_{2})^{2\alpha}\sum_{v\in{\cal N}(X_{j},{\cal
C}_{n+1})}d^{2\alpha}(X_{j},v).$

Since the Euclidean length of any edge is at most $\sqrt{2},$ we have that
$d^{2\alpha}(X_{j},v)\leq(\sqrt{2})^{\alpha}d^{\alpha}(X_{j},v)$ and so

$g_{1}^{2}(X_{j})\leq 2(4c_{2}^{2}\sqrt{2})^{\alpha}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}d^{\alpha}(X_{j},v),$

proving the first relation in (3.6). Consequently

$\displaystyle\sum_{j=1}^{n+1}\mathbb{E}g_{1}^{2}(X_{j})$ $\displaystyle\leq$
$\displaystyle
2(4c_{2}^{2}\sqrt{2})^{\alpha}\mathbb{E}\sum_{j=1}^{n+1}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}d^{\alpha}(X_{j},v)$ (3.10) $\displaystyle\leq$
$\displaystyle
2\left(\frac{4c_{2}^{2}\sqrt{2}}{c_{1}}\right)^{\alpha}\mathbb{E}\sum_{j=1}^{n+1}\sum_{v\in{\cal
N}(X_{j},{\cal C}_{n+1})}h^{\alpha}(X_{j},v),$

using (1.2). As before, the double summation in the right side of (3.10) is
simply twice the weighted TSP length of ${\cal C}_{n+1}$ and so using
expectation upper bound (1), we also get the second estimate in (3.6).

_Proof of ( 3.7) in Lemma 4_: Let $a_{0}<\frac{1}{16\sqrt{2}}$ be a positive
constant and tile the unit square $S$ into
$\frac{8A_{0}}{n^{\theta}}\times\frac{8A_{0}}{n^{\theta}}$ squares
$Q_{l},1\leq l\leq\frac{n^{2\theta}}{64A_{0}^{2}}$ where
$A_{0}=A_{0}(n)\in[a_{0},2a_{0})$ is such that $\frac{n^{\theta}}{8A_{0}}$ is
an integer for all $n$ large. If $Q^{0}_{l}$ is the
$\frac{2A_{0}}{n^{\theta}}\times\frac{2A_{0}}{n^{\theta}}$ square with the
same centre as $Q_{l}$ then the number of nodes $N^{0}_{l}$ of
$\\{X_{i}\\}_{1\leq i\neq j\leq n+1}$ within the square $Q_{l}^{0}$ is
Binomially distributed with mean

$n\int_{Q^{0}_{l}}f(x)dx\geq\epsilon_{1}n\cdot\frac{4A_{0}^{2}}{n^{2\theta}}\geq
4\epsilon_{1}a_{0}^{2}n^{1-2\theta},$

using the bounds for $f(.)$ in (1.1). From the deviation estimate (7.2) in
Appendix we then get that $N^{0}_{l}$ is at least
$2\epsilon_{1}a_{0}^{2}n^{1-2\theta}$ with probability at least
$1-e^{-2D_{1}n^{1-2\theta}},$ for some constant $D_{1}>0.$ Setting

$E_{dense}:=\bigcap_{1\leq
l\leq\frac{n^{2\theta}}{64A_{0}^{2}}}\\{N^{0}_{l}\geq
2\epsilon_{1}a_{0}^{2}n^{1-2\theta}\\},$

we therefore have

$\mathbb{P}(E_{dense})\geq
1-\frac{n^{2\theta}}{64A_{0}^{2}}e^{-2D_{1}n^{1-2\theta}}\geq
1-e^{-D_{1}n^{1-2\theta}}$ (3.11)

for all $n$ large.

The event $E_{dense}$ defined above is useful in the following way. Say that a
$\frac{8A_{0}}{n^{\theta}}\times\frac{8A_{0}}{n^{\theta}}$ square $Q_{l}$ is a
_bad_ square if every edge of the TSP ${\cal C}_{n}(j)$ with one endvertex
within $Q^{0}_{l},$ has its other endvertex outside $Q_{l}$ and let
$E_{no\\_bad}$ be the event that no square in $\\{Q_{k}\\}$ is bad. Suppose
the event $E_{dense}\cap E_{no\\_bad}$ occurs and the (new) node $X_{j}$ is
added to the square $Q_{l}.$ There exists an edge $e=(u,v)$ of the TSP ${\cal
C}_{n}(j)$ with both endvertices in the smaller square $Q^{0}_{l}$ and so the
Euclidean lengths $d(u,v),d(X_{j},u)$ and $d(X_{j},v)$ are each no more than
$\frac{8A_{0}\sqrt{2}}{n^{\theta}},$ the length of the diagonal of $Q_{l}.$
Using $A_{0}\leq 2a_{0}<\frac{1}{8\sqrt{2}}$ (see the first sentence of this
proof) we then that
$\frac{8A_{0}\sqrt{2}}{n^{\theta}}\leq\frac{16a_{0}\sqrt{2}}{n^{\theta}}<\frac{1}{n^{\theta}}$
and so the event $E_{good}(\theta)$ occurs.

In what follows, we estimate the probability of the event $E_{dense}\cap
E_{no\\_bad}.$ Suppose that the event $E_{dense}\cap E^{c}_{no\\_bad}$ occurs
so that there is at least one bad square and let $Q_{l}$ be a bad square so
that each node within the smaller subsquare $Q^{0}_{l}$ belongs to a (long)
edge of the cycle ${\cal C}_{n}(j)$ whose other endvertex lies outside the
bigger square $Q_{l}.$ The Euclidean length of each such long edge is at least
$\frac{3A_{0}}{n^{\theta}},$ the width of the annulus $Q_{l}\setminus
Q^{0}_{l}$ and so using $A_{0}\geq a_{0},$ the weight of the long edge is at
least $\left(\frac{3a_{0}c_{1}}{n^{\theta}}\right)^{\alpha},$ using the bounds
for the weight function $h$ in (1.2). Additionally, since the event
$E_{dense}$ occurs, there are at least $2\epsilon_{1}a_{0}^{2}n^{1-2\theta}$
nodes in $Q^{0}_{l}$ and so

$\displaystyle TSP_{n}(j)1{1}(E_{dense}\cap E^{c}_{no\\_bad})$
$\displaystyle\geq$ $\displaystyle
2\epsilon_{1}a_{0}^{2}n^{1-2\theta}\cdot\left(\frac{3a_{0}c_{1}}{n^{\theta}}\right)^{\alpha}1{1}(E_{dense}\cap
E^{c}_{no\\_bad})$ $\displaystyle=$ $\displaystyle
2\epsilon_{1}a_{0}^{2}(3a_{0}c_{1})^{\alpha}n^{1-(2+\alpha)\theta}1{1}(E_{dense}\cap
E^{c}_{no\\_bad}).$

For any integer constant $k\geq 1,$ we therefore get that

$\mathbb{E}TSP^{k}_{n}(j)1{1}(E_{dense}\cap
E^{c}_{no\\_bad})\geq\left(2\epsilon_{1}a_{0}^{2}(3a_{0}c_{1})^{\alpha}\right)^{k}n^{k(1-(2+\alpha)\theta)}\mathbb{P}(E_{dense}\cap
E^{c}_{no\\_bad}).$

But using the expectation upper bound in (1), we have

$\mathbb{E}TSP^{k}_{n}(j)1{1}(E_{dense}\cap
E^{c}_{no\\_bad})\leq\mathbb{E}TSP^{k}_{n}(j)\leq
D_{1}n^{k\left(1-\frac{\alpha}{2}\right)}$

for some constant $D_{1}>0$ and so $\mathbb{P}\left(E_{dense}\cap
E^{c}_{no\\_bad}\right)\leq\frac{D_{2}}{n^{k\theta_{1}}},$ where $D_{2}>0$ is
a constant and $\theta_{1}:=\frac{\alpha}{2}-(2+\alpha)\theta.$ By choice
$\theta<\frac{\alpha}{2(2+\alpha)}$ (see (3.3)) and so choosing $k$
sufficiently large satisfying $k\theta_{1}>2\theta\alpha,$ we get

$\mathbb{P}\left(E_{dense}\cap
E^{c}_{no\\_bad}\right)\leq\frac{D_{2}}{n^{k\theta_{1}}}\leq\frac{1}{n^{2\theta\alpha}}$

for all $n$ large. Using the bounds for the probability of the event
$E_{dense}$ from (3.11), we then get that

$\mathbb{P}(E_{dense}\cap E_{no\\_bad})\geq
1-e^{-D_{1}n^{1-2\theta}}-\frac{1}{n^{2\theta\alpha}}\geq
1-\frac{2}{n^{2\theta\alpha}}$

for all $n$ large. This implies that $\mathbb{P}(E_{good}(\theta))\geq
1-\frac{2}{n^{2\theta\alpha}}.$

### Variance upper bound for TSP

We use one node difference estimate (3.4) together with the martingale
difference method to obtain a bound for the variance. For $1\leq j\leq
n~{}+~{}1,$ let ${\cal F}_{j}=\sigma\left(\\{X_{k}\\}_{1\leq k\leq j}\right)$
denote the sigma field generated by the node positions $\\{X_{k}\\}_{1\leq
k\leq j}.$ Defining the martingale difference

$H_{j}=\mathbb{E}(TSP_{n+1}|{\cal F}_{j})-\mathbb{E}(TSP_{n+1}|{\cal
F}_{j-1}),$ (3.12)

we then have that $TSP_{n+1}-\mathbb{E}TSP_{n+1}=\sum_{j=1}^{n+1}H_{j}$ and so
by the martingale property

$var(TSP_{n+1})=\mathbb{E}\left(\sum_{j=1}^{n+1}H_{j}\right)^{2}=\sum_{j=1}^{n+1}\mathbb{E}H_{j}^{2}.$
(3.13)

To evaluate $\mathbb{E}H_{j}^{2}$ we rewrite the martingale difference $H_{j}$
in a more convenient form. Letting $X^{\prime}_{j}$ be an independent copy of
$X_{j}$ which is also independent of $\\{X_{k}\\}_{1\leq k\neq j\leq n+1}$ we
rewrite

$H_{j}=\mathbb{E}(TSP_{n+1}(X_{j})-TSP_{n+1}(X^{\prime}_{j})|{\cal F}_{j}),$
(3.14)

where $TSP_{n+1}(X_{j})$ is the weight of the MST formed by the nodes
$\\{X_{i}\\}_{1\leq i\leq n+1}$ and $TSP_{n+1}(X^{\prime}_{j})$ is the weight
of the TSP formed by the nodes
$\\{X_{i}\\}_{1\leq i\neq j\leq n+1}~{}\cup~{}\\{X^{\prime}_{j}\\}.$ Using the
triangle inequality and the one node difference estimate (3.4), we have that
$|TSP_{n+1}(X_{j})-TSP_{n+1}(X^{\prime}_{j})|$ is bounded above as

$\displaystyle|TSP_{n+1}(X_{j})-TSP_{n}(j)|+|TSP_{n+1}(X^{\prime}_{j})-TSP_{n}(j)|$
$\displaystyle\;\;\;\leq\;\;g_{1}(X_{j})+g_{2}(X_{j})+g_{1}(X^{\prime}_{j})+g_{2}(X^{\prime}_{j}),$

where $g_{1}$ and $g_{2}$ are as in (3.4) and we recall that $TSP_{n}(j)$ is
the weight of the MST formed by the nodes $\\{X_{k}\\}_{1\leq k\neq j\leq
n+1}.$ Thus

$\displaystyle|H_{j}|$ $\displaystyle\leq$
$\displaystyle\mathbb{E}(|TSP_{n+1}(X_{j})-TSP_{n+1}(X^{\prime}_{j})||{\cal
F}_{j})$ $\displaystyle\leq$ $\displaystyle\mathbb{E}(g_{1}(X_{j})|{\cal
F}_{j})+\mathbb{E}(g_{2}(X_{j})|{\cal
F}_{j})+\mathbb{E}(g_{1}(X^{\prime}_{j})|{\cal
F}_{j})+\mathbb{E}(g_{2}(X^{\prime}_{j})|{\cal F}_{j})$ $\displaystyle=$
$\displaystyle\mathbb{E}(g_{1}|{\cal F}_{j})+\mathbb{E}(g_{2}|{\cal
F}_{j})+\mathbb{E}(g_{1}|{\cal F}_{j-1})+\mathbb{E}(g_{2}|{\cal F}_{j-1}).$

Using $(a_{1}+a_{2}+a_{3}+a_{4})^{2}\leq
4(a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+a_{4}^{2}),$ we then get

$\displaystyle H_{j}^{2}$ $\displaystyle\leq$ $\displaystyle
4\left(\left(\mathbb{E}(g_{1}|{\cal
F}_{j})\right)^{2}+\left(\mathbb{E}(g_{2}|{\cal
F}_{j})\right)^{2}+\left(\mathbb{E}(g_{1}|{\cal
F}_{j-1})\right)^{2}+\left(\mathbb{E}(g_{2}|{\cal F}_{j-1})\right)^{2}\right)$
$\displaystyle\leq$ $\displaystyle 4\left(\mathbb{E}(g^{2}_{1}|{\cal
F}_{j})+\mathbb{E}(g^{2}_{2}|{\cal F}_{j})+\mathbb{E}(g^{2}_{1}|{\cal
F}_{j-1})+\mathbb{E}(g^{2}_{2}|{\cal F}_{j-1})\right)$

since $(\mathbb{E}(X|{\cal F}))^{2}\leq\mathbb{E}(X^{2}|{\cal F}).$ Thus
$\mathbb{E}H_{j}^{2}\leq
8\left(\mathbb{E}g_{1}^{2}(X_{j})+\mathbb{E}g_{2}^{2}(X_{j})\right)$ and
plugging this in (3.13), we have

$var(TSP_{n+1})=\sum_{j=1}^{n+1}\mathbb{E}H_{j}^{2}\leq
8\left(\sum_{j=1}^{n+1}\mathbb{E}g_{1}^{2}(X_{j})+\sum_{j=1}^{n+1}\mathbb{E}g_{2}^{2}(X_{j})\right).$

Plugging the estimates for $\mathbb{E}g_{1}^{2}(X_{j})$ and
$\mathbb{E}g_{2}^{2}(X_{j})$ from (3.6) and (3.7), respectively, we get
$var(TSP_{n+1})\leq
D\left(n^{1-\frac{\alpha}{2}}+n^{1-2\theta\alpha}\right)\leq 2Dn^{\epsilon}$
for some constant $D>0,$ by our choice of $\theta$ in (3.3).

##  4 Variance lower bound for $TSP_{n}$

###### Theorem 5

Suppose there is a square $S_{0}$ with a constant side length $s_{0}$ such
that $h(u,v)=d(u,v)$ if either $u$ or $v$ is in $S_{0}.$ For every $\alpha<1,$
there is positive constant $D_{2}$ such that

$var(TSP_{n})\geq D_{2}n^{1-\alpha}$

for all $n$ large.

We indirectly compute the variance lower bound for the TSP by computing a
related spanning path ${\cal P}_{app}(n+1)$ which has approximately the same
length as the TSP of the nodes $\\{X_{i}\\}_{1\leq i\leq n+1}$ and estimate
the variance of the weight of ${\cal P}_{app}(n+1).$ Using this estimate, we
obtain the desired variance lower bound for $TSP_{n+1}.$

We tile the unit square $S$ into disjoint
$\frac{400A}{\sqrt{n}}\times\frac{400A}{\sqrt{n}}$ squares $\\{R_{i}\\}$ where
$1\leq A\leq 1+\frac{1}{\log{n}}$ is such that $\frac{\sqrt{n}}{400A}$ is an
integer for all $n$ large. This is possible by an argument following (2.1).
Let $R(1)\in\\{R_{i}\\}$ be the (random) square containing the node $X_{1}$
and let $R^{small}(1)$ be the
$\frac{200A}{\sqrt{n}}\times\frac{200A}{\sqrt{n}}$ square with the same centre
as $R(1)$ and contained in $R(1).$

Let ${\cal P}_{in}(n+1)$ be the minimum weight spanning path formed by the
nodes of $\\{X_{i}\\}_{1\leq i\leq n+1}$ present within the square
$R^{small}(1)$ and let $u_{in}$ and $v_{in}$ be the endvertices of ${\cal
P}_{in}(n+1).$ We define ${\cal P}_{in}(n+1)$ to be the minimum weight _in-
spanning path_. Let $v_{close}$ be the node closest (in terms of Euclidean
length) to but outside $R^{small}(1)$ and suppose $v_{in}$ is closer in terms
of Euclidean length to $v_{close}$ than $u_{in}.$ We define
$e_{min}=(v_{in},v_{close})$ to be the _cross edge_. Finally, let ${\cal
P}_{out}(n+1)$ be the minimum weight spanning path formed by the nodes of
$\\{X_{i}\\}_{1\leq i\leq n+1}$ present outside $R^{small}(1)$ and having
$v_{close}$ as an endvertex. We denote ${\cal P}_{out}(n+1)$ to be the minimum
weight _out-spanning path_. By construction, the union

${\cal P}_{app}(n+1)={\cal P}_{app}(n+1,\\{X_{i}\\}_{1\leq i\leq n+1}):={\cal
P}_{in}(n+1)\cup\\{e_{min}\\}\cup{\cal P}_{out}(n+1)$ (4.1)

is an _overall spanning path_ containing all the nodes $\\{X_{i}\\}_{1\leq
i\leq n+1}$ and we define ${\cal P}_{app}(n~{}+~{}1)$ to be the _approximate
overall TSP path_.

As in (1.3), we define $W_{n+1}:=W({\cal P}_{app}(n+1))=\sum_{e\in{\cal
P}_{app}(n+1)}h^{\alpha}(e)$ to be the weight of the approximate overall TSP
path ${\cal P}_{app}(n+1)$ and recall that $TSP_{n+1}$ is the minimum weight
of the overall spanning cycle containing all the $n+1$ nodes
$\\{X_{i}\\}_{1\leq i\leq n+1}.$ The following result shows that the
approximate overall TSP path has nearly the same weight as the optimal overall
TSP cycle and obtains a lower bound on the variance.

###### Lemma 6

There exists a constant $D>0$ such that

$\mathbb{E}|TSP_{n+1}-W_{n+1}|^{2}\leq D(\log{n})^{2}$ (4.2)

and

$var(W_{n+1})\geq D\cdot n^{1-\alpha}$ (4.3)

for all $n$ large.

From the bounds in Lemma 6, we obtain a lower bound for the variance of
$TSP_{n+1}$ as follows. Using $(a+b)^{2}\leq 2(a^{2}+b^{2})$ we have for any
two random variables $X$ and $Y$ that

$var(X+Y)\leq 2(var(X)+var(Y))\leq 2var(X)+2\mathbb{E}Y^{2}.$

Setting $X=TSP_{n+1},Y=W_{n+1}-TSP_{n+1}$ and using the bounds in Lemma 6, we
therefore get

$\displaystyle var(TSP_{n+1})$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\cdot var(W_{n+1})-\mathbb{E}|TSP_{n+1}-W_{n+1}|^{2}$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}\cdot D\cdot
n^{1-\alpha}-D(\log{n})^{2},$

obtaining the desired bound on the variance of $TSP_{n+1}.$

_Proof of ( 4.2) in Lemma 6_: Joining the endvertices of the approximate
overall TSP path ${\cal P}_{app}(n+1)$ by an edge, we get an overall spanning
cycle containing all the nodes $\\{X_{i}\\}_{1\leq i\leq n+1}.$ The added edge
has a Euclidean length of at most $\sqrt{2}$ and so a weight of at most
$(c_{2}\sqrt{2})^{\alpha},$ by (1.2). Thus

$TSP_{n+1}\leq W_{n+1}+(c_{2}\sqrt{2})^{\alpha}.$ (4.4)

To get an estimate in the other direction, we first get from (4.1) that

$W_{n+1}=W({\cal P}_{in}(n+1))+h^{\alpha}(e_{min})+W({\cal P}_{out}(n+1))$

and estimate the lengths of ${\cal P}_{in}(n+1),e_{min}$ and ${\cal
P}_{out}(n+1)$ in that order. If $N_{in}$ is the number nodes of
$\\{X_{i}\\}_{1\leq i\leq n+1}$ present in the square $R^{small}(1),$ then the
number of edges in the in-spanning path ${\cal P}_{in}(n+1)$ is
$N_{in}-1~{}<~{}N_{in}.$ As argued before, each such edge has a weight of at
most $(c_{2}\sqrt{2})^{\alpha}$ and so $W({\cal P}_{in}(n+1))\leq
N_{in}\cdot(c_{2}\sqrt{2})^{\alpha}.$ Similarly
$h^{\alpha}(e_{min})\leq(c_{2}\sqrt{2})^{\alpha}.$

We now find bounds for $W({\cal P}_{out}(n+1))$ in terms of $TSP_{n+1}$ as
follows. We recall that ${\cal P}_{out}(n+1)$ is an out-spanning path with
vertex set being the nodes of $\\{X_{i}\\}_{1\leq i\leq n+1}$ outside
$R^{small}(1).$ Also ${\cal P}_{out}(n+1)$ has $v_{close}$ as an endvertex,
where $v_{close}$ is the node closest to but outside $R^{small}(1).$ We
therefore obtain an upper bound for $W({\cal P}_{out}(n+1))$ by constructing
an out-spanning path ${\cal P}_{fin}$ with $v_{close}$ as an endvertex,
starting from the overall spanning cycle ${\cal
C}_{n+1}=(u_{1},\ldots,u_{n+1},u_{1})$ with weight $TSP_{n+1}.$

Let
$(u_{j_{1}},\ldots,u_{j_{2}}),(u_{j_{3}},\ldots,u_{j_{4}}),\ldots,(u_{j_{s}},\ldots,u_{j_{s+1}})$
be the subpaths of ${\cal C}_{n+1}$ that are contained within the square
$R^{small}(1)$ in the following sense: For example in the path
$(u_{j_{1}},\ldots,u_{j_{2}}),$ the nodes $u_{j_{1}}$ and $u_{j_{2}}$ are
present outside $R^{small}(1)$ and the rest of the nodes are present inside
$R^{small}(1).$ Removing all these subpaths and adding the edges
$(u_{j_{1}},u_{j_{2}}),(u_{j_{3}},u_{j_{4}}),\ldots,(u_{j_{s-1}},u_{j_{s}}),$
we therefore get an out-spanning cycle ${\cal C}_{temp}.$ Further removing an
edge containing $v_{close}$ from ${\cal C}_{temp},$ we get an out-spanning
path ${\cal P}_{fin}$ having $v_{close}$ as an endvertex. Thus $W({\cal
P}_{out}(n+1))\leq W({\cal P}_{fin})$ and it suffices to upper bound $W({\cal
P}_{fin}).$

Recalling that $N_{in}$ is the number nodes of $\\{X_{i}\\}_{1\leq i\leq n+1}$
present in $R^{small}(1),$ we get that the total number of edges added in the
above procedure is at most $s\leq N_{in}.$ As argued before, the weight of any
edge is at most $(c_{2}\sqrt{2})^{\alpha}$ by (1.2) and so

$W({\cal P}_{out}(n+1))\leq W({\cal P}_{fin})\leq
TSP_{n+1}+N_{in}\cdot(c_{2}\sqrt{2})^{\alpha}.$

Combining this with the estimates for $W({\cal P}_{in}(n+1))$ and the weight
of the edge $e_{min}$ obtained before, we get

$W_{n+1}\leq TSP_{n+1}+(2N_{in}+1)\cdot(c_{2}\sqrt{2})^{\alpha}.$

and so from (4.4) we get

$|W_{n+1}-TSP_{n+1}|\leq(2N_{in}+2)\cdot(c_{2}\sqrt{2})^{\alpha}.$

Taking expectations we get

$\mathbb{E}|W_{n+1}-TSP_{n+1}|^{2}\leq
4\cdot(c_{2}\sqrt{2})^{2\alpha}\cdot\mathbb{E}(N_{in}+1)^{2}.$

and we prove below that $\mathbb{E}(N_{in}+1)^{2}\leq 2(\log{n})^{2},$ thus
obtaining (4.2).

To estimate $N_{in},$ we write $N_{in}\leq\max_{i}N(R_{i}),$ where $N(R_{i})$
is the number of nodes of $\\{X_{l}\\}_{1\leq l\leq n+1}$ in the square
$R_{i}.$ Any square in $\\{R_{i}\\}$ has an area of $\frac{10^{4}A^{2}}{n}$
and so using (1.1) and $A\leq 1+\frac{1}{\log{n}}\leq 2,$ we get that
$N(R_{i})$ is Binomially distributed with a mean and a variance of at most
$\epsilon_{2}(n+1)\frac{10^{4}A^{2}}{n}\leq D_{1}$ for some constant
$D_{1}\geq 1.$ Therefore from the proof of the deviation estimate (7.1) in
Appendix, we get for $s>0$ that $\mathbb{E}e^{sN(R_{i})}\leq
e^{D_{1}(e^{s}-1)}$ and so by Chernoff bound,

$\mathbb{P}(N(R_{i})\geq\log{n})\leq
e^{-s\log{n}}e^{D_{1}(e^{s}-1)}\leq\frac{D_{2}}{n^{4}}$

by setting $s=4$ and $D_{2}=e^{D_{1}(e^{4}-1)}.$ Since there are at most
$\frac{n}{10^{4}A^{2}}$ squares in $\\{R_{i}\\}$ we further get

$\mathbb{P}(\max_{i}N(R_{i})\geq\log{n})\leq\frac{n}{10^{4}A^{2}}\cdot\frac{D_{2}}{n^{4}}\leq\frac{D_{3}}{n^{3}}$
(4.5)

for some constant $D_{3}>0$ and so

$\displaystyle\mathbb{E}(N_{in}+1)^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}(N_{in}+1)^{2}1{1}(\max_{i}N(R_{i})\leq\log{n})$
$\displaystyle\;\;\;\;\;+\;\;\mathbb{E}(N_{in}+1)^{2}1{1}(\max_{i}N(R_{i})>\log{n})$
$\displaystyle\leq$
$\displaystyle(\log{n}+1)^{2}+\mathbb{E}(N_{in}+1)^{2}1{1}(\max_{i}N(R_{i})>\log{n}).$

Using $N_{in}\leq n+1$ and (4.5), we get

$\displaystyle\mathbb{E}(N_{in}+1)^{2}1{1}(\max_{i}N(R_{i})>\log{n})$
$\displaystyle\leq$
$\displaystyle(n+1)^{2}\mathbb{P}(\max_{i}N(R_{i})>\log{n})$
$\displaystyle\leq$ $\displaystyle(n+1)^{2}\cdot\frac{D_{3}}{n^{3}}$
$\displaystyle\leq$ $\displaystyle 1$

for all $n$ large. Thus $\mathbb{E}(N_{in}+1)^{2}\leq 2(\log{n})^{2},$ proving
the desired estimate.

_Proof of ( 4.3) in Lemma 6_ We perform some preliminary computations. As in
the proof of the variance upper bound for $1\leq j\leq n+1$ we let ${\cal
F}_{j}$ denote the sigma field generated by the nodes $\\{X_{i}\\}_{1\leq
i\leq j}$ and define the martingale difference $G_{j}=\mathbb{E}(W_{n+1}|{\cal
F}_{j})-\mathbb{E}(W_{n+1}|{\cal F}_{j-1})$ so that

$var(W_{n+1})=\left(\sum_{j=1}^{n+1}\mathbb{E}G_{j}\right)^{2}=\sum_{j=1}^{n+1}\mathbb{E}G_{j}^{2},$
(4.6)

by the martingale property. To evaluate $\mathbb{E}G_{j}^{2}$ we rewrite the
martingale difference $G_{j}$ in a more convenient form as

$G_{j}=\mathbb{E}(W_{n+1}(X_{j})-W_{n+1}(X^{\prime}_{j})|{\cal F}_{j}),$ (4.7)

where $X^{\prime}_{j}$ is an independent copy of $X_{j},$ also independent of
$\\{X_{i}\\}_{1\leq i\neq j\leq n+1}$ and $W_{n+1}(X_{j})$ and
$W_{n+1}(X^{\prime}_{j})$ are the weights of the approximate TSP paths formed
by the nodes $\\{X_{i}\\}_{1\leq i\leq n+1}$ and $\\{X_{i}\\}_{1\leq i\neq
j\leq n+1}\cup\\{X^{\prime}_{j}\\}.$ In words,
$W_{n+1}(X_{j})-W_{n+1}(X^{\prime}_{j})$ represents the change in the length
of the approximate overall TSP path after “replacing” the node $X_{j}$ by
$X^{\prime}_{j}.$

Below we define an event $E_{good}(j)$ with the following properties:
$(p1)$ There exists a constant $D>0$ not depending on $j$ such that

$(W_{n+1}(X_{j})-W_{n+1}(X^{\prime}_{j}))1{1}(E_{good}(j))\geq D\cdot
n^{-\frac{\alpha}{2}}\cdot 1{1}(E_{good}(j)).$

$(p2)$ The minimum probability $\min_{2\leq j\leq
n+1}\mathbb{P}(E_{good}(j))\geq c_{0}$ for some constant $c_{0}>0.$
Assuming $(p1)-(p2),$ we get from the expression for $G_{j}$ in (4.7) that

$\mathbb{E}|G_{j}|\geq\mathbb{E}|G_{j}|1{1}(E_{good}(j))=\mathbb{E}G_{j}1{1}(E_{good}(j))\geq
Dn^{-\frac{\alpha}{2}}\mathbb{P}(E_{good}(j))\geq
Dn^{-\frac{\alpha}{2}}c_{0}.$

Thus from (4.6), we have

$var(W_{n+1})\geq\sum_{j=2}^{n+1}\mathbb{E}G^{2}_{j}\geq\sum_{j=2}^{n+1}(\mathbb{E}|G_{j}|)^{2}\geq
D^{2}c_{0}^{2}n^{1-\alpha},$

proving (4.3).

_Proof of $(p1)-(p2)$_: We recall the tiling of the unit square $S$ into small
$\frac{400A}{\sqrt{n}}\times\frac{400A}{\sqrt{n}}$ squares $\\{R_{i}\\}.$ The
side length of the smaller square $S_{0}\subseteq S$ is $s_{0},$ a constant
and there are
$W\geq\frac{1}{2}\cdot\left(\frac{s_{0}\sqrt{n}}{400A}\right)^{2}$ squares of
$\\{R_{i}\\}$ completely contained in $S_{0},$ which we label as
$R_{1},\ldots,R_{W}.$ For each square $R_{i},$ we let
$R_{i}^{B},R_{i}^{C},R_{i}^{D}$ and $R_{i}^{E}$ be
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ subsquares contained in $R_{i},$
as illustrated in Figure 4, equidistant from the left and right sides of
$R_{i}.$ Say that $R_{i}$ is a $j-$good square if the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ square $R_{i}^{B}$ contains a
single node of $\\{X_{k}\\}_{2\leq k\neq j\leq n+1}$ and the rest of $R_{i}$
does not contain any node of $\\{X_{k}\\}_{2\leq k\neq j\leq n+1}.$ Recalling
that $R(1)\in\\{R_{i}\\}$ is the random square containing the node $X_{1},$ we
define the event

$\displaystyle E_{good}(j)$ $\displaystyle:=$
$\displaystyle\\{R(1)\in\\{R_{i}\\}_{1\leq i\leq W}\\}\cap\\{R(1)\text{ is
}j-\text{good}\\}$ (4.8) $\displaystyle\;\;\;\;\cap\\{X_{1}\in
R^{C}(1)\\}\cap\\{X^{\prime}_{j}\in R^{D}(1)\\}\cap\\{X_{j}\in R^{E}(1)\\}.$

Figure 4: The $a\times a$ squares $R^{B}_{i},R^{C}_{i},R^{D}_{i}$ and
$R^{E}_{i}$ contained within the $400a\times 400a$ square $R_{i}$ with
$a=\frac{A}{\sqrt{n}}.$ The $200a\times 200a$ square denotes $R^{small}_{i}$
and the centres of all the $a\times a$ squares are equidistant from the left
and right sides of $R_{i}.$

Assuming the event $E_{good}(j)$ occurs, we now determine the change in the
weight of the approximate overall TSP path upon “replacing” the node $X_{j}$
with the node $X^{\prime}_{j}.$ The square $R(1)$ containing the node $X_{1}$
is contained within the square $S_{0}$ and so the weight of any edge with an
endvertex in $R(1)$ is simply the Euclidean length of the edge (see statement
of the Theorem). Since there are only two nodes $\\{X_{j},X_{1}\\}$ present in
the square $R^{small}(1)\subset R(1),$ the in-spanning path ${\cal
P}_{in}(n~{}+~{}1)$ is the single edge $(X_{j},X_{1}).$

Next, the node $v$ present in the subsquare $R^{B}(1)\subset R(1)$ is _the_
node closest to but outside $R^{small}(1)$ and $v$ is closer to $X_{1}\in
R^{C}(1)$ than $X_{j}\in R^{D}(1).$ Therefore $v_{close}=v$ and the minimum
length cross edge $e_{min}=(X_{1},v).$ Combining we get

${\cal P}_{app}(n+1)={\cal P}_{app}\left(n+1,\\{X_{i}\\}_{1\leq i\leq
n+1}\right)={\cal P}_{out}(n+1)\cup\\{(X_{1},X_{j})\\}\cup\\{(X_{1},v)\\}.$
(4.9)

By an analogous analysis we have

${\cal P}_{app}\left(n+1,\\{X_{i}\\}_{1\leq i\neq j\leq n+1}\cup
X^{\prime}_{j}\right)={\cal
P}_{out}(n+1)\cup\\{(X_{1},X^{\prime}_{j})\\}\cup\\{(X_{1},v)\\}.$ (4.10)

Denoting $W_{n+1}(X_{j})$ and $W_{n+1}(X^{\prime}_{j})$ to be the respective
weights of the approximate paths formed by $\\{X_{i}\\}_{1\leq i\leq n+1}$ and
$\\{X_{i}\\}_{1\leq i\neq j\leq n+1}\cup\\{X^{\prime}_{j}\\},$ we get from
(4.9) and (4.10) that

$\displaystyle W_{n+1}(X_{j})1{1}(E_{good}(j))$ $\displaystyle=$
$\displaystyle W_{n+1}(X^{\prime}_{j})1{1}(E_{good}(j))$
$\displaystyle\;\;\;\;+\;\;\left(d^{\alpha}(X_{1},X_{j})-d^{\alpha}(X_{1},X^{\prime}_{j})\right)1{1}(E_{good}(j))$

since $X_{1},X_{j}$ and $X^{\prime}_{j}$ belong to $S_{0}$ and so as metioned
before, the weight of the edges is simply the corresponding Euclidean lengths
raised to the power $\alpha.$

From Figure 4, we have that the squares $R^{C}(1),R^{D}(1)$ and $R^{E}(1)$ are
spaced $10a$ apart. Since the nodes $X_{1}\in R^{C}(1),X^{\prime}_{j}\in
R^{D}(1)$ and $X_{j}\in R^{E}(1),$ we have that $d(X_{1},X_{j})\geq
d(X_{1},X^{\prime}_{j})+10a$ and $10a\leq d(X_{1},X^{\prime}_{j})\leq 14a.$
Thus

$d^{\alpha}(X_{1},X_{j})=(d(X_{1},X^{\prime}_{j})+10a)^{\alpha}\geq(20a)^{\alpha}$

and so we get from (LABEL:one_diff_wl) that

$W_{n+1}(X_{j})1{1}(E_{good}(j))\geq
W_{n+1}(X^{\prime}_{j})1{1}(E_{good}(j))+((20a)^{\alpha}-(14a)^{\alpha})1{1}(E_{good}(j)).$
(4.12)

Setting $a=\frac{A}{\sqrt{n}}$ and using $A\geq 1,$ we finally get

$\displaystyle W_{n+1}(X_{j})1{1}(E_{good}(j))$ $\displaystyle\geq$
$\displaystyle W_{n+1}(X^{\prime}_{j})1{1}(E_{good}(j))$
$\displaystyle\;\;\;\;+\;\;((20)^{\alpha}-(14)^{\alpha})\cdot\left(\frac{1}{\sqrt{n}}\right)^{\alpha}1{1}(E_{good}(j)),$

It remains to estimate the probability of the event $E_{good}(j)$ and we use
Poissonization. None of the constants appearing below depend on the index $j.$
As before, we let ${\cal P}$ be a Poisson process with intensity $nf(.)$ in
the unit square with corresponding probability measure $\mathbb{P}_{0}.$ A
$\frac{400A}{\sqrt{n}}\times\frac{400A}{\sqrt{n}}$ square in
$R_{i}\in\\{R_{k}\\}$ is good if the
$\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$ subsquare $R^{B}_{i}$ contains
exactly one node of ${\cal P}$ and the rest of $R_{i}$ contains no node of
${\cal P}.$ The mean number of nodes of ${\cal P}$ in $R_{i}$ is
$n\int_{R_{i}}f(x)dx$ and $\mathbb{P}_{0}\left(R_{i}\text{ contains exactly
one node of }{\cal P}\right)$ equals

$n\int_{R_{i}}f(x)dx\exp\left(-n\int_{R_{i}}f(x)dx\right)\geq
A^{2}\epsilon_{1}e^{-A^{2}\epsilon_{2}}\geq\epsilon_{1}e^{-4\epsilon_{2}}$
(4.14)

where the first inequality in (4.14) follows from the bounds for $f(.)$ in
(1.1) and the second inequality in (4.14) is true since $1\leq A\leq
1+\frac{1}{\log{n}}\leq 2.$ Given that $R_{i}$ contains a single node of
${\cal P},$ the node is distributed in $R_{i}$ with density $f(.)$ and so is
present in the subsquare $R^{B}_{i}$ with conditional probability
$\frac{\int_{R^{B}_{i}}f(x)dx}{\int_{R_{i}}f(x)dx}\geq\frac{\epsilon_{1}}{(400)^{2}\epsilon_{2}},$
again using the bounds for $f(.)$ in (1.1); i.e.,

$\mathbb{P}_{0}\left(R_{i}\text{ is good}|R_{i}\text{ contains exactly one
node of }{\cal
P}\right)=\frac{\int_{R^{B}_{i}}f(x)dx}{\int_{R_{i}}f(x)dx}\geq\frac{\epsilon_{1}}{(400)^{2}\epsilon_{2}}.$
(4.15)

Combining (4.15) and (4.14) we get that $\mathbb{P}_{0}(R_{i}\text{ is
good})\geq p_{0}$ for some constant $p_{0}>0$ not depending on $i.$ The
Poisson process is independent on disjoint sets and so
$N_{good}=\sum_{i=1}^{W}1{1}(R_{i}\text{ is good})$ is a sum of independent
Bernoulli random variables with mean at least $p_{0},$ where we recall that
$\\{R_{i}\\}_{1\leq i\leq W}$ are all the squares contained completely inside
the smaller square $S_{0}.$ Using the standard deviation estimate (7.2) in
Appendix with $m=W,\mu_{1}=p_{0}$ and $\epsilon=\frac{1}{2},$ we therefore
have that $\mathbb{P}_{0}\left(N_{good}\geq\frac{p_{0}W}{2}\right)\geq
1-e^{-C_{1}W}\geq 1-e^{-2C_{2}n}$ for some positive constants $C_{1}$ and
$C_{2},$ since
$W\geq\frac{1}{2}\cdot\left(\frac{s_{0}\sqrt{n}}{400A}\right)^{2}$ (see
discussion prior to (4.8)).

Using the dePoissonization formula (2.4), we therefore get that

$\mathbb{P}\left(N_{good}\geq\frac{p_{0}W}{2}\right)\geq
1-C_{3}\sqrt{n}e^{-2C_{2}n}\geq 1-e^{-C_{2}n}$

where $N_{good}$ is the number of $j-$good squares (containing exactly one
node of $\\{X_{k}\\}_{2\leq k\neq j\leq n+1}$) contained within $S_{0}.$ Given
that $N_{good}\geq\frac{p_{0}W}{2}\geq C_{4}n,$ where $C_{4}>0$ is a constant
(see previous paragraph), the nodes $X_{1},X^{\prime}_{j}$ and
$X^{\prime}_{j}$ are all present in the same
$\frac{400A}{\sqrt{n}}\times\frac{400A}{\sqrt{n}}$ good square $R_{i}\subset
S_{0}$ in the corresponding $\frac{A}{\sqrt{n}}\times\frac{A}{\sqrt{n}}$
subsquares $R^{C}_{i},R^{D}_{i}$ and $R^{E}_{i}$ with probability at least
$\left(\frac{p_{0}W}{2}\epsilon_{1}\frac{A^{2}}{n}\right)^{3}\geq p_{1}$ for
some constant $p_{1}>0,$ using the bounds for $f(.)$ in (1.1). From (4.8) we
therefore get that $\mathbb{P}(E_{good}(j))\geq p_{1}(1-e^{-C_{2}n}).$

##  5 Proof of convergence results

In this section, we obtain convergence results for $TSP_{n}$ appropriately
scaled and centred. We have the following result.

###### Theorem 7

$(i)$ If $0<\alpha<2(\sqrt{2}-1),$ then

$\frac{1}{n^{1-\frac{\alpha}{2}}}\left(TSP_{n}-\mathbb{E}TSP_{n}\right)\longrightarrow
0\text{ a.s.}$

as $n\rightarrow\infty.$
$(ii)$Suppose the edge weight function $h$ is a metric and the edge weight
exponent is $0<\alpha<1.$ We have that

$\frac{1}{n^{1-\frac{\alpha}{2}}}\left(TSP_{n}-\mathbb{E}TSP_{n}\right)\longrightarrow
0\text{a.s.\ }$

as $n\rightarrow\infty.$

The advantage of allowing $h$ to be a metric is that the TSP length satisfies
the monotonocity property if the edge weight exponent is $\alpha\leq 1;$ in
other words, adding more nodes increases the length of the TSP. We then obtain
a.s. convergence via a subsequence argument by simply considering an upper
bound on the TSP formed by the nodes with indices present outside the
subsequence (see Section 5).

To construct an example of $h$ which is a metric, we recall that
$S=\left[-\frac{1}{2},\frac{1}{2}\right]^{2}$ is the unit square and define
$h_{1}:S\rightarrow(0,\infty)$ as $h_{1}(u,v)=|(1+u)^{2}-(1+v)^{2}|$ for
$u,v\in\left[-\frac{1}{2},\frac{1}{2}\right]$ so that $h_{1}$ is a metric.
Also,

$|u-v|\leq h_{1}(u,v)=|u-v|(2+u+v)\leq 3|u-v|.$ (5.1)

For $x=(x_{1},x_{2}),y=(y_{1},y_{2}),$ define

$h(x,y)=h_{1}(x_{1},y_{1})+h_{1}(x_{2},y_{2})$

so that $h$ is a metric in $S$ and using (5.1) we also get

$d(x,y)\leq|x_{1}-y_{1}|+|x_{2}-y_{2}|\leq h(x,y)\leq
3(|x_{1}-y_{1}|+|x_{2}-y_{2}|)\leq 3\sqrt{2}d(x,y).$

To prove Theorem 7, we have the following preliminary lemma. We recall that
$TSP_{k}$ denotes the length of the TSP cycle formed by the nodes
$\\{X_{i}\\}_{1\leq i\leq k}$ as defined in (1.4). For a constant $M>0$ we let

$J_{n}=J_{n}(M):=\max_{n^{M}\leq k<(n+1)^{M}}\left|TSP_{k}-TSP_{n^{M}}\right|$
(5.2)

and have the following result.

###### Lemma 8

There is a constant $D>0$ such that

$\mathbb{E}\left(\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)\leq\frac{D}{n^{1-\frac{\alpha}{2}}}\text{
and
}\mathbb{E}\left(\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)^{2}\leq\frac{D}{n^{2-y}},$
(5.3)

where $y=\max\left(M\frac{\alpha}{2},\alpha\right).$ If the edge weight
function $h$ is a metric and $0<\alpha\leq 1,$ then

$\mathbb{E}\left(\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)\leq\frac{D}{n^{1-\frac{\alpha}{2}}}\text{
and
}\mathbb{E}\left(\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)^{2}\leq\frac{D}{n^{2-\alpha}}.$
(5.4)

_Proof of ( 5.3) in Lemma 8_: From the partial one node estimate (3.1), we
have that $TSP_{l}\leq TSP_{l+1}+g_{1,l},$ where $g_{1,l}\geq 0$ is such that

$\max\left(\mathbb{E}g_{1,l},\mathbb{E}g^{2}_{1,l}\right)\leq\frac{D}{l^{\frac{\alpha}{2}}}$
(5.5)

for some constant $D_{1}>0,$ using estimates (3.5) and (3.6). For $n^{M}+1\leq
k<(n+1)^{M},$ we therefore have

$TSP_{n^{M}}\leq TSP_{k}+\sum_{l=n^{M}}^{k}g_{1,l}.$

To get an estimate in the reverse direction, we use relation (7.4) in Appendix
and get that

$TSP_{k}\leq
TSP_{n^{M}}+TSP(X_{n^{M}+1},\ldots,X_{k})+(c_{2}\sqrt{2})^{\alpha}.$

Combining we get $J_{n}\leq J_{n,1}+J_{n,2}+(c_{2}\sqrt{2})^{\alpha}$ where

$J_{n,1}:=\sum_{l=n^{M}}^{(n+1)^{M}}g_{1,l}\text{ and
}J_{n,2}:=\max_{n^{M}+1\leq k<(n+1)^{M}}TSP(X_{n^{M}+1},\ldots,X_{k}).$

We evaluate $J_{n,1}$ and $J_{n,2}$ separately. Using (5.5), we have that

$\mathbb{E}J_{n,1}\leq\sum_{l=n^{M}}^{(n+1)^{M}}\frac{D}{l^{\frac{\alpha}{2}}}\leq((n+1)^{M}-n^{M})\frac{D}{n^{\frac{M\alpha}{2}}}\leq\frac{2MD}{n}\cdot
n^{M\left(1-\frac{\alpha}{2}\right)}$ (5.6)

since

$(n+1)^{M}-n^{M}\leq M(n+1)^{M-1}\leq 2Mn^{M-1}$ (5.7)

for all $n$ large. Similarly, using $(\sum_{i=1}^{t}a_{i})^{2}\leq
t\sum_{i=1}^{t}a_{i}^{2},$ we get

$\mathbb{E}J^{2}_{n,1}\leq((n+1)^{M}-n^{M})\sum_{l=n^{M}}^{(n+1)^{M}}\mathbb{E}g_{1,l}^{2}\leq((n+1)^{M}-n^{M})\sum_{l=n^{M}}^{(n+1)^{M}}\frac{D}{l^{\frac{\alpha}{2}}},$

using (5.5). Again using (5.7), we then get that

$\mathbb{E}J_{n,1}^{2}\leq D_{1}n^{2M-2-M\frac{\alpha}{2}}$ (5.8)

for some constant $D_{1}>0.$

To estimate $J_{n,2},$ we let $L_{k}:=TSP(X_{n^{M}+1},\ldots,X_{k})$ so that
$L_{k}\leq(k-n^{M}-1)\cdot(c_{2}\sqrt{2})^{\alpha}$ by (1.2) since there are
$k-n^{M}-1$ edges each of length at most $\sqrt{2}.$ Thus

$J_{n,2}\leq((n+1)^{M}-n^{M})\cdot(c_{2}\sqrt{2})^{\alpha}\leq Dn^{M-1}$ (5.9)

for some constant $D>0$ using (5.7) and if
$x=(M-1)\left(1-\frac{\alpha}{2}\right),$ then

$\max_{n^{M}+1\leq k<n^{M}+1+n^{x}}L_{k}\leq
D_{1}n^{x}=D_{1}n^{(M-1)\left(1-\frac{\alpha}{2}\right)},$ (5.10)

for some constant $D_{1}>0.$ To bound $L_{k}$ for the remaining range of $k,$
we use the deviation estimate in Theorem 1. For $\Delta>0,$ and
$n^{M}+1+n^{x}\leq k\leq(n+1)^{M}$ we have from (1.7) that
$\mathbb{P}\left(L_{k}\leq D_{1}(k-n^{M}-1)^{1-\frac{\alpha}{2}}\right)\geq
1-\frac{1}{k^{\Delta}}$ for some constant $D_{1}>0$ and so for
$n^{M}+1+n^{x}\leq k<(n+1)^{M},$ we have that

$L_{k}\leq D_{1}((n+1)^{M}-n^{M})^{\left(1-\frac{\alpha}{2}\right)}\leq
D_{2}n^{(M-1)\left(1-\frac{\alpha}{2}\right)}$ (5.11)

for some constant $D_{2}>0,$ with probability at least
$1-\frac{1}{k^{\Delta}}\geq 1-\frac{1}{n^{M\Delta}},$ where the final estimate
in (5.11) follows from (5.7). Setting $D_{3}=\max(D_{1},D_{2}),$ where $D_{1}$
and $D_{2}$ are as in (5.10) and (5.11), respectively, we therefore get that

$\mathbb{P}\left(J_{n,2}\leq
D_{3}n^{(M-1)\left(1-\frac{\alpha}{2}\right)}\right)\geq
1-\frac{1}{n^{M\Delta}}((n+1)^{M}-n^{M})\geq 1-\frac{2Mn^{M-1}}{n^{M\Delta}},$
(5.12)

by (5.7).

From (5.12) and (5.9), we get

$\mathbb{E}J_{n,2}\leq
Dn^{(M-1)\left(1-\frac{\alpha}{2}\right)}+Dn^{M-1}\cdot\frac{Dn^{M-1}}{n^{M\Delta}}\leq
2Dn^{(M-1)\left(1-\frac{\alpha}{2}\right)},$ (5.13)

provided $\Delta>0$ large. Choosing $\Delta>0$ larger if necessary and arguing
as above, we also get that

$\mathbb{E}J_{n,2}^{2}\leq 4D^{2}n^{(M-1)(2-\alpha)}.$ (5.14)

From (5.6) and (5.13), we get the desired bound for $\mathbb{E}J_{n}$ in
(5.3). Also, using $(a+b)^{2}\leq 2(a^{2}+b^{2})$ and (5.8) and (5.14), we get
the desired bound for $\mathbb{E}J_{n}^{2}$ in (5.3).

_Proof of ( 5.4) in Lemma 8_: From (7.4) and the monotonicity relation (7.5)
we get that that $J_{n}\leq TSP(X_{n^{M}+1},\ldots,X_{(n+1)^{M}})$ and so

$\mathbb{E}J_{n}^{2}\leq\mathbb{E}TSP^{2}(X_{n^{M}+1},\ldots,X_{(n+1)^{M}})\leq
D_{1}\left((n+1)^{M}-n^{M}\right)^{2-\alpha}\leq D_{2}n^{(M-1)(2-\alpha)}$
(5.15)

for some constants $D_{1},D_{2}>0,$ where the second inequality in (5.15)
follows from the expectation upper bound for $TSP^{k}(.)$ in (1) with $k=2$
and the final inequality in (5.15) is true by (5.7). Thus

$\left(\frac{\mathbb{E}J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)^{2}\leq\frac{\mathbb{E}J^{2}_{n}}{n^{2M-M\alpha}}\leq\frac{D_{2}}{n^{M(2-\alpha)}},$

proving (5.4).

_Proof of Theorem 7 $(i)$_: We prove a.s. convergence via a subsequence
argument using the variance upper bound for $TSP_{n}$ obtained in Theorem 3.
Letting $\epsilon_{0}:=\frac{(2-\alpha)(1+\alpha)}{2+\alpha},$ we use
$\alpha<2(\sqrt{2}-1)<1$ to get that
$\frac{2}{\alpha}>\frac{2+\alpha}{2-\alpha}=\frac{1}{2-\alpha-\epsilon_{0}}.$
We therefore choose $M>0$ such that
$\frac{2}{\alpha}>M>\frac{1}{2-\alpha-\epsilon_{0}}$ and let
$\epsilon>\epsilon_{0}$ be sufficiently close to $\epsilon_{0}$ so that
$\frac{2}{\alpha}>M>\frac{1}{2-\alpha-\epsilon}.$ Fixing such $M$ and
$\epsilon$ we also have that $y=\max\left(M\frac{\alpha}{2},\alpha\right)<1.$
For simplicity, we treat $n^{M}$ as an integer for all $n$ and work the
subsequence $\\{n^{M}\\}.$

From the variance estimate in Theorem 3 $(i)$ we have that
$var\left(\frac{TSP_{n}}{n^{1-\frac{\alpha}{2}}}\right)\leq\frac{D}{n^{2-\alpha-\epsilon}}$
for some constant $D>0$ and all $n$ large. Since $M(2-\alpha-\epsilon)>1,$ we
get by an application of the Borel-Cantelli Lemma that

$\frac{1}{n^{M\left(1-\frac{\alpha}{2}\right)}}(TSP_{n^{M}}-\mathbb{E}TSP_{n^{M}})\longrightarrow
0\;\;\;\;a.s.\ $

as $n\rightarrow\infty.$ To prove convergence along the subsequence $a_{n}=n,$
we let $J_{n}$ be as in (5.2) and obtain from (5.3) that

$\left(\frac{\mathbb{E}J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)^{2}\leq\frac{\mathbb{E}J^{2}_{n}}{n^{M(2-\alpha)}}\leq\frac{D_{1}}{n^{2-y}}\longrightarrow
0$

as $n\rightarrow\infty$ and since $y<1$ (see the first paragraph of this
proof), we also get from Borel-Cantelli Lemma that
$\frac{J_{n}}{n^{M(1-\frac{\alpha}{2})}}\longrightarrow 0$ a.s. as
$n\rightarrow\infty.$ For $n^{M}\leq k<(n+1)^{M}$ we then write

$\displaystyle\frac{|TSP_{k}-\mathbb{E}TSP_{k}|}{k^{1-\frac{\alpha}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{|TSP_{k}-TSP_{n^{M}}|}{k^{1-\frac{\alpha}{2}}}+\frac{\mathbb{E}|TSP_{k}-TSP_{n^{M}}|}{k^{1-\frac{\alpha}{2}}}$
(5.16) $\displaystyle\leq$
$\displaystyle\frac{J_{n}}{k^{1-\frac{\alpha}{2}}}+\frac{\mathbb{E}J_{n}}{k^{1-\frac{\alpha}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}+\frac{\mathbb{E}J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}$

and get that
$\frac{TSP_{k}-\mathbb{E}TSP_{k}}{k^{1-\frac{\alpha}{2}}}\longrightarrow 0$
a.s. as $n\rightarrow\infty.$

_Proof of Theorem 7 $(ii)$_: Here we prove a.s. convergence for $0<\alpha\leq
1$ assuming that the edge weight function $h$ is a metric. The proof is
analogous as before with some modifications. Let
$2-\alpha>\epsilon>(2-\alpha)\cdot\frac{1+\alpha}{2+\alpha}.$ From the
variance estimate in Theorem 3 $(i)$ we have that

$var\left(\frac{TSP_{n}}{n^{1-\frac{\alpha}{2}}}\right)\leq\frac{D}{n^{2-\alpha-\epsilon}}$

for some constant $D>0$ and all $n$ large. Letting $M>0$ be a large integer so
that $M(2-\alpha-\epsilon)>1,$ we get by an application of the Borel-Cantelli
Lemma that

$\frac{1}{n^{M\left(1-\frac{\alpha}{2}\right)}}(TSP_{n^{M}}-\mathbb{E}TSP_{n^{M}})\longrightarrow
0\text{ a.s.\ }$

as $n\rightarrow\infty.$

To prove a.s. convergence along the sequence $a_{n}=n$ we let $J_{n}$ be as in
(5.2) and get from (5.4) in property $(p2)$ above that

$\left(\frac{\mathbb{E}J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\right)^{2}\leq\frac{\mathbb{E}J^{2}_{n}}{n^{2M-M\alpha}}\leq\frac{D}{n^{M(2-\alpha)}}\longrightarrow
0$

as $n\rightarrow\infty,$ for some constant $D>0.$ Thus
$\frac{\mathbb{E}J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\longrightarrow
0$ as $n\rightarrow\infty$ and since $M(2-\alpha)>M(2-\alpha-\epsilon)>1,$ we
get from Borel-Cantelli lemma that
$\frac{J_{n}}{n^{M\left(1-\frac{\alpha}{2}\right)}}\longrightarrow 0$ a.s. as
$n\rightarrow\infty.$ Arguing as in (5.16) above, we then get the desired a.s.
convergence.

##  6 Uniform TSPs

In this Section, we assume that the nodes $\\{X_{i}\\}_{1\leq i\leq n}$ are
uniformly distributed in the unit square and obtain bounds on the asymptotic
values of the expected weight, appropriately scaled and centred. We assume
that the positive edge weight function
$h:\mathbb{R}^{2}\times\mathbb{R}^{2}\rightarrow\mathbb{R}$ satisfies (1.2)
along with the following two properties:
$(b1)$ For every $a>0$ we have

$h(au,av)=a\cdot h(u,v)\text{ for all }u,v\in\mathbb{R}^{2}$

$(b2)$ There exists a constant $h_{0}>0$ such that for all
$b\in\mathbb{R}^{2}$ we have

$h(b+u,b+v)\leq h_{0}\cdot h(u,v).$ (6.1)

For example, recalling that $d(u,v)$ denotes the Euclidean distance between
$u$ and $v,$ we have that the function

$h(u,v)=d(u,v)+\frac{1}{2}|d(u,0)-d(v,0)|$ (6.2)

is a metric since

$d(u,0)\leq d(0,v)+d(v,u)\text{ and }d(v,0)\leq d(0,u)+d(u,v)$

by triangle inequality and so

$d(u,v)\leq h(u,v)\leq d(u,v)+\frac{1}{2}d(u,v).$

This implies that $h(u,v)$ satisfies (1.2) and by definition $h$ also
satisfies $(b1).$ Moreover using the triangle inequality we have

$\displaystyle h(b+u,b+v)$ $\displaystyle=$ $\displaystyle
d(b+u,b+v)+\frac{1}{2}|d(u+b,0)-d(v+b,0)|$ $\displaystyle=$ $\displaystyle
d(u,v)+\frac{1}{2}|d(u+b,0)-d(v+b,0)|$ $\displaystyle\leq$ $\displaystyle
d(u,v)+\frac{1}{2}d(u+b,v+b)$ $\displaystyle=$ $\displaystyle
d(u,v)+\frac{1}{2}d(u,v)$ $\displaystyle\leq$ $\displaystyle\frac{3}{2}h(u,v)$

by definition of $h$ in (6.2). Thus $(b2)$ is also satisfied with
$h_{0}=\frac{3}{2}.$

We have the following result.

###### Theorem 9

Suppose the distribution function $f(.)$ is uniform, i.e.,
$\epsilon_{1}=\epsilon_{2}=1$ in (1.1) and the edge weight function $h(u,v)$
satisfies (1.2) and properties $(b1)-(b2)$ above. If the edge weight exponent
is $0<\alpha<2,$ then

$0<\liminf_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}\leq\limsup_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}\leq
h_{0}^{\alpha}\cdot\liminf_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}<\infty.$
(6.3)

Thus the scaled weight of the TSP remains bounded within a factor of
$h_{0}^{\alpha}.$

Letting

$J_{n}=\max_{n^{2}\leq k<(n+1)^{2}}|TSP_{k}-TSP_{n^{2}}|$

be as in (5.2) with $M=2,$ we get for $n^{2}\leq k<(n+1)^{2}$ that

$\frac{\mathbb{E}TSP_{k}}{k^{1-\frac{\alpha}{2}}}\leq\frac{\mathbb{E}TSP_{k}}{n^{2-\alpha}}\leq\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}+\frac{\mathbb{E}J_{n}}{n^{2-\alpha}}$

and

$\frac{\mathbb{E}TSP_{k}}{k^{1-\frac{\alpha}{2}}}\geq\frac{\mathbb{E}TSP_{k}}{(n+1)^{2-\alpha}}\geq\frac{\mathbb{E}TSP_{n^{2M}}}{(n+1)^{2-\alpha}}-\frac{\mathbb{E}J_{n}}{(n+1)^{2-\alpha}}.$

Using the estimate (5.3) with $M=2,$ we have
$\frac{\mathbb{E}J_{n}}{n^{2-\alpha}}\longrightarrow 0$ as
$n\rightarrow\infty$ and so we get

$\limsup_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}=\limsup_{n}\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}$

and

$\liminf_{n}\frac{\mathbb{E}TSP_{n}}{n^{1-\frac{\alpha}{2}}}=\liminf_{n}\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}.$

In what follows therefore, we work with the sequence $a_{n}=n^{2}.$

We begin with the following preliminary Lemma.

###### Lemma 10

There is a constant $D>0$ such that for any positive integers $n_{1},n_{2}\geq
1$ we have

$\displaystyle\mathbb{E}TSP_{n_{1}+n_{2}}\leq\mathbb{E}TSP_{n_{1}}+Dn_{2}^{1-\frac{\alpha}{2}}+2(\sqrt{2})^{\alpha}.$
(6.4)

Also for any fixed integer $m\geq 1$ we have

$\limsup_{n}\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}\leq\limsup_{k}\frac{\mathbb{E}TSP_{k^{2}m^{2}}}{(km)^{2-\alpha}}.$
(6.5)

_Proof of ( 6.4) in Lemma 10_: From the additive relation (7.4) in Appendix we
have

$TSP_{n_{1}+n_{2}}\leq
TSP_{n_{1}}+TSP(X_{n_{1}+1},\ldots,X_{n_{1}+n_{2}})+2(\sqrt{2})^{\alpha}$

and using the TSP expectation upper bound in (1), the middle term is bounded
above by $Dn_{2}^{1-\frac{\alpha}{2}}$ for some constant $D>0.$

_Proof of ( 6.5) in Lemma 10_: Fix an integer $m\geq 1$ and write $n=qm+s$
where $q=q(n)\geq 1$ and $0\leq s=s(n)\leq m-1$ are integers. As
$n\rightarrow\infty,$

$q(n)\longrightarrow\infty\text{ and }\frac{n}{q(n)}\longrightarrow m.$ (6.6)

Also using $s<m,$ we have $qm+s<(q+1)m$ and so $q_{1}:=(qm+s)^{2}-(qm)^{2}$ is
bounded above by

$q_{1}\leq m^{2}\left((q+1)^{2}-q^{2}\right)\leq 4m^{2}q.$ (6.7)

Using property $(b1)$ we therefore have that
$\mathbb{E}TSP_{n^{2}}=\mathbb{E}TSP_{(qm+s)^{2}}$ equals

$\mathbb{E}TSP_{(qm)^{2}+q_{1}}\leq\mathbb{E}TSP_{(qm)^{2}}+Dq_{1}^{1-\frac{\alpha}{2}}+2(\sqrt{2})^{\alpha}$

for some constant $D>0.$ From (6.7), we have
$Dq_{1}^{1-\frac{\alpha}{2}}\leq\frac{D_{1}}{q^{1-\frac{\alpha}{2}}}\cdot(qm)^{2-\alpha}$
for some constant $D_{1}>0$ and so

$\displaystyle\limsup_{n}\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}$
$\displaystyle\leq$
$\displaystyle\limsup_{n}\left(\frac{qm}{n}\right)^{2-\alpha}\frac{\mathbb{E}TSP_{(qm)^{2}}}{(qm)^{2-\alpha}}$
$\displaystyle\;\;\;\;\;\;\;\;\;+\;\;\limsup_{n}\left(\frac{qm}{n}\right)^{2-\alpha}\left(\frac{D_{1}}{q^{1-\frac{\alpha}{2}}}+\frac{2(\sqrt{2})^{\alpha}}{(qm)^{2-\alpha}}\right).$

Since $q(n)\longrightarrow\infty$ and $\frac{n}{q(n)}\longrightarrow m$ (see
(6.6)), $m$ is fixed and $0<\alpha<2,$ the second term in (LABEL:tsp_temp_km1)
is zero and the first term in (LABEL:tsp_temp_km1) equals
$\limsup_{n}\frac{\mathbb{E}TSP_{(qm)^{2}}}{(qm)^{2-\alpha}}.$

But since $q(n)\geq\frac{n-m}{m}\geq\frac{l-m}{m}$ for $n\geq l,$ we have that

$\sup_{n\geq l}\frac{\mathbb{E}TSP_{q^{2}m^{2}}}{(qm)^{2-\alpha}}=\sup_{n\geq
l}\frac{\mathbb{E}TSP_{q^{2}(n)m^{2}}}{(q(n)m)^{2-\alpha}}\leq\sup_{k\geq\frac{l-m}{m}}\frac{\mathbb{E}TSP_{k^{2}m^{2}}}{(km)^{2-\alpha}}$
(6.9)

and as $l\uparrow\infty,$ the final term in (6.9) converges to the second term
in (6.5).

If $\lambda:=\liminf_{n}\frac{\mathbb{E}TSP_{n^{2}}}{n^{2-\alpha}}$ then from
(1), we have that $\lambda>0.$ We show below that for every $\epsilon>0,$
there exists $m$ sufficiently large such that

$\limsup_{k}\frac{\mathbb{E}TSP_{k^{2}m^{2}}}{(km)^{2-\alpha}}\leq
h_{0}^{2}\cdot\lambda+\epsilon.$ (6.10)

Since $\epsilon>0$ is arbitrary, the desired bound in Theorem 9 follows from
(6.5). In the rest of this Section, we prove (6.10) via a series of Lemmas.

Let $k$ and $m$ be positive integers and distribute $k^{2}m^{2}$ nodes
$\\{X_{i}\\}_{1\leq i\leq k^{2}m^{2}}$ independently and uniformly in the unit
square $S.$ Also divide $S$ into $k^{2}$ disjoint squares $\\{W_{j}\\}_{1\leq
j\leq k^{2}}$ each of size $\frac{1}{k}\times\frac{1}{k}$ as in Figure 3 so
that the top left most square is labelled $W_{1},$ the square below $W_{1}$ is
$W_{2}$ and so on until we reach the square $W_{k}$ intersecting the bottom
edge of the unit square $S.$ The square to the right of $W_{k}$ is then
labelled $W_{k+1}$ and the square above $W_{k+1}$ is $W_{k+2}$ and so on.

The next result obtains an upper bound for $TSP_{k^{2}m^{2}}$ in terms of the
local TSPs of the squares $W_{j}.$ For $1\leq j\leq k^{2},$ Let $N(j)$ be the
number of nodes of $\\{X_{i}\\}$ present in the square $W_{j}$ and let
$TSP_{j}(N(j))$ be the TSP length of the nodes present in $W_{j}.$ We have the
following Lemma.

###### Lemma 11

There exists a constant $D>0$ not depending on $k$ or $m$ such that

$\mathbb{E}TSP_{k^{2}m^{2}}\leq\sum_{j=1}^{k^{2}}\mathbb{E}TSP_{j}(N(j))+D\cdot
k^{2-\alpha}+(c_{2}\sqrt{2})^{\alpha},$ (6.11)

where $c_{2}$ is as in (1.2).

_Proof of Lemma 11_: We first connect all nodes within each square $W_{j}$ by
a path of minimum weight to get local minimum weigh paths. We then join all
these paths together to get an overall spanning path containing all the
$k^{2}m^{2}$ nodes. Joining the endvertices of this new path by an edge, we
get a spanning cycle whose weight is at least $TSP_{k^{2}m^{2}}.$

For $1\leq j\leq k^{2},$ let ${\cal P}(j)$ and ${\cal C}(j)$ respectively
denote the minimum spanning path and minimum spanning cycle, containing all
the $N(j)$ nodes. If $N(j)=0$ we set ${\cal P}(j)=\emptyset$ and if $N(j)\leq
2,$ we set ${\cal P}(j)={\cal C}(j).$ For any $1\leq j\leq k^{2}m^{2}$ we
first show that

$W({\cal P}(j))\leq W({\cal C}(j))\leq W({\cal
P}(j))+\left(\frac{c_{2}\sqrt{2}}{k}\right)^{\alpha}.$ (6.12)

To see that (6.12) is true, let ${\cal C}$ be any spanning cycle containing
all the nodes in the square $W_{j}.$ Removing an edge of ${\cal C}$ we get a
spanning path ${\cal P}$ and so $W({\cal P}(j))\leq W({\cal P})\leq W({\cal
C}).$ Taking minimum over all spanning cycles we obtain the first relation in
(6.12). Taking the minimum spanning path ${\cal P}(j)$ with endvertices $u,v$
and adding the edge $(u,v),$ we obtain a spanning cycle ${\cal C}_{new}$ and
since the length of the edge $(u,v)$ is at most $\frac{\sqrt{2}}{k}$ we use
(1.2) to get that

$W({\cal C}(j))\leq W({\cal C}_{new})\leq W({\cal
P}(j))+\left(\frac{c_{2}\sqrt{2}}{k}\right)^{\alpha},$

proving (6.12).

For $1\leq j\leq k^{2}-1,$ let $j~{}+~{}T^{next}_{j}:=\min\\{i\geq
j+1:W_{i}\text{ is not empty}\\}$ be the next nonempty square after $W_{j},$
containing at least one node of $\\{X_{i}\\}_{1\leq i\leq k^{2}m^{2}}.$ If no
such square exists, set $j+T^{next}_{j}~{}=~{}k^{2}.$ If both $W_{j}$ and
$W_{j+T^{next}_{j}}$ are nonempty, let $e_{j}$ be the edge with one endvertex
in $W_{j}$ and the other endvertex in $W_{j+T^{next}_{j}},$ having the
smallest Euclidean length $d(e_{j})$ and set $e_{j}=\emptyset$ and
$d(e_{j})=0,$ otherwise. The union

${\cal P}_{ov}:=\cup_{1\leq j\leq k^{2}}{\cal P}(j)\cup\cup_{1\leq j\leq
k^{2}-1}\\{e_{j}\\}$

is a spanning path containing all the $k^{2}m^{2}$ nodes and joining the
endvertices of ${\cal P}_{ov}$ (by an edge of length at most $\sqrt{2}$), we
again use (1.2) to get

$\displaystyle TSP_{k^{2}m^{2}}$ $\displaystyle\leq$ $\displaystyle W({\cal
P}_{ov})+(c_{2}\sqrt{2})^{\alpha}$ (6.13) $\displaystyle=$
$\displaystyle\sum_{j=1}^{k^{2}}W({\cal
P}(j))+\sum_{j=1}^{k^{2}-1}h^{\alpha}(e_{j})+(c_{2}\sqrt{2})^{\alpha}$
$\displaystyle\leq$ $\displaystyle\sum_{j=1}^{k^{2}}W({\cal
P}(j))+c_{2}^{\alpha}\sum_{j=1}^{k^{2}-1}d^{\alpha}(e_{j})+(c_{2}\sqrt{2})^{\alpha}$
$\displaystyle\leq$ $\displaystyle\sum_{j=1}^{k^{2}}W({\cal
C}(j))+c_{2}^{\alpha}\sum_{j=1}^{k^{2}-1}d^{\alpha}(e_{j})+(\sqrt{2})^{\alpha},$

using (6.12).

Taking expectations in (6.13) and recalling that $TSP_{j}(N(j)):=W({\cal
C}(j))$ we get

$\mathbb{E}TSP_{k^{2}m^{2}}\leq\sum_{j=1}^{k^{2}}\mathbb{E}TSP_{j}(N(j))+c_{2}^{\alpha}\cdot
k^{2}\max_{1\leq j\leq
k^{2}-1}\mathbb{E}d^{\alpha}(e_{j})+(c_{2}\sqrt{2})^{\alpha}.$ (6.14)

We show that there exists a constant $D>0$ not depending on $k$ or $m$ such
that

$\max_{1\leq j\leq
k^{2}-1}\mathbb{E}d^{\alpha}(e_{j})\leq\frac{D}{k^{\alpha}}$ (6.15)

and this proves Lemma 11. Indeed, the Euclidean length of the edge $e_{j}$ is
at most $\frac{2T^{next}_{j}\sqrt{2}}{k}$ and so
$\mathbb{E}d^{\alpha}(e_{j})\leq\frac{(2\sqrt{2})^{\alpha}}{k^{\alpha}}\mathbb{E}(T^{next}_{j})^{\alpha}.$
Next, for any $l\geq 1$ we have $T^{next}_{j}>l$ if and only if
$W_{j+1},\ldots,W_{j+l}$ are empty, which happens with probability
$\left(1-l\cdot\frac{1}{k^{2}}\right)^{k^{2}m^{2}}\leq e^{-lm^{2}}\leq
e^{-l},$ since $m\geq 1.$ Thus

$\mathbb{E}(T^{next}_{j})^{\alpha}\leq\mathbb{E}(T^{next}_{j})^{2}\leq\sum_{l\geq
1}l\mathbb{P}\left(T^{next}_{j}\geq l\right)\leq\sum_{l\geq
1}le^{-(l-1)}\leq\frac{1}{(1-e^{-1})^{2}},$

proving (6.15).

Lemma 11 is useful in the following manner. For $1\leq j\leq k^{2}$ let
$TSP(N(j))$ be the _shifted_ TSP of the nodes present in $W_{j}$ defined as
follows: If $v_{1},\ldots,v_{t}$ are the nodes of $\\{X_{i}\\}$ present in the
square $W_{j}$ with centre $s_{j},$ then $TSP(N(j))$ is the TSP formed by the
nodes $v_{1}-s_{j},\ldots,v_{t}-s_{j}.$ From the translation relation (7.11)
in Appendix, we have $TSP_{j}(N(j))\leq h_{0}^{\alpha}\cdot TSP(N(j))$ and so
we get from Lemma 11 that

$\displaystyle\mathbb{E}TSP_{k^{2}m^{2}}$ $\displaystyle\leq$ $\displaystyle
h_{0}^{\alpha}\cdot\sum_{j=1}^{k^{2}}\mathbb{E}TSP(N(j))+D\cdot
k^{2-\alpha}+(c_{2}\sqrt{2})^{\alpha}$ $\displaystyle=$ $\displaystyle
h_{0}^{\alpha}\cdot k^{2}\cdot\mathbb{E}TSP(N(1))+D\cdot
k^{2-\alpha}+(c_{2}\sqrt{2})^{\alpha}$

To evaluate $TSP(N(1)),$ we let $0<\gamma<\frac{1}{2}$ and
$\frac{(2-\alpha)(1+\alpha)}{2+\alpha}<\epsilon_{1}<2-\alpha$ be constants
(not depending on $k$ or $m$) such that

$2-\alpha+2\gamma-2\epsilon_{1}>0$ (6.16)

This is possible since
$2\frac{(2-\alpha)(1+\alpha)}{2+\alpha}-(2-\alpha)=\frac{\alpha(2-\alpha)}{2+\alpha}<1$
for all $0<\alpha<2$ and so we choose $\epsilon_{1}$ greater than but
sufficiently close to $\frac{(2-\alpha)(1+\alpha)}{2+\alpha}$ and $2\gamma$
less than but sufficiently close to one so that (6.16) holds.

We have the following Lemma.

###### Lemma 12

There is a constant $D>0$ not depending on $k$ or $m$ such that

$\mathbb{E}TSP(N(1))\leq\frac{1}{k^{\alpha}}\left(\mathbb{E}TSP_{m^{2}}+Dm^{2(\epsilon_{1}-\gamma)}+D\frac{m^{2-\alpha}}{m^{\alpha(1-2\gamma)}}\right)$
(6.17)

_Proof Lemma 12_: We write $\mathbb{E}TSP(N(1))=I_{1}+I_{2},$ where

$I_{1}=\mathbb{E}TSP(N(1))1{1}(F_{1}),I_{2}=\mathbb{E}TSP(N(1))1{1}(F_{1}^{c})$

and $F_{1}:=\\{m^{2}\left(1-\frac{1}{m^{2\gamma}}\right)\leq N(1)\leq
m^{2}\left(1+\frac{1}{m^{2\gamma}}\right)\\}.$ Each node $X_{i},1\leq i\leq
k^{2}m^{2}$ has a probability $\frac{1}{k^{2}}$ of being present in the
$\frac{1}{k}\times\frac{1}{k}$ square $W_{1}.$ Therefore the number of nodes
$N(1)$ in the square $W_{1}$ is binomially distributed with mean
$\mathbb{E}N(1)=m^{2}$ and $var(N_{1})\leq m^{2}.$ We therefore get from
Chebychev’s inequality that

$\mathbb{P}(F^{c}_{1})\leq\frac{1}{m^{2(1-2\gamma)}}.$ (6.18)

_Evaluation of $I_{1}$_: We write

$I_{1}=\sum_{j=j_{low}}^{j_{up}}\mathbb{E}TSP(N(1))1{1}(N(1)=j),$

where $j_{low}:=m^{2}\left(1-\frac{1}{m^{2\gamma}}\right)\leq
m^{2}\left(1+\frac{1}{m^{2\gamma}}\right)=:j_{up}.$ Given $N_{1}=j,$ the nodes
in $W_{1}$ are independently and uniformly distributed in $W_{1}$ and we let
$\mathbb{E}TSP\left(j;\frac{1}{k}\right)$ be the expected length of the TSP
containing $j$ nodes independently and uniformly distributed in the
$\frac{1}{k}\times\frac{1}{k}$ square centred at origin. From the scaling
relation (7.10) in Appendix we have

$I_{1}=\sum_{j=j_{low}}^{j_{up}}\mathbb{E}TSP\left(j;\frac{1}{k}\right)\mathbb{P}(N(1)=j)=\frac{1}{k^{\alpha}}\sum_{j=j_{low}}^{j_{up}}\left(\mathbb{E}TSP_{j}\right)\mathbb{P}(N(1)=j),$
(6.19)

by (7.10).

Letting $2-\alpha>\epsilon_{1}>\frac{(2-\alpha)(1+\alpha)}{2+\alpha}$ be as in
(6.16), we have from the one node difference estimate (3.8) that for any
integers $j_{1}$ and $j_{2}$ lying between $j_{low}$ and $j_{up},$ the term
$\mathbb{E}|TSP_{j_{2}}-TSP_{j_{1}}|$ is bounded above by

$\sum_{u=j_{low}}^{j_{up}-1}\mathbb{E}|TSP_{u+1}-TSP_{u}|\leq\sum_{u=j_{low}}^{j_{up}-1}\frac{D_{1}}{u^{1-\epsilon_{1}}}\leq\frac{D_{2}(j_{up}-j_{low})}{m^{2(1-\epsilon_{1})}}=2D_{2}\frac{m^{2(1-\gamma)}}{m^{2(1-\epsilon_{1})}},$
(6.20)

where $D_{1},D_{2}>0$ are constants not depending on $j_{1}$ or $j_{2}.$
Setting $j_{1}=m^{2}$ and $j_{2}=j$ and using (6.20) we get
$\mathbb{E}TSP_{j}\leq\mathbb{E}TSP_{m^{2}}+D_{2}m^{2(\epsilon_{1}-\gamma)}$
for all $j_{low}\leq j\leq j_{up}.$ From the expression for $I_{1}$ in (6.19)
we therefore have that

$I_{1}\leq\frac{1}{k^{\alpha}}\left(\mathbb{E}TSP_{m^{2}}+D_{2}m^{2(\epsilon_{1}-\gamma)}\right).$
(6.21)

_Evaluation of $I_{2}$_: There are $N(1)$ nodes in the
$\frac{1}{k}\times\frac{1}{k}$ square $W_{1}$ and given $N(1)=l,$ the $l$
nodes are uniformly distributed in $W_{1}$ and so

$\mathbb{E}(TSP(N(1))|N(1)=l)=\mathbb{E}TSP\left(l;\frac{1}{k}\right)=\frac{1}{k^{\alpha}}\mathbb{E}TSP_{l}\leq
D_{1}\frac{l^{1-\frac{\alpha}{2}}}{k^{\alpha}}$

for some constant $D_{1}>0$ using the expectation upper bound in (1). Thus

$\displaystyle\mathbb{E}TSP(N(1))1{1}(N(1)=l)$ $\displaystyle=$
$\displaystyle\mathbb{E}(TSP(N(1))|N(1)=l)\mathbb{P}(N(1)=l)$
$\displaystyle\leq$ $\displaystyle
D_{1}\frac{l^{1-\frac{\alpha}{2}}}{k^{\alpha}}\mathbb{P}(N(1)=l)$

and consequently $I_{2}=\mathbb{E}TSP(N(1))1{1}(F_{1}^{c})$ equals

$\displaystyle\sum_{l\leq j_{low}}+\sum_{l\geq
j_{up}}\mathbb{E}TSP(N(1))1{1}(N(1)=l)$ $\displaystyle\leq\;\;\;\sum_{l\leq
j_{low}}+\sum_{l\geq
j_{up}}D_{1}\frac{l^{1-\frac{\alpha}{2}}}{k^{\alpha}}\mathbb{P}(N(1)=l)$
$\displaystyle=\;\;\;\frac{D_{1}}{k^{\alpha}}\mathbb{E}(N(1))^{1-\frac{\alpha}{2}}1{1}(F_{1}^{c}).$
(6.22)

Using Holder’s inequality
$\mathbb{E}XY\leq\left(\mathbb{E}X^{p}\right)^{\frac{1}{p}}\left(\mathbb{E}Y^{q}\right)^{\frac{1}{q}}$
with $X=(N(1))^{1-\frac{\alpha}{2}},$
$Y=1{1}(F_{1}^{c}),p=\frac{2}{2-\alpha}>1$ and $q=\frac{2}{\alpha}>1,$ we get

$\displaystyle\mathbb{E}(N(1))^{1-\frac{\alpha}{2}}1{1}(F_{1}^{c})$
$\displaystyle\leq$
$\displaystyle\left(\mathbb{E}N(1)\right)^{1-\frac{\alpha}{2}}\left(\mathbb{P}(F_{1}^{c})\right)^{\frac{\alpha}{2}}$
(6.23) $\displaystyle=$ $\displaystyle
m^{2-\alpha}\left(\mathbb{P}(F_{1}^{c})\right)^{\frac{\alpha}{2}}$
$\displaystyle\leq$ $\displaystyle
m^{2-\alpha}\frac{1}{m^{\alpha(1-2\gamma)}},$

by (6.18). From (6.22) we therefore get that

$I_{2}\leq\frac{D_{2}m^{2-\alpha}}{k^{\alpha}}\frac{1}{m^{\alpha(1-2\gamma)}}.$
(6.24)

From the estimate for $I_{1}$ in (6.21), we therefore get that

$\mathbb{E}TSP(N(1))=I_{1}+I_{2}\leq\frac{1}{k^{\alpha}}\left(\mathbb{E}TSP_{m^{2}}+D_{2}m^{2(\epsilon_{1}-\gamma)}+D_{2}\frac{m^{2-\alpha}}{m^{\alpha(1-2\gamma)}}\right),$

proving Lemma 11.

Substituting (6.17) of Lemma 11 into (6.11) we get

$\displaystyle\mathbb{E}TSP_{k^{2}m^{2}}$ $\displaystyle\leq$ $\displaystyle
k^{2-\alpha}\left(h_{0}^{\alpha}\cdot\mathbb{E}TSP_{m^{2}}+Dm^{2(\epsilon_{1}-\gamma)}+D\frac{m^{2-\alpha}}{m^{\alpha(1-2\gamma)}}+D\right)$

for some constant $D>0.$ Thus

$\limsup_{k}\frac{\mathbb{E}TSP_{k^{2}m^{2}}}{(km)^{2-\alpha}}\leq
h_{0}^{\alpha}\cdot\frac{\mathbb{E}TSP_{m^{2}}}{m^{2-\alpha}}+\frac{D}{m^{2-\alpha+2\gamma-2\epsilon_{1}}}+\frac{D}{m^{\alpha(1-2\gamma)}}+\frac{D}{m^{2-\alpha}}$

for all $m$ large. By choice of $\gamma,\epsilon_{1}>0$ in (6.16) we have
$2\gamma<1$ and
$2-\alpha+2\gamma-2\epsilon_{1}>0$ and so

$\limsup_{k}\frac{\mathbb{E}TSP_{k^{2}m^{2}}}{(km)^{2-\alpha}}\leq
h_{0}^{\alpha}\cdot\frac{\mathbb{E}TSP_{m^{2}}}{m^{2-\alpha}}+\epsilon,$
(6.26)

for all $m$ large by definition of $\lambda$ in (6.5). Letting $\\{m_{j}\\}$
be any sequence such that
$\frac{\mathbb{E}TSP_{m^{2}_{j}}}{m_{j}^{2-\alpha}}\longrightarrow\lambda=\liminf_{n}\frac{\mathbb{E}TSP_{n}^{2}}{n^{2-\alpha}}$
and allowing $m\rightarrow\infty$ through the sequence $\\{m_{j}\\}$ in
(6.26), we get that $\limsup_{n}\frac{\mathbb{E}TSP_{n}^{2}}{n^{2-\alpha}}\leq
h_{0}^{\alpha}\cdot\lambda+\epsilon.$ Since $\epsilon>0$ is arbitrary, this
obtains (6.10).

##  7 Appendix : Miscellaneous results

### Standard deviation estimates

We use the following standard deviation estimates for sums of independent
Poisson and Bernoulli random variables.

###### Lemma 13

Suppose $W_{i},1\leq i\leq m$ are independent Bernoulli random variables
satisfying
$\mu_{1}\leq\mathbb{P}(W_{1}=1)=1-\mathbb{P}(W_{1}~{}=~{}0)\leq\mu_{2}.$ For
any $0<\epsilon<\frac{1}{2},$

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}>m\mu_{2}(1+\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}m\mu_{2}\right)$
(7.1)

and

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}<m\mu_{1}(1-\epsilon)\right)\leq\exp\left(-\frac{\epsilon^{2}}{4}m\mu_{1}\right)$
(7.2)

Estimates (7.1) and (7.2) also hold if $\\{W_{i}\\}$ are independent Poisson
random variables with $\mu_{1}\leq\mathbb{E}W_{1}\leq\mu_{2}.$

For completeness, we give a quick proof.
_Proof of Lemma 13_: First suppose that $\\{W_{i}\\}$ are independent Poisson
with
$\mu_{1}\leq\mathbb{E}W_{i}\leq\mu_{2}$ so that
$\mathbb{E}e^{sW_{i}}=\exp\left(\mathbb{E}W_{i}(e^{s}-1)\right)\leq\exp\left(\mu_{2}(e^{s}-1)\right)$
for $s~{}>~{}0.$ By Chernoff bound we then have

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}>m\mu_{2}(1+\epsilon)\right)\leq
e^{-sm\mu_{2}(1+\epsilon)}\exp\left(m\mu_{2}(e^{s}-1)\right)=e^{m\mu_{2}\Delta_{1}},$

where $\Delta_{1}=e^{s}-1-s-s\epsilon.$ For $s\leq 1,$ we have the bound

$e^{s}-1-s=\sum_{k\geq 2}\frac{s^{k}}{k!}\leq s^{2}\sum_{k\geq
2}\frac{1}{k!}=s^{2}(e-2)\leq s^{2}$

and so we set $s=\frac{\epsilon}{2}$ to get that $\Delta_{1}\leq
s^{2}-s\epsilon=\frac{-\epsilon^{2}}{4}.$

Similarly for $s>0,$ we have

$\mathbb{E}e^{-sW_{i}}=\exp\left(\mathbb{E}W_{i}(e^{-s}-1)\right)\leq\exp\left(\mu_{1}(e^{-s}-1)\right)$

and so

$\mathbb{P}\left(\sum_{i=1}^{m}W_{i}<m\mu_{1}(1-\epsilon)\right)\leq
e^{sm\mu_{1}(1-\epsilon)}\exp\left(m\mu_{1}(e^{-s}-1)\right)=e^{-m\mu_{1}\Delta_{2}},$

where $\Delta_{2}=1-s-e^{-s}+s\epsilon.$ For $s\leq 1,$ the term $e^{-s}\leq
1-s+\frac{s^{2}}{2}$ and so we get
$\Delta_{2}\geq-\frac{s^{2}}{2}+s\epsilon=\frac{\epsilon^{2}}{2}$ for
$s=\epsilon.$

The proof for the Binomial distribution follows from the fact that if
$\\{W_{i}\\}_{1\leq i\leq m}$ are independent Bernoulli distributed with
$\mu_{1}\leq\mathbb{E}W_{i}\leq\mu_{2},$ then for $s>0$ we have
$\mathbb{E}e^{sW_{i}}=1-\mathbb{E}W_{i}+e^{s}\mathbb{E}W_{i}\leq\exp\left(\mathbb{E}W_{i}(e^{s}-1)\right)\leq\exp\left(\mu_{2}(e^{s}-1)\right)$
and similarly $\mathbb{E}e^{-sW_{i}}\leq\exp\left(\mu_{1}(e^{-s}-1)\right).$
The rest of the proof is then as above.

### Proof of the monotonicity property (2.24)

For $\alpha\leq 1$ we couple the original Poisson process ${\cal P}$ and the
homogenous process ${\cal P}_{\delta}$ in the following way. Let $V_{i},i\geq
1$ be i.i.d. random variables each with density $f(.)$ and let $N_{V}$ be a
Poisson random variable with mean $n,$ independent of $\\{V_{i}\\}.$ The nodes
$\\{V_{i}\\}_{1\leq i\leq N_{V}}$ form a Poisson process with intensity
$nf(.)$ which we denote as ${\cal P}$ and colour green.

Let $U_{i},i\geq 1$ be i.i.d. random variables each with density
$\epsilon_{2}-f(.)$ where $\epsilon_{2}\geq 1$ is as in (1.1) and let $N_{U}$
be a Poisson random variable with mean $n(\epsilon_{2}-1).$ The random
variables $(\\{U_{i}\\},N_{U})$ are independent of $(\\{V_{i}\\},N_{V})$ and
the nodes $\\{U_{i}\\}_{1\leq i\leq N_{U}}$ form a Poisson process with
intensity $n(\epsilon_{2}-f(.))$ which we denote as ${\cal P}_{ext}$ and
colour red. The nodes of ${\cal P}$ and ${\cal P}_{ext}$ together form a
homogenous Poisson process with intensity $n\epsilon_{2},$ which we denote as
${\cal P}_{\delta}$ and define it on the probability space
$(\Omega_{\delta},{\cal F}_{\delta},\mathbb{P}_{\delta}).$

Let $\omega_{\delta}\in\Omega_{\delta}$ be any configuration and let ${\cal
I}:=\\{i_{j}\\}_{1\leq j\leq Q}$ be the indices of the dense squares in
$\\{R_{j}\\},$ each containing at least three nodes of ${\cal P}$ and let
${\cal I}_{\delta}:=\\{i^{(\delta)}_{j}\\}_{1\leq j\leq Q_{\delta}}$ be the
indices of the $\delta-$dense squares in $\\{R_{j}\\},$ each containing at
least three nodes of ${\cal P}_{\delta}.$ We set ${\cal I}=\emptyset$ if
$\omega_{\delta}$ contains no dense square and set ${\cal
I}_{\delta}=\emptyset$ if $\omega_{\delta}$ contains no $\delta-$dense square.
By definition ${\cal I}\subseteq{\cal I}_{\delta}$ and defining
$S_{\alpha}=S_{\alpha}(\omega_{\delta})$ and
$S^{(\delta)}_{\alpha}=S_{\alpha}^{(\delta)}(\omega_{\delta})$ as before, we
have that $S_{\alpha}$ is determined only by the green nodes of
$\omega_{\delta}$ while $S^{(\delta)}_{\alpha}$ is determined by both green
and red nodes of $\omega_{\delta}.$

From the monotonicity property, we therefore have that
$S_{\alpha}(\omega_{\delta})\leq S^{(\delta)}_{\alpha}(\omega_{\delta})$ and
so for any $x>0$ we have

$\mathbb{P}_{\delta}(S^{(\delta)}_{\alpha}<x)\leq\mathbb{P}_{\delta}(S_{\alpha}<x)=\mathbb{P}_{0}(S_{\alpha}<x),$
(7.3)

proving (2.24).

If $\alpha>1,$ we perform a slightly different analysis. Letting
$\epsilon_{1}\leq 1$ be as in (1.1), we construct a Poisson process ${\cal
P}_{ext}$ with intensity $n(f(.)-\epsilon_{1})$ and colour nodes of ${\cal
P}_{ext}$ red. Letting ${\cal P}_{\delta}$ be another independent Poisson
process with intensity $n\epsilon_{1},$ we colour nodes of ${\cal P}_{\delta}$
green. The superposition of ${\cal P}_{ext}$ and ${\cal P}_{\delta}$ is a
Poisson process with intensity $nf(.),$ which we define on the probability
space $(\Omega_{\delta},{\cal F}_{\delta},\mathbb{P}_{\delta}).$ In this case,
the sum $S_{\alpha}$ is determined by both green and red nodes while
$S^{(\delta)}_{\alpha}$ is determined only by the green nodes. Again using the
monotonicity property of $S_{\alpha},$ we get (7.3).

### Additive relations

If $TSP(x_{1},\ldots,x_{j}),j\geq 1$ denotes the length of the TSP cycle with
vertex set $\\{x_{1},\ldots,x_{j}\\},$ then for any $k\geq 1,$ we have

$TSP(x_{1},\ldots,x_{j+k})\leq
TSP(x_{1},\ldots,x_{j})+TSP(x_{j+1},\ldots,x_{j+k})+(c_{2}\sqrt{2})^{\alpha}$
(7.4)

and if $\alpha\leq 1$ and the edge weight function $h$ is a metric, then

$TSP(x_{1},\ldots,x_{j})\leq TSP(x_{1},\ldots,x_{j+k}).$ (7.5)

_Proof of ( 7.4) and (7.5)_: To prove (7.4), suppose ${\cal C}_{1}$ is the
minimum weight spanning cycle formed by the nodes $\\{x_{l}\\}_{1\leq l\leq
j}$ and ${\cal C}_{2}$ is the minimum weight spanning cycle formed by
$\\{x_{l}\\}_{j+1\leq l\leq j+k}.$ Let $e_{1}=(u_{1},v_{1})\in{\cal C}_{1}$
and $e_{2}=(u_{2},v_{2})\in{\cal C}_{2}$ be any two edges. The cycle

${\cal C}_{tot}=\left({\cal C}_{1}\setminus\\{e_{1}\\}\right)\cup\left({\cal
C}_{2}\setminus\\{e_{2}\\}\right)\cup\\{(u_{1},u_{2}),(v_{1},v_{2})\\}$

obtained by removing the edges $e_{1},e_{2}$ and adding the “cross” edges
$(u_{1},u_{2})$ and $(v_{1},v_{2})$ is a spanning cycle containing all the
nodes $\\{x_{l}\\}_{1\leq l\leq j+k}.$ The edges $(u_{1},u_{2})$ and
$(v_{1},v_{2})$ have a Euclidean length of at most $\sqrt{2}$ and so a weight
of at most $(c_{2}\sqrt{2})^{\alpha}$ using the bounds for the metric $h$ in
(1.2). This proves (7.4).

It suffices to prove (7.5) for $k=1.$ Let ${\cal
C}=(y_{1},\ldots,y_{j+1},y_{1})$ be any cycle with vertex set
$\\{y_{i}\\}_{1\leq i\leq j+1}=\\{x_{i}\\}_{1\leq i\leq j+1}$ and without loss
of generality suppose that $y_{j+1}=x_{j+1}.$ Removing the edges
$(y_{j},y_{j+1})$ and $(y_{j+1},y_{1}),$ and adding the edge $(y_{1},y_{j})$
we get a new cycle ${\cal C}^{\prime}$ with vertex set $\\{x_{i}\\}_{1\leq
i\leq j}.$

Since the edge weight function $h$ is a metric, we have by triangle inequality
that $h(y_{j},y_{1})\leq h(y_{j},y_{j+1})+h(y_{j+1},y_{1}).$ Using
$(a+b)^{\alpha}\leq a^{\alpha}+b^{\alpha}$ for $a,b>0$ and $0<\alpha\leq 1$ we
get that $h^{\alpha}(y_{j},y_{1})\leq
h^{\alpha}(y_{j},y_{j+1})+h^{\alpha}(y_{j+1},y_{1}).$ Therefore the weight
$W({\cal C}^{\prime})$ of ${\cal C}^{\prime}$

$W({\cal
C^{\prime}})=\sum_{i=1}^{j-1}h^{\alpha}(y_{i},y_{i+1})+h^{\alpha}(y_{j},y_{1})\leq\sum_{i=1}^{j}h^{\alpha}(y_{i},y_{i+1})+h^{\alpha}(y_{j+1},y_{1})=W({\cal
C}).$

Therefore $TSP(x_{1},\ldots,x_{j})\leq W({\cal C}^{\prime})\leq W({\cal C}).$
Taking minimum over all cycles ${\cal C}$ with vertex set $\\{x_{i}\\}_{1\leq
i\leq j+1},$ we get (7.5) for $k=1.$

### Moments of random variables

Let $X\geq 1$ be any integer valued random variable such that

$\mathbb{P}(X\geq l)\leq e^{-\theta(l-1)}$ (7.6)

for all integers $l\geq 1$ and some constant $\theta>0$ not depending on $l.$
For every integer $r\geq 1,$

$\mathbb{E}X^{r}\leq r\sum_{l\geq 1}l^{r-1}\mathbb{P}(X\geq l)\leq
r\sum_{l\geq 1}l^{r-1}e^{-\theta(l-1)}\leq\frac{r!}{(1-e^{-\theta})^{r}}$
(7.7)

_Proof of ( 7.7)_: For $r\geq 1$ we have

$\mathbb{E}X^{r}=\sum_{l\geq 1}l^{r}\mathbb{P}(X=l)=\sum_{l\geq
1}l^{r}\mathbb{P}(X\geq l)-l^{r}\mathbb{P}(X\geq l+1)$ (7.8)

and substituting the $l^{r}$ in the final term of (7.8) with
$(l+1)^{r}-((l+1)^{r}-l^{r})$ we get

$\displaystyle\mathbb{E}X^{r}$ $\displaystyle=$ $\displaystyle\sum_{l\geq
1}\left(l^{r}\mathbb{P}(X\geq l)-(l+1)^{r}\mathbb{P}(X\geq l+1)\right)$ (7.9)
$\displaystyle\;\;\;\;\;\;\;\;+\;\;\;\sum_{l\geq
1}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$ $\displaystyle=$ $\displaystyle
1+\sum_{l\geq 1}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$ $\displaystyle=$
$\displaystyle\sum_{l\geq 0}((l+1)^{r}-l^{r})\mathbb{P}(X\geq l+1)$

where the second equality is true since $l^{r}\mathbb{P}(X\geq l)\leq
l^{r}e^{-\theta(l-1)}\longrightarrow 0$ as $l~{}\rightarrow~{}\infty.$ Using
$(l+1)^{r}-l^{r}\leq r\cdot(l+1)^{r-1}$ in (7.9), we get the first relation in
(7.7).

We prove the second relation in (7.7) by induction as follows. Let
$\gamma=e^{-\theta}<1$ and $J_{r}:=\sum_{l\geq 1}l^{r-1}\gamma^{l-1}$ so that

$J_{r+1}(1-\gamma)=\sum_{l\geq 1}l^{r}\gamma^{l-1}-\sum_{l\geq
1}l^{r}\gamma^{l}=\sum_{l\geq 1}\left(l^{r}-(l-1)^{r}\right)\gamma^{l-1}.$

Using $l^{r}-(l-1)^{r}\leq r\cdot l^{r-1}$ for $l\geq 1$ we therefore get that

$J_{r+1}(1-\gamma)\leq r\sum_{l\geq 1}l^{r-1}\gamma^{l-1}=rJ_{r}$

and so the second relation in (7.7) follows from induction.

### Scaling and translation relations

For a set of nodes $\\{x_{1},\ldots,x_{n}\\}$ in the unit square $S,$ recall
from Section 1 that $K_{n}(x_{1},\ldots,x_{n})$ is the complete graph formed
by joining all the nodes by straight line segments and the edge
$(x_{i},x_{j})$ is assigned a weight of $d^{\alpha}(x_{i},x_{j}),$ where
$d(x_{i},x_{j})$ is the Euclidean length of the edge $(x_{i},x_{j}).$ We
denote $TSP(x_{1},\ldots,x_{n})$ to be the length of the minimum spanning
cycle of $K_{n}(x_{1},\ldots,x_{n})$ with edge weights obtained as in (1.4),

_Scaling_ : For any $a>0,$ consider the graph $K_{n}(ax_{1},\ldots,ax_{n})$
where the length of the edge between the vertices $ax_{1}$ and $ax_{2}$ is
simply $a$ times the length of the edge between $x_{1}$ and $x_{2}$ in the
graph $K_{n}(x_{1},\ldots,x_{n})$ Using the definition of TSP in (1.4) we then
have $TSP(ax_{1},\ldots,ax_{n})=a^{\alpha}TSP(x_{1},\ldots,x_{n})$ and so if
$Y_{1},\ldots,Y_{n}$ are $n$ nodes uniformly distributed in the square $aS$ of
side length $a,$ then

$TSP(n;a):=TSP(Y_{1},\ldots,Y_{n})=a^{\alpha}TSP(X_{1},\ldots,X_{n}),$

where $X_{i}=\frac{Y_{i}}{a},1\leq i\leq n$ are i.i.d. uniformly distributed
in $S.$ Recalling the notation $TSP_{n}=TSP(X_{1},\ldots,X_{n})$ from (1.4) we
therefore get

$\mathbb{E}TSP(n;a)=a^{\alpha}\mathbb{E}TSP_{n}.$ (7.10)

_Translation_ : For $b\in\mathbb{R}^{2}$ consider the graph
$K_{n}(x_{1}+b,\ldots,x_{n}+b).$ Using the translation property $(b2),$ the
weight $h(x_{1}+b,x_{2}+b)\leq h_{0}\cdot h(x_{1},x_{2}),$ the weight of the
edge between $x_{1}$ and $x_{2}.$ Using the definition of TSP in (1.4) we
therefore have

$TSP(x_{1}+b,\ldots,x_{n}+b)\leq h_{0}^{\alpha}\cdot TSP(x_{1},\ldots,x_{n}),$
(7.11)

obtaining the desired bound.

### Acknowledgement

I thank Professors Rahul Roy, Thomas Mountford, Federico Camia, C. R.
Subramanian and the referee for crucial comments that led to an improvement of
the paper. I also thank IMSc for my fellowships.

## References

  * [1] Beardwood, J., Halton, J. H. and Hammersley, J. M. (1959)  The shortest path through many points.  Proceedings Cambridge Philosophical Society, 55, pp. 299–327.
  * [2] Bradonjic, M., Elsasser, R., Friedrich, T., Sauerwald, T. and Stauffer, A. (2010)  Efficient Broadcast on Random Geometric Graphs.  Proceedings SODA 2010, pp. 1412–1421.
  * [3] Gutin, G. and Punnen, A. P. (2006)  The traveling salesman problem and its variations.  Springer.
  * [4] Steele, J. M. (1981)  Subadditive Euclidean functionals and nonlinear growth in geometric probability.  Annals of Probability, 9, pp. 365–376.
  * [5] Steele, J. M. (1997)  Probability Theory and Combinatorial Optimization.  SIAM.
  * [6] Steinerberger, S. (2015)  New bounds for the Traveling Salesman constant.  Advances in Applied Probability, 47, pp. 27–36.
  * [7] Rhee, W. T. (1991)  On the Fluctuations of the Stochastic Traveling Salesperson Problem.  Mathematics of Operation Research, 16, pp. 482–489.
  * [8] Yukich, J. (1998)  Probability Theory of Classical Euclidean Optimization Problems.  Lecture Notes in Mathematics, 1675, Springer.