# Asymptotics of functional of i.i.d. Rademacher random variables

Let $X_1,\ldots, X_n$ be i.i.d. Rademacher random variables. That is, $\operatorname{Pr}(X_i = 1) = \operatorname{Pr}(X_i = -1) = 1/2$. I was wondering if the following argument is true: $$\mathbb{E} \exp\biggl( C\cdot \left(\sum_{i=1}^n X_i\right)^4\big/n^3 \biggr) = 1 + O(1/n),$$ where $C \geq 0$ is a constant.

I did some numerical simulations and the results validated this argument. I would appreciate it if anyone can give a proof.

If my conjecture is correct, this problem reveals an interesting phenomenon of probability theory. In fact, if we replace $\sum_{i=1}^n X_i /\sqrt{n}$ by a standard norm random variable, the expectation is $\infty$. This means that we cannot simply plug in Gaussian approximation here.

P.S.: As pointed out by Christian Remling, this problem has trivial lower bound $2^{-n} \exp(C n)$. So the expectation will explode when $C > \log 2$. What if $0\leq C \leq \log 2$?

• A trivial lower bound is $2^{-n}e^n$, so this is false. – Christian Remling Jan 23 '16 at 4:13
• @ChristianRemling Thanks for your comment! I've modified the question a little bit. What if $C < \log 2$? In this case, the trivial lower bound $2^{-n} \exp(Cn)$ goes to zero. Thanks! – Steve Jan 23 '16 at 4:42

I believe the conjecture is true for sufficiently small $C$. Previously I was trying to disprove it using Large deviation theory. But I missed a sign at the last step. But the same argument can be turned around.

In compact form, one gets $$\lim \frac{1}{n} \log P(\sum_i X_i > \alpha n) = -I(\alpha),$$ where $I(\alpha) = \sup_\theta (\alpha \theta - \log \mathbb{E} e^{\theta X_1})$. One can compute $$I(\alpha) = (\frac{1}{2} - \alpha)\log (\frac{1}{2} - \alpha) + (\frac{1}{2} + \alpha)\log(\frac{1}{2} + \alpha) + \log 2.$$

More precisely, the lower bound (Cramer's inequality) states that for any $\epsilon > 0$, as long as $n$ is sufficient large, we get $P(\sum_i X_i \ge \alpha n) \ge e^{-n (I(\alpha) + \epsilon)}$; see this lecture notes. The upper bound is without the $\epsilon$ and can be proved easily using exponential Tchebyshev. We only need the upper bound here.

Now write the original expectation as $\int_0^1 1 + P(|\sum X_i | > \alpha n) \frac{d}{d\alpha} e^{C \alpha^4 n} d\alpha$, by the so-called integration by parts formula in probability; see page 66 lemma 1.4.30 here. The latter is bounded by $$\int_0^1 1 d\alpha + \int_0^1 4 \alpha^3 C n e^{(C \alpha^4 - I(\alpha))n} d\alpha.$$

After evaluating the third moment of a Gaussian of variance $n^{-1}$ near $\alpha = 0$, one sees that the integral near $0$ goes to zero as $C n^{-2}$, and the rest of the integral is clearly very small.

Note this argument doesn't work for Gaussian because the upper bound of integration is $\infty$ in that case. This is a good check of my often reckless arithmetic.

• Both links are broke. – Hans Jan 7 '18 at 22:06

EDITED: As pointed out by Anthony and John, my 2am solution was anything but. In summary, the conjecture is TRUE for $C$ smaller than approximately 0.6880137 and false for larger $C$.

The exact value is $$S(C,n) = \sum_{k=0}^n 2^{-n}\binom{n}{k} \exp\bigl(Cn^{-3}(n-2k)^4\bigr)$$ since the product of the first two terms is the probability that $\sum_i X_i=n-2k$.

Consider the term $k=(\tfrac12+\beta)n$, where $-\frac12\le\beta\le\frac12$. Stirling's approximation for constant $\beta\ne\pm\frac12$ is $$2^{-n}\binom nk \approx \bigl(2\pi(\tfrac12-\beta)(\tfrac12+\beta)n\bigr)^{-1/2} \bigl(2 (\tfrac12-\beta)^{\tfrac12-\beta} (\tfrac12+\beta)^{\tfrac12+\beta}\bigr)^{-n}$$

Therefore the value of the term is close to $$\bigl(2\pi(\tfrac12-\beta)(\tfrac12+\beta)n\bigr)^{-1/2} \exp\bigl(f(\beta)n\bigr),$$ where $$f(\beta) = -(\tfrac12-\beta)\ln(\tfrac12-\beta) - (\tfrac12+\beta)\ln(\tfrac12+\beta) - \ln 2 + 16C\beta^4.$$ (Note that there is an order $1/n$ term from Stirling's formula missing. Since it doesn't depend on $C$ and the value of the sum is 1 for $C=0$, the effect of the missing term is easily corrected at the end.)

The function $f(\beta)$ has a local maximum of value 0 at $\beta=0$ for every $C$. There is a constant $C_0\approx 0.6880137$ (note: less than $\ln 2$) so that for $C\lt C_0$ we have $f(\beta)\lt 0$ for all $\beta\ne 0$. For $C\gt C_0$ there are places where $f(\beta)\gt 0$ and the sum will be exponential.

Therefore, when $C\lt C_0$ the sum is dominated by terms near $\beta=0$. Around there, $$f(\beta) = -2\beta^2 + (16C-\tfrac43)\beta^4 + O(\beta^6),$$ so the term is close to $$(\pi n/2)^{-1/2} e^{-2\beta^2 n}\bigl(1+(16C-\tfrac43)\beta^4n\bigr)$$ with terms for $\beta=O(n^{-1/2})$ mattering. Approximating the sum by an integral, I get $$S(C,N) = 1 + 3C/n + O(n^{-2}),$$ for $C\lt C_0$.

ADDED: The exact value of $C_0$ is $$\frac{1}{64\beta_0^3}\ln\Bigl(\frac{1+2\beta_0}{1-2\beta_0}\Bigr),$$ where $\beta_0$ is the zero near 0.4953 of $$\bigl(-\tfrac12+\tfrac34\beta\bigr)\ln(1-2\beta) + \bigl(-\tfrac12-\tfrac34\beta\bigr)\ln(1+2\beta).$$ To 50 digits: $C_0 = 0.68880137394879099153980106986892429419403651844842$.

• It seems like Stirling's formula would be better to use than a normal approximation. – Douglas Zare Jan 23 '16 at 16:27
• But only small $\alpha$ are available to you, right? – Anthony Quas Jan 23 '16 at 18:07
• @Anthony: now I am confused. was I right before or am I right now? – John Jiang Jan 23 '16 at 23:03
• This proof seems to make the same mistake as I did with my previous deleted one: first alpha can't be larger than 1 as Anthony pointed out. Then for small alpha actually the square dominates the fourth power, so the lower bound is less than 0. Am I right? – John Jiang Jan 23 '16 at 23:55
• @John : Yes, that problem is there. Now that I have woken up, sort of, I'll see if I can fix it. – Brendan McKay Jan 24 '16 at 0:10