BEARDWOOD-HALTON-HAMMERSLEY THEOREM FOR STATIONARY ERGODIC SEQUENCES: A COUNTEREXAMPLE

We construct a stationary ergodic process X-1, X-2,... such that each X-t has the uniform distribution on the unit square and the length Ln of the shortest path through the points X-1, X-2,, X-n is not asymptotic to a constant times the square root of n. In other words, we show that the Beardwood, Halton, and Hammersley [Proc. Cambridge Philos. Soc. 55 (1959) 299-327] theorem does not extend from the case of independent uniformly distributed random variables to the case of stationary ergodic sequences with uniform marginal distributions.