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

-
Try expressing $x^4$ in the form $x(x-1)(x-2)(x-3) + a_1x(x-1)(x-2) + a_2x(x-1) + a_3x$ which will help in computing $E[X^4] = \sum_i i^4 p(X = i)$ when you write $i^4$ as $i(i-1)(i-2)(i-3) + \cdots$ and cancel lots of things from numerators and denominators. – Dilip Sarwate Nov 2 '11 at 19:30
For b), you probably have a typo, and it should read $\mathbb{P}(\vert X \vert > c) \le \frac{\mathbb{E}(X^4)}{c^4}$ – Sasha Nov 2 '11 at 20:04

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

-

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

-