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

Research output: Contribution to journalArticle

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) 92-100 9 Computational Statistics and Data Analysis 122 https://doi.org/10.1016/j.csda.2018.01.007 Published - Jun 1 2018

Fingerprint

Binomial distribution
Poisson distribution
Distribution functions
Distribution Function
Convolution
Computing
Random variables
Trees (mathematics)
Bernoulli Random Variables
Sums of Random Variables
Calculate
Fourier transforms
Image processing
Identically distributed
Image Processing
Fourier transform
Demonstrate

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

In: Computational Statistics and Data Analysis, Vol. 122, 01.06.2018, p. 92-100.

Research output: Contribution to journalArticle

@article{15c4cbf2329e497ebd3891c741948447,
title = "A simple and fast method for computing the Poisson binomial distribution function",
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.",
keywords = "Convolution, Fourier transform, Independent Bernoulli sum, Poisson binomial",
author = "William Biscarri and Zhao, {Sihai Dave} and Brunner, {Robert J}",
year = "2018",
month = "6",
day = "1",
doi = "10.1016/j.csda.2018.01.007",
language = "English (US)",
volume = "122",
pages = "92--100",
journal = "Computational Statistics and Data Analysis",
issn = "0167-9473",
publisher = "Elsevier",

}

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 -