Boys-and-girls Birthdays and Hadamard Products

Issue title: Lattice Path Combinatorics and Applications

Article type: Research Article

Authors: Bodini, Olivier | Gardy, Danièle | Roussel, Olivier

Affiliations: LIPN, Paris-XIII and UMR 7030, France; ANR project MAGNUM, [email protected] | PRiSM, Université Versailles St Quentin, CNRS UMR 8144, France, [email protected] | LIP6, Paris-VI and UMR 7606, France; ANR project MAGNUM, [email protected]

Note: [] Address for correspondence: LIPN, Paris-XIII and UMR 7030 (France)

Abstract: Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient and easy-to-write algorithms for the random generation of combinatorial objects. This paper proposes to extend Boltzmann generators to a new field of applications by uniformly sampling a Hadamard product. Under an abstract real-arithmetic computation model, our algorithm achieves approximate-size sampling in expected time ${\cal O}$(n${\sqrt n}$) or ${\cal O}$(nσ) depending on the objects considered, with σ the standard deviation of smallest order for the component object sizes. This makes it possible to generate random objects of large size on a standard computer. The analysis heavily relies on a variant of the so-called birthday paradox, which can be modelled as an occupancy urn problem.

DOI: 10.3233/FI-2012-689

Journal: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 85-101, 2012