Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Thanks!

share|improve this question
add comment

3 Answers

$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|improve this answer
add comment

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|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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.