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

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

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?

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_{y\in\mathcal{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?