# Sharp Concentration Inequalities for Deviations from the Mean for Sums of Independent Rademacher Random Variables

Annals of Combinatorics

, Volume 21, Issue 2, pp 281–291

First Online: 11 May 2017Received: 08 January 2015DOI: 10.1007-s00026-017-0351-3

Cite this article as: Hendriks, H. & van Zuijlen, M.C.A. Ann. Comb. 2017 21: 281. doi:10.1007-s00026-017-0351-3

Abstract

For a fixed unit vector \{a = a 1, a 2,

., a n \in S^{n-1}}\, that is, \{\sum^n {i=1} a^2 1 = 1}\, we consider the 2 signed vectors \{\varepsilon = \varepsilon 1, \varepsilon 2,

., \varepsilon n \in \{-1, 1\}^n}\ and the corresponding scalar products \{a \cdot \varepsilon = \sum^n {i=1} a i \varepsilon i}\. In 3 the following old conjecture has been reformulated. It states that among the 2 sums of the form \{\sum \pm a i}\ there are not more with \{|\sum^n {i=1} \pm a i| > 1}\ than there are with \{|\sum^n {i=1} \pm a i| \leq 1}\. The result is of interest in itself, but has also an appealing reformulation in probability theory and in geometry. In this paper we will solve an extension of this problem in the uniform case where \{a 1 = a 2 = \cdot\cdot\cdot = a n = n^{-1-2}}\. More precisely, for Sn being a sum of n independent Rademacher random variables, we will give, for several values of \{\xi}\, precise lower bounds for the probabilities$$P n: = \mathbb{P} \{-\xi \sqrt{n} \leq S n \leq \xi \sqrt{n}\}$$or equivalently for$$Q n: = \mathbb{P} \{-\xi \leq T n \leq \xi \},$$ where \{T n}\ is a standardized binomial random variable with parameters n and \{p = 1-2}\. These lower bounds are sharp and much better than for instance the bound that can be obtained from application of the Chebyshev inequality. In case \{\xi = 1}\ Van Zuijlen solved this problem in 5. We remark that our bound will have nice applications in probability theory and especially in random walk theory cf. 1, 2.Mathematics Subject Classification60E15 60G50 62E15 62N02 Keywordssums of independent Rademacher random variables tail probabilities lower bounds concentration inequalities random walk finite samples Download to read the full article text

Author: Harrie Hendriks - Martien C. A. van Zuijlen