On the algebraic numbers computable by some generalized Ehrenfest urns
Marie Albenque, Lucas Gerin
Abstract
This article deals with some stochastic population protocols,
motivated by theoretical aspects of distributed computing. We modelize
the problem by a large urn of black and white balls from which at
every time unit a fixed number of balls are drawn and their colors is
changed according to the number of black balls among them.The limiting
behaviour of the composition of the urn when both the time and the
number of balls tend to infinity is investigated and the proportion of
black balls is shown to converge to an algebraic number. We prove also
that, surprisingly enough, not every algebraic number can be
``computed'' this way.
Full Text: PDF PostScript