2
$\begingroup$

Let us say that a RV $X$ with mean $\mu$ and variance $\sigma^2$ satisfies Bernstein condition with a parameter $\beta>0$, if for all $k \ge 2$, it holds that $$ |\mathbb{E}[(X - \mu)^k]| \le \frac 12 k! \sigma^2 \beta^{k-2}. $$ Trivially, if $X$ satisfies the Bernstein condition with a parameter $\beta$, then it also satisfies it with any $\beta' > \beta$.

If there are $n$ independent RVs $X_1,X_2,\dotsc,X_n$ with means $\mu_1,\dotsc,\mu_n$, variances $\sigma_1^2,\dotsc,\sigma_n^2$, and satisfying Bernstein condition with parameters $\beta_1,\dotsc,\beta_n$, respectively, what can we say about their sum $X=X_1+\dotsb+X_n$?

I think I can show that $X$ satisfies Bernstein condition with the parameter $$ \beta = \sqrt[3]{n} \max(\sigma_1,\dotsc,\sigma_n,\beta_1,\dotsc,\beta_n). $$

But I also believe this parameter can be decreased. What could be a smaller value of the Bernstein parameter of $X$?

UPD: I have a suspicion that it can be shown that $\beta = \max(\sigma_1,\dotsc,\sigma_n,\beta_1,\dotsc,\beta_n)$ but is it true?

$\endgroup$

3 Answers 3

4
$\begingroup$

$\newcommand{\be}{\beta}\newcommand{\si}{\sigma}$No, this is not true. Indeed, suppose that $X_1,\dots,X_n$ are i.i.d. zero-mean normal random variables (r.v.'s) with variance $\si^2$ such that \begin{equation*} |E(X-EX)^k|\le\frac{k!}2\,E(X-EX)^2 \be^{k-2} \end{equation*} for all $k=2,3,\dots$. For $k=4$ this becomes $3(n\si^2)^2\le12n\si^2\be^2$, so that \begin{equation*} \be\ge n^{1/2}\si/2. \tag{1}\label{1} \end{equation*}

On the other hand, for all $m=1,2,\dots$, we have $EX_i^{2m+1}=0$ and $EX_i^{2m}=1\cdot3\cdot\,\cdots\,\cdot(2m-1)\si^{2m}\le\frac{(2m)!}2\,\si^{2m}$. So, for all $k=2,3,\dots$ and all $i\in[n]:=\{1,\dots,n\}$, we have the Bernstein condition \begin{equation*} |E(X_i-EX_i)^k|\le \frac{k!}2\,\si_i^2 \be_i^{k-2} \tag{2}\label{2} \end{equation*} with $\si_i:=\si$ and $\be_i:=\si$.

So, in view of \eqref{1}, \begin{equation*} \be\ge \frac{n^{1/2}}2\,M,\quad\text{where }M:=\max(\si_1,\dots,\si_n,\be_1,\dots,\be_n). \tag{3}\label{3} \end{equation*}


On the positive side, we will prove the following Bernstein condition on $X$: \begin{equation*} \begin{aligned} E|X-\mu|^k \le ck!\,B^2\be^{k-2}\le \frac{k!}2\,B^2(2c\be)^{k-2} \end{aligned} \tag{4}\label{4} \end{equation*} for all integers $k\ge3$, where $c:=\frac94\,\sqrt{\frac43}=2.598\ldots$, $\mu:=EX=\mu_1+\cdots+\mu_n$, $B^2:=E(X-EX)^2=\si_1^2+\cdots+\si_n^2$,
\begin{equation*} \be=\sqrt{\frac83}\,n^{1/2}M, \tag{5}\label{5} \end{equation*} and, as before, \begin{equation*} M:=\max(\si_1,\dots,\si_n,\be_1,\dots,\be_n), \end{equation*} so that the $\be$ in \eqref{5} is optimal up to a universal positive real constant factor. (Note that the inequality $E|X-\mu|^k\le \frac{k!}2\,B^2(2c\be)^{k-2}$ clearly holds for $k=2$.)

To prove \eqref{4}, for $i\in[n]:=\{1,\dots,n\}$, let \begin{equation*} Y_i:=X_i-X'_i, \end{equation*} where $(X'_1,\dots,X'_n)$ is an independent copy of $(X_1,\dots,X_n)$, and then let \begin{equation*} Y:=\sum_{i\in[n]}Y_i. \end{equation*} Then for any integer $m\ge1$ we have $EY_i^{2m-1}=0$ and $Y_i^{2m}\le2^{2m-1}[(X_i-\mu_i)^{2m}+(X'_i-\mu_i)^{2m}]$, so that, by the Bernstein condition \eqref{2},
\begin{equation*} EY_i^{2m}\le2^{2m-1}\,(2m)!\,\si_i^2 M^{2m-2}. \tag{6}\label{6} \end{equation*} By the multinomial formula and \eqref{6}, \begin{equation*} \begin{aligned} EY^{2m}&=\sum\nolimits'\frac{(2m)!}{(2m_1)!\cdots(2m_n)!}\,EY_1^{2m_1}\cdots EY_n^{2m_n} \\ &=(2m)!\sum_{J\subseteq[n]}\sum\nolimits^J \prod_{j\in J}\frac{EY_j^{2m_j}}{(2m_j)!} \\ &\le(2m)!\sum_{\emptyset\ne J\subseteq[n]} \sum\nolimits^J 2^{2m-|J|}M^{2m-2}\min_{j\in J}\si^2_j \\ &\le(2m)!\sum_{\emptyset\ne J\subseteq[n]} \sum\nolimits^J 2^{2m-|J|}M^{2m-2}\si^2_J \\ &\le(2m)!2^{2m-1}M^{2m-2}S, \end{aligned} \tag{7}\label{7} \end{equation*} where

  • $\sum\nolimits'$ is the sum over all $n$-tuples $(m_1,\dots,m_n)$ of nonnegative integers such that $m_1+\dots+m_n=m$; such $n$-tuples are called the $n$-weak compositions of $m$;

  • $|J|$ is the cardinality of $J$;

  • $\sum\nolimits^J$ is the sum over all families $(m_j)_{j\in J}$ of integers $\ge1$ such that $\sum_{j\in J}m_j=m$; such a family $(m_j)_{j\in J}$ exists only if $1\le|J|\le m$; if the latter condition does not hold, then $\sum^J\cdots=0$;

  • $\si^2_J:=\frac1{|J|}\,\sum_{j\in J}\si_j^2$;

  • $S:=\sum_{J\subseteq[n]}\sum\nolimits^J \si^2_J$.

Note that $S$ is a symmetric homogeneous polynomial function of $\si^2_1,\dots,\si^2_n$ of degree $1$ in each $\si^2_j$. So, \begin{equation*} S=\Big(\frac1n\,\sum_{j\in[n]}\si_j^2\Big)\sum_{J\subseteq[n]}\sum\nolimits^J 1 =\frac{B^2}n\,\sum\nolimits' 1 =\frac{B^2}n\,\binom{m+n-1}m. \tag{8}\label{8} \end{equation*}

Without loss of generality, $n\ge2$. By induction on $m$, for all integers $m\ge2$ we have \begin{equation*} \frac1n\binom{m+n-1}m \le\frac{n+1}{2}(2n/3)^{m-2}. \end{equation*}

So, by \eqref{7}, \eqref{8}, and \eqref{5},
\begin{equation*} \begin{aligned} EY^{2m}& \le c_n(2m)!\,B^2 \be^{2m-2}, \end{aligned} \end{equation*} with \begin{equation*} c_n:=\frac{3n+3}{2n}\le\frac94. \end{equation*} so that, by the Jensen inequality $E(X-\mu)^{2m}\le EY^{2m}$, we have \begin{equation*} \begin{aligned} E(X-\mu)^{2m}& \le\frac94\,(2m)!\,B^2\be^{2m-2}; \end{aligned} \end{equation*} the latter inequality clearly holds for $m=1$ as well.

So, for all integers $m\ge1$, by the Cauchy--Schwarz inequality, \begin{equation*} \begin{aligned} E|X-\mu|^{2m+1}&\le\sqrt{E(X-\mu)^{2m}\,E(X-\mu)^{2m+2}} \\ &\le\frac94\,\sqrt{\frac43}\,(2m+1)!\,B^2 \be^{2m-1}. \end{aligned} \end{equation*}

So, for all integers $k\ge3$, we have the first inequality in \eqref{4}; the second inequality there is trivial. $\quad\Box$

Remark: By the Bernstein condition \eqref{2} with $k=4$ and the inequality $E(X_i-EX_i)^4\ge\si_i^4$, we have $\si_i^2\le12\be_i^2$. So, \begin{equation*} M\le\sqrt{12}\max(\be_1,\dots,\be_n). \end{equation*}

$\endgroup$
11
  • $\begingroup$ Hmmm... let me check the "proof" I have for the cubic root result... $\endgroup$ Commented Sep 26 at 17:16
  • $\begingroup$ Yep, it seems the counter-example with Guassian RVs is correct. I think for the general case, I can show that something of order $\sqrt{n}$ will work $\endgroup$ Commented Sep 26 at 20:26
  • 1
    $\begingroup$ Yes, $\sqrt n$ works. See the addition to this answer. $\endgroup$ Commented Sep 27 at 11:35
  • 1
    $\begingroup$ @YauhenYakimenka : This has now been fixed. $\endgroup$ Commented Sep 29 at 9:26
  • 1
    $\begingroup$ @YauhenYakimenka ; All right. Please keep in touch. $\endgroup$ Commented Oct 1 at 17:47
1
$\begingroup$

This is an alternative proof to show that $\beta \le \sqrt n \max(\sigma_1,\dotsc,\sigma_n,\beta_1,\dotsc, \beta_n)$.


In the proof, we assume for simplicity that all $\mu_i=0$, as Bernstein's condition is only concerned with central moments. We use a shorthand $\beta_\max \triangleq \max \{\beta_1,\ldots,\beta_n, \sigma_1,\dotsc,\sigma_n\}$.

For $k=3$, the result can be checked in a straightforward manner. For $n\ge 2$ and $k \ge 4$, we have: \begin{align*} &\left| \mathbb E{\left(X_1+\dotsb+X_n\right)^k} \right| \\ &= \left| \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \ge 0}} \frac{k!}{i_1!\cdot \dots \cdot i_n!} \mathbb E{X_1^{i_1}} \cdot \dots \cdot \mathbb E{X_n^{i_n}}\right| \\ &\le \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \ge 0}} \frac{k!}{i_1!\cdot \dots \cdot i_n!} \prod_{j=1}^n \left|\mathbb E{X_j^{i_j}}\right| \end{align*}

Note that $\mathbb E{X_j^0} = 1$ and $\mathbb E{X_j}=\mu_j=0$. We continue: \begin{align*} &\le \sum_{j=1}^n \left|\mathbb E{X_j^k}\right| + \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac{k!}{i_1!\cdot \dots \cdot i_n!} \prod_{\substack{j=1\\i_j \neq 0}}^n \left|\mathbb E{X_j^{i_j}}\right| \\ &\le \sum_{j=1}^n \frac 12 k! \sigma_j^2 \beta_j^{k-2} \\ &\qquad + \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac{k!}{i_1!\cdot \dots \cdot i_n!} \prod_{\substack{j=1\\i_j \neq 0}}^n \frac 12 i_j! \sigma_j^2 \beta_j^{i_j-2} \\ &\le \frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} + k! \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_H(i_1,\dotsc,i_n)}} \beta_{\mathrm{max}}^{k-w_H(i_1,\dotsc,i_n)} \prod_{\substack{j=1\\i_j \neq 0}}^n \sigma_j, \end{align*} where $w_H(i_1,\dotsc,i_n)$ denotes the number of non-zeros among $i_1,\dotsc,i_n$.

Observe that if $J = \{j \in [n] \mid i_j \neq 0\}$, where $|J| = w \ge 2$, then for any $j_1,j_2 \in J$, $j_1 < j_2$, it is true that $$ \prod_{j \in J} \sigma_j \le \sigma_{j_1} \sigma_{j_2} \beta_{\mathrm{max}}^{w-2}. $$ Summing up over the choice of ordered pairs $(j_1,j_2) \in J^2$, $j_1 < j_2$, we get: $$ \prod_{j \in J} \sigma_j \le \frac{\beta_{\mathrm{max}}^{w-2}}{\binom w2} \sum_{\substack{j_1,j_2 \in J \\ j_1 < j_2}} \sigma_{j_1} \sigma_{j_2} $$

We continue: \begin{align*} &\le \frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} + k! \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_H(i_1,\dotsc,i_n)}} \beta_{\mathrm{max}}^{k-w_H(i_1,\dotsc,i_n)} \prod_{\substack{j=1\\i_j \neq 0}}^n \sigma_j \\ &\le \frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} \\ &\qquad + \frac 12 k! \beta_{\mathrm{max}}^{k-2} \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_H(i_1,\dotsc,i_n)-1} \binom{w_H(i_1,\dotsc,w_n)}2} \sum_{\substack{1 \le j_1 < j_2 \le n \\ i_{j_1},i_{j_2} \neq 0}} \sigma_{j_1} \sigma_{j_2} \end{align*}

Consider the following polynomial in $\binom n2$ variables $s_{j_1j_2}$, $j_1,j_2 \in [n]$, $j_1 < j_2$: \begin{align} &f(s_{12},\dotsc,s_{n-1,n}) \\ &\qquad= \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_\mathrm{H}(i_1,\dotsc,i_n)-1} \binom{w_\mathrm{H}(i_1,\dotsc,i_n)}2} \sum_{\substack{1 \le j_1 < j_2 \le n \\ i_{j_1},i_{j_2} \neq 0}} s_{j_1j_2} \tag{1} \end{align} It has degree $1$ (linear) and symmetric in its variables. Any degree-$1$ symmetric polynomial in $\binom n2$ variables has the form \begin{equation}\tag{2} f(s_{12},\dotsc,s_{n-1,n}) = a \frac{s_{12} + s_{13} + \dotsb + s_{n-1,n}}{\binom n2}. \end{equation} Setting all $s_{j_1j_2} = 1$, and comparing (1) with (2), we obtain that $$ a = \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_\mathrm{H}(i_1,\dotsc,i_n)-1}}. $$ Therefore, \begin{align*} &\frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} \\ &\qquad + \frac 12 k! \beta_{\mathrm{max}}^{k-2} \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_\mathrm{H}(i_1,\dotsc,i_n)-1} \binom{w_\mathrm{H}(i_1,\dotsc,i_n)}2} \sum_{\substack{1 \le j_1 < j_2 \le n \\ i_{j_1},i_{j_2} \neq 0}} \sigma_{j_1} \sigma_{j_2} \\ &=\frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} \\ &\qquad + \frac 12 k! \frac{\sum_{1 \le j_1 < j_2 \le n} \sigma_{j_1} \sigma_{j_2}}{\binom n2} \beta_{\mathrm{max}}^{k-2} \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_\mathrm{H}(i_1,\dotsc,i_n)-1}} \end{align*}

For a fixed $2 \le w \le \lfloor \frac k2 \rfloor$, the number of integer solutions of \begin{gather*} i_1+\dotsb+i_n=k, \\ i_1,\dotsc,i_n \neq 1,k-1,k, \\ w=w_\mathrm{H}(i_1,\dotsc,i_n), \end{gather*} is $\binom nw$ times the number of integer solutions of (everywhere we assume that $\binom xy = 0$ if $x < y$) \begin{gather*} x_1 + \dotsb + x_w = k, \\ 2 \le x_1, \dotsc, x_w \le k-2, \end{gather*} Since $w \ge 2$, the constraint $\le k-2$ is redundant and can be dropped. Next, by substitution $x_i = y_i+1$, the equation is equivalent to the following one: \begin{gather*} y_1 + \dotsb + y_w = k-w, \\ y_1, \dotsc, y_w \ge 1, \end{gather*} which has $\binom{k-w-1}{w-1}$ integer solutions (the number of $w$-compositions).

Altogether, we continue: \begin{align*} &\frac 12 k! \sigma^2 \beta_\max^{k-2} \\ &\qquad + \frac 12 k! \frac{\sum_{1 \le j_1 < j_2 \le n} \sigma_{j_1} \sigma_{j_2}}{\binom n2} \beta_\max^{k-2} \sum_{\substack{i_1+\dotsb+i_n=k \\ i_1,\dotsc,i_n \neq 1,k-1,k}} \frac 1{2^{w_\mathrm{H}(i_1,\dotsc,i_n)-1}} \\ &\le \frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} + \frac 12 k! \left(\sum_{1 \le j_1 < j_2 \le n} \sigma_{j_1} \sigma_{j_2}\right) A_{nk} \beta_{\mathrm{max}}^{k-2}, \end{align*} where $$ A_{nk} \triangleq \frac{1}{\binom n2}\sum_{w=2}^{\lfloor \frac k2 \rfloor} \frac 1{2^{w-1}} \binom nw \binom{k-w-1}{w-1} $$ Now we will require that \begin{align*} &\frac 12 k! \sigma^2 \beta_{\mathrm{max}}^{k-2} + \frac 12 k! \left(\sum_{1 \le j_1 < j_2 \le n} \sigma_{j_1} \sigma_{j_2}\right) A_{nk} \beta_{\mathrm{max}}^{k-2} \\ &\qquad \le \frac 12 k! \sigma^2 \left(\alpha_{nk} \sqrt n \beta_{\mathrm{max}}\right)^{k-2}, \end{align*} where $\alpha_{nk} > 0$ is some expression we want to bound. The last inequality is equivalent to \begin{equation} \sigma^2 \left( \alpha_{nk}^{k-2} n^{\frac k2 - 1} - 1 \right) - A_{nk} \sum_{1 \le i<j \le n} \sigma_i \sigma_j \ge 0.\tag{3} \end{equation} Observe that $$ \sigma^2 = \frac{\sum_{1 \le i<j \le n} (\sigma_i - \sigma_j)^2 + 2\sigma_i\sigma_j}{n-1} $$ Thus, (3) is equivalent to $$ \sum_{1 \le i<j \le n} (\sigma_i - \sigma_j)^2 + \left(2 - \frac{(n-1)A_{nk}}{\alpha_{nk}^{k-2} n^{\frac k2 - 1} - 1} \right) \sum_{1 \le i<j \le n} \sigma_i \sigma_j \ge 0. $$ Since all standard deviations are non-negative, it is sufficient to require that \begin{gather*} 2 - \frac{(n-1)A_{nk}}{\alpha_{nk}^{k-2} n^{\frac k2 - 1} - 1} = 0, \\ \alpha_{nk}^{k-2} = \frac{1}{n^{\frac k2 - 1}} + \frac{n-1}{2 n^{\frac k2 - 1}} A_{nk}. \end{gather*} Now, we want to find an upper bound for all $n \ge 2$ and $k \ge 4$ on $\alpha_{nk}^{k-2}$: \begin{align*} &\frac{1}{n^{\frac k2 - 1}} + \frac{n-1}{2 n^{\frac k2 - 1}} A_{nk} \\ &=\frac{1}{n^{\frac k2 - 1}} + \frac{n-1}{2 n^{\frac k2 - 1}} \frac{1}{\binom n2}\sum_{w=2}^{\lfloor \frac k2 \rfloor} \frac 1{2^{w-1}} \binom nw \binom{k-w-1}{w-1} \tag{4}\\ &=\frac{1}{n^{\frac k2 - 1}} + \frac{1}{n^{\frac k2}} \sum_{w=2}^{\lfloor \frac k2 \rfloor} \frac 1{2^{w-1}} \binom nw \binom{k-w-1}{w-1} \\ &\le\frac{1}{n^{\lfloor\frac k2\rfloor - 1}} + \frac{1}{n^{\lfloor\frac k2\rfloor}} \sum_{w=2}^{\lfloor \frac k2 \rfloor} \frac 1{2^{w-1}} \binom nw \binom{2 \lfloor \frac k2 \rfloor-w}{w-1} \\ &= \left[ \ell \triangleq \lfloor \frac k2 \rfloor \ge 2 \right] \\ &= \frac{1}{n^{\ell-1}} + \frac{1}{n^\ell} \sum_{w=2}^{\ell} \frac{1}{2^{w-1}} \binom nw \binom{2\ell-w}{w-1} \\ &=\left[\text{for $w \le \ell$, we have } \frac{\binom nw}{n^\ell} \le \frac{1}{w!n^{\ell-w}}\right] \\ &\le \frac{1}{n^{\ell-1}} + \sum_{w=2}^{\ell} \frac{1}{2^{w-1} w! n^{\ell-w}} \binom{2\ell-w}{w-1} \end{align*} The last expression for a fixed $\ell \ge 2$ has the following form: $$ a_0 + \frac{a_1}{n} + \frac{a_2}{n^2} + \dotsb + \frac{a_{\ell-1}}{n^{\ell-1}}, $$ where $a_0,a_1,\dotsc,a_{\ell-1}$ are positive constants. Thus, for a fixed $\ell \ge 2$, it is decreasing in $n$, and \begin{align*} &\frac{1}{n^{\ell-1}} + \sum_{w=2}^{\ell} \frac{1}{2^{w-1} w! n^{\ell-w}} \binom{2\ell-w}{w-1} \\ &\le \left.\left( \frac{1}{n^{\ell-1}} + \sum_{w=2}^{\ell} \frac{1}{2^{w-1} w! n^{\ell-w}} \binom{2\ell-w}{w-1} \right)\right|_{n=2} \\ &= \frac{1}{2^{\ell-1}} + \frac{1}{2^{\ell-1}}\sum_{w=2}^{\ell} \frac{1}{w!} \binom{2\ell-w}{w-1} \end{align*} Since $\frac{1}{w!} \binom{2l-w}{w-1} \le 2^{l-w}$, we have: \begin{align*} &\frac{1}{2^{\ell-1}} + \frac{1}{2^{\ell-1}}\sum_{w=2}^{\ell} \frac{1}{w!} \binom{2\ell-w}{w-1} \\ &\qquad\le \frac{1}{2^{\ell-1}} + \frac{1}{2^{\ell-1}}\sum_{w=2}^{\ell} 2^{\ell-w} = 1. \end{align*}

Therefore, $\alpha_{nk}^{k-2} \le 1$, and thus, $\alpha_{nk} \le 1$. We can take $\alpha_{nk} = 1$ and thus obtain that for any $n \ge 2$ and $k \ge 4$, \begin{align*} \left| \mathbb E{\left(X_1+\dotsb+X_n\right)^k} \right| \le \frac 12 k! (\sqrt n \beta_{\mathrm{max}})^{k-2}, \end{align*} and $X_1 + \dotsb + X_n$ satisfies the Bernstein's condition with the parameter $\sqrt n \beta_{\mathrm{max}}$.


If instead of bounding, we calculate (4) with Mathematica for $n$ and $k$ up to $100$, we get that $\alpha_{nk} \le \frac{\sqrt[4]{7}}2 \approx 0.81$. This achieved for $n=2$ and $k=6$ and seems to decrease for larger $n$ and $k$. So perhaps the constant in front of $\sqrt n \beta_\max$ can be further improved.
$\endgroup$
9
  • $\begingroup$ Looks intriguing. Two things so far: (i) You should exclude $i_j=1$ already in your first display. (ii) What is $w_H$? $\endgroup$ Commented Oct 17 at 16:03
  • $\begingroup$ $w_H$ is a Hamming weight (or support), i.e., the number of non-zeros among $i_1,\dotsc, i_n$. I will add an explanation about this, thanks! $\endgroup$ Commented Oct 17 at 23:35
  • $\begingroup$ And I exclude $i_j=1$ in my second display after I explicitly mention the reason for that ($\mathbb E X_j =0$). Some places in my proof are a bit too detailed perhaps but well... Or do you mean it is a mistake to not exclude them in the very first display? (Then I don't see what the problem is...) $\endgroup$ Commented Oct 17 at 23:42
  • $\begingroup$ Not sure if it was clear, but $w=w_H(i_1,\dotsc,i_n)$ is just a notational shorthand in the expressions when we sum over the choices of $i_1,\dotsc,i_n$. Later, however, $w$ becomes just an iterator in the sums... $\endgroup$ Commented Oct 17 at 23:56
  • 1
    $\begingroup$ This is very nice. However: (i) my previous point (i) has not been taken into account. (ii) After (3), you can just use $\sigma_i\sigma_j\le(\sigma_i^2+\sigma_j^2)/2$. (iii) How do you prove that $\frac{1}{w!} \binom{2l-w}{w-1} \le 2^{l-w}$? (iv) Instead of "we continue"'s, you can denote the expression by a symbol and then use that symbol. $\endgroup$ Commented Oct 18 at 13:35
0
$\begingroup$

$\newcommand{\be}{\beta}\newcommand{\bem}{\beta_{\max}}\newcommand{\si}{\sigma}\newcommand{\sem}{\si_{\max}}$Here is another way to obtain a Bernstein-type condition on your $X$, which will oftentimes provide a better (that is, smaller) upper bound on the centered moments of $X$.

Without loss of generality, $\mu_i=0$ for all $i$, and hence $\mu=EX=0$. Let $$\bem:=\max(\be_1,\dots,\be_n). $$ Then your Bernstein condition on the $X_i$'s implies (see e.g. this answer) $$Ee^{hX}\le\exp\frac{h^2 B^2}{2(1-h\bem)} \tag{10}\label{10}$$ for all $h\in[0,1/\bem)$, where, as in the previous answer, $$B:=\sqrt{\si_1^2+\cdots+\si_n^2}.$$ Inequality \eqref{10} holds with $-X$ in place of $X$. So, for $m=1,2,\dots$, $$\frac{h^{2m}}{(2m)!}\,EX^{2m}\le E\cosh hX\le\exp\frac{h^2 B^2}{2(1-h\bem)}.$$ Taking now any real $c_1>0$ and any $c_2\in(0,1)$, and then choosing $h=\min(\frac{c_1}{B},\frac{c_2}{\bem})$, we get $$ EX^{2m}\le C(2m)!\max\Big(\frac {B}{c_1},\frac{\bem}{c_2}\Big)^{2m},$$ where $C:=\exp\frac{c_1^2}{2(1-c_2)}$. Using now the Cauchy--Schwarz inequality as at the end of the previous answer, we get $$ E|X|^k\le b_{20}:=\sqrt{\frac43}\, Ck!\max\Big(\frac {B}{c_1},\frac{\bem}{c_2}\Big)^k \tag{20}\label{20}$$ for $k=2,3,\dots$. The upper bound $b_{20}$ on $E|X|^k=E|X-EX|^k$ in \eqref{20} can be compared with the upper bound
\begin{equation*} \begin{aligned} b_4:=ck!\,B^2\be^{k-2} \end{aligned} \end{equation*} on $E|X-EX|^k$ given by inequality (4) in the previous answer, where $c:=\frac9{8\sqrt3}=0.649\ldots$ and \begin{equation*} \be=\sqrt{\frac83}\,n^{1/2}\max(\sem,\bem),\quad \sem:=\max(\si_1,\dots,\si_n). \end{equation*} We see that $b_{20}$ may be much smaller than $b_4$ if (i) the $\si_i$'s are of very different magnitudes or (ii) $\bem$ is large so as to be comparable with $B$ while $n$ is large. The latter condition, (ii), occurs e.g. when $\frac12(1-P(X_i=0))=P(X_i=\pm1)=\frac p2\asymp\frac1n$ for all $i=1,\dots, n$, with $\bem=\max_{k=3,4,\dots}(\frac2{k!})^{1/(k-2)} =(\frac2{3!})^{1/(3-2)}=\frac13\asymp1\asymp B$ and $n\to\infty$.

$\endgroup$

You must log in to answer this question.

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