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)$?

Improve this question
$\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
    Commented 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.
    Commented Jan 26, 2017 at 12:18
  • $\begingroup$ I know, that's why I suggested it. $\endgroup$
    – domotorp
    Commented Jan 26, 2017 at 12:19

1 Answer 1

Reset to default
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)$.

Improve this answer
$\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
    Commented 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.
    Commented Jan 18, 2017 at 4:36
  • 1
    $\begingroup$ I tried the case $n=3$ numerically, and $1/2$ does appear to be optimal. $\endgroup$
    – Robert Israel
    Commented 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$
    – Robert Israel
    Commented Jan 23, 2017 at 19:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .