We consider a basic problem in unsupervised learning: learning an unknown . A Poisson Binomial Distribution (PBD) over @math is the distribution of a sum of @math independent Bernoulli random variables which may have arbitrary, potentially non-equal, expectations. These distributions were first studied by S. Poisson in 1837 Poisson:37 and are a natural @math -parameter generalization of the familiar Binomial Distribution. Surprisingly, prior to our work this basic learning problem was poorly understood, and known results for it were far from optimal. We essentially settle the complexity of the learning problem for this basic class of distributions. As our first main result we give a highly efficient algorithm which learns to @math -accuracy (with respect to the total variation distance) using @math samples . The running time of the algorithm is in the size of its input data, i.e., @math bit-operations. (Observe that each draw from the distribution is a @math -bit string.) Our second main result is a proper learning algorithm that learns to @math -accuracy using @math samples, and runs in time @math . This is nearly optimal, since any algorithm for this problem must use @math samples. We also give positive and negative results for some extensions of this learning problem to weighted sums of independent Bernoulli random variables.
The Poisson binomial distribution is approximated by a binomial distribution and also by finite signed measures resulting from the corresponding Krawtchouk expansion. Bounds and asymptotic relations for the total variation distance and the point metric are given. The sum of finitely many variates possesses, under familiar conditions, an almost Gaussian probability distribution. This already much discussed "central limit theorem"(x) in the theory of probability is the object of further investigation in the present paper. The cases of Liapounoff(2), Lindeberg(3), and Feller(4) will be reviewed. Numerical estimates for the degrees of approximation attained in these cases will be presented in the three theorems of §4. Theorem 3, the arithmetical refinement of the general theorem of Feller, constitutes our principal result. As the foregoing implies, we require throughout the paper that the given variates be totally independent. And we consider only one-dimensional variates. The first three sections of the paper are devoted to the preparatory Theorem 1 in which the variates.meet the further condition of possessing finite third order absolute moments. Let X , Xi, • • • , Xn be the given variates. For each k k = ,2, ■ ■ ■ , n) let ^(Xk) and ixs Xk) denote, respectively, the second and third order absolute moments of Xk about its mean (expected) value a*. These moments are either both zero or both positive. The former case arises only when Xk is essentially constant, i.e., differs from its mean value at most in cases of total probability zero. To avoid trivialities we suppose that PziXk) >0 for at least one k (k = 1, 2, • • • , n). The non-negative square root of m Xk) is the standard deviation of Xk and will be denoted by ak. We call    The simple example (n = 1) is given for classroom presentation when teaching UMPU tests. Along with the more general example (any n), it is intended to dispel a common belief that the labels UMP and UMPU are synonymous. A student could thus be encouraged to look beyond a single best test among unbiased tests by trying alternative methods. The issue will then be one of practicality: The importance of using an unbiased test that is not very powerful must be weighed against the power superiority, in a large subset of the alternative parameter space, of a biased test. 4. CONCLUSION A binomial approximation theorem for dependent indicators using Stein's method and coupling is proved. The approximating binomial distribution B(n � ,p � ) is chosen in such a way that its first moment is equal to that of W and its variance is asymptotically equal to that of W as ntends to infinity where W is the sum of independent indicators and pis bounded away from 1. Three examples, one of which concerns two different approximations for the hypergeometric distribution, are given to illustrate applications of the theorem obtained.    Upper and lower bounds are given for the total variation distance between the distribution of a sum S of n independent, non-identically distributed 0-1 random variables and the binomial distribution (n, p) having the same expectation as S. The proof uses the Stein--Chen technique. Equivalence of the total variation and the Kolmogorov distance is established, and an application to sampling with and without replacement is presented.  where A = P1 + P2 + * .. + Pn Naturally, this inequality contains the classical Poisson limit law (Just set pi = A n and note that the right side simplifies to 2A2 n), but it also achieves a great deal more. In particular, Le Cam's inequality identifies the sum of the squares of the pi as a quantity governing the quality of the Poisson approximation. Le Cam's inequality also seems to be one of those facts that repeatedly calls to be proved-and improved. Almost before the ink was dry on Le Cam's 1960 paper, an elementary proof was given by Hodges and Le Cam [18]. This proof was followed by numerous generalizations and refinements including contributions by Kerstan [19], Franken [15], Vervatt [30], Galambos [17], Freedman [16], Serfling [24], and Chen [11, 12]. In fact, for raw simplicity it is hard to find a better proof of Le Cam's inequality than that given in the survey of Serfling [25]. One purpose of this note is to provide a proof of Le Cam's inequality using some basic facts from matrix analysis. This proof is simple, but simplicity is not its raison d'etre. It also serves as a concrete introduction to the semi-group method for approximation of probability distributions. This method was used in Le Cam [20], and it has been used again most recently by Deheuvels and Pfeifer [13] to provide impressively precise results. The semi-group method is elegant and powerful, but it faces tough competition, especially from the coupling method and the Chen-Stein method. The literature of these methods is reviewed, and it is shown how they also lead to proofs of Le Cam's inequality.