Proof of Tomaszewski's Conjecture on Randomly Signed Sums

2020/06/30 by Keller, Nathan, Klein, Ohad · 1 citation
#05A20 #05D40 #60C05 #60F05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2006.16834

Abstract

We prove the following conjecture, due to Tomaszewski (1986): Let X= ∑_i=1ⁿ a_i x_i, where ∑_i a_i²=1 and each x_i is a uniformly random sign. Then Pr[|X|≤ 1] ≥ 1/2. Our main novel tools are local concentration inequalities and an improved Berry-Esseen inequality for Rademacher sums.

Cited by

• Recurrence, transience and anti-concentration of Rademacher random walks

Related

• Probability Mass of Rademacher Sums Beyond One Standard Deviation
• Linear combinations of Rademacher random variables
• Sign changes of the partial sums of a random multiplicative function
• Reverse Littlewood--Offord problems with parity conditions
• Sharp upper bounds for the deviations from the mean of the sum of independent Rademacher random variables