6
$\begingroup$

For $r,d\in\mathbb{N}$, let

$$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$

be the set of integer points of the $d$-dimensional cross-polytope with radius $r$.

What is (currently) the fastest way to sample from $C_{r,d}$ uniformly? Is there a method which is polynomial in $d$ and $\log(r)$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Look at page two of Kannan and Vempala.

$\endgroup$
2
  • $\begingroup$ If I understand their paper correctly, then they give an algorithm which is polynomial in $d$ and $\frac{1}{\epsilon}$ to sample from a distribution on $C_{r,d}$ whose distance from the uniform distribution on $C_{r,d}$ is at most $\epsilon$ (in total variance), provided that $r\in\Omega(d\cdot\sqrt{d})$. What about the other cases? For example, $r=1$ or $r\in\mathcal{O}(d)$? $\endgroup$ Jan 24, 2016 at 11:06
  • $\begingroup$ According to Lemma 1 of their paper, the size of $r$ depends also on $\epsilon$, i.e., $r\ge 8\cdot d\cdot\sqrt{\log{\frac{2^d}{\epsilon}}}$. Does that mean that their method cannot be arbitrarily exact for fixed $r$ and $d$? $\endgroup$ Jan 25, 2016 at 6:55

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.