Expected value of number of dots in random placed circle

228 Views Asked by At

Given a square with vertices at $(0,0), (1,0), (0,1), (1,1)$ and $N$ labeled dots in this square with coordinates $(x_i, y_i)$. Bowser picks a dot $(a, b)$ in square (with uniform distribution) and counts score: number of labeled dots that are in a circle including border with center $(a, b)$ and radius $R$. Find expected value of score.

We have a random variable $\xi$ that is finite, because its values are nonnegative integers in range $[0, N]$, so its EV could be calculated using this formula: $E[\xi] = \sum_{i=1}^{N+1} x_ip_i$. However I can't figure out formulas for probabilities because it's all parameterized and would be happy to hear some ideas.

1

There are 1 best solutions below

0
On

Let $Q$ denote the square.

Think of it a little differently. Let $\xi_1,\dots,\xi_N$ be the indicators that point $1,\dots,N$ respectively, is in the circle. Therefore $\xi = \sum_{i=1}^N \xi_i$, and $E[\xi] = \sum_{i=1}^N E[\xi_i]=\sum_{i=1}^N P(\xi_i=1)$.

Now $\xi_i=1$ if and only if the distance between $(x_i,y_i)$ and $(a,b)$ is $\le R$. That is $\xi_i=1$ if and only if $(a,b)$ is in the disk of radius $R$ centered at $(x_i,y_i)$. Denote this disk by $B_i$. Because $(a,b)$ is uniformly distributed on $Q$ and $Q$ has area $1$, the probability of this event is equal to the area of the intersection $B_i \cap Q$, we denote this area by $|B_i \cap Q|$.

Thus, $$E[\xi] = \sum_{i=1}^N |B_i \cap Q|.$$

The numerical answer depends on the choice of the points and on $R$ (think of the case of small $R$ and all are near corners, or all are near the center).

Nevertheless, one can get two-sided bounds, depending only on $R$ and $N$, but not on the choice of the balls: $N\min(\pi R^2,1)$ is an easy upper bound, while for a lower bound one needs to work a little more.

You can also see that as $R\to \infty$ the expectation tends to $N$ and as $R\to 0$ the expectation $E[\xi] \sim N \pi R^2$.

Hope this helps.