← All problems

Weighted Bernoulli sums above their mean

14 years old · traced to

Conjecture 1. Let 0≤p≤1/30\leq p\leq 1/3 be a fixed real number. Let w∈R>0mw\in\mathbb{R}_{>0}^{m} satisfy ∑i=1mwi=1\sum_{i=1}^{m}w_i=1, and let v∈{0,1}mv\in\{0,1\}^{m} be a random vector whose coordinates are independent and each has distribution Bernoulli⁡(p)\operatorname{Bernoulli}(p). Prove that

P[⟨v,w⟩≥p]≥p.\mathbb{P}\left[\langle v,w\rangle\geq p\right]\geq p.

Equivalently, prove P[∑i=1mwivi≥p]≥p\mathbb{P}[\sum_{i=1}^{m}w_i v_i\geq p]\geq p. The cited paper additionally proves that this inequality is false for every p∈(1/3,1)p\in(1/3,1) except p=1/2p=1/2 by explicit choices of weights.

References

Progress summary

Refreshed
Open · progress reported

The exact range has not been determined: the inequality is known to work for extremely small probabilities and to fail above one-third except at one-half.

A recent note formulates the assertion as a conjecture for 0≤p≤1/30\leq p\leq 1/3. The threshold is sharp in the upper direction: outside that range, explicit small equal-weight constructions give counterexamples, apart from p=1/2p=1/2.

Known results

  • Alon, Emek, Feldman, and Tennenholtz proved Pr⁡[X≥EX]≥p(1−p)/10\Pr[X\geq\mathbb{E}X]\geq p(1-p)/10 in general.
  • Their coupling argument proves the target inequality when p=1/np=1/n for a positive integer nn.

June 2026 arXiv note

The note reduces the conjecture to a version of the Manickam–Miklós–Singi conjecture; if that conjecture holds, the result follows for p≤1/4p\leq 1/4. Using work of Pokrovskiy, it proves the inequality for 0≤p≤10−460\leq p\leq 10^{-46}. It also proves failure for every p∈(1/3,1)p\in(1/3,1) except p=1/2p=1/2, via weights (1/3,1/3,1/3)(1/3,1/3,1/3) or (1/2,1/2)(1/2,1/2).

Current status (as of June 2026): Failure is settled for p∈(1/3,1)p\in(1/3,1) except p=1/2p=1/2, while the full assertion for 0≤p≤1/30\leq p\leq 1/3 remains open beyond the recorded partial ranges.

Sources

Solutions 0

No solutions have been posted yet.