[Math] Average absolute value of sum with Rademacher random variables

binomial-coefficientsinequalityprobabilityprobability theoryrandom variables

Let $a_1, \ldots, a_n $ be independent Rademacher random variables with distribution $P(a_i=1) = P(a_i=-1) = \frac 12$. Estimate from below $$E \left|\sum_{i=1}^n a_i\right|.$$

I've reduced this problem to the next one (for even $n$):

Estimate from below following $$\frac 1{2^{n-1}} \left(\sum_{k=n/2}^n kC_n^k – \sum_{k=0}^{n/2}kC_n^k\right).$$

Best Answer

We don't need to estimate it ... we can find the exact solution.

If $Z$~Bernoulli($\frac12$), then $X=2Z-1$ has a Rademacher distribution where $X=-1$ or $1$ with equal probability. Let $X_1, ..., X_n$ denote indepedent Rademacher random variables. Then, the pmf of:

$$ \sum_{i=1}^n X_i = (2 \sum_{i=1}^n Z_i) - n = 2 Y -n$$

where $Y$~ $Binomial(n,\frac12)$ (since the sum of $n$ Bernoulli's is $Binomial(n,p)$).

Let random variable $Y$ have pmf $f(y)$:

enter image description here

Then, the expectation we seek, namely, $E[ \left| \sum_{i=1}^n X_i \right|]$ can be found as $E[ \left| 2 Y - n \right|]$, derived here using mathStatica (of which I am one of the authors):

enter image description here

All done.

Here is a plot of the solution as $n$ increases from 1 to 100:

enter image description here

Monte Carlo check

When using computer algebra systems (or indeed working manually), it is always good practise to check one's work using alternative methods. For example, when $n = 130$, the exact solution derived above yields:

sol /. n -> 130.

9.07981

Here is a quick Monte Carlo 'check' in Mathematica ... when $n = 130$, we generate 100000 samples, each containing the sum of 130 Rademacher random variables, sum them up, take the absolute value, and compute the sample mean:

Mean[Table[ 
              Abs[Total[Table[RandomChoice[{-1, 1}], {130}]]], 
           {100000}]] // N

9.07358

:)

Related Question