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$
  • $\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 '17 at 8:27
  • $\begingroup$ @domotorp: we can suppose the coordinates are between 0 and 1, wlog (by scaling coorsinates). $\endgroup$ – j.s. Jan 26 '17 at 12:18
  • $\begingroup$ I know, that's why I suggested it. $\endgroup$ – domotorp Jan 26 '17 at 12:19
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)$.

| cite | improve this answer | |
$\endgroup$
  • $\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 '17 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 '17 at 4:36
  • 1
    $\begingroup$ I tried the case $n=3$ numerically, and $1/2$ does appear to be optimal. $\endgroup$ – Robert Israel Jan 23 '17 at 19:02
  • 1
    $\begingroup$ Also for $n=4$, $1/3$ appears to be optimal. I don't have proofs though. $\endgroup$ – Robert Israel Jan 23 '17 at 19:12

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.