# Nested Uniform Distributions in Monte Carlo Integration

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.

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})}$$

• 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} – tisPrimeTime Jan 28 at 11:23
• The Jacobian is lower triangular with only 1's hence equal to 1. – Xi'an Jan 28 at 11:45
• 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!) – tisPrimeTime Jan 28 at 11:55
• 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. – tisPrimeTime Jan 31 at 2:06