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.

  • $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Nov 2 '11 at 19:30
  • $\begingroup$ 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}$ $\endgroup$ – 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) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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