8
$\begingroup$

Let $A$ be the subset of $\mathbb{R}^n$ defined by $A=\{x\in\mathbb{R}^{n}:|x_{1}-x_{n}|+\sum_{i=1}^{n-1}|x_{i+1}-x_{i}|\leq d\}$ for a given $d$. Next, sample a point $p$ uniformly in the unit cube, and let $B$ be the $\ell_1$ ball of fixed radius $r$ about $p$. Is there a good upper bound for the probability that $A\cap B$ is nonempty, in terms of $n$, $d$, and $r$? I am most interested in limiting behavior as $n\to\infty$ (in which case, obviously, $d$ and $r$ would have to depend on $n$).

$\endgroup$
4
  • $\begingroup$ You seem to use $\ell$ in two different senses... $\endgroup$ Sep 1, 2017 at 19:04
  • $\begingroup$ Why isn't this the same question as taking $r=0$ and $d=d+r$? $\endgroup$ Sep 2, 2017 at 9:51
  • $\begingroup$ @AnthonyQuas, if that were the case, then it would also be the same as taking $r=d+r$ and $d=0$. If we take $d+r=1$ and have $p=(0,1)$, then your set is empty, whereas the new set I just described is not. $\endgroup$ Sep 2, 2017 at 18:08
  • $\begingroup$ Hmmm... Maybe I meant $d=d+2r$? If I'm right that there's a reformulation like this, it will clearly make your problem much easier. $\endgroup$ Sep 2, 2017 at 20:28

2 Answers 2

4
$\begingroup$

For $n=3$ this is easy. A triple is in $A$ iff its maximum and minimum are within $d/2$. So $A \cap B_p$ is non-empty iff the maximum and minimum coordinates of $p$ are within $c=\min(1,d/2+2r)$. This has probability $$6\left(\int_{x=0}^{1-c} \int_{y=x}^{x+c} \int_{z=y}^{x+c} dz\, dy\, dx + \int_{x=1-c}^1 \int_{y=x}^1 \int_{z=y}^1 dz\, dy\, dx \right) $$ $$=6\left(\frac{c^2-c^3}{2}+\frac{c^3}{6}\right)=3c^2-2c^3.$$

We'd need other descriptions of $A$ in higher dimensions to make this work for larger $n$.

$\endgroup$
2
$\begingroup$

Not an answer. Just wanted to see what your set $A$ looks like in $\mathbb{R}^3$:


          SolbergSet
          Set $A$ for $d = 0.6$ in origin-centered unit cube.


$\endgroup$

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.