Bart Jacobs - Drawing with Distance

lmcs:13680 - Logical Methods in Computer Science, April 30, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:11)2025
Drawing with DistanceArticle

Authors: Bart Jacobs

    Drawing (a multiset of) coloured balls from an urn is one of the most basic models in discrete probability theory. Three modes of drawing are commonly distinguished: multinomial (draw-replace), hypergeometric (draw-delete), and Polya (draw-add). These drawing operations are represented as maps from urns to distributions over multisets of draws. The set of urns is a metric space via the Kantorovich distance. The set of distributions over draws is also a metric space, using Kantorovich-over-Kantorovich. It is shown that these three draw operations are all isometries, that is, they exactly preserve the Kantorovich distances. Further, drawing is studied in the limit, both for large urns and for large draws. First it is shown that, as the urn size increases, the Kantorovich distances go to zero between hypergeometric and multinomial draws, and also between Pólya and multinomial draws. Second, it is shown that, as the drawsize increases, the Kantorovich distance goes to zero (in probability) between an urn and (normalised) multinomial draws from the urn. These results are known, but here, they are formulated in a novel metric manner as limits of Kantorovich distances. We call these two limit results the law of large urns and the law of large draws.


    Volume: Volume 21, Issue 2
    Published on: April 30, 2025
    Accepted on: February 12, 2025
    Submitted on: May 29, 2024
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Probability

    Consultation statistics

    This page has been seen 263 times.
    This article's PDF has been downloaded 126 times.