2
$\begingroup$

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!

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Under what conditions? You must require $d$ to be rapidly increasing, since $X$ converges to a normal distribution with variance $n$. $\endgroup$
    – Brendan McKay
    Commented Dec 2, 2011 at 23:10
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .