Integration of product of functions on a probability simplex

2010/09/09

I saw this trick in Wolpert and Wolf 1995, and I thought I would share it.

Given a product of functions $\prod_{i=1}^K h_i(p_i)$ over a probability mass function $\left\{ p_i \right\}$ where K is the cardinality of alphabets, and real valued function $h_i(\cdot)$ , we want to compute the integral of this over the probability simplex ( $p_i$ are non-negative and sum up to 1). The trick is to realize that the integral can be written in convolutions, and use the convolution theorem for Laplace transform.

$\int_0^1 \int_0^{1 - p_1} \cdots \int_0^{1-\sum_{i=1}^{K-1} p_i} \prod h(p_i) dp_1 dp_2 \cdots dp_{K-1}$

Note that $p_K$ is not integrated, since it is determined by the rest of the variables. Define $\tau_j = 1 - \sum_{i=1}^{j}$ . Note that $p_j = \tau_{j-1} - p_{j-1}$ . Rewrite the integral as,

$\int_0^1 \int_0^{\tau_1} \cdots \int_0^{\tau_{K-2}} \prod_{i=1}^{K-2} h_i(p_i) \int_0^{\tau_{K-1}} h_{K-1}(p_{K-1}) h_{K}(\tau_{K-1} - q_{K-1}) dp_{K-1} dp_1 dp_2 \cdots dp_{K-2}$

Recognizing the convolution, it can be simplified as,

$\int_0^1 \int_0^{\tau_1} \cdots \int_0^{\tau_{K-2}} \prod_{i=1}^{K-2} h_i(p_i) (h_{K-1} \otimes h_{K})(\tau_{K-1}) dp_1 dp_2 \cdots dp_{K-2}$

Using $\tau_{j} = \tau_{j-1} - p_{j-1}$ ,

$\int_0^1 \int_0^{\tau_1} \cdots \int_0^{\tau_{K-3}} \prod_{i=1}^{K-3} h_i(p_i) \int_0^{\tau_{K-2}} h_{K-2}(p_{K-2})(h_{K-1} \otimes h_{K})(\tau_{K-2} - p_{K-2}) dp_{K-2} dp_1 dp_2 \cdots dp_{K-3}$

Again, the convolution form is there. By induction, we end up with,

$\left( \otimes_{i=1}^{K} h_i \right)(1)$

Now, just apply the Laplace transform, and you are good to go!
This trick is useful for Bayesian integrals on Dirichlet prior.

Reference

David Wolpert, David Wolf. Estimating functions of probability distributions from a finite set of samples. Physical Review E, Vol. 52, No. 6. (December 1995), pp. 6841-6854.

5 Comments leave one →

memming permalink*

2012/08/01 11:16 am

It turns out, in Kingman 1975 (Random discrete distributions), an alternative derivation which is more general and simple is given. See equation (16).

Reply
Curious permalink

2013/06/19 1:53 pm

Nice post! I am wondering if there exists an equivalent trick for sums of functions

Reply

	memming on 8th Black Board Day (BBD8…
	Jesse on 8th Black Board Day (BBD8…
	happyjack27ismyhandl… on A guide to discrete entropy…
	neil on NIPS 2015 Part 3
	Integral of product… on Integration of product of func…

the inconsistent

Integration of product of functions on a probability simplex

Like this:

Related

Trackbacks

Leave a Reply Cancel reply

Pages

Recent Comments

Twitter Updates