# Construction of non-negative random variables with fixed expectation to maximize probability

I want to construct independent non-negative random variables $X_1,X_2,X_3$ and $X_4$ such that $\mathbb{E}(X_n)=n$ and then maximize the probability: $$\mathbb{P}\left(X_1+X_2+X_3+X_4 \geq 11\right)$$

By Markov's inequality this must be smaller or equal to 10/11 but I would not know how to actually maximize this.

• Hmm, the principle of maximum entropy (or possibly minimum Fisher information) comes to mind, since you want to find pdf's under some conditions of expectation, which are incorporated using Lagrange-multipliers, but I don't have enough experience with this method to utilize here. – Bobson Dugnutt Jan 27 '17 at 10:41
• Are your $X_n$ discrete or continuous ? – Jean Marie Jan 27 '17 at 11:30
• If we take $X_n$ as being exponential with mean $n$, extensive simulations give $\mathbb{P}\left(X_1+X_2+X_3+X_4 \geq 11\right) \approx 0.352$. What kind of distribution(s) can do better ? – Jean Marie Jan 27 '17 at 13:58
• It's somehow relevant to "Feige's Conjecture" – MR_BD Jan 28 '17 at 11:27
• @Axolotl Yes! assuming Feige's conjecture the best you can do for this problem is $1-1/e \approx .632$ (so I don't know how you're getting .82) – spaceisdarkgreen Jan 28 '17 at 18:28

Let $X_1\ldots X_n$ be independent non-negative random variables with means $\mu_1\le\mu_2\le\ldots \le \mu_n.$ Then for every $\lambda>\sum_k\mu_k$ there is some $i$ with $1\le i\le n$ such that $P(\sum_kX_k\ge \lambda)$ is maximized when the $X_j$ are distributed as follows: 1) For $j<i,$ $X_j=\mu_j$ with probability $1$. 2) For $j\ge i$, $X_j$ takes the value $\lambda - \sum_{k=1}^{i-1} \mu_k$ with probability $\frac{\mu_j}{\lambda - \sum_{k=1}^{i-1} \mu_k}$ and $0$ otherwise.
Fortunately, he also claims that Samuels has proven this for $n\le 4$ in these two papers. So it appears this you can get the answer for finding the best value of $i$ above, though the proof might take a bit to work through.
• Thank you for your answer, this means that for my problem we will have a maximum probability of $\frac{4}{5}$. – Jan Jan 28 '17 at 21:12
• @Jan Thanks to both of you, $\frac{4}{5}$ is exactly what i achieved via simulations... – MR_BD Jan 29 '17 at 6:32
• @spaceisdarkgreen Can you find an example in which $i<n$ i.e. more than one RVs could not be constant? – MR_BD Jan 30 '17 at 8:40
• @Axolotl Yes, just take $\lambda$ very large, then it starts to make more sense to give each variable a shot. For instance if we look at $P(X_1+X_2+X_3+X_4\ge 30),$ then if we let the first three be constant and $X_4 =24$ w.p. 4/24, and $0$ otherwise we get$1/6.$ However If we let each $X_1,X_2,X_3,X_4 = 30$ with probabilities $1/30,2/30,3/30,4/30$ and zero otherwise the probability the sum is $\ge 30$ is $1-(29/30)(28/30)(27/30)(26/30)\approx 0.3$ – spaceisdarkgreen Jan 30 '17 at 9:29