4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Just to be clear: There is just one weight function $w$ here? (Since you wrote "For each $x$, let...") $\endgroup$
    – Mitch
    Jan 6, 2010 at 3:30
  • $\begingroup$ Yes, there is just one weight function w. $\endgroup$
    – Wilson
    Jan 6, 2010 at 4:17

1 Answer 1

1
$\begingroup$

Is your weight convex or concave? Your property 1) is self-contradictory.

In the concave case, you can just take a uniform, polynomial size sample from your simplex and select your point from this selection based on the actual weights.

In the convex case, the same algorithm works if the average of $w$ is comparable to the maximum (both can be obtained in polynomial time by taking a uniform sample and by local descent respectively). If that is not the case, then you can test the same property for the projection of $w$ onto one of the facets of $\mathcal L$. If this projection has the required property, you sample from that facet according to the projected weight and then sample from the fiber over the selected point according to $w$ if the property still does not hold, you take an $n-2$ dimensional face etc. When you get down to vertices, you already know that $w$ is concentrated around the vertices of $\mathcal L$ and can find neighbourhoods of them containing almost all of the weight and having the property of the average of $w$ being comparable to the maximum of $w$ within these neighbourhoods (choose the entire $L$ and repeatedly shrink it by a factor of $1-\frac{1}{poly}$ and test the condition). From those neighbourhoods, choose one according to their total weight, and within the chosen one, take a polynomial size uniform sample and sample according to $w$ from within it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.