Skip to content

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

Advertisement
5 Comments leave one →
1. 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).

2. Curious permalink
2013/06/19 1:53 pm

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