Abstract
We consider two interesting generalizations of learning Poisson Binomial Distributions (PBDs), namely learning all powers of a PBD and learning a Graph Binomial Distribution. A PBD is the distribution of X = X_1+...+X_n, where X_1, ..., X_n are independent Bernoulli trials with Exp[X_i] = p_i. The k-th power of X is X^{(k)} = X^{(k)}_1+...+X^{(k)}_n, where X^{(k)}_1, ..., X^{(k)}_n are independent Bernoulli trials with Exp[X^{(k)}_i] = p^k_i. A learning algorithm can take samples from any power. It should compute a sequence of distributions Y^{(1)}, Y^{(2)}, ... such that with probability at least 1-\delta, each Y^{(k)} is within total variation distance at most \eps to X^{(k)}. The question is to which extent a learning algorithm can exploit the special structure of powers and succeed in learning all powers of X using a number of samples comparable to the number of samples required for learning X alone. A Graph Binomial Distribution (GBD) is determined by a graph G(V, E). It is the distribution of Z = \sum_{\{ u, v \} \in E} Z_u Z_v, where Z_v s are independent Bernoulli trials. A learning algorithm can take samples from Z and should compute a distribution Q such that with probability at least 1-\delta, Q is within total variation distance at most \epsilon to Z. The question is to which extent (and for which classes of graphs) the dependencies among edge terms make learning Z more difficult than learning a standard PBD. We present upper and lower bounds on the number of samples required for learning (i) all powers of a PBD and (ii) a GBD. We also provide some insights on the structure of GBDs for simple classes of graphs.