5
$\begingroup$

A discrete version of the ham sandwich theorem states as follows (see for instance "Common Hyperplane Medians for Random Vectors" - Hill):

For every $\mu_1,...,\mu_n$ discrete (i.e., purely atomic) probability measures on $\mathbb{R}^n$, there is a hyperplane $H$ defined by $\sum_{i=1}^n a_i x_i =b$ such that for every $1 \leq j \leq n$, we have that $$ \mu_j (\lbrace (x_1,...,x_n ) : \sum_{i=1}^n a_i x_i \geq b \rbrace ) \geq \dfrac{1}{2} \text{ and } \mu_j (\lbrace (x_1,...,x_n ) : \sum_{i=1}^n a_i x_i \leq b \rbrace ) \geq \dfrac{1}{2} .$$

My question is about the error when one considers open half planes. I am looking for a result of the following nature:

Let $\mu_1,...,\mu_n$ are discrete probability measures that are supported on finite sets (I don't know if the assumption on the support makes a difference). Assume there is $0 <\delta$ such that for every $x \in \mathbb{R}^n$ and for every $j$ we have $\mu_j (x) \leq \delta$, then there is $\varepsilon = \varepsilon (\delta)$ and a hyperplane $\sum_{i=1}^n a_i x_i =b$ such that for every $j$, $$ \mu_j (\lbrace (x_1,...,x_n ) : \sum_{i=1}^n a_i x_i > b \rbrace ) \geq \dfrac{1}{2} - \varepsilon \text{ and } \mu_j (\lbrace (x_1,...,x_n ) : \sum_{i=1}^n a_i x_i < b \rbrace ) \geq \dfrac{1}{2} - \varepsilon ,$$ and $\lim_{\delta \rightarrow 0} \varepsilon (\delta ) = 0$.

I assume that this should be a known result, but I haven't found a reference yet.

$\endgroup$
5
$\begingroup$

You could not find a reference because the statement is not true. Suppose that we are in two dimensions but both are measures are concentrated on a line. The first measure is uniform on $1,\ldots,k$ while the second measure is uniform on $-1,\ldots,-k$. In this case any open halfplane has measure $0$ or $1$ with respect to one of the metrics.

If you add the condition that the points in the support are in a general position, then the statement follows trivially from the continuous version.

$\endgroup$

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.