$\begingroup$

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).$$

$\endgroup$

1 Answer

$\begingroup$

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)$:

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):

All done.

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

---

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

:)

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy