MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Given: $X_i$ are independent {-1,1} variables with expected value 0 and $X = \sum_{i=1}^n X_i$

Is there a closed form solution / tight bound for $E[ X^{2d} ]$ ?

I realize this problem sounds very simple and may be viewed as a potential homework problem, so I will mention that I'm reading a paper on combinatorial design, involving 2d-independent variables, and I'm trying to take the 2d-th moment of the chebyshev extension.

If you know of a reference, providing the reference (rather than typing out the solution) would suffice.


share|cite|improve this question

$E[X^{2d}]/(2d)!$ is the coefficient of $x^{2d}$ in the Taylor expansion of $\cosh(x)^n$, since $\cosh(x)$ is the exponential moment generating function of each $X_i$.

I don't know if there is a closed form but expanding $\cosh(x)=\frac12(e^{-x}+e^{x})$ by the binomial theorem gives $$ E[X^{2d}] = 2^{-n} \sum_{j=0}^n \binom{n}{j} (n-2j)^{2d}, $$ which is also easy to see from first principles. It isn't obvious but the leading term in $E[X^{2d}]$ is $(2d-1)(2d-3)...(3) n^d$.

This is surely in print somewhere but I didn't look.

share|cite|improve this answer

If you are interested in approximation for large $n,d$, with a simple Poissonization argument I get:

$$ E(X^{2d}) \approx n^{2d} \left( \frac{1+e^{-2\lambda}}{2} \right)^n$$

where $\lambda = \frac{2d}{n}$

share|cite|improve this answer
Under what conditions? You must require $d$ to be rapidly increasing, since $X$ converges to a normal distribution with variance $n$. – Brendan McKay Dec 2 '11 at 23:10

The paper "Randomness-Efficient Oblivious Sampling" by Mihir Bellare and John Rompel approaches this by applying a Chernoff bound. (See Appendix A)

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.