Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.