1. Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: A counterexample
- Author
-
Alessandro Arlotto and J. Michael Steele
- Subjects
90C27 ,Statistics and Probability ,Uniform distribution (continuous) ,Beardwood–Halton–Hammersley theorem ,construction of stationary processes ,Stationary ergodic process ,Unit square ,01 natural sciences ,subadditive Euclidean functional ,Combinatorics ,Traveling salesman problem ,010104 statistics & probability ,equidistribution ,Mathematics::Probability ,Square root ,Primary 60D05, 90B15, Secondary 60F15, 60G10, 60G55, 90C27 ,FOS: Mathematics ,Ergodic theory ,60D05 ,0101 mathematics ,Mathematics - Optimization and Control ,Mathematics ,Mathematics::Commutative Algebra ,stationary ergodic processes ,Probability (math.PR) ,010102 general mathematics ,90B15 ,Optimization and Control (math.OC) ,60F15 ,60G55 ,Statistics, Probability and Uncertainty ,Marginal distribution ,60G10 ,Random variable ,Mathematics - Probability ,Counterexample - Abstract
We construct a stationary ergodic process $X_1, X_2, \ldots $ such that each $X_t$ has the uniform distribution on the unit square and the length $L_n$ of the shortest path through the points $X_1, X_2, \ldots,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 theorem does not extend from the case of independent uniformly distributed random variables to the case of stationary ergodic sequences with uniform marginal distributions., 24 pages, 1 figure
- Published
- 2016