2
$\begingroup$

Suppose we have a subset $S\subseteq I_0\times I_1\times \dotsm \times I_{d-1}$ of a cartesian product of finite intervals $I_i\subseteq\mathbb{N}$, with $S$ defined by explicity specified computable logical conditions in classical logic (I am favoring a vague-yet-brief over explict-yet-long description of the problem I am having).

Suppose that also we have to sample from $S$ uniformly at random, explicitly, via a computer program. To my mind, there are two clearly distinct approaches:

  1. Explictly write down a parametrization of $S$ with domain a single interval, in other words, explicitly define a bijective function (or, here, a path) $P\colon I\rightarrow S$, and then sample from $I$ uniformly at random, and take the $P$-images of those samples as the sample points you are really interested in. One could call this Hamilton-path-sampling. This results in a uniform distribution on your shape $S$.

  2. Sample uniformly at random from the product $I_0\times I_1\times\dotsm I_{d-1}$ and do rejection sampling, i.e., let the algorithm check after each sample whether the logical conditions defining $S$ are satisfied, and, if not, discard the sample. This, too, results in a uniform distribution on your shape $S$.

Questions.

(0) Are there any mathematical reasons for whether to use approach 1. or 2., *apart from the evident reason that if $\lvert S\rvert$ is much smaller than $\lvert I_0\times I_1\times\dotsm\times I_{d-1}\rvert$, then the rejection sampling involves a much larger sample space?

(1) Are there literature references dedicated to the above distinction? I.e., not just anything from sampling theory, Markov chain theory, and so, but rather a references addressing this particular decision: whether to parametrize a given shape via one (Hamilton-)path, or whether to do rejection sampling?

I expect that there is not much to say in general mathematically on this, and that it just depends on the problem at hand. Apart from a vague tradeoff 'Hamilton-path sampling requires you to write down a potentially complicated parametrization yet gives you a smaller sample space;rejection sampling lets you just re-use the logical conditions you used to implicitly define $S$ yet gives you a larger sample space.

I would appreciate to learn of relevant mathematical reasons which approach to choose.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.