Marek Klonowski ; Jacek Cichoń ; Rafał Kapelko - On the Dynamics of Systems of Urns

dmtcs:2143 - Discrete Mathematics & Theoretical Computer Science, October 16, 2015, Vol. 17 no.2 -
On the Dynamics of Systems of UrnsArticle

Authors: Marek Klonowski 1; Jacek Cichoń 1; Rafał Kapelko ORCID1

  • 1 Institute of Mathematics and Computer Science [Wroclaw]

In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of formulas for the expected numbers of black balls in a given urn and we analyze some special cases (parallel and serial configurations). We are mainly interested in a counterpart of the Coupon Collector Problem for the model considered. The primary motivation for our research is the formal analysis of the mix networks (introduced by D. Chaum) and its immunity to so-called flooding (blending) attacks.

Volume: Vol. 17 no.2
Section: Analysis of Algorithms
Published on: October 16, 2015
Submitted on: September 5, 2014
Keywords: Coupon Collector Problem,mix networks,urn and balls model,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 427 times.
This article's PDF has been downloaded 436 times.