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

Question

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

Answer 1

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\left(\sum_i X_i > \alpha n\right) = -I(\alpha),$$ where $I(\alpha) = \sup_\theta (\alpha \theta - \log \mathbb{E} e^{\theta X_1})$. One can compute $$I(\alpha) =\left(\frac{1}{2} - \alpha\right)\log \left(\frac{1}{2} - \alpha\right) + \left(\frac{1}{2} + \alpha\right)\log\left(\frac{1}{2} + \alpha\right) + \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 note. 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.

Answer 2

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

Answer 3

I think there is no absolute constant, but rather dependency on $n$.

Having a look at the moment generating function (I denote $t:=C$) $$ \phi(t)=\mathbf{E}\mathrm{e}^{t S_n^4/n^3} = 1+\sum_{k=1}^{\infty}\frac{t^k\mathbf{E}S_n^{4k}}{n^{3k} k!}, $$

we see that the radius of convergence is $$ R = \frac{1}{\limsup_k\frac{(\mathbf{E} S_n^{4k}/n^{3k})^{\frac{1}{k}}}{(k!)^{\frac{1}{k}}}} = \frac{1}{\mathrm{e}n}, $$ where we use the fact that $n$ is fixed, and so $\|S_n\|_k \to \|S_n\|_{\infty} = n$ as $k\to+\infty$, and so $(\mathbf{E}S_n^{4k})^{1/k} = \|S_n\|_{4k}^{4}\to n^4$.

Within the convergence regime $t\leqslant \delta < R$, we have an analytic function and can indeed write $$ \phi(t) = 1 + O_{\delta}(t/n) = 1 + O_{\delta}(n^{-1}) $$ but only for $t$ smaller than the radius which decreases with $n$.