ABSTRACT
Urn models play an important role to express various basic ideas in probability theory. Here we extend this urn model with tubes. An urn contains coloured balls, which can be drawn with probabilities proportional to the numbers of balls of each colour. For each colour a tube is assumed. These tubes have different sizes (lengths). The idea is that after drawing a ball from the urn it is dropped in the tube of the corresponding colour. We consider two associated probability distributions. The first-full distribution on colours gives for each colour the probability that the corresponding tube is full first, before any of the other tubes. The negative distribution on natural numbers captures for a number $k$ the probability that all tubes are full for the first time after $k$ draws.
This paper uses multisets to systematically describe these first-full and negative distributions in the urns and tubes setting, in fully multivariate form, for all three standard drawing modes (multinomial, hypergeometric, and Pólya).
► BibTeX data
► References
[1] C. Baier and J.-P. Katoen. Principles of Model Checking. MIT Press, Cambridge, MA, 2008.
[2] M. Barr and Ch. Wells. Toposes, Triples and Theories. Springer, Berlin, 1985. Revised and corrected version available from URL: www.tac.mta.ca/tac/reprints/articles/12/tr12.pdf.
http://www.tac.mta.ca/tac/reprints/articles/12/tr12.pdf
[3] A. Edwards. Pascal and the problem of points. Intern. Statistical Review, 50(3):259–266, 1982. doi:10.2307/1402496.
https://doi.org/10.2307/1402496
[4] M. Hayhoe, F. Alajaji, and B. Gharesifard. A pólya urn-based model for epidemics on networks. In American Control Conference, pages 358–363, 2017. doi:10.23919/ACC.2017.7962979.
https://doi.org/10.23919/ACC.2017.7962979
[5] B. Jacobs. Learning along a channel: the Expectation part of Expectation-Maximisation. In B. König, editor, Math. Found. of Programming Semantics, number 347 in Elect. Notes in Theor. Comp. Sci., pages 143–160. Elsevier, Amsterdam, 2019. doi:10.1016/j.entcs.2019.09.008.
https://doi.org/10.1016/j.entcs.2019.09.008
[6] B. Jacobs. The mathematics of changing one's mind, via Jeffrey's or via Pearl's update rule. Journ. of Artif. Intelligence Research, 65:783–806, 2019. doi:10.1613/jair.1.11349.
https://doi.org/10.1613/jair.1.11349
[7] B. Jacobs. From multisets over distributions to distributions over multisets. In Logic in Computer Science. IEEE, Computer Science Press, 2021. doi:10.1109/lics52264.2021.9470678.
https://doi.org/10.1109/lics52264.2021.9470678
[8] B. Jacobs. Multinomial and hypergeometric distributions in Markov categories. In A. Sokolova, editor, Math. Found. of Programming Semantics, number 351 in Elect. Proc. in Theor. Comp. Sci., pages 98–115, 2021. doi:10.4204/EPTCS.351.7.
https://doi.org/10.4204/EPTCS.351.7
[9] B. Jacobs. Multisets and distributions, in drawing and learning. In A. Palmigiano and M. Sadrzadeh, editors, Samson Abramsky on Logic and Structure in Computer Science and Beyond. Springer, 2022, to appear.
[10] B. Jacobs. Structured probabilistic reasoning. forthcoming book, see http://www.cs.ru.nl/B.Jacobs/PAPERS/ProbabilisticReasoning.pdf, 2023.
http://www.cs.ru.nl/B.Jacobs/PAPERS/ProbabilisticReasoning.pdf
[11] B. Jacobs and S. Staton. De Finetti's construction as a categorical limit. In D. Petrişan and J. Rot, editors, Coalgebraic Methods in Computer Science (CMCS 2020), number 12094 in Lect. Notes Comp. Sci., pages 90–111. Springer, Berlin, 2020. doi:10.1007/978-3-030-57201-3_6.
https://doi.org/10.1007/978-3-030-57201-3_6
[12] K. Janardan. A characterization of multinomial and negative multinomial distributions. Scand. Actuarial Journ., 1:58–62, 1974. doi:10.1080/03461238.1974.10408662.
https://doi.org/10.1080/03461238.1974.10408662
[13] N. Johnson, A. Kemp, and S. Kotz. Univariate Discrete Distributions. John Wiley & Sons, $3^{rd}}$ edition, 2005.
[14] N. Johnson and S. Kotz. Urn models and their application: An approach to modern discrete probability theory. John Wiley, 1977.
[15] N. Johnson, S. Kotz, and N. Balakrishnan. Discrete Multivariate Distributions. John Wiley & Sons, 1997.
[16] L. Kaelbling, M. Littman, and A. Moore. Reinforcement learning: A survey. Journ. of Artif. Intelligence Research, 4:237–285, 1996. doi:10.1613/jair.301.
https://doi.org/10.1613/jair.301
[17] P. Lau, T. Koo, and C. Wu. Spatial distribution of tourism activities: A Pólya urn process model of rank-size distribution. Journ. of Travel Research, 59(2):231–246, 2020. doi:10.1177/0047287519829258.
https://doi.org/10.1177/0047287519829258
[18] D. Ma. The problem of points. A Blog on Probability and Statistics, see https://probabilityandstats.wordpress.com/2016/11/06/the-problem-of-points/, Nov. 6 2016.
https://probabilityandstats.wordpress.com/2016/11/06/the-problem-of-points/
[19] H. Mahmoud. Pólya Urn Models. Chapman and Hall, 2008.
[20] G. Miller and S. Fridell. A forgotten discrete distribution? Reviving the negative hypergeometric model. The American Statistician, 61(4):347–350, 2007. doi:10.1198/000313007X245140.
https://doi.org/10.1198/000313007X245140
[21] J. Panaretos. A characterization of the negative multinomial distribution. In C. Taillie, G. Patil, and B. Baldessari, editors, Statistical Distributions in Scientific Work, volume 79 of Series C: Math. and Phys. Sciences. Springer, Dordrecht, 1981.
[22] H. Pishro-Nik. Introduction to probability, statistics, and random processes. Kappa Research LLC, 2014. Available at https://www.probabilitycourse.com.
https://www.probabilitycourse.com
[23] M. Puterman. Markov Decision Processes. Discrete Stochastic Dynamic Programming. John Wiley and Sons, New Jersey, 1994.
[24] S. Ross. A first course in probability. Pearson Education, $10^{th}}$ edition, 2018.
[25] E. Schuster and W. Sype. On the negative hypergeometric distribution. Int. Journ. of Math. Education in Sci. and Techn., 18(3):453–459, 1987. doi:10.1080/0020739870180316.
https://doi.org/10.1080/0020739870180316
[26] M. Sibuya, I. Yoshimura, and R. Shimizu. Negative multinomial distribution. Ann. Inst. Stat. Math., 6:409–426, 1964. doi:10.1007/BF02868583.
https://doi.org/10.1007/BF02868583
[27] R. Sutton and A. Barto. Reinforcement Learning. An Introduction. MIT Press, Cambridge, MA, $2^{nd}}$ edition, 2005.
Cited by
[1] Bart Jacobs, Lecture Notes in Computer Science 14574, 101 (2024) ISBN:978-3-031-57227-2.
[2] Bart Jacobs, Lecture Notes in Computer Science 13225, 176 (2022) ISBN:978-3-031-10735-1.
[3] Bart Jacobs, Lecture Notes in Computer Science 13923, 256 (2023) ISBN:978-3-031-39783-7.
[4] Bart Jacobs and Dario Stein, "Overdrawing Urns using Categories of Signed Probabilities", Electronic Proceedings in Theoretical Computer Science 397, 172 (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2024-04-27 20:11:07). The list may be incomplete as not all publishers provide suitable and complete citation data.
On SAO/NASA ADS no data on citing works was found (last attempt 2024-04-27 20:11:07).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.