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. 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.
    3. 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.

    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. Deligiannis, Michalis & Liberopoulos, George, 2023. "Dynamic ordering and buyer selection policies when service affects future demand," Omega, Elsevier, vol. 118(C).
    5. 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.
    6. 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.
    7. Marie Ernst & Yvik Swan, 2022. "Distances Between Distributions Via Stein’s Method," Journal of Theoretical Probability, Springer, vol. 35(2), pages 949-987, June.
    8. 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.
    9. 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.
    10. 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).
    11. 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.
    12. Zhang, Yazhe, 2016. "Binomial approximation for sum of indicators with dependent neighborhoods," Statistics & Probability Letters, Elsevier, vol. 119(C), pages 146-154.
    13. Stanislao Gualdi & Giulio Cimini & Kevin Primicerio & Riccardo Di Clemente & Damien Challet, 2016. "Statistically validated network of portfolio overlaps and systemic risk," Papers 1603.05914, arXiv.org, revised Sep 2016.
    14. Samuel Davis & Nasser Fard, 2020. "Theoretical bounds and approximation of the probability mass function of future hospital bed demand," Health Care Management Science, Springer, vol. 23(1), pages 20-33, March.
    15. Alessio Farcomeni & Monia Ranalli & Sara Viviani, 2021. "Dimension reduction for longitudinal multivariate data by optimizing class separation of projected latent Markov models," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(2), pages 462-480, June.
    16. Peizhou Liao & Hao Wu & Tianwei Yu, 2017. "ROC Curve Analysis in the Presence of Imperfect Reference Standards," Statistics in Biosciences, Springer;International Chinese Statistical Association, vol. 9(1), pages 91-104, June.
    17. Musa Çağlar & Sinan Gürel, 2017. "Public R&D project portfolio selection problem with cancellations," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(3), pages 659-687, July.
    18. Li Zhang & Ying-Ying Zhang, 2022. "The Bayesian Posterior and Marginal Densities of the Hierarchical Gamma–Gamma, Gamma–Inverse Gamma, Inverse Gamma–Gamma, and Inverse Gamma–Inverse Gamma Models with Conjugate Priors," Mathematics, MDPI, vol. 10(21), pages 1-27, October.
    19. Taro Ohdoko & Satoru Komatsu, 2023. "Integrating a Pareto-Distributed Scale into the Mixed Logit Model: A Mathematical Concept," Mathematics, MDPI, vol. 11(23), pages 1-22, November.
    20. Greene, Evan & Wellner, Jon A., 2016. "Finite sampling inequalities: An application to two-sample Kolmogorov–Smirnov statistics," Stochastic Processes and their Applications, Elsevier, vol. 126(12), pages 3701-3715.

    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.