Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-27T03:03:29.490Z Has data issue: false hasContentIssue false
  • English
  • Français

A Binomial Splitting Process in Connection with Corner Parking Problems

Part of: Algorithms - Computer Science Limit theorems Combinatorial probability

Published online by Cambridge University Press:  30 January 2018

Michael Fuchs ,
Hsien-Kuei Hwang ,
Yoshiaki Itoh  and
Hosam H. Mahmoud
Michael Fuchs*
Affiliation:
National Chiao Tung University
Hsien-Kuei Hwang*
Affiliation:
Academia Sinica
Yoshiaki Itoh*
Affiliation:
Institute of Statistical Mathematics
Hosam H. Mahmoud*
Affiliation:
The George Washington University
*
∗ Postal address: Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300, Taiwan. Email address: [email protected]
∗∗ Postal address: Institute of Statistical Science and Institute of Information Science, Academia Sinica, Taipei, 115, Taiwan.
∗∗∗ Postal address: Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo, 190-8562, Japan.
∗∗∗∗ Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper studies a special type of binomial splitting process. Such a process can be used to model a high dimensional corner parking problem as well as determining the depth of random PATRICIA (practical algorithm to retrieve information coded in alphanumeric) tries, which are a special class of digital tree data structures. The latter also has natural interpretations in terms of distinct values in independent and identically distributed geometric random variables and the occupancy problem in urn models. The corresponding distribution is marked by a logarithmic mean and a bounded variance, which is oscillating, if the binomial parameter p is not equal to ½, and asymptotic to one in the unbiased case. Also, the limiting distribution does not exist as a result of the periodic fluctuations.

Keywords

Binomial distributionparking problemperiodic fluctuationasymptotic approximationdigital treede-Poissonization

MSC classification

Primary: 60C05: Combinatorial probability 68W40: Analysis of algorithms
Secondary: 60F05: Central limit and other weak theorems
Type
Research Article
Information
Journal of Applied Probability , Volume 51 , Issue 4 , December 2014 , pp. 971 - 989
Copyright
© Applied Probability Trust 

References

Archibald, M., Knopfmacher, A. and Prodinger, H. (2006). The number of distinct values in a geometrically distributed sample. Europ. J. Combinatorics 27, 1059–1081.CrossRefGoogle Scholar
Evans, J. W. (1993). Random and cooperative sequential adsorption. Rev. Modern Phys. 65, 1281–1330.CrossRefGoogle Scholar
Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press.CrossRefGoogle Scholar
Flajolet, P., Gourdon, X. and Dumas, P. (1995). Mellin transforms and asymptotics: harmonic sums. Theoret. Comput. Sci. 144, 3–58.CrossRefGoogle Scholar
Fuchs, M., Hwang, H.-K. and Zacharovas, V. (2014). An analytic approach to the asymptotic variance of trie statistics and related structures. Theoret. Comput. Sci. 527, 1–36.CrossRefGoogle Scholar
Hayman, W. K. (1956). A generalisation of Stirling's formula. J. Reine Angew. Math. 196, 67–95.CrossRefGoogle Scholar
Hwang, H.-K. and Janson, S. (2008). Local limit theorems for finite and infinite urn models. Ann. Prob. 36, 992–1022.CrossRefGoogle Scholar
Hwang, H.-K., Fuchs, M. and Zacharovas, V. (2010). Asymptotic variance of random symmetric digital search trees. Discrete Math. Theoret. Comput. Sci. 12, 103–165.Google Scholar
Itoh, Y. and Solomon, H. (1986). Random sequential coding by Hamming distance. J. Appl. Prob. 23, 688–695.CrossRefGoogle Scholar
Itoh, Y. and Ueda, S. (1983). On packing density by a discrete random sequential packing of cubes in a space of m dimension. Proc. Inst. Statist. Math. 31, 65–69 (in Japanese).Google Scholar
Jacquet, P. and Szpankowski, W. (1998). Analytical de-Poissonization and its applications. Theoret. Comput. Sci. 201, 1–62.CrossRefGoogle Scholar
Janson, S. and Szpankowski, W. (1997). Analysis of an asymmetric leader election algorithm. Electron. J. Combinatorics 4, Research Paper 17.CrossRefGoogle Scholar
Janson, S., Lavault, C. and Louchard, G. (2008). Convergence of some leader election algorithms. Discrete Math. Theoret. Comput. Sci. 10, 171–196.Google Scholar
Kalpathy, R. and Mahmoud, H. (2014). Perpetuities in fair leader election algorithms. Adv. Appl. Prob. 46 203–216.CrossRefGoogle Scholar
Kirschenhofer, P. and Prodinger, H. (1987). Asymptotische Untersuchungen über charakteristische Parameter von Suchbäumen. Zahlentheoretische Analysis II, Lecture Notes in Math., 1262, 93–107, Springer, Berlin.Google Scholar
Kirschenhofer, P., Prodinger, H. and Szpankowski, W. (1996). Analysis of a splitting process arising in probabilistic counting and other related algorithms. Random Structures Algorithms 9, 379–401.3.0.CO;2-U>CrossRefGoogle Scholar
Mahmoud, H. M. (1992). Evolution of Random Search Trees. John Wiley, New York.Google Scholar
Olver, F. W. J. (1974). Asymptotics and Special Functions. Academic Press, New York.Google Scholar
Pittel, B. (1986). Paths in a random digital tree: limiting distributions. Adv. Appl. Prob. 18, 139–155. (Correction: 24 (1992), 759.)CrossRefGoogle Scholar
Prodinger, H. (2004). Periodic oscillations in the analysis of algorithms and their cancellations. J. Iranian Statist. Soc. 3, 251–270.Google Scholar
Rais, B., Jacquet, P. and Szpankowski, W. (1993). Limiting distribution for the depth in PATRICIA tries. SIAM J. Discrete Math. 6, 197–213.CrossRefGoogle Scholar
Dutour Sikirić, M. and Itoh, Y. (2011). Random Sequential Packing of Cubes. World Scientific, Hackensack, NJ.CrossRefGoogle Scholar