Expectation of Random Walk

Question

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.

Answer 1

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

Answer 2

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