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


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


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.