Dirichlet's principle revisited : an inverse Dirichlet's principle definition and its bound estimation improvement using stochastic combinatorics

• Autorzy: Štepánek Lubomír , Habarta Filip , Malá Ivana , Marek Luboš

Identyfikatory

DOI

10.15439/2022F221

• Konferencja: 17th Conference on Computer Science and Intelligence Systems
• Języki publikacji: EN

Abstrakty

EN

Dirichlet's principle, also known as a pigeonhole principle, claims that if n item are put into m containers, with n > m, then there is a container that contains more than one item. In this work, we focus rather on an inverse Dirichlet's principle (by switching items and containers), which is as follows: considering n items put in m containers, when n < m, then there is at least one container with no item inside. Furthermore, we refine Dirichlet's principle using discrete combinatorics within a probabilistic framework. Applying stochastic fashion on the principle, we derive the number of items n may be even greater than or equal to m, still very likely having one container without an item. The inverse definition of the problem rather than the original one may have some practical applications, particularly considering derived effective upper bound estimates for the items number, as demonstrated using some applied mini-studies.

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 32
• Strony: 113--116
• Opis fizyczny: Bibliogr. 5 poz., rys., tab., wykr.

Twórcy

autor

Štepánek Lubomír

• Department of Statistics and Probability Faculty of Informatics and Statistics Prague University of Economics and Business nám. W. Churchilla 4, 130 67 Prague, Czech Republic

autor

Habarta Filip

• Department of Statistics and Probability Faculty of Informatics and Statistics Prague University of Economics and Business nám. W. Churchilla 4, 130 67 Prague, Czech Republic

autor

Malá Ivana

• Department of Statistics and Probability Faculty of Informatics and Statistics Prague University of Economics and Business nám. W. Churchilla 4, 130 67 Prague, Czech Republic

autor

Marek Luboš

• Department of Statistics and Probability Faculty of Informatics and Statistics Prague University of Economics and Business nám. W. Churchilla 4, 130 67 Prague, Czech Republic

Bibliografia

• 1. Lynn Loomis and Shlomo Sternberg. “Potential theory in E “. In: Advanced Calculus. World Scientific, Mar. 2014, pp. 474-508. http://dx.doi.org/10.1142/9789814583947_0013.
• 2. Giridhar D. Mandyam, Nasir U. Ahmed, and Neeraj Magotra. “DCT-based scheme for lossless image compression”. In: SPIE Proceedings. SPIE, Apr. 1995. http://dx.doi.org/10.1117/12.206386.
• 3. Yakir Aharonov, Fabrizio Colombo, Sandu Popescu, et al. “Quantum violation of the pigeonhole principle and the nature of quantum correlations”. In: Proceedings of the National Academy of Sciences 113.3 (Jan. 2016), pp. 532-535. http://dx.doi.org/10.1073/pnas.1522411112.
• 4. Benoit Rittaud and Albrecht Heeffer. “The Pigeonhole Principle, Two Centuries Before Dirichlet”. In: The Mathematical Intelligencer 36.2 (Aug. 2013), pp. 27-29. http://dx.doi.org/10.1007/s00283-013-9389-1.
• 5. Mario Cortina Borja and John Haigh. “The birthday problem”. In: Significance 4.3 (Aug. 2007), pp. 124-127. http://dx.doi.org/10.1111/j.1740-9713.2007.00246.x.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).