# 2d moment of chebyshev

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!

-

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

-

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

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

-