# Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$. Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable such that $\Pr[X_i = 1] = x_i$ and $\Pr[X_i = 0] = 1 - x_i$. All $X_i$'s are independent, and let $X = X_1 + \dots + X_n$. Let $f : P \to \mathbb{R}$ be defined such that $f(x) = \mathbb{E}[\min(X, k)]$.

We proved that $f(x)$ is minimized when $x = (\frac{k}{n}, \dots, \frac{k}{n})$ for any $k \leq n$, and numerically verified $f(x)$ is convex for small values of $n$ and $k$.

• There is a literature on these kind of issues started by Hoeffding (1963). On page 360 of Marshal and Olkin "Theory of Inequalities and Majorization" you can see some results that may be of help (due to Karlin and Novikoff). – martin cripps May 26 '16 at 12:22

$\min\{X,k\}$ is a convex function of $X$ and the $X_i$'s are independent. So, by Karlin and Novikov (1963), $f(x)=E(\min\{X,k\})$ is a Schur concave function of $x=(x_1,\dots,x_n)$. This means that if $x\prec x'$ then $f(x)>f(x')$, where $\prec$ is the majorization ordering. (Loosely speaking $x\prec x'$ if the vector $x'$ is more spread out, or unequal, than the vector $x$.)

What this result implies is that the function $f(x)=E(\min\{X,k\})$ is maximised when $x=(\frac{k}{n},\dots,\frac{k}{n})$ and minimised when $x=(0,\dots,0,1,\dots,1)$. (There are $k$ 1's in this vector.) The minimization is intuitive because this choice of $x$ ensures that $X=k$ with probability one. The maximisation is also intuitive a the symmetry maximises the probability of extreme values of $X$.

Given these properties it seems highly unlikely that $f(.)$ is convex as you ask.

Let $\epsilon\perp\xi\perp\xi'$ three independent Bernouilli r.v with $\mathbb{P}(\epsilon=1)=1-\mathbb{P}(\epsilon=0)=\lambda$, $\mathbb{P}(\xi=1)=1-\mathbb{P}(\xi=0)=x$ and $\mathbb{P}(\xi'=1)=1-\mathbb{P}(\xi'=0)=y$.

Then $Z = \epsilon\xi+(1-\epsilon)\xi'$ is a r.v such that : $\mathbb{P}(Z=1)=1-\mathbb{P}(Z=0)=\lambda x + (1-\lambda)y$.

So it is not easy to generalize to multiple independent Bernouilli r.v to get :

$$\begin{split}f(\lambda x + (1-\lambda)y) &= \mathbb{E}(\min(\epsilon X+(1-\epsilon)Y,k))\\ &= \mathbb{E}(\epsilon\min(X,k)+(1-\epsilon)\min(Y,k)) \\ &= \lambda f(x)+(1-\lambda)f(y) \end{split}$$

• I am not sure I understand your answer. How do you intend to use conditional Jensen? – user92057 May 25 '16 at 23:18