2
$\begingroup$

In terms of importance sampling for numerical Monte Carlo integration we can proceed as follows:

\begin{align} \int_{\Omega} p(\mathbf{x}) d\mathbf{x} &= \int_{\Omega} p(\mathbf{x}) \frac{q(\mathbf{x})}{q(\mathbf{x})}d\mathbf{x} \\ & = E_{\mathbf{x} \sim q(\mathbf{x})}\left[\frac{p(\mathbf{x})}{q(\mathbf{x})}\right] \\ & \approx \frac{1}{N} \sum_{i=1}^N \left[\frac{p(\mathbf{x}_i)}{q(\mathbf{x}_i)}\right] \end{align}

Therefore we can empirically estimate the integral by sampling $\mathbf{x}$ from some distribution $q(\cdot)$.

Now in my problem I know for a fact that my $\mathbf{x}$ is a finite vector ($\mathbf{x}=[x_1,x_2,x_3,...x_n]$), all values are contained in the interval $[0,1]$ (so $\Omega = [0,1]^d$), and there is a particular ordering to my $\mathbf{x}$, i.e.:

$x_1 \geq x_2$

$x_2\geq x_3$

$x_2 \geq x_3$ etc....


So given the structure of my problem (nested, all values in $[0,1]$), my questions are:

Question 1: Given this nested structure to my problem, is it better to choose certain $q(\cdot)$ functions over others?

I feel that because all my variables are in the interval $[0,1]$, and I have no reason to believe any particular weighting of the points (I am actually evaluating an integral to help find a volume), so should I choose a uniform distribution?

Question 2: If I opt for a uniform distribution for $q(\cdot)$, do I need to reflect the prior structure of my variables in the sampling procedure?

i.e. I cannot just sample $\mathbf{x} \sim U[0,1]^n$, as this will occasionally violate my required hierarchical/ordering/nested structure.

Question 3: In many importance sampling integration problems, they give the example of uniform 1D, in which case $q(\cdot) = \frac{1}{b-a}$, so this term can be removed from the expectation/sum to the front. How can I calculate this same volume, assuming I opt for $q(\cdot)$ to have a nested hierarchical structure? How should this scale and be dealt with


Thus ultimately I am unable to understand how to properly include such a prior knowledge of the nested nature of my variables into MC integration.

$\endgroup$
2
$\begingroup$

Question 1: Given this nested structure to my problem, is it better to choose certain $q(⋅)$ functions over others?

A generic recommendation is to have the importance function $q(⋅)$ supported by the same support as the integrand $p(⋅)$. Therefore, if $\mathbf x$ belongs to the restricted unit hypercube, the function $q(⋅)$ should only be positive over this restricted unit hypercube.

Question 2: If I opt for a uniform distribution for $q(⋅)$, do I need to reflect the prior structure of my variables in the sampling procedure?

The constraint on the components of $\mathbf x\in(0,1)^n$ can be expressed by a change of variables: \begin{align*} x_1 &= y_1 &y_1\ge 0\\ x_2 &= x_1 + y_2 &y_2\ge 0\\ &\vdots \\ x_n &=x_{n-1}+y_n &y_n\ge0\\ &\qquad\qquad y_1+\ldots+y_n\le 1 \end{align*} which indicates that $\mathbf y=(y_1,\ldots,y_n)$ belongs to the simplex of $\mathbb R^n$ (or $\mathbb R^{n+1}$ depending on the convention). A natural family of distributions on the simplex of $\mathbb R^{n}$ is made of the Dirichlet $\mathcal D(\alpha_1,\ldots,\alpha_{n+1})$ distributions with density $$f(\mathbf y)=\dfrac{\Gamma(\alpha_1)\cdots\Gamma(\alpha_{n+1})}{\Gamma(\alpha_1+\cdots+\alpha_{n+1})}y_1^{\alpha_1-1}\cdots y_{n+1}^{\alpha_{n+1}-1}$$ over this simplex of $\mathbb R^{n}$. The Uniform case corresponds to $$\alpha_1=\cdots=\alpha_{n+1}=1$$

Question 3: In many importance sampling integration problems, they give the example of Uniform 1D, in which case $q(⋅)=1/(b−a)$, so this term can be removed from the expectation/sum to the front. How can I calculate this same volume, assuming I opt for $q(⋅)$ to have a nested hierarchical structure?

The volume of the simplex of $\mathbb R^{n}$ is given by the constant $$\dfrac{\Gamma(\alpha_1+\cdots+\alpha_{n+1})}{\Gamma(\alpha_1)\cdots\Gamma(\alpha_{n+1})}$$

$\endgroup$
  • $\begingroup$ Thank you! :) Just one follow up. Suppose I perform the proposed change of variables to the integral, I will require the determinant of the Jacobian. For a simple system ($x_1 = y_1, \quad x_2 = x_1 + y_2 = \sum_i^2 y_i, \quad x_3 = x_2 + y_3 = \sum_i^3 y_i$), the jacbian matrix should be (I believe): \begin{matrix} \left[1 $0 $0 \\ y_2 $ y_1 $ 0\\ y_2 + y_3 & y_1 + y_3 & y_1 + y_2 \right] \end{matrix} $\endgroup$ – tisPrimeTime Jan 28 at 11:23
  • $\begingroup$ The Jacobian is lower triangular with only 1's hence equal to 1. $\endgroup$ – Xi'an Jan 28 at 11:45
  • $\begingroup$ Sorry, I didn't finish my equation before properly (the time to edit ran out!). I thought the Jacobian should look something like this: \begin{bmatrix} 1 &0 &0 \\ y_2 & y_1 & 0\\ y_2 + y_3 & y_1 + y_3 & y_1 + y_2 \end{bmatrix} I get the lower triangular part, but for each row we would have something like $\partial x_n / \partial y_m$ so wouldn't there need to be some sort of residual sum of the other terms left over (i.e. I don't get how it becomes only 1s (but if it is that is super nice!) $\endgroup$ – tisPrimeTime Jan 28 at 11:55
  • $\begingroup$ never mind, I was being a bit silly, for some reason I thought $\frac{\partial }{\partial y_1}(y_1 + y_2 + y_3) = y_2 + y_3$ or something ridiculous.... when the answer should be 1, thereby creating the lower triangular matrix of completely 1s. $\endgroup$ – tisPrimeTime Jan 31 at 2:06

Your Answer

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

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