Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: A counterexample

We construct a stationary ergodic process X1;X2;::: such that each Xt has the uniform distribution on the unit square and the length Ln of the shortest path through the points X1;X2;:::;Xn is not asymptotic to a constant times the square root of n. In other words, we show that the Beardwood, Halton and Hammersley theorem does not extend from the case of independent uniformly distributed random variables to the case of stationary ergodic sequences with uniform marginal distributions.