On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917616454467584 |
|---|---|
| author | Cicirello, Vincent A. |
| author_facet | Cicirello, Vincent A. |
| contents | The BTPE algorithm (Binomial, Triangle, Parallelogram, Exponential) of Kachitvichyanukul and Schmeiser is one of the faster and more widely utilized algorithms for generating binomial random variates. Cicirello's open source Java library, $ρμ$, includes an implementation of BTPE as well as a variety of other random number related utilities. In this report, I explore the average case runtime of the BTPE algorithm when generating random values from binomial distribution $B(n,p)$. Beginning with Kachitvichyanukul and Schmeiser's formula for the expected number of acceptance-rejection sampling iterations, I analyze the limit behavior as $n$ approaches infinity, and show that the average runtime of BTPE converges to a constant. I instrument the open source Java implementation from the $ρμ$ library to experimentally validate the analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11018 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm Cicirello, Vincent A. Data Structures and Algorithms Mathematical Software 68Q25, 68Q87, 68W40, 60-04 F.2.1; G.3; G.4; I.1.2 The BTPE algorithm (Binomial, Triangle, Parallelogram, Exponential) of Kachitvichyanukul and Schmeiser is one of the faster and more widely utilized algorithms for generating binomial random variates. Cicirello's open source Java library, $ρμ$, includes an implementation of BTPE as well as a variety of other random number related utilities. In this report, I explore the average case runtime of the BTPE algorithm when generating random values from binomial distribution $B(n,p)$. Beginning with Kachitvichyanukul and Schmeiser's formula for the expected number of acceptance-rejection sampling iterations, I analyze the limit behavior as $n$ approaches infinity, and show that the average runtime of BTPE converges to a constant. I instrument the open source Java implementation from the $ρμ$ library to experimentally validate the analysis. |
| title | On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm |
| topic | Data Structures and Algorithms Mathematical Software 68Q25, 68Q87, 68W40, 60-04 F.2.1; G.3; G.4; I.1.2 |
| url | https://arxiv.org/abs/2403.11018 |