Skip to main content
7 of 8
better approximation
user avatar
user avatar

We can in principle find the optimal first $n$ moments for a polynomial approximation of $f$. This reduces the problem to a truncated Hausdorff moment problem, for which solutions exist.

Let $f \colon [0,1]^d \to \mathbb{R}$ be a continuous function. Approximate $|f|$ with the multivariate Bernstein polynomials of order $n$ (writing $f_{k_1\cdots k_d} = f(k_1/n, \ldots k_d/n)$ for short),

$$|f_n|(x) = \sum_{k_1 \cdots k_d} |f_{k_1\cdots k_d}| \prod_{i=1}^{d} \binom{n}{k_i} \, x_i^{k_i} (1-x_i)^{n-k_i} \;.$$

Let $S_k = E[X^k (1-X)^{n-k}]$. The expectation of the approximant is then

$$E[|f_n|(X)] = \sum_{k_1 \cdots k_d} |f_{k_1\cdots k_d}| \prod_{i=1}^{d} \binom{n}{k_i} \, S_{k_i} \;,$$

which should be maximal. The value of $S_{k}$ is a linear combination on the first $n$ moments $M$ of the resulting distribution. Expanding

$$S_k = \sum_{r=0}^{n} \binom{n-k}{r-k} (-1)^{r-k} \, M_r \;,$$

the expectation in terms of the moments is

$$E[|f_n|(X)] = \sum_{k_1 \cdots k_d} \sum_{r_1 \cdots r_d} |f_{k_1\cdots k_d}| \prod_{i=1}^{d} \binom{n}{r_i} \binom{r_i}{k_i} (-1)^{r_i-k_i} \, M_{r_i} \;.$$

The problem is hence the constrained multilinear optimisation

$$ \begin{aligned} \max_{M_1 \cdots M_n} \;&\; \sum_{k_1 \cdots k_d} \sum_{r_1 \cdots r_d} |f_{k_1\cdots k_d}| \prod_{i=1}^{d} \binom{n}{r_i} \binom{r_i}{k_i} (-1)^{r_i-k_i} \, M_{r_i} \;, \\ \text{s.t.} \;&\; \sum_{r=0}^{n} \binom{n-k}{r-k} (-1)^{r-k} \, M_r \ge 0 \;, \\ &\; M_r \in [0,1] \;, \quad M_0 = 1 \;. \end{aligned} $$

To make the problem slightly more tractable, the relation between $S_k$ and $M_r$ can be inverted using the binomial partial sums,

$$M_r = \sum_{k=0}^{n} \binom{n-r}{k-r} \, S_k \;,$$

so that the optimisation becomes

$$ \begin{aligned} \max_{S_1 \cdots S_n} \;&\; \sum_{k_1 \cdots k_d} |f_{k_1\cdots k_d}| \prod_{i=1}^{d} \binom{n}{k_i} \, S_{k_i} \;, \\ \text{s.t.} \;&\; \sum_{k=0}^{n} \binom{n-r}{k-r} \, S_k \in [0,1] \;, \\ &\; \sum_{k=0}^{n} \binom{n}{k} \, S_k = 1 \;, \quad S_k \ge 0 \;. \end{aligned} $$

Once the moments are found, it is necessary to construct an approximate distribution $g_n$ with first moments $M_r$, $r = 1, \ldots, n$, matching the optimal moments. This is the truncated Hausdorff moment problem, for which methods exist: this paper for example discusses an approximation by Beta distributions.

From a cursory Google search, multilinear optimisation appears difficult (but I have no idea, really). Nevertheless, it is a recipe for calculations: For the baby problem, I find (with $n = 20$) the expectation 0.0615258 and moments 1., 0.500007, 0.403758, 0.355633, 0.329122, 0.313417, 0.303534, 0.296983, 0.292437, ..., using a quick Mathematica test run, and the numbers are relatively robust against changes in $n$ and match the distributions suggestions from the comments.

user114668