5
$\begingroup$

Let $T$ be a set of $n\ge 3$ points in the plane such that not all of them lie in a common line. Pick two distinct points $\{a=\left( \begin{array}{c} a_{1} \\a_{2} \end{array} \right) ,b=\left( \begin{array}{c} b_{1} \\b_{2} \end{array} \right)\}$ uniformly at random from $T$. Let $R$ be the rectangle whose sides are horizontal and vertical, and whose two diagonally opposite vertices are $\{a,b\}$. Let $X$ be the length of horizontal side of $R$ and $Y$ be the length of its vertical side (i.e. $X=|a_{1}-b_{1}|$ and $Y=|a_{2}-b_{2}|$).

Assuming $\mathbb{E}(X)=\mathbb{E}(Y)$, how small can be expected value of random variable $Z := \min(X,Y)$? What lower bounds can one get for $\mathbb{E}(Z)$?

$\endgroup$
3
  • $\begingroup$ What happens if we suppose that the coordinates are between 0 and 1, and instead of $Z=min(X,Y)$, we ask the same thing about $Z'=X\cdot Y$? This might be easier to handle. $\endgroup$
    – domotorp
    Jan 25, 2017 at 8:27
  • $\begingroup$ @domotorp: we can suppose the coordinates are between 0 and 1, wlog (by scaling coorsinates). $\endgroup$
    – j.s.
    Jan 26, 2017 at 12:18
  • $\begingroup$ I know, that's why I suggested it. $\endgroup$
    – domotorp
    Jan 26, 2017 at 12:19

1 Answer 1

8
$\begingroup$

Since you can scale everything linearly, let's suppose $\mathbb E(X) = \mathbb E(Y) = 1$.

I'm not sure this is optimal, but I think it must be close. Consider a case where all but two of the points are at the origin, with one point (call it $c$) at $(n/2, 0)$ and one ($d$) at $(0, n/2)$. (You actually want $n$ distinct points, so make all but two points very close to the origin, and insert the word "approximately" as needed below). Then $X = 0$ unless one of your two points is $c$ (which has probability $2/n$ and makes $X = n/2)$, so $\mathbb E(X) = 1$, and similarly $Y = 0$ unless one of your points is $d$. $Z = 0$ unless both $c$ and $d$ are chosen, which has probability $2/(n(n-1))$, so $\mathbb E(Z) = 1/(n-1)$.

$\endgroup$
4
  • $\begingroup$ This is good, and my intuition was also that $Z$ can be very small. I wonder if it could be much smaller than the construction you give (say $1/n^2$). If the truth is $c/n$, then a proof of that might be easy [haven't thought much]. $\endgroup$
    – Pat Devlin
    Jan 18, 2017 at 0:11
  • $\begingroup$ @Dear Robert: thanks. I think that your construction has minimum $\mathbb E(Z)$. Do you have any idea how we might prove we have always $\mathbb E(Z) \ge 1/(n-1)$? $\endgroup$
    – j.s.
    Jan 18, 2017 at 4:36
  • 1
    $\begingroup$ I tried the case $n=3$ numerically, and $1/2$ does appear to be optimal. $\endgroup$ Jan 23, 2017 at 19:02
  • 1
    $\begingroup$ Also for $n=4$, $1/3$ appears to be optimal. I don't have proofs though. $\endgroup$ Jan 23, 2017 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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