# Expectation of sum of $n$ random variables.

Let $X_1, X_2, X_3 \ldots, X_n$ be n random variables which take values from $\{+1,-1\}$ uniformly. Let $S_n$ be defined as $$S_n =|X_1+ X_2+ X_3+ \dots +X_n|$$ Find the expectation $E(S_n)$ of the random variable.

Now I can find the closed form solution to be equal to $n 2^{1-n}{{n-1}\choose{(n-1)/2}}$

But I can not see how the book says that $E(S_n) = ((2/\pi)^\frac{1}{2} + o(1))\sqrt{2}$.

$X_1 + \ldots + X_n = 2 Y - n$ where $Y$ is a binomial random variable with parameters $n$ and $1/2$, and $E[S_n] = 2 \sum_{j=1}^n j P(Y = (n+j)/2)$. I'll do the case where $n=2m$ is even, so we sum over even $j = 2i$. $$E[S_n] = 4 \sum_{i=1}^{m} i {2m \choose m+i} 2^{-n} = (m+1) {2m \choose m+1} 2^{1-2m}$$ Using Stirling's approximation, as $m \to \infty$ we have $$E[S_n] = 2 \sqrt{\dfrac{m}{\pi}}- \dfrac{1}{4 \sqrt{\pi m}}+ \ldots = \sqrt{\dfrac{2n}{\pi}} + o(1)$$ This must be what the book meant (or you copied it wrong).