5
$\begingroup$

Let $X_1, \dots, X_N$ be uniform random variables (r.v.) in $[-1, 1]$, and let $S_N$ be their sum $S_N = \sum_{i=1}^N X_i$.

If the r.v. are taken independent, then the CLT suggests that $S_N$ is typically of order $N^{1/2}$, and Hoeffding's inequality shows that in fact $S_N$ is of order at most $N$ except with probability $\leq \exp(-N)$.

Now let us assume that the independent r.v. are conditioned so that the following holds: there exists $k_0$ (depending on $N$) so that for any $k \geq k_0$, if $P$ is any subset of $\{1, \dots, N\}$ of size $k$ we have $$ \left|\sum_{i \in P} X_i\right| \leq f(k) $$ with $f$ sub-linear. Interesting examples would be $f(k) = k^{1- \alpha}$ or $f(k) = (Nk)^{\alpha}$ with $0 < \alpha < 1$ (in the latter case the inequality is useful only if $k_0$ is chosen larger than $N^{\frac{\alpha}{1-\alpha}}$).

I would expect $S_N$ to be of lower order than given by the CLT, and/or the concentration estimates to be also better than Hoeffding's bound (e.g. with the functions $f$ as above, we would have $S_N = O(N^{1- \epsilon})$ with probability $1 - \exp(-N)$, for some $\epsilon > 0$ small enough depending on the choice of $\alpha$).

Are such constraints on the "partial" sums (more precisely, sums on large subsets) studied somewhere? Any idea or reference is most welcome!

Edit (rephrasing). Of course in the i.i.d. case the concentration bound with probability exp(-N) is in fact trivial, since really $S_N = O(N)$ a.s. Similarly, with the assumption on the sum over large subsets, we have $S_N \leq f(N)$ a.s. so clearly we have "better than Hoeffding". I would rather like to know wether one can do "better (than obvious)" with such an assumption, e.g. by showing concentration with probability $1- e^{-N}$ at a lower order than what is given by $f$.

$\endgroup$
4
  • $\begingroup$ Can you clarify what is meant for i.i.d. uniform random variables in $[-1,1]$ to be "conditioned" so that the $f(k)$ inequality holds? Doesn't this contradict independence? $\endgroup$
    – Michael
    Jun 21, 2015 at 4:44
  • $\begingroup$ Yes, they are not independent anymore, and one would expect that their correlation works towards a better concentration bound. $\endgroup$
    – TLeble
    Jun 21, 2015 at 14:36
  • $\begingroup$ In that case, what is the probabilistic description? Without that, it seems you are just talking about deterministic sequences, it seems misleading to talk about probabilistic bounds such as central limit or Hoeffding. $\endgroup$
    – Michael
    Jun 22, 2015 at 1:25
  • $\begingroup$ It seems to me that the $k_0$ property requires $k_0\leq N$ (else there are no subsets $\{1, \ldots, N\}$ of size at least $k_0$). Also, in that case, it seems the property reduces to just saying $|\sum_{i=1}^N X_i |\leq f(N)$ for all $N$, since that is the minimal required and the most we can guarantee. $\endgroup$
    – Michael
    Jun 22, 2015 at 1:29

0

Your Answer

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