Fast Algorithms for sum of independent random variables

Question

CLT implies the sum of n i.i.d random variables,after property normalized converge to a Normal distribution as n goes to infinity. Furthermore, Linderberg's condition points out not necessarily identically distributed ,the one sufficient condition for the sum converges to Normal distribution in the limit case. From a computational perspective, we want to know how numerically the sum converges to a Normal distribution, this is given by Berry-Esseen Theorem. https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem. Essentially, the theorem says the converges rate is determined by the 2,3 moments of those R.V . For convenience,we call this Berry-Esseen metric. B-E metric

With this theoretic results, a natural idea is when summing those R.V ,for some R.V we can well approximate their sums by a normal distribution ,and some 'exotic' r.v for simulation, hence reduce the computation complexity(simulation is time-consuming) .The question is how to build such 'cluster algorithms' Assuming we know 2 and 3rd moments of each R.V? --Noticed that ,unlike tradition Cluster algorithms in Machine learning, where they clustering is based on some 'distance',in this B-E metric, the expression is highly asymmetric for sigma and pho.

Answer 1

$\newcommand{\De}{\Delta} \newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \renewcommand{\th}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}}$

Knowing only the 2nd and 3rd moments of the (presumable centered) summand random variables (r.v.'s) is hardly enough for very good approximation.

Also, it is somewhat unclear what you mean by "3 moments". In the Berry--Esseen bound, the absolute 3rd moments are used, whereas the Edgeworth expansion (which is in a sense more accurate) is given in terms of initial moments.

So, given only the limited information you have, here is a fast way to approximate and simulate the sum $S_n$ of independent centered r.v.'s $X_1,\dots,X_n$ with given $\E X_i^2$ and $\E X_i^3$: just match the 2nd and 3rd (initial) moments of $S_n$ with the corresponding moments of a r.v. of the form $cZ$, where $c$ is a real number, $Z=Y-\E Y=Y-\la$, and $Y$ has the Poisson distribution with some parameter $\la>0$. Note that $\E S_n^2=B_2:=\sum_1^n \E X_i^2$, $\E S_n^3=B_3:=\sum_1^n \E X_i^3$, and $\E Z^2=\la=\E Z^3$. So, the "matching" system of equations is \begin{equation} c^2\la=B_2,\quad c^3\la=B_3. \end{equation} Solving this system, we get \begin{equation} c=c_*:=\frac{B_3}{B_2},\quad \la=\la_*:=\frac{B_2^3}{B_3^2}. \end{equation} So, we can approximately simulate $S_n$ as $c_*(Y-\la_*)$ with $Y\sim\text{Poisson}(\la_*)$.

One may note that in the case when the $X_i$'s are identically distributed, $\la_*$ is inversely proportional to the coefficient in the leading term of the Edgeworth expansion. More generally, if the $\E X_i^2$'s are of the same order of magnitude and if the $\E X_i^3$'s are also of the same order of magnitude, then $\la_*$ is of the order of $n$; so, $\la_*$ is then large if $n$ is large, and then the distributions of $S_n$ and its Poisson approximation $c_*(Y-\la_*)$ are both close to $N(0,B_2)$ and hence to each other.

Answer 2

Thanks for losif Pinelis's answer.Here is my original thought. Let's start with a concrete example. Assume we want to sum Xi where Xi is in the form Xi=C(j)*Z(m),

where C(j) are positive real number and Z(m) is Poisson distributed r.v with parameter λ(m).

Denote those X(i) who share same Z(m) as 'equivalent class',so in each 'equivalent class', X(i)=C(i)*Z.

The Berry-Esseen metric can be further simplified as B_E=constant*A3/A2. where A3=∑C(i)^3 ,A2=(∑C(i)^2)^3/2 Then from Holder's inequality ,the minimum is achieved iff c(i)'s are equal.

This implies B_E is small when C(i)'s are close.

Therefore, I can apply usual cluster algorithms to group this r.v's. whenever their B-E is smaller than a threshold then approximate them by a Normal distribution, If not,do a simulation for the distribution. Notice, if we have a finite 'equivalent class', which is often the case in real-world application, we can sum up those Normal distribution across different equivalent class , and do a simulation for the 'leftovers'. The best part of this algorithm is that , the more number in each 'equivalent class', the lower their B-E metric, hence more likely to approximate by a Normal distribution. The challenge is that if those X(i) have very 'general' distribution ,it's often hard if not possible to group them into such 'equivalent class'.