IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v122y2018icp92-100.html
   My bibliography  Save this article

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

Author

Listed:
  • Biscarri, William
  • Zhao, Sihai Dave
  • Brunner, Robert J.

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.

Suggested Citation

  • Biscarri, William & Zhao, Sihai Dave & Brunner, Robert J., 2018. "A simple and fast method for computing the Poisson binomial distribution function," Computational Statistics & Data Analysis, Elsevier, vol. 122(C), pages 92-100.
    • Handle: RePEc:eee:csdana:v:122:y:2018:i:c:p:92-100
    DOI: 10.1016/j.csda.2018.01.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947318300082
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2018.01.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ehm, Werner, 1991. "Binomial approximation to the Poisson binomial distribution," Statistics & Probability Letters, Elsevier, vol. 11(1), pages 7-16, January.
    2. Ruckdeschel, Peter & Kohl, Matthias, 2014. "General Purpose Convolution Algorithm in S4 Classes by Means of FFT," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 59(i04).
    3. anonymous, 1973. "Letters to the Editor," Management Science, INFORMS, vol. 20(2), pages 253-256, October.
    4. Stafford Beer & A. Charnes & W. W. Cooper & B. Mellon & R. E. D. Woolsey, 1973. "Letter to the Editor—Comments on a Letter by Woolsey," Operations Research, INFORMS, vol. 21(3), pages 858-861, June.
    5. Karen Sparck Jones, 1973. "Letters to the Editor," Journal of the American Society for Information Science, Association for Information Science & Technology, vol. 24(2), pages 166-167, March.
    6. Hong, Yili, 2013. "On computing the distribution function for the Poisson binomial distribution," Computational Statistics & Data Analysis, Elsevier, vol. 59(C), pages 41-51.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Volker Nocke & Roland Strausz, 2023. "Collective Brand Reputation," Journal of Political Economy, University of Chicago Press, vol. 131(1), pages 1-58.
    2. Damba Lkhagvasuren & Erdenebat Bataa, 2023. "Finite-State Markov Chains with Flexible Distributions," Computational Economics, Springer;Society for Computational Economics, vol. 61(2), pages 611-644, February.
    3. Xiaoyu Shen & Fang Fang & Chengguang Liu, 2024. "The Fourier Cosine Method for Discrete Probability Distributions," Papers 2410.04487, arXiv.org, revised Oct 2024.
    4. Richard A. Feinberg & Matthias von Davier, 2020. "Conditional Subscore Reporting Using Iterated Discrete Convolutions," Journal of Educational and Behavioral Statistics, , vol. 45(5), pages 515-533, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arun G. Chandrasekhar & Robert Townsend & Juan Pablo Xandri, 2018. "Financial Centrality and Liquidity Provision," NBER Working Papers 24406, National Bureau of Economic Research, Inc.
    2. Róbert Pethes & Levente Kovács, 2023. "An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution," Mathematics, MDPI, vol. 11(6), pages 1-24, March.
    3. Arun Chandrasekhar & Robert Townsend & Juan Pablo Pablo Xandri, 2019. "Financial Centrality and the Value of Key Players," Working Papers 2019-26, Princeton University. Economics Department..
    4. Mauricio Romero & Ã lvaro Riascos & Diego Jara, 2015. "On the Optimality of Answer-Copying Indices," Journal of Educational and Behavioral Statistics, , vol. 40(5), pages 435-453, October.
    5. Deligiannis, Michalis & Liberopoulos, George, 2023. "Dynamic ordering and buyer selection policies when service affects future demand," Omega, Elsevier, vol. 118(C).
    6. David M. Phillippo & Sofia Dias & A. E. Ades & Mark Belger & Alan Brnabic & Alexander Schacht & Daniel Saure & Zbigniew Kadziola & Nicky J. Welton, 2020. "Multilevel network meta‐regression for population‐adjusted treatment comparisons," Journal of the Royal Statistical Society Series A, Royal Statistical Society, vol. 183(3), pages 1189-1210, June.
    7. Neal, Zachary & Domagalski, Rachel & Yan, Xiaoqin, 2020. "Party Control as a Context for Homophily in Collaborations among US House Representatives, 1981 -- 2015," OSF Preprints qwdxs, Center for Open Science.
    8. Marie Ernst & Yvik Swan, 2022. "Distances Between Distributions Via Stein’s Method," Journal of Theoretical Probability, Springer, vol. 35(2), pages 949-987, June.
    9. Richard L. Warr & Cason J. Wight, 2020. "Error Bounds for Cumulative Distribution Functions of Convolutions via the Discrete Fourier Transform," Methodology and Computing in Applied Probability, Springer, vol. 22(3), pages 881-904, September.
    10. Van der Auweraer, Sarah & Boute, Robert, 2019. "Forecasting spare part demand using service maintenance information," International Journal of Production Economics, Elsevier, vol. 213(C), pages 138-149.
    11. Jenq-Tzong Shiau, 2021. "Analytical Water Shortage Probabilities and Distributions of Various Lead Times for a Water Supply Reservoir," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 35(11), pages 3809-3825, September.
    12. Piero Mazzarisi & Adele Ravagnani & Paola Deriu & Fabrizio Lillo & Francesca Medda & Antonio Russo, 2022. "A machine learning approach to support decision in insider trading detection," Papers 2212.05912, arXiv.org.
    13. Aihua Xia & Fuxi Zhang, 2009. "Polynomial Birth–Death Distribution Approximation in the Wasserstein Distance," Journal of Theoretical Probability, Springer, vol. 22(2), pages 294-310, June.
    14. Ton Waal & Jacco Daalmans, 2024. "Calibrated imputation for multivariate categorical data," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 108(3), pages 545-576, September.
    15. Mika J. Straka & Guido Caldarelli & Tiziano Squartini & Fabio Saracco, 2017. "From Ecology to Finance (and Back?): Recent Advancements in the Analysis of Bipartite Networks," Papers 1710.10143, arXiv.org.
    16. Jeff Alstott & Giorgio Triulzi & Bowen Yan & Jianxi Luo, 2017. "Mapping technology space by normalizing patent networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 110(1), pages 443-479, January.
    17. Van der Auweraer, Sarah & Zhu, Sha & Boute, Robert N., 2021. "The value of installed base information for spare part inventory control," International Journal of Production Economics, Elsevier, vol. 239(C).
    18. Valeriy A. Naumov & Yuliya V. Gaidamaka & Konstantin E. Samouylov, 2020. "Computing the Stationary Distribution of Queueing Systems with Random Resource Requirements via Fast Fourier Transform," Mathematics, MDPI, vol. 8(5), pages 1-9, May.
    19. Zhang, Yazhe, 2016. "Binomial approximation for sum of indicators with dependent neighborhoods," Statistics & Probability Letters, Elsevier, vol. 119(C), pages 146-154.
    20. María Belén Atiencia-Carrera & Fausto Sebastián Cabezas-Mera & Eduardo Tejera & António Machado, 2022. "Prevalence of biofilms in Candida spp. bloodstream infections: A meta-analysis," PLOS ONE, Public Library of Science, vol. 17(2), pages 1-23, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:122:y:2018:i:c:p:92-100. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.