Rates of convergence of means of Euclidean functionals

DOI10.1007/S10959-007-0089-7MaRDI QIDQ2471129zbMATH OpenOpenAlexFDO

Authors Yoo Young Koo, Sungchul Lee

Publication date 18 February 2008

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609382

zbMATH Keywords

Euclidean functionalsrate of convergencetraveling salesman problem

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Strong limit theorems (60F15)

Abstract: Let $L$ be the Euclidean functional with $p$-th power-weighted edges. Examples include the sum of the $p$-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (1994, 1996) have shown that for $n$ i.i.d. sample points $X_1,\mathrm{...},X_n$ from $[0,1{]}^d$, $L(X_1,\mathrm{...},X_n)/n^{(d-p)/d}$ converges a.s. to a finite constant. Here we bound the rate of convergence of $EL(X_1,\mathrm{...},X_n)/n^{(d-p)/d}$.

Review text

Let \(X_1,\dots, X_n\) be i.i.d. random vectors with values in \(\mathbb{R}^d\). A special class of functions \(L(X_1,\dots, X_n)\), called Euclidean functionals, have been studied in a series of papers of a number mathematicians. In the paper the rate of convergence of mathematical expectations \(EL(X_1,\dots X_n)/b_n\), \(n\to\infty\), is investigated. Constants \(b_n\), \(n= 1,2,\dots\) are of a special form, for example \(n^{(d-p)/d}\) with \(p\in [1,d)\). Proofs are based on ideas from \textit{C. Redmond} and \textit{J. E. Yukich} [Ann. Appl. Probab. 4, No. 4, 1057--1073 (1994; Zbl 0812.60033) and Stochastic Processes Appl. 61, No. 2, 289--304 (1996; Zbl 0849.60030)]. All results are rather bulky to be cited here. The sum of the \(p\)th power-weighted length of the edges in a minimal tour \(\pi\) is an Euclidean function. The minimal tour \(\pi\) is a permutation on \(\{1,\dots, n\}\) with \(\pi(n+ 1)= \pi(1)\) such that \[ \sum^n_{k=1} |X_{\pi(k+1)}- X_{\pi(k)}|^p= \min\Biggl\{\sum^n_{k=1} |X_{\pi'(k+1)}- X_{\pi'(k)}|^p:\pi'\text{ a permutation on }\{1,\dots, n\}\Biggr\}. \]

Recommendations

• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems
• Asymptotics for Euclidean functionals with power-weighted edges
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Asymptotic of power-weighted Euclidean functionals

Cites work

• Asymptotic of power-weighted Euclidean functionals
• Asymptotics for Euclidean functionals with power-weighted edges
• Boundary effects in the traveling salesperson problem
• Complete Convergence of Short Paths and Karp's Algorithm for the TSP
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Limit theorems and rates of convergence for Euclidean functionals
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• Probability theory of classical Euclidean optimization problems
• Rate of convergence for the Euclidean minimum spanning tree limit law
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Subadditive Euclidean functionals and nonlinear growth in geometric probability

Cited in

(9)

• Rates of convergence of means for distance-minimizing subadditive Euclidean functionals
• Limit theorems and rates of convergence for Euclidean functionals
• Rate of convergence of power-weighted Euclidean minimal spanning trees
• Asymptotic of power-weighted Euclidean functionals
• Strong laws for Euclidean graphs with general edge weights
• Worst case asymptotics of power-weighted Euclidean functionals
• Convergence Rate for Degenerate von Mises Functionals
• Limit theorems in discrete stochastic geometry
• Rate of convergence of the mean for sub-additive ergodic sequences

This page was built for publication: Rates of convergence of means of Euclidean functionals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2471129)