Expectation of the absolute value in a sequence of Bernoulli trials On this tweet:

Can I get some help in understanding the proposed solution by N. Taleb:



*

*It is not clear how he describes success, i.e. $n-x$ to come up with $\binom{n}{n-x}.$ It almost seems as though $x$ should correspond to the number of tails, according to the formulation of the question, but I bet it's not...

*He applies LOTUS (?) in the equation
$$\mathbb E(|X|)=\sum_{x=0}^n\Big\lvert x-\frac{n}{2}\Big\rvert \phi_n(x)$$
but where does the term $\lvert x-\frac{n}{2}\rvert$ come from?


*Where do the gamma functions come from?

 A: The solution you cite is approximate, and we can avoid the gamma function (I also believe that solution has some errors).  We are tossing a fair coin independently $n$ times, coding the outcomes as $+1$ or $-1$, respectively.  Summing this up we get $X_n$. Let $R_n$ be the number of times we throw $+1$, then we find that $X_n=2 R_n-n$, and $R_n$ has a binomial distribution with $p=1/2$. The expectation of $|X_n|$ is then
$$ \DeclareMathOperator{\E}{\mathbb{E}}
   a_n=\E |X_n | = \E |2R_n-n| = 2^{-n}\sum_{k=0}^n |2k-n| \binom{n}{k}
$$ (the solution you cited seems to have missed a factor of 2 here. Thats why they get 1/2 in their binomial coefficient, so need to use gamma function). 
This looks complicated, because of the absolute value, so let us try to rewrite without the absolute value. But first note that we have $a_{2m}=a_{2m-1}$. This is because the walk can never reach 0 (the starting point) after an odd number of steps. Therefore we only need to study the case $n=2m$, an even number of steps.
Remember the symmetry of the binomial coefficient, that $\binom{n}{k}=\binom{n}{n-k}$, also the absolute value term is symmetric about the midpoint of the series of terms. Write now $n=2m$. Then the above sum can be written as 
$$
   2\cdot 2^{-n} \sum_{k=0}^{m} \left( 2(m-k)\right) \binom{2m}{k}
$$
which we can sum exactly to get (I got tired and used maple)
$$
   2\cdot 2^{-n} (m+1) \binom{2m}{m+1}
$$
Now we could rewrite this using gamma functions, but there is no need to. 
What is the limit of this absolute expected value when $n \to\infty$? By using Stirling approximation we can see it must be $\infty$, but some asymptotic expression would be more useful. First, let us simplify the above expression to something that is obviously asymptotically equivalent.
$$
(n+\frac12) \cdot 2^{-n} \cdot \binom{n}{n/2+1}
$$
and using Stirling's approximation we can find a first order asymptotic approximation as
$$
    \E |X_n| \sim \sqrt{\frac{2 n}{\pi}}
$$
so after $n$ steps the expected distance from the origin is of the order of $\sqrt{n}$. To some further terms we can find the asymptotic approximation
$$
\E |X_n| \sim \sqrt{\frac{2}{\pi}}\left\{ \sqrt{n} - \frac74 \frac1{\sqrt{n}} +\frac{109}{32}(\frac1{\sqrt{n}})^3 - \frac{865}{128}(\frac1{\sqrt{n}})^5 - \pm \dotsm \right\}
$$
