What is the probability that these sets intersect?

Question

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

Answer 1

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$.

Answer 2

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

---

         
          ^{Set $A$ for $d = 0.6$ in origin-centered unit cube.}

---