### Abstract

It is shown that the Poisson binomial distribution function can be efficiently calculated using simple convolution based methods. The Poisson binomial distribution describes how the sum of independent but not identically distributed Bernoulli random variables is distributed. Due to the intractability of the Poisson binomial distribution function, efficient methods for computing it have been of particular interest in past Statistical literature. First, it is demonstrated that simply and directly using the definition of the distribution function of a sum of random variables can calculate the Poisson binomial distribution function efficiently. A modified, tree structured Fourier transform convolution scheme is then presented, which provides even greater gains in efficiency. Both approaches are shown to outperform the current state of the art methods in terms of accuracy and speed. The methods are then evaluated on a real data image processing example in order to demonstrate the efficiency advantages of the proposed methods in practical cases. Finally, possible extensions for using convolution based methods to calculate other distribution functions are discussed.

Original language | English (US) |
---|---|

Pages (from-to) | 92-100 |

Number of pages | 9 |

Journal | Computational Statistics and Data Analysis |

Volume | 122 |

DOIs | |

State | Published - Jun 1 2018 |

### Fingerprint

### Keywords

- Convolution
- Fourier transform
- Independent Bernoulli sum
- Poisson binomial

### ASJC Scopus subject areas

- Statistics and Probability
- Computational Mathematics
- Computational Theory and Mathematics
- Applied Mathematics

### Cite this

**A simple and fast method for computing the Poisson binomial distribution function.** / Biscarri, William; Zhao, Sihai Dave; Brunner, Robert J.

Research output: Contribution to journal › Article

*Computational Statistics and Data Analysis*, vol. 122, pp. 92-100. https://doi.org/10.1016/j.csda.2018.01.007

}

TY - JOUR

T1 - A simple and fast method for computing the Poisson binomial distribution function

AU - Biscarri, William

AU - Zhao, Sihai Dave

AU - Brunner, Robert J

PY - 2018/6/1

Y1 - 2018/6/1

N2 - It is shown that the Poisson binomial distribution function can be efficiently calculated using simple convolution based methods. The Poisson binomial distribution describes how the sum of independent but not identically distributed Bernoulli random variables is distributed. Due to the intractability of the Poisson binomial distribution function, efficient methods for computing it have been of particular interest in past Statistical literature. First, it is demonstrated that simply and directly using the definition of the distribution function of a sum of random variables can calculate the Poisson binomial distribution function efficiently. A modified, tree structured Fourier transform convolution scheme is then presented, which provides even greater gains in efficiency. Both approaches are shown to outperform the current state of the art methods in terms of accuracy and speed. The methods are then evaluated on a real data image processing example in order to demonstrate the efficiency advantages of the proposed methods in practical cases. Finally, possible extensions for using convolution based methods to calculate other distribution functions are discussed.

AB - It is shown that the Poisson binomial distribution function can be efficiently calculated using simple convolution based methods. The Poisson binomial distribution describes how the sum of independent but not identically distributed Bernoulli random variables is distributed. Due to the intractability of the Poisson binomial distribution function, efficient methods for computing it have been of particular interest in past Statistical literature. First, it is demonstrated that simply and directly using the definition of the distribution function of a sum of random variables can calculate the Poisson binomial distribution function efficiently. A modified, tree structured Fourier transform convolution scheme is then presented, which provides even greater gains in efficiency. Both approaches are shown to outperform the current state of the art methods in terms of accuracy and speed. The methods are then evaluated on a real data image processing example in order to demonstrate the efficiency advantages of the proposed methods in practical cases. Finally, possible extensions for using convolution based methods to calculate other distribution functions are discussed.

KW - Convolution

KW - Fourier transform

KW - Independent Bernoulli sum

KW - Poisson binomial

UR - http://www.scopus.com/inward/record.url?scp=85041477750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041477750&partnerID=8YFLogxK

U2 - 10.1016/j.csda.2018.01.007

DO - 10.1016/j.csda.2018.01.007

M3 - Article

VL - 122

SP - 92

EP - 100

JO - Computational Statistics and Data Analysis

JF - Computational Statistics and Data Analysis

SN - 0167-9473

ER -