IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v122y2018icp92-100.html

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

    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. 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.
    2. Cho, Youngjin & Hong, Yili & Du, Pang, 2025. "An accurate computational approach for partial likelihood using Poisson-binomial distributions," Computational Statistics & Data Analysis, Elsevier, vol. 208(C).
    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. Volker Nocke & Roland Strausz, 2023. "Collective Brand Reputation," Journal of Political Economy, University of Chicago Press, vol. 131(1), pages 1-58.
    5. 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.
    6. Zhengzhi Lin & Yueyao Wang & Yili Hong, 2023. "The computing of the Poisson multinomial distribution and applications in ecological inference and machine learning," Computational Statistics, Springer, vol. 38(4), pages 1851-1877, December.

    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 Chandrasekhar & Robert Townsend & Juan Pablo Pablo Xandri, 2019. "Financial Centrality and the Value of Key Players," Working Papers 2019-26, Princeton University. Economics Department..
    2. Arun G. Chandrasekhar & Robert Townsend & Juan Pablo Xandri, 2018. "Financial Centrality and Liquidity Provision," NBER Working Papers 24406, National Bureau of Economic Research, Inc.
    3. 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.
    4. Karlsson, Niklas & Lunander, Anders, 2025. "Cutoff Point in Multiple Choice Examinations using Negative Marking or Number of Correct Scoring - An Analysis of Statistical Power," Working Papers 2025:9, Örebro University, School of Business.
    5. Bos, Hayo & Baas, Stef & Boucherie, Richard J. & Hans, Erwin W. & Leeftink, Gréanne, 2025. "Bed census prediction combining expert opinion and patient statistics," Omega, Elsevier, vol. 133(C).
    6. Vydas Čekanavičius & Bero Roos, 2006. "Compound Binomial Approximations," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 58(1), pages 187-210, March.
    7. 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.
    8. Musa Çağlar & Sinan Gürel, 2024. "Public R &D project portfolio selection under expenditure uncertainty," Annals of Operations Research, Springer, vol. 341(1), pages 375-399, October.
    9. Deligiannis, Michalis & Liberopoulos, George, 2023. "Dynamic ordering and buyer selection policies when service affects future demand," Omega, Elsevier, vol. 118(C).
    10. 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.
    11. López, Fernando & Matilla-García, Mariano & Mur, Jesús & Marín, Manuel Ruiz, 2010. "A non-parametric spatial independence test using symbolic entropy," Regional Science and Urban Economics, Elsevier, vol. 40(2-3), pages 106-115, May.
    12. 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.
    13. Marie Ernst & Yvik Swan, 2022. "Distances Between Distributions Via Stein’s Method," Journal of Theoretical Probability, Springer, vol. 35(2), pages 949-987, June.
    14. 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.
    15. Zhengzhi Lin & Yueyao Wang & Yili Hong, 2023. "The computing of the Poisson multinomial distribution and applications in ecological inference and machine learning," Computational Statistics, Springer, vol. 38(4), pages 1851-1877, December.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.