3
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ 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. $\endgroup$ – Bobson Dugnutt Jan 27 '17 at 10:41
  • $\begingroup$ Are your $X_n$ discrete or continuous ? $\endgroup$ – Jean Marie Jan 27 '17 at 11:30
  • $\begingroup$ 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 ? $\endgroup$ – Jean Marie Jan 27 '17 at 13:58
  • 1
    $\begingroup$ It's somehow relevant to "Feige's Conjecture" $\endgroup$ – MR_BD Jan 28 '17 at 11:27
  • 1
    $\begingroup$ @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) $\endgroup$ – spaceisdarkgreen Jan 28 '17 at 18:28
2
$\begingroup$

Thanks to Axolotl's comment, we see this is related to Feige's Conjecture. In Feige's Paper he references a much older conjecture (Conjecture 2) due to Samuels that would answer your problem. It says

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.

$\endgroup$
8
  • $\begingroup$ Thank you for your answer, this means that for my problem we will have a maximum probability of $\frac{4}{5}$. $\endgroup$ – Jan Jan 28 '17 at 21:12
  • $\begingroup$ @Jan, yep! That's what I get too. $\endgroup$ – spaceisdarkgreen Jan 28 '17 at 22:06
  • $\begingroup$ @Jan Thanks to both of you, $\frac{4}{5}$ is exactly what i achieved via simulations... $\endgroup$ – MR_BD Jan 29 '17 at 6:32
  • $\begingroup$ @spaceisdarkgreen Can you find an example in which $i<n$ i.e. more than one RVs could not be constant? $\endgroup$ – MR_BD Jan 30 '17 at 8:40
  • $\begingroup$ @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$ $\endgroup$ – spaceisdarkgreen Jan 30 '17 at 9:29

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.