Rademacher distribution

In probability theory and statistics, the Rademacher distribution (which is named after Hans Rademacher) is a discrete probability distribution where a random variate X has a 50% chance of being +1 and a 50% chance of being -1.^[1]

A series (that is, a sum) of Rademacher distributed variables can be regarded as a simple symmetrical random walk where the step size is 1.

Mathematical formulation

The probability mass function of this distribution is

f(k) = \left\{\begin{matrix} 1/2 & \mbox {if }k=-1, \\ 1/2 & \mbox {if }k=+1, \\ 0 & \mbox {otherwise.}\end{matrix}\right.

f( k ) = \frac{ 1 }{ 2 } \left( \delta \left( k - 1 \right) + \delta \left( k + 1 \right) \right).

Van Zuijlen has proved the following result.^[2]

Let X_i be a set of independent Rademacher distributed random variables. Then

\Pr \left(\left|{\frac {\sum _{i=1}^{n}X_{i}}{\sqrt {n}}}\right|\leq 1\right)\geq 0.5.

The bound is sharp and better than that which can be derived from the normal distribution (approximately Pr > 0.31).

Let {x_i} be a set of random variables with a Rademacher distribution. Let {a_i} be a sequence of real numbers. Then

\Pr \left(\sum _{i}x_{i}a_{i}>t||a||_{2}\right)\leq e^{-{\frac {t^{2}}{2}}}

where ||a||₂ is the Euclidean norm of the sequence {a_i}, t > 0 is a real number and Pr(Z) is the probability of event Z.^[3]

Let Y = Σ x_ia_i and let Y be an almost surely convergent series in a Banach space. The for t > 0 and s ≥ 1 we have^[4]

\Pr \left(||Y||>st\right)\leq \left[{\frac {1}{c}}\Pr(||Y||>t)\right]^{cs^{2}}

for some constant c.

Let p be a positive real number. Then the Khintchine inequality says that^[5]

c_{1}\left[\sum {\left|a_{i}\right|^{2}}\right]^{\frac {1}{2}}\leq \left(E\left[\left|\sum {a_{i}x_{i}}\right|^{p}\right]\right)^{\frac {1}{p}}\leq c_{2}\left[\sum {\left|a_{i}\right|^{2}}\right]^{\frac {1}{2}}

where c₁ and c₂ are constants dependent only on p.

For p ≥ 1,

$c_{2}\leq c_{1}{\sqrt {p}}.$

See also: Concentration inequality - a summary of tail-bounds on random variables.

The Rademacher distribution has been used in bootstrapping.

Random vectors with components sampled independently from the Rademacher distribution are useful for various stochastic approximations, for example:

The Hutchinson trace estimator,^[6] which can be used to efficiently approximate the trace of a matrix of which the elements are not directly accessible, but rather implicitly defined via matrix-vector products.
SPSA, a computationally cheap, derivative-free, stochastic gradient approximation, useful for numerical optimization.

Rademacher random variables are used in the Symmetrization Inequality.

Bernoulli distribution: If X has a Rademacher distribution, then $\frac{X+1}{2}$ has a Bernoulli(1/2) distribution.
Laplace distribution: If X has a Rademacher distribution and Y ~ Exp(λ), then XY ~ Laplace(0, 1/λ).

^ Hitczenko, P.; Kwapień, S. (1994). "On the Rademacher series". Probability in Banach Spaces. Progress in probability. 35. pp. 31–36. doi:10.1007/978-1-4612-0253-0_2. ISBN 978-1-4612-6682-2.
^ van Zuijlen, Martien C. A. (2011). "On a conjecture concerning the sum of independent Rademacher random variables". arXiv:1112.4988. Bibcode:2011arXiv1112.4988V.
^ Montgomery-Smith, S. J. (1990). "The distribution of Rademacher sums". Proc Amer Math Soc. 109 (2): 517–522. doi:10.1090/S0002-9939-1990-1013975-0.
^ Dilworth, S. J.; Montgomery-Smith, S. J. (1993). "The distribution of vector-valued Radmacher series". Ann Probab. 21 (4): 2046–2052. arXiv:math/9206201. doi:10.1214/aop/1176989010. JSTOR 2244710. S2CID 15159626.
^ Khintchine, A. (1923). "Über dyadische Brüche". Math. Z. 18 (1): 109–116. doi:10.1007/BF01192399. S2CID 119840766.
^ Avron, H.; Toledo, S. (2011). "Randomized algorithms for estimating the trace of an implicit symmetric positive semidefinite matrix". Journal of the ACM. 58 (2): 8. CiteSeerX 10.1.1.380.9436. doi:10.1145/1944345.1944349. S2CID 5827717.

Support	$k \in \{-1,1\}\,$
PMF	$f(k)=\left\{{\begin{matrix}1/2&{\mbox{if }}k=-1,\\1/2&{\mbox{if }}k=+1,\\0&{\mbox{otherwise.}}\end{matrix}}\right.$
CDF	$F(k) = \begin{cases} 0, & k < -1 \\ 1/2, & -1 \leq k < 1 \\ 1, & k \geq 1 \end{cases}$
Mean	$0\,$
Median	$0\,$
Mode	N/A
Variance	$1\,$
Skewness	$0\,$
Ex. kurtosis	$-2\,$
Entropy	$\ln(2)\,$
MGF	$\cosh(t)\,$
CF	$\cos(t)\,$