2
$\begingroup$

Consider a two dimensional square domain ($S$) of size $l \times l$. We generate a point $\mathbf{x}_i = (x_i,y_i)$ in S with uniform distribution, i.e., the point is equally likely to be anywhere inside the domain.

Let $\mathbf{x}$ be any other point in the domain $S$. The distance of the point from $\mathbf{x}_i$ (in $\ell_2$ sense) is denoted by $d(\mathbf{x},\mathbf{x}_i)$. I am interested in finding the expected value of the maximum distance of any other point from the generated point, i.e.,

\begin{equation} E[\max_{\mathbf{x} \in S} d(\mathbf{x},\mathbf{x}_i)], \end{equation} where the expectation is taken over the uniform distribution of $\mathbf{x}_i$ in $S$.

Can this result be generalized to squares in higher dimension?

$\endgroup$
4
$\begingroup$

We can assume that our square is $2\times 2$, and scale by $\frac{l}{2}$ at the end.

Imagine that our square has corners $(0,0)$, $(0,2)$, $(2,2)$, $(0,2)$.

Divide our square into four $1\times 1$ squares. Without loss of generality we may assume that our variable point is chosen in the northeast little square. Then the point furthest away is the origin. So our expected maximum distance is $$\int_1^2 \int_1^2\sqrt{x^2+y^2}\,dx\,dy.$$ By changing to polar coordinates, we can compute the above integral in closed form.

$\endgroup$
6
  • $\begingroup$ +1: Maxima gives this (after halving) to be about $1.070447$. Simulation confirms the first few digits. $\endgroup$ – Henry Dec 9 '13 at 23:57
  • 1
    $\begingroup$ Isn't it true that the maximum distance, $\max_{\mathbf{x} \in S} d(\mathbf{x},\mathbf{x}_i) \geq \sqrt{2}$ for a square of size $2 \times 2$? $\endgroup$ – Sumeet Kumar Dec 10 '13 at 0:25
  • $\begingroup$ For a $2\times 2$ square, sure. But in terms of $l$, it is $\frac{\sqrt{2} \,l}{2}$. $\endgroup$ – André Nicolas Dec 10 '13 at 0:28
  • $\begingroup$ How about $\frac{3l}{2\sqrt{2}}$ as the solution? And in a $D$-dimensional domain, $\frac{3\sqrt{D}l}{4}$ as the solution? $\endgroup$ – Sumeet Kumar Dec 10 '13 at 1:09
  • $\begingroup$ I have not done he integration. Maybe one can find a closed form. Your suggestion does not agree with the numerical computation by Henry, though it is not far away. For $3$ dimensions, the same argument will work, a triple integral involving $\sqrt{x^2+y^2+z^2}$. Probably the same idea works in an arbitrary number of dimensions. But I have not written it out for arbitrary dimensions, and prefer to make claims only about what I know for sure. $\endgroup$ – André Nicolas Dec 10 '13 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.