DROPS

Document

DOI: 10.4230/LIPIcs.CALCO.2025.8

Drawing and Recolouring

Authors: Bart Jacobs and Márk Széles

Published in: LIPIcs, Volume 342, 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)

Abstract

Drawing a ball from an urn filled with balls of different colours is one of the basic models in probability theory. The probability of drawing a ball of a particular colour is determined by the proportion / fraction of balls of that colour. This paper introduces a new stochastic model for such urns: draw a ball, recolour (repaint) it, and put it back into the urn. One can distinguish four modes of drawing-and-recolouring, namely whether done proportionally or uniformly (both for drawing and recolouring). These modes can be reformulated in financial terms as redistribution of wealth or in biological terms as evolutionary drift. The resulting four operations form a coalgebra for the distribution monad, on the set of multisets of a fixed size. In fact they form a Markov chain and even a hidden Markov model, in combination with the frequentist learning map as emission channel. This paper identifies fixed points, capturing stable situations, for these four modes of drawing-and-recolouring.

Cite as

Bart Jacobs and Márk Széles. Drawing and Recolouring. In 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 342, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jacobs_et_al:LIPIcs.CALCO.2025.8,
  author =	{Jacobs, Bart and Sz\'{e}les, M\'{a}rk},
  title =	{{Drawing and Recolouring}},
  booktitle =	{11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-383-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{342},
  editor =	{C\^{i}rstea, Corina and Knapp, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2025.8},
  URN =		{urn:nbn:de:0030-drops-235674},
  doi =		{10.4230/LIPIcs.CALCO.2025.8},
  annote =	{Keywords: Markov-chain, Urn model, Multiset}
}

Search Results

Documents authored by Széles, Márk

Drawing and Recolouring

Abstract

Cite as

Thanks for your feedback!

Could not send message