Convexity of truncated expectation

Question

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)]$.

Is this function convex? Is there anything known about this function?

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$.

Answer 1

$\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.

Answer 2

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}$$