Expectation of Random Walk At each time step, I have 1/2 probability of walking one step to the right, and  the same probability of walking one step to the left. 
Let X be the random variable corresponding to the final position of the $n$ step I walk.
Compute 
a) $E[X^4]$ for this random variable
b) Show that $P(|X|>c) \le \dfrac{E[X^4]}{c^4}$
My thought:
I tried to use the definition of expectation to compute but the polynomial of degree 4 got really messy. I was wondering if there is an elegant way to approach this problem. And I also tried to use generating function but how to write the generating function for this random variable. 
 A: A less elegant, but simple approach: 
$X=Z_1 + Z_2 + \cdots + Z_n$ with $Z_i =\pm 1$.
We must compute $E[ (Z_1 + Z_2 + \cdots + Z_n)^4]$ . If we expand this, we get a sum of $n^4$ fourth degree monomials. But because $Z_i$ are iid with zero mean, all terms vanish except those that contains exclusively even exponents; that is, those that are of the form $E(Z_i^4)$ or $E(Z_i^2 Z_j^2)$. 
Now, there are $n$ terms of the first form, and $ {4 \choose 2} {n \choose 2} = 3 n (n-1)$ terms of the second. Besides, $E(Z_i^2) = E(Z_i^4)=1$ trivially. Hence 
$$E(X^4) = n + 3 \; n( n - 1) = n \; (3 n -2)$$
A: Notice that $X \stackrel{d}{=} 2 U - n$, where $U$ follows binomial distribution $Bi(n, \frac{1}{2})$. Moment generating function of the symmetric binomial distribution is $g(t) = \mathbb{E}\left( \mathbb{e}^{t U} \right) = \left( \frac{1}{2} + \frac{1}{2} \mathrm{e}^t \right)^n$. Therefore
$$
 \mathbb{E}\left( \mathbb{e}^{t X} \right) = \mathrm{e}^{-t n} g(2t) = \cosh^n(t)
$$
The fourth moment can be extracted from series expansion:
$$
   \cosh^n(t) = 1 + n \frac{t^2}{2!} + n(3n-2) \frac{t^4}{4!} + o(t^4)
$$
