Discretization of the parking problem
DOI:
https://doi.org/10.21638/spbu01.2020.408Abstract
The present work consider a natural discretization of R´enyi’s so-called “parking problem”. Let l, n, i be integers satisfying l ≥ 2, n ≥ 0 and 0 ≤ i ≤ n − l. We place an open interval (i, i + l) in the segment [0, n] with i being a random variable taking values 0, 1, 2, . . . , n − l with equal probability for all n ≥ l. If n < l we say that the interval does not fit. After placing the first interval two free segments [0, i] and [i + l, n] are formed and independently filled with the intervals of length l according to the same rule, etc. At the end of the filling process the distance between any two adjacent unit intervals is at most l−1. Let ξn,l denote the cumulative length of the intervals placed. The asymptotics behavior of expectations of the aforementioned random sequence have already been studied. This contribution has an aim to continue this investigation and establish the behavior of variances of the same sequence.Keywords:
random filling, discrete “parking” problem, asymptotic behavior of moments
Downloads
Download data is not yet available.
References
Литература
1. R´enyi A. On a one-dimensional problem concerning space-filling // Publ. of the Math. Inst. of Hungarian Acad. of Sciences. 1958. Vol. 3. P. 109–127.
2. Dvoretzky A., Robbins H. On the “parking” problem // Publ. of the Math. Inst. of Hungarian Acad. of Sciences. 1964. Vol. 9. P. 209–226.
3. Ананьевский С. М., Крюков Н. А. Задача об эгоистичнойпарковке // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. 2018. Т. 5 (63). Вып. 4. С. 549–555. https://doi.org/10.21638/11701/spbu01.2018.402
4. Ананьевский С. М., Крюков Н. А. Об асимптотическойнормальности в одном обобщении задачи Реньи // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. 2019. Т. 6 (64). Вып. 3. С. 353–362. https://doi.org/10.21638/11701/spbu01.2019.301
5. Pinsky R. G. A One-Dimensional Probabilistic Packing Problem. In: Problems from the Discrete to the Continuous. Switzerland: Springer International Publishing. 2014. Chapter 3. P. 21–34.
6. Clay M. P., Simanyi N. J. R´enyi’s parking problem revisited // Stochastics and Dynamics. 2016. Vol. 16, no. 2. https://doi.org/10.1142/S0219493716600066
7. Geri L. The Page-R´enyi parking process // The Electronic Journal of Combinatorics. 2015. Vol. 22. Iss. 4. https://doi.org/10.37236/5150
8. Ананьевский С. М. Некоторые обобщения задачи о «парковке» // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. 2016. Т. 3 (61). Вып. 4. С. 525–532. https://doi.org/10.21638/11701/spbu01.2016.401
9. Ананьевский С. М. Задача парковки для отрезков различнойдлины // Записки научн. семинаров ПОМИ РАН. 1996. Т. 228. Вероятность и статистика. С. 16–23.
10. Iльєнко А. Б., Фатенко В. В. Узагальнення задачi Реньї про паркування // Науковi вiстi НТУУ «КПI»: мiжнароднийнауково-технiчнийжурнал. 2017. №4(114). С. 54–60.
References
1. R´enyi A., “On a one-dimensional problem concerning space-filling”, Publ. of the Math. Inst. Of Hungarian Acad. of Sciences 3, 109–127 (1958).
2. Dvoretzky A., Robbins H., “On the “parking” problem”, Publ. of the Math. Inst. of Hungarian Acad. of Sciences 9, 209–226 (1964).
3. Ananjevskii S. M., Kryukov N. A., “The problem of selfish parking”, Vestnik St. Petersburg University: Mathematics 51, iss. 4, 322–326 (2018). https://doi.org/10.21638/11701/spbu01.2018.402
4. Ananjevskii S. M., Kryukov N. A., “On asymptotic normality in one generalization of the R´enyi problem”, Vestnik of St. Petersburg University. Mathematics. Mechanics. Astronomy 6 (64), iss. 3, 353–362 (2019). https://doi.org/10.21638/11701/spbu01.2019.301 (In Russian)
5. Pinsky R. G., A One-Dimensional Probabilistic Packing Problem. In: Problems from the Discrete to the Continuous, Chapter 3, 21–34 (Springer International Publishing, Switzerland, 2014).
6. Clay M. P., Simanyi N. J., “R´enyi’s parking problem revisited”, Stochastics and Dynamics 16 (2) (2016). https://doi.org/10.1142/S0219493716600066
7. Geri L., “The Page-R´enyi parking process”, The Electronic Journal of Combinatorics 22 (4) (2015). https://doi.org/10.37236/5150
8. Ananjevskii S. M., “Generalizations of “Parking” Problem”, Vestnik St. Petersburg University. Mathematics 49, iss. 4, 299–304 (2016). https://doi.org/10.3103/S1063454116040026
9. Ananjevskii S. M., “The “parking” problem for segments of different length”, Journal of Mathematical Sciences 93, 259–264 (1999). https://doi.org/10.1007/BF02364808
10. Ilyenko A. B., Fatenko V. V., “Generalization of the R´enyi’s parking problem”, Scientific News NTUU «KPI»: international scientific and technical journal (4(114)), 54–60 (2017). (In Ukrainian)
Downloads
Published
2020-12-27
How to Cite
Kryukov N. А. (2020). Discretization of the parking problem. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 7(4), 662–677. https://doi.org/10.21638/spbu01.2020.408
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
