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

  • $\begingroup$ I'm really sorry I didn't accept the answer to previous question. I didn't review it till now. I am just reading the book (you'll have noticed by now) Probabilistic Methods by N. Alon and asking questions wherever I get stuck. $\endgroup$ – Alvis Sep 1 '14 at 21:25
  • $\begingroup$ But S_n is the abs(X_1 + X_2 ... X_n ). And I am not sure how you replaces the (X_1 + X_2 ... X_n ) with 2*Y -n $\endgroup$ – Alvis Sep 1 '14 at 22:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.