- Lei Li, Bharath Ramsundar, Stuart J. Russell. 2013. Dynamic Scaled Sampling for Deterministic Constraints. Abstract: Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in which the relationship Z = f(X1;:::;Xk) holds, where each Xi has a continuous prior pdf and we wish to obtain samples from the conditional distribution P (X1;:::;Xkj Z = s). When f is addition, the problem is NP-hard even when the Xi are independent. In more restricted cases|for example, i.i.d. Boolean or categorical Xi|ecient exact samplers have been obtained previously. For the general continuous case, we propose a dynamic scaling algorithm (DYSC), and prove that it hasO(k) expected running time and nite variance. We discuss generalizations of DYSC to functions f described by binary operation trees. We evaluate the algorithm on several examples.
