4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ – martin cripps May 26 '16 at 12:22
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.