Concentration inequality involving the ball of a fixed radius from uniform distribution

51 Views Asked by At

Let $X_1, \cdots ,X_n$ be uniformly and independently distributed points in the $m \times m$ square with $m = \sqrt{n}$ and let $Y = | \cup_i B_{X_i}(1)|$ where $B_{X}(r)$ is the ball of radius $r$ about the point $P$. Show that there exists some fixed $c >0$ such that

$$ P(| Y - \mathbf{E}(Y)| > \epsilon\sqrt{n}) \leq e^{-c\epsilon^2}) $$ $|.|$ is the cardinality of the set.

I tried to solve this as follows: since each $X_i$ are iids $Y$ is the sum of iids. My plan was to use Hoeffding's inequality, but $X_i$s are not bounded. So I am stuck. Any help ?. This is the second question given here https://sites.math.washington.edu/~eyal/523A/lec/hw-1.pdf.

NB: this is an exercise for self study.