Rough estimate of number of bad indices?

33 Views Asked by At

Suppose I have $n$ pairs of points in a plane $P = \{(x_i,y_i)\}_{i=1}^n$ in a plane. Let $X^2=\sum_{i}x_i^2$ and $Y^2=\sum_{i}y_i^2$. Further assume that $Y^2 \leq \epsilon^4X^2$ for some error parameter $0<\epsilon\leq1$.

Define $GOOD = \{i\in[n] : y_i^2 \leq \epsilon x_i^2\}$, and $BAD= [n]-GOOD$. Since sum of squares of y-coordinate is "very" small compared to sum of squares of x-coordinates, I think there should not be lots of indices in $BAD$ set.

Clearly $\vert BAD\vert < n$, i.e not all points are bad. Is there a sharper upper bound other that the aforementioned obvious bound?

My goal is to show that if I sample a point uniformly from $P$, then it should not land in $BAD$ set with high probability.

1

There are 1 best solutions below

4
On BEST ANSWER

No, there is no sharper bound.

Indeed, you can make $n-1$ of the points bad and then adjust the final point to be extremely good to make $Y^2\leq \epsilon^4 X^2$. The reason this is possible is that the latter inequality only involves aggregate quantities.

More explicitly, fix any values for $x_1,\ldots,x_{n-1}$ and let $y_i=2x_i$ for $i=1,\ldots,n-1$. Then $$ Y^2=4(X^2-x_n^2)+y_n^2, $$ so the inequality $Y^2\leq \epsilon^4 X^2$ is equivalent to $$ 4(X^2-x_n^2)+y_n^2\leq \epsilon^4 X^2. $$ We can choose $y_n=0$ and thus the inequality is satisfied whenever $$ (1-\frac{\epsilon^4}{4})X^2\leq x_n^2, $$ which can be arranged by choosing $$x_n^2\geq \frac{4-\epsilon^4}{\epsilon^4} (x_1^2+\cdots +x_{n-1}^2).$$

In summary, any set of points $(x_1,2x_1),\ldots,(x_{n-1},2x_{n-1}),(x_n,0)$ with non-zero $x_i$ and satisfying $$ |x_{n}|\geq \sqrt{\frac{4-\epsilon^4}{\epsilon^4}(x_1^2+\cdots+x_{n-1}^2)} $$ will have $n-1$ bad points and $1$ good point and fit your condition.