Efficient computation for the Poisson binomial distribution

Direct construction of the probability distribution function for a Poisson binomial random variable, where success probabilities may vary from trial to trial, requires on the order of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$2^{n}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mn>2</mn> <mi>n</mi> </msup> </math> </EquationSource> </InlineEquation> calculations, and is computationally infeasible for all but modest sized problems. An approach offered by Thomas and Taub (J Stat Comput Simul 14:125–131 <CitationRef CitationID="CR6">1982</CitationRef>) reduces this effort to approximately <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$n^{2}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>n</mi> <mn>2</mn> </msup> </math> </EquationSource> </InlineEquation>, which, while certainly an improvement, can still be significant for large values of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$n$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>n</mi> </math> </EquationSource> </InlineEquation>. We offer modifications to the method of Thomas and Taub that greatly reduce the computations while still delivering highly accurate results. Copyright Springer-Verlag Berlin Heidelberg 2014