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

• 成果类型: Article
• 署名作者: Arlotto, Alessandro; Steele, J. Michael
• 署名单位: Duke University; University of Pennsylvania
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/15-AAP1142
• 发表日期: 2016
• 页码: 2141-2168
• 关键词: euclidean traveling salesman; power-weighted edges; CONVERGENCE; functionals; asymptotics; points; paths; rates

摘要

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.