Exercise 1.7 (The moment problem)

Question

Suppose that $Z$ is a random variable taking values in the set $0,1, \ldots, K$, with probabilities $p_{0}, p_{1}, \ldots, p_{K}$, respectively. We are given the values of the first two moments $E[Z]=\sum_{k=0}^{K} k p_{k}$ and $E\left[Z^{2}\right]=$ $\sum_{k=0}^{K} k^{2} p_{k}$ of $Z$ and we would like to obtain upper and lower bounds on the value of the fourth moment $E\left[Z^{4}\right]=\sum_{k=0}^{K} k^{4} p_{k}$ of $Z$. Show how linear programming can be used to approach this problem.

Elu Thingol · Accepted Answer

The variables of our linear optimization problem are the probabilities $p_0,p_1,\ldots,p_K$. Probability axioms require $p_i$ to be non-negative and to sum up to unity. Additionally, our knowledge about the first and the second moments results in two additional restrictions. We thus obtain two linear programs: one to minimize $\sum_{k=0}^{K} k^4p_k$ (the lower bound), and one to maximize it (the upper bound).

\begin{equation}
\begin{array}{ll}
	ext{minimize} \quad & \sum_{k=0}^{K} k^{4} p_{k}\
	ext{subject to} \quad & \sum_{k=0}^{K} k p_{k} = E[Z]\
& \sum_{k=0}^{K} k^2 p_{k} = E[Z^2]\
& p_{k} \geq 0, \ k=0,\ldots,K\
& \sum_{k=0}^{K} p_{k} = 1
\end{array}
\end{equation}

This can be translated into a standard form problem as follows:

\begin{equation}
\begin{array}{ll}
	ext{minimize} \quad & \sum_{k=0}^{K} k^{4} p_{k}\
	ext{subject to} \quad &
\begin{bmatrix}
0   & 1   & \ldots & K\
0^2 & 1^2 & \ldots & K^2\
1   & 1   & \ldots & 1
\end{bmatrix}
\begin{bmatrix} p_0 \ p_1 \ \vdots \ p_K \end{bmatrix}
= 
\begin{bmatrix} E[Z] \ E[Z^2] \ 1\end{bmatrix},\
&\begin{bmatrix} p_0 \ p_1 \ \vdots \ p_K \end{bmatrix} \geq \mathbf{0}
\end{array}
\end{equation}

The problem of maximizing the fourth moment is analogous.

Exercise 1.7 (The moment problem)

Answers

Comments

Exercise 1.7 (The moment problem)

Answers

Comments

Add answer