convex polytopes - Efficiently sampling points from an integer lattice.

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 < 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_{yinmathcal{L}}w(y)}$$

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.

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.

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

Is there a known method that would allow efficient sampling from this distribution?

• Next ag.algebraic geometry - Upper bound on greatest prime of bad reduction for a plane curve
• Previous naked eye - Seconds of Arc and the Unaided Eye