# Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup:

Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such that $\mathbb{E}[f_k(X)]$ is finite. There exist a discrete real-valued random variable $Z$ with at most $m+1$ atoms, such that:

(1) $\mathbb{E}[f_k(X)] = \mathbb{E}[f_k(Z)]$ for $k = 1, \ldots m$.

This is a simple consequence of Caratheodory's theorem in convex analysis, because the point $P = (\mathbb{E}[f_1(X)], \ldots, \mathbb{E}[f_m(X)])$ belongs to the convex hull of the set $E = \{(f_1(x), \ldots, f_m(x)): x \in \mathbb{R} \} \subset \mathbb{R}^m$. Therefore $P$ can be written as a convex combination of at most $m+1$ points in $E$.

The above is an existence result. Here are my questions:

1) Given the density of $X$ and $f_1, \ldots, f_m$, is there an efficient algorithm to compute the location and weights of $Z$? I know how to do this when polynomials are concerned, i.e., $f_k(x) = x^k$. As elucidated by fedja in reply to a question I asked before, this problem is solved by the Gaussian quadrature, and the locations are given by roots of orthogonal polynomials. The problem I am facing is for standard normal $X$ and $f_k(x) = \exp(-x^2) x^k$. I do not have a clue how to solve this highly nonlinear problem.

2) Let us take a closer look at the special case when $f$'s are monomials. In this case what Gaussian quadrature achieves is twice better than Caratheodory's theorem, namely, $(m+1)/2$ atoms are enough to satisfy (1). This number is optimal intuitively, because we have $m+1$ equations to solve: $m$ equations in (1) and weights sum up to one. Hence we need at least $m+1$ "degrees of freedoms", half being locations and half being weights. (My friend told me this can be made precise by algebraic geometry, though I do not understand). I wonder what is so special about polynomials in this problem. I do not suppose Caratheodory's theorem can be improved by a factor of two. For non-polynomial functions, like those in my first question, is $m+1$ really necessary?

-
Right after Eq. (1), I don't understand what $E[f_1(x)]$ with $x \in R$ means. What is the expectation taken with respect to? –  alex May 17 '10 at 19:52
i am sorry for the typo. fixed now. –  mr.gondolier May 17 '10 at 23:15