Sample integer points of cross-polytope uniformly

Question

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

Igor Rivin · Accepted Answer · 2016-01-23 19:20:38Z

2

Look at page two of Kannan and Vempala.

answered Jan 23, 2016 at 19:20

Igor Rivin

95.6k11 gold badges147 silver badges357 bronze badges

$\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$
– Tobias Windisch
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$
– Tobias Windisch
Jan 25, 2016 at 6:55

Add a comment |

1 Answer 1