Overdrawing Urns using Categories of Signed Probabilities
Bart Jacobs Dario Stein
A basic experiment in probability theory is drawing without replacement from
an urn filled with multiple balls of different colours. Clearly, it is
physically impossible to overdraw, that is, to draw more balls from the urn
than it contains. This paper demonstrates that overdrawing does make sense
mathematically, once we allow signed distributions with negative probabilities.
A new (conservative) extension of the familiar hypergeometric
('draw-and-delete') distribution is introduced that allows draws of arbitrary
sizes, including overdraws. The underlying theory makes use of the dual basis
functions of the Bernstein polynomials, which play a prominent role in computer
graphics. Negative probabilities are treated systematically in the framework of
categorical probability and the central role of datastructures such as
multisets and monads is emphasised.