Systematic Alias Sampling: an efficient and low-variance way to sample from a discrete distribution
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908563758120960 |
|---|---|
| author | Vallivaara, Ilari Poikselkä, Katja Rikula, Pauli Röning, Juha |
| author_facet | Vallivaara, Ilari Poikselkä, Katja Rikula, Pauli Röning, Juha |
| contents | In this paper we combine the Alias method with the concept of systematic sampling, a method commonly used in particle filters for efficient low-variance resampling. The proposed method allows very fast sampling from a discrete distribution: drawing k samples is up to an order of magnitude faster than binary search from the cumulative distribution function (cdf) or inversion methods used in many libraries. The produced empirical distribution function is evaluated using a modified Cramér-Von Mises goodness-of-fit statistic, showing that the method compares very favourably to multinomial sampling. As continuous distributions can often be approximated with discrete ones, the proposed method can be used as a very general way to efficiently produce random samples for particle filter proposal distributions, e.g. for motion models in robotics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24089 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Systematic Alias Sampling: an efficient and low-variance way to sample from a discrete distribution Vallivaara, Ilari Poikselkä, Katja Rikula, Pauli Röning, Juha Data Structures and Algorithms Mathematical Software Robotics F.2.2; G.3; G.4; I.2.9; I.6.6 In this paper we combine the Alias method with the concept of systematic sampling, a method commonly used in particle filters for efficient low-variance resampling. The proposed method allows very fast sampling from a discrete distribution: drawing k samples is up to an order of magnitude faster than binary search from the cumulative distribution function (cdf) or inversion methods used in many libraries. The produced empirical distribution function is evaluated using a modified Cramér-Von Mises goodness-of-fit statistic, showing that the method compares very favourably to multinomial sampling. As continuous distributions can often be approximated with discrete ones, the proposed method can be used as a very general way to efficiently produce random samples for particle filter proposal distributions, e.g. for motion models in robotics. |
| title | Systematic Alias Sampling: an efficient and low-variance way to sample from a discrete distribution |
| topic | Data Structures and Algorithms Mathematical Software Robotics F.2.2; G.3; G.4; I.2.9; I.6.6 |
| url | https://arxiv.org/abs/2509.24089 |