User wilson - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T02:58:16Z http://mathoverflow.net/feeds/user/3024 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice Efficiently sampling points from an integer lattice. Wilson 2010-01-06T00:02:59Z 2010-01-06T10:00:20Z <p>Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m &lt; n$. For each $x \in \mathcal{L}$, let w : $\mathcal{L}$ $\rightarrow$ $\mathcal{R}^+$ denote an efficiently computable weighting function. Let $\mathcal{D}$ define a probability distribution over $\mathcal{L}$ that selects each element from $\mathcal{L}$ with probability proportional to its weight: $$\Pr_\mathcal{D}[x] = \frac{w(x)}{\sum_{y\in\mathcal{L}}w(y)}$$</p> <p>I would like to (approximately) sample from this distribution efficiently, where efficiently means in time polynomial in n, the dimension of the space. The algorithm may query the weight function $w$ a polynomial number of times. In general, this is hard, but I know two additional facts about the weighting function that I suspect make the problem tractable.</p> <p>1) The weight function is convex: in particular, for any C, the set of points with weight at least C lies inside some convex polytope.</p> <p>2) The weight function is Lipschitz: for any $x,y \in \mathcal{L} : ||x-y||_1 \leq 1$, $|w(x) - w(y)| \leq$ poly(n).</p> <p>Is there a known method that would allow efficient sampling from this distribution?</p>