Expecation of sum of random +-1 vars

Question

Let $X_i$ and $Y_i$ be i.i.d. random variables taking on $1$ and $-1$ with probability $\frac12$. Let $C_n = \frac 1n\sum_{i=1}^n X_i Y_i$. What is the expected value of $|C_n|$?

EDIT:

It looks to me like $E|C_n| = \frac{2n\binom{2n}{n}}{2^{2n}}$, at least when $n$ is even... I am trying to prove it. If this is incorrect please let me know.

Answer 1

What is the expected value of $|C_n|$? ... How do we tighten this bound?

The best solution to the second question is the answer to the first question: i.e. find the exact solution.

Let $Z = X Y$, where $X$ and $Y$ are indepedent Rademacher random variables i.e. $X$ and $Y$ each independently take -1 or 1 with equal probability. Then $Z$ is also a Rademacher random variable.

Let $U \sim \text{Bernoulli}(\frac12)$ i.e. $U = 0$ or $U=1$ with equal probability. Then $Z = 2 U - 1$. Then:

$$ \sum_{i=1}^n Z_i \quad = \quad (2 \sum_{i=1}^n U_i) - n \quad = \quad 2 S -n$$

where $S \sim \text{Binomial}(n,\frac12)$, since the sum of $n$ Bernoulli's is $\text{Binomial}(n,p)$.

Our Binomial random variable $S$ has pmf $f(s)$:

We seek:

$$ E\big[ \, \frac1n \left| \sum_{i=1}^n Z_i \right| \, \big] \quad = \quad E_f \big[ \, {\frac{1}{n} \large \left | 2 S - n \right| } \, \big]$$

which is derived here using mathStatica:

All done.

Here is a plot of the EXACT solution just derived (Blue dots) as $n$ increases from 1 to 30:

In the above plot:

• the BLUE dots denote the EXACT solution
• the ORANGE dots plot the $\frac{1}{\sqrt{n}}$ bound suggested by Simeon [see comments above].

Notes

1. As disclosure, I should add that I am one of the authors of the mathStatica software used.

2. Floor[x] is a Mathematica function that gives the greatest integer less than or equal to x.