On the Dynamics of Systems of Urns
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 for...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2143/pdf |
| _version_ | 1797270054343016448 |
|---|---|
| author | Marek Klonowski Jacek Cichoń Rafał Kapelko |
| author_facet | Marek Klonowski Jacek Cichoń Rafał Kapelko |
| author_sort | Marek Klonowski |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:10Z |
| format | Article |
| id | doaj.art-1382aef5c21d4631af106f2266f39386 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:10Z |
| publishDate | 2015-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1382aef5c21d4631af106f2266f393862024-03-07T15:28:22ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-10-01Vol. 17 no.2Analysis of Algorithms10.46298/dmtcs.21432143On the Dynamics of Systems of UrnsMarek Klonowski0Jacek Cichoń1Rafał Kapelko2https://orcid.org/0000-0001-5847-8259Institute of Mathematics and Computer Science [Wroclaw]Institute of Mathematics and Computer Science [Wroclaw]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.https://dmtcs.episciences.org/2143/pdfcoupon collector problemmix networksurn and balls model[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Marek Klonowski Jacek Cichoń Rafał Kapelko On the Dynamics of Systems of Urns Discrete Mathematics & Theoretical Computer Science coupon collector problem mix networks urn and balls model [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On the Dynamics of Systems of Urns |
| title_full | On the Dynamics of Systems of Urns |
| title_fullStr | On the Dynamics of Systems of Urns |
| title_full_unstemmed | On the Dynamics of Systems of Urns |
| title_short | On the Dynamics of Systems of Urns |
| title_sort | on the dynamics of systems of urns |
| topic | coupon collector problem mix networks urn and balls model [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2143/pdf |
| work_keys_str_mv | AT marekklonowski onthedynamicsofsystemsofurns AT jacekcichon onthedynamicsofsystemsofurns AT rafałkapelko onthedynamicsofsystemsofurns |