2
$\begingroup$

Consider a random variable $X\sim B(n,\frac 12)$. I'm trying to estimate the asymptotic behaviour of its central moments $E((X-\frac n2)^r)$, where $r$ is even and in the range $\Omega(1)\leq r\leq O(n)$, and $n$ goes to $\infty$.

I've looked at inequalities for central moments of sums of independent variables, but they seem too general. I'd be very grateful if someone can point me in the right direction.

$\endgroup$
11
  • 1
    $\begingroup$ You can use the binomial formula to get exact expression. Better suited for math exchange. $\endgroup$
    – John Jiang
    Mar 17, 2016 at 17:13
  • $\begingroup$ Thank you. Indeed, the binomial formula yields an exact expression, but what I'm looking for is the asymptotic growth of this expression. I will edit the question to reflect this. $\endgroup$ Mar 17, 2016 at 17:35
  • $\begingroup$ I think it is a reasonable question. To clarify, do you want a strict upper bound or instead the asymptotic behaviour as $n \rightarrow \infty$? A normal approximation of the Binomial random variable quickly gives you $E((X-n/2)^r) \approx (\sqrt{n}/2)^r (r-1)!!$, where $(r-1)!! = (r-1)(r-3) ... 1$. $\endgroup$ Mar 17, 2016 at 17:45
  • $\begingroup$ By exact I actually meant you can write the expectation as a closed form function of N, r. It will involve some special functions, but their asymptotic behavior is pretty well undetstood. My mathematica is broken right now but I will try to do it once it's reinstalled. $\endgroup$
    – John Jiang
    Mar 17, 2016 at 22:31
  • 2
    $\begingroup$ Surely it has been done before, but I'd do it thus: the mgf is $$E e^{tX} = 2^{-n}e^{-tn/2}(e^t+1)^n.$$ Now estimate the coefficient of $t^r$ using the saddle-point method (or otherwise). $\endgroup$ Mar 18, 2016 at 0:25

3 Answers 3

1
$\begingroup$

Let $M:=(E(X-n/2)^r)^{1/r}$. By Corollary 2 in [Latala], $M\sim S$, where $A\sim B$ means that $\frac1C\,B\le A\le C B$ for some universal positive constant $C$ and \begin{equation} S:=r\sup\{t(2n/r)^t\colon1/r\le t\le t_*\}, \end{equation} where $t_*:=\frac12\wedge\frac nr$. It is not hard to see that $t(2n/r)^t$ increases in $t\in[1/r,t_*]$, and so, $S=rt_*(2n/r)^{t_*}$. Thus, $M\sim\sqrt{nr}$ if $r\le2n$ and $M\sim n(n/r)^{n/r}\sim n$ if $r\ge2n$. That is, $M\sim\sqrt{n(r\wedge n)}$.

$\endgroup$
2
  • $\begingroup$ Thanks! This reference is pretty much what I was looking for. $\endgroup$ Mar 24, 2016 at 13:10
  • $\begingroup$ Since I'm interested in $M^r$, this gives an estimate tight up to a factor exponential in $r$. Will update if I find anything better. Again, thank you very much. $\endgroup$ Mar 24, 2016 at 13:17
1
$\begingroup$

I wonder if this perhaps-naive approach can help you. Let's shift by the mean, so consider $X = \sum_{j=1}^n X_j$ where each $X_j = 0.5$ or $-0.5$ independently with one-half probability each. So $\mathbb{E} X^r$ should be the value you're looking for. Now,

\begin{align} X^r &= \left(X_1 + \dots + X_n\right)^r \\ &= \sum_{\text{$j_1,\dots,j_r$}} ~~ \prod_{s=1}^r X_{j_s} \end{align} where the sum is over all vectors $(j_1,\dots,j_r)$ of indices in $\{1,\dots,n\}$. Now the expectation of the sum is the sum of the expectations, so let's look at the expectation of one term: \begin{align} \mathbb{E} \prod_{s=1}^r X_{j_s} &= \left(0.5^r\right) \mathbb{E} \prod_{s=1}^r \begin{cases} 1 & X_{j_s} > 0 \\ -1 & \text{otherwise} \end{cases} \\ &= \left(0.5^r\right) \begin{cases} 1 & \text{each index appears in $\vec{j}$ an even number of times} \\ 0 & \text{otherwise}. \end{cases} \end{align} (Why is this true? We split the product into a product over distinct indices $j$ of $X_j^{m(j)}$, where $m(j)$ is the multiplicity of $j$ in the multiset. The indices are independent Bernoullis, so the expectation of the product is the product of the expectations. Each distinct index's expected product is 1 if that index has even multiplicity and zero if odd.)

So if I've made no mistakes, the expectation you're looking for is equal to $0.5^r$ times the number of vectors in $\{1,\dots,n\}^r$ where each $j \in \{1,\dots,n\}$ appears in the vector an even number of times.

Example: For $r=2$, there are $n$ vectors of all-even multiplicity (one for each index, where that index appears twice), so we get $0.5^2*n = n/4$. For $r=4$, there are $n$ vectors containing just $1$ element and $6{n\choose 2}$ vectors containing two elements twice each (because there are six ways to arrange 2 indices into 4 slots, each taking two). So we get $0.5^4 \left(n + 6{n \choose 2}\right) = \frac{1}{16}\frac{2n + 6n^2 - 6n}{2} = \frac{3n^2}{16} - \frac{n}{8}$ (which is also correct -- it's nice to check).

I didn't get to think about how hard this is to estimate in general (I hope someone much more knowledgable in combinatorics can comment).

$\endgroup$
3
  • $\begingroup$ From this it is easy to recover the exact formula $2^{-n}\sum_j\binom{n}{n/2+j} j^r$, but I don't know to get asymptotics from it directly. $\endgroup$ Mar 18, 2016 at 3:14
  • 1
    $\begingroup$ @usul, you've actually given my motivation for asking this question. I started by looking for the asymptotics of the number of sequences of vectors in $\{1\ldots n\}^r$ in which each element appears an even number of times. :-) $\endgroup$ Mar 18, 2016 at 9:40
  • $\begingroup$ @Yonatan, aww, well, it's nice to see the connection but sorry it wasn't useful! $\endgroup$
    – usul
    Mar 18, 2016 at 12:18
0
$\begingroup$

Symmetric Binomial $B(n,1/2)$ has sub-gaussian tails with variance-proxy $\sigma^2 = n/4$. Thus the growth of of the $r$-th moment is at most $(\mathbf{E}\|S\|^r)^{1/r} = O(\sqrt{r}\cdot \sigma) = O(\sqrt{r n})$.

The constant can be calculated by integrating the tails, see for example https://www.hse.ru/data/2016/11/24/1113029206/Concentration%20inequalities.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.