2
$\begingroup$

Let $p_1, ... ,p_n$ be chosen independently from the uniform distribution on the unit torus $[0,1]^2$.

I want to prove a theorem of the form: "With high probability, every circle of radius $r$ contains approximately $\pi r^2 n$ points".

The problem is that there are infinitely many circles, so proving concentration for a single circle and then union bounding won't work. How do I do this?

Improve this question
$\endgroup$
3
  • $\begingroup$ How strong do you want the concentration to be? You can tile the torus with very small squares such that the boundary of each disk intersects a few squares, and then union bound the event "empirical density of each square is close to its expected density". $\endgroup$
    – Daniel Paleka
    Commented May 20, 2021 at 11:17
  • $\begingroup$ So I figured out a similar way to use discrete methods, which might be equivalent to Iosif's answer below: Take an $n \times m$ grid of circle centers, and consider all circles with centers in the grid and radius either $r+\frac{1}{m}$ or $r-\frac{1}{m}$. We can get concentration for these circles and then use the fact that all radius $r$ circles contain and are contained in the circles of the nearest grid point. $\endgroup$
    – Zur Luria
    Commented May 23, 2021 at 5:49
  • 1
    $\begingroup$ I am still surprised that there seems to be no "clean" continuous approach here that doesn't reduce the problem to the discrete case. $\endgroup$
    – Zur Luria
    Commented May 23, 2021 at 5:51

1 Answer 1

Reset to default
3
$\begingroup$

$\newcommand\C{\mathscr C}\newcommand\ep{\varepsilon}$Let $\C$ denote the set of all disks of a radius $r\in(0,\infty)$ contained in the unit square. Using a rectangular grid of centers of disks in $\C$, we can cover $\C$ by $N=O(r^2/\ep^2)$ balls of radius $\ep\in(0,\infty)$, where the balls are considered with respect to the distance between disks equal the Lebesgue measure of the symmetric difference between the disks and the constant in $O(\cdot)$ is universal.

Hence, Talagrand's Theorem 1.1 for empirical measures (used here with $v=2$) implies the following: $$P\Big(\sup_{C\in\C}\Big|\sum_1^n 1(p_j\in C)-\pi r^2 n\Big|\ge z\sqrt n\Big) \le K(r)z^3e^{-2z^2} \tag{1}$$ for all real $z>0$, where $K(r)\in(0,\infty)$ depends only on $r$ (in a way that can be found from the proof).

Obviously, a condition of the form $z\ge c$ with a universal constant $c\in(0,\infty)$ is missing here; cf. e.g. Azencott and Vayatis, p. 564.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .