A Little Quant Interview Question

Question was originally inspired by Guillermo Angeris post on $\mathbb{X}$. He gave it a much deeper consideration than I did here.

A decade ago, this is the type of problem that my classmates would pretend they could reliably do 1) on the spot, 2) in their head. Some of them work at Jane Street now, so maybe not all of them were lying. Certainly does bear some resemblance to a question you might see in Heard on The Street.

Very straightforward question. $X_i \sim \{\pm 1\} \;; X=\sum_{i=1}^n X_i$. Assuming $+1$ and $-1$ appear with equal probability, what is $E[|X|]$?

It is clear $E[X]=0$, but how can we go about finding the expected absolute value of $X$? To get a very rough approximation, let’s first use Jensen’s inequality on $X^2$.

$$\begin{equation} E[|X|] = E[\sqrt{X^2}] \leq \sqrt{E[X^2]} = \sqrt{n} \end{equation}$$

The second equality in the statement above comes from the observation that $X_i \in \{\pm 1\}$ implies $\sum^{n}X_i^2 = n$. This alone is actually pretty good, but we can do even better with just an iota more effort. We can approximate the sum of independent Rademacher RVs to $N\Big(0, \sqrt{n})$. With this fact, we can then just compute twice the expectation on $\Big(0, \infty)$.

$$\begin{equation} \frac{2}{\sqrt{2n\pi}}\int_{0}^{\infty\ }x\ e^{-\frac{1}{2}\left(\frac{x}{\sqrt{n}}\right)^{2}}dx \approx \sqrt{\frac{2}{\pi}}\sqrt{n} \end{equation}$$