Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

On the algebraic numbers computable by some generalized Ehrenfest urns

Marie Albenque, Lucas Gerin


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