APPROXIMATING A LINE THROWN AT RANDOM ONTO A GRID
成果类型：
Article
署名作者：
Hall, Peter; Raimondo, Marc
署名单位：
Australian National University; Commonwealth Scientific & Industrial Research Organisation (CSIRO)
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1997
页码：
648-665
关键词：
摘要：
Throw a straight line at random into a plane, within which is inscribed a square grid. Color black each grid vertex that lies above the line, and white each vertex below it. Now remove the line, and attempt to reconstruct it from the pattern of vertex colors in an m x m section of the grid. We show that for all epsilon > 0, the line can be approximated to within order m(-1) (log m)(log log m)(1+epsilon), with probability 1, and that there is no deterministic subsequence along which the best achievable rate is better than (m log m)(-1)(log log m)(-1-epsilon) with positive probability. Both these results fail if epsilon = 0. More generally, we provide a complete characterization of almost sure rates of approximation, in terms of the convergence or divergence of an infinite series. Applying these results, we develop near-optimal local linear approximations to general smooth boundaries. We address the case where vertex color is a shade of gray, varying in the continuum and subject to stochastic error.