Uniformly sampling with a constraint on a linear combination of logarithms

Question

Suppose we have $N$ fixed reals $p_1, p_2, \dots, p_N$ satisfying $p_i\in [0, 0.5]$ and $N$ variables $q_1, q_2, \dots, q_N$ in the range $[0, 0.5]$ such that $$\sum_{i=1}^{N}p_i\log (q_i) + (1-p_i)\log(1-q_i) = D$$ for some constant $D$. I am struggling to find ways to uniformly sample from the space of all possible distributions in $q_1\times q_2\times\dots\times q_N$ satisfying this constraint. I've looked around the internet and have found methods for uniformly sampling from convex polytopes, but haven't found anything about nonlinear constraints in general. Any help or links to relevant literature would be appreciated.

Answer 1

The issue with your case is not that the set is not polytopal: methods like hit and run or rejection sampling are perfectly fine working with any set of full dimension, and are computationally efficient if that set is convex (depending on how its specified to the routines). Instead the problem is that you're sampling from a boundary of the convex set $\{f(q;p) \ge D\}$, which is dimension-deficient (i.e., it's a $N-1$ dimensional submanifold of $\mathbb{R}^N$). This makes vanilla rejection sampling or hit and run fail: e.g., a uniform over the simplex proposal distribution will a.s. never propose a point in the set, and for hit and run, almost all proposal directions are useless and don't lead to any diffusion. Note that this would also be an issue if you were trying to sample from $\{ q: \sum \alpha_i q_i = a\}$.

Nevertheless, given that your set is the boundary of a convex set, there are algorithmic techniques that are viable. One reference I know is Narayanan, Hariharan, and Partha Niyogi. "Sampling hypersurfaces through diffusion. APPROX 2008". There may well be other methods for this, but I guess this should be enough to give you a start into what kind of terms to search for et c. I'll conclude with a quick description of the scheme from this paper.

---

Here's a description of the scheme: suppose $A$ is a convex set with piecewise smooth boundary, and you have access to a uniform sampler from $A$, and a membership oracle from $A$. In your case $A = [0,0.5]^N \cap \{f(q;p) \ge D\},$ and you can generate an (approximately) uniform sampler via, say, hit and run, and the membership oracle would just evaluate the function and check the level.

Let $\kappa$ be the smallest eigenvalue of $\mathrm{Cov}(X)$ where $X \sim \mathrm{Unif}(A)$, which can be approximated quickly. Then their sampler repeatedly essentially samples $Y = X + \mathcal{N}(0, \sigma^2I),$ where $\sigma^2 \propto \varepsilon^2\kappa/d^2$ and $X \sim \mathrm{Unif}(A)$, until $Y \not\in A,$ and then gives the unique point of $\partial A$ that lies on the line from $X$ to $Y$. Remarkably, this is shown to be $\varepsilon$-accurate in total variation, and to stop in time $O(N^4/\varepsilon).$

There's a small hitch in that instead of a drawing a point uniformly from $A$, you can only do this approximately. This is not a big deal though, because if you can ensure that the distribution of $X$ is $\varepsilon$-close to $\mathrm{Unif}(A),$ then this just increases the error rate of the boundary sample by another $\varepsilon$.