Can I prove this, or hopeless? Deviating too much from mean

57 Views Asked by At

Can I prove this:

We have a sequence of vectors $\left(X_i(n)\right)$ for $i=1,\ldots,t$, where $n\rightarrow \infty$. $t$ does depend on $n$ and is Chosen such that $1 \ll t \ll n$, for instance, take $t=\log(n)$. We know that $$X(n):=\sum_{i=1}^t X_i(n).$$

Can we prove that $$X(n)= \left(\sum_{i \ : P(i) } X_i(n) \right)(1+o(1))$$ where $P(i)$ is a predicate with $$P(i)=1 \text{ iff } X_i(n) = \Omega\left(\frac{X(n)}{t}\right),$$ thus $0$ when $X_i(n)$ is asymptotically smaller than $\frac{X(n)}{t}$.

Stated differently, can we prove that $X(n)$ depends only on the Terms $X_i(n)$ for which the predicate is true?

This seems to be rather intuitive. But I cannot prove it. Would be glad if you could provide a proof.

1

There are 1 best solutions below

6
On BEST ANSWER

Define $$ \lambda:=\frac{\sum_{i\not\in P(i)} X_i(n)}{\sum_{i\in P(i)} X_i(n)} $$ and note that $\sum_{i\not\in P(i)} X_i(n)=\mathcal{O}(X(n)/t)$ and $\sum_{i\in P(i)} X_i(n)=\Omega(X(n)/t)$.

Your desired result requires that $\lambda=o(1)$. But this only necessarily follows if $\mathcal{O}(f)/\Omega(f)=o(1)$ for all functions $f$, which isn't true. However, the following (weaker) statement is obviously true $$X(n)= \left(\sum_{i \ : P(i) } X_i(n) \right)(1+\mathcal{O}(1))$$

The issue is that some of the $X_i(n)$ terms may grow asymptotically to the average $\frac{1}{t}\sum_{i=1}^t X_i(n)$ from below ($\mathcal{O})$ while others do so from above ($\Omega$).