# Integrating multidimensional PDFs on Boolean cube separated by hyperplane

Problem Statement: Let $$f:[0,1]^d \rightarrow [0,1]$$ be a $$d$$-dimensional probability density function. Further, for $$c\in [0, 1]$$ and $$\mathbf{w}\in \mathbb{R}^d$$, let $$H = \{\mathbf{x} \in [0,1]^d : \mathbf{w}\bullet\mathbf{x} = c\}$$ be a hyperplane. This separating hyperplane partitions partitions the unit hypercube $$[0, 1]^d$$, into two regions,

$$U = \{\mathbf{x} \in [0,1]^d :\mathbf{w} \bullet \mathbf{x} > c\} \quad \text{ and }\quad L = \{ \mathbf{x} \in [0, 1]^d: \mathbf{w} \bullet \mathbf{x} \leq c\}$$

Under what conditions on $$f$$ can one efficiently compute (approximately or exactly) the cumulative probability of $$f$$ over $$L$$ (or equivalently over $$U$$), i.e. $$\int_{L} f(\mathbf{x})d\mathbf{x}$$?

Preliminary Ideas: If $$f$$ is something like the uniform distribution then the integral can be computed exactly. For sake of example, suppose that $$\mathbf{0}\in L$$ and $$H$$ represents the upper limits of integration. Then we are integrating

$$\int_{0}^c\int_{0}^{\frac{c – w_dx_d}{w_{d-1}}}\dots\int_{0}^{\frac{c – w_2x_2 – \dots w_dx_d}{w_1}} 1 dx_1 \dots dx_{d-1} dx_d$$

Which each integral has a closed form solution derivable in polynomial time, and there are only $$d$$ number of integrals. Assuming this is correct, then if $$f$$ is any polynomial it can also be solved exactly.

Question Are there any characteristics, or common families of PDFs in which this problem is polynomial time solvable? In practice, PDFs such as a Gaussian are computed numerically, is there any literature on how well of a numerical approximation can be achieved in this setting, for $$d$$-dimensional PDFs which are computed numerically?

Posted on Categories proxies