Различные задачи случайного заполнения множеств
Оглавление:
1. Введение 3
2. Обобщение задачи Реньи о парковке 5
3. Задачи о дискретной парковке в классической постановке 9
4. Задачи о дискретной парковке в эгоистичной постановке 42
5. Размещение интервалов случайной длины 65
6. Приложение 70
Первая глава
В первой главе, которая является введением, описывается степень разработанности
темы диссертации и её актуальность. Также, формулируются цели работы,
методы, описывается её степень достоверности и апробация. Кроме того,
приводятся формулировки выносимых на защиту положений.
Вторая глава
Во второй главе рассматривается следующее обобщение задачи, приведённой
в работе [1] и описанной в первой главе. Пусть интервалы (t, t+1) размещаются
на отрезке [0, x] отличным от равномерного образом. Будем считать, что
распределения располагаемых интервалов не зависят от конкретного отрезка,
а только от его длины. В таком случае нам достаточно определить семейство
распределений
P = {Px }x>1 ,
где Px — некоторое распределение на отрезке [0, x−1]. Тогда интервал (t, t+1)
располагается на отрезке [0, x] таким образом, чтобы случайная величина t
имела распределение Px . Обозначим за ξP (x) общее количество размещённых
на изначальном отрезке [0, x] единичных интервалов.
Мы также предполагаем, что распределения Px имеют соответствующие
плотности px . В данной главе приведён следующий результат.
Теорема 2.1. Рассмотрим два множества случайных величин ξ1 (t) и ξ2 (t),
которые определены при неотрицательных t следующим образом:
ξ1 (t) = ξ2 (t) = 0,t<1
ξ1 (1) = ξ2 (1) = 1
ξ1 (t + 1) = 1 + ξ1 (η1 (t)) + ξ1 (t − η1 (t)),t>0
ξ2 (t + 1) = 1 + ξ2 (η2 (t)) + ξ2 (t − η2 (t)),t > 0,
где множества случайных величин η1 (t) и η2 (t) независимы и соответственно
имеют плотности p1,t (x) и p2,t (x), определённые на отрезке [0, t] и удовлетворяющие
следующему соотношению (свойство антисимметричности):
pi,t (u) + pi,t (t − u) = ,∀u ∈ [0, t],∀i = 1, 2.(3)
t
Тогда распределения случайных величин ξ1 (t) и ξ2 (t) совпадают для всех
положительных t.
Также, показаны два следствия из описанной выше теоремы, первое из
которых утверждает, что распределение случайных величин ξP (x) не зависит
от конкретного семейства P, а второе обобщает асимптотический результат,
полученный в работе [2] (Теорема 1.3) на множество случайных величин
ξP (x).
Следствие 1. Пусть P1 , P2 — два семейства мер, удовлетворяющих соотношению
(3). Тогда для любого x > 0 случайные величины ξP1 (x) и ξP2 (x) имеют
одинаковые распределения.
Следствие 2. Пусть P — семейство мер, удовлетворяющее соотношению
(3). Тогда последовательность случайных величин
ξP (x) − E {ξP (x)}
p
D {ξP (x)}
слабо сходится к стандартной нормальной случайной величине при x → ∞.
Третья глава.
В третьей главе рассматривается следующий дискретный аналог задачи
Реньи о парковке, описанный ранее в работе [3]. Пусть n, l — два натуральных
числа. Будем случайно помещать на отрезок [0, n] интервалы длины l таким
образом, чтобы начало и конец интервала были целыми числами. В случае
n < l такое невозможно, и процесс считается завершённым. Иначе поместим
интервал (t, t + l), где t — случайная величина, равномерно распределённая
на множестве {0, . . . , n − l}. Он разбивает изначальный отрезок на два: [0, t]
и [t + l, n], которые заполняются независимо по аналогичному правилу. Как
только процесс завершается, что означает, что все оставшиеся свободными
отрезки имеют длину меньше чем l, обозначим за ξn,l суммарную длину
расположенных интервалов.
В данной главе представлено следующее уточнение результата, полученного
в работе [3], описывающего поведение математических ожиданий случайных
величин ξn,l .
Теорема 2.2. Для описанных выше случайных величин ξn,l и любого T > 1
верно соотношение
E {ξn,l } = lλl n + l2 λl − l + o(T −n ),(n → +∞),(4)
где константа λl имеет вид
l−1
P1
Z1l−1
Pxi
−2i2i
λl = ei=1ei=1dx.(5)
Отдельно, для случая l = 2, приведено точное выражение для математических
ожиданий случайных величин ξn,2 .
Теорема 2.3. Для описанных выше случайных величин ξn,2 верно соотношение
n Γ(n + 1, −2) (−2)n+12 Γ(n + 1, −2)
E {ξn,2 } = n − 2−− 2.
en!n!en!
Также, получен аналогичный результат в отношении дисперсий случайных
величин ξn,l
Теорема 2.4. Для описанных выше случайных величин ξn,l верно соотношение
D{ξn,l } = K0 (n − l) + o(1).
Для константы K0 также было приведена точная формула. В дополнение,
приведённое выше соотношение для дисперсий было обобщено на все центральные
моменты случайных величин ξn,l следующим образом.
Теорема 2.5. Для определённой выше последовательности случайных величин
для любого натурального k при n → ∞ верно соотношение
E (ξn,l − E{ξn,l })k = n[ 2 ] (ck + o(1)),
k
где ck ∈ R, и при чётных k для констант ck верно равенство
k/2
ck = c2 (k − 1)!!.(6)
В заключении третьей главы была доказана следующая теорема, являющаяся
аналогом Теоремы 1.3 для случая дискретного расположения отрезков.
Теорема 2.6. Последовательность случайных величин
ξn,l − E {ξn,l }
p
D {ξn,l }
слабо сходится к стандартной нормальной случайной величине
Четвёртая глава.
В четвёртой главе рассматривается дискретная задача о парковке для
машин длины один. Заметим, что в этом случае постановка задачи, представленная
в предыдущей главе, не имеет смысла – мы в любом случае заполним весь
отрезок. Поэтому необходимо ввести дополнительные ограничения. Допустим,
что мы не можем расположить интервал не только если он не поместиться на
отрезок (то есть длина отрезка строго меньше, чем длина интервала), но и
в случае, если длина отрезка просто не является достаточной, независимо от
длины располагаемого интервала. В таком случае количество расположенных
интервалов вновь будет случайной величиной, и задача в такой постановке
обретает смысл.
Таким образом, поставим следующую задачу. Зафиксируем натуральное
l > 0. Пусть у нас есть отрезок [0, n]. Если его длина меньше чем l, процесс
прекращается. Иначе расположим на нём случайным образом интервал (t, t+
1) с целыми концами. Он разбивает изначальный отрезок на два, каждый из
которых далее рассматривается отдельно, аналогично изначальному. Фраза
«случайным образом» здесь также означает, что t является случайной величиной,
равномерно распределённой на множестве целых чисел {0, . . . , n − 1}. Когда
длина всех оставшихся отрезков становится меньше l, процесс прекращается,
и подсчитывается суммарное количество расположенных отрезков. Обозначим
эту случайную величину за ξn .
В первой части четвёртой главы диссертации показаны следующие результаты,
касающиеся первых моментов последовательности случайных величин ξn .
Теорема 2.7. Для любой натуральной константы l > 0 описанные выше
случайные величины ξn имеют следующие математические ожидания:
E{ξ0 } = . . . = E{ξl−1 } = 0,
2n + 1 − l
E{ξn } =,при n > l.
l+1
Теорема 2.8. Для любой натуральной константы l > 0 описанные выше
случайные величины ξn имеют следующие дисперсии:
D{ξ0 } = . . . = D{ξl } = 0,
2(l − 1)(l2 + 2l + 3)
D{ξl+1 } =,
(l + 1)3 (l + 2)
4(l − 1)(l2 + 2l + 3)
D{ξn } = (n + 1),при n > l + 2,
(l + 1)3 (l + 2)2 (l + 3)
а их третьи центральные моменты равны
E{ξ0 − Eξ0 }3 = . . . = E{ξl − Eξl }3 = 0,
2(l − 1)(l3 − l2 − 5l − 7)
E{ξl+1 − Eξl+1 }3 =,
(l + 1)4 (l + 2)2
34(l − 1)(l3 − l2 − 5l − 7)
E{ξn − Eξn } = (n − 1),при n > l + 2.
(l + 1)4 (l + 2)2 (l + 3)
Для случая l = 2. также был получен результат, аналогичный приведённому
в Теореме 1.3.
Теорема 2.9. В случае l = 2 последовательность распределений случайных
величин
ξn − E {ξn }
p(n = 1, 2, . . .)(7)
D{ξn }
слабо сходится к стандартной нормальной мере.
Во второй части четвёртой главы рассматривается обобщение описанной
выше задачи на случай неравномерного расположения интервала. Рассмотрим
задачу случайного расположения интервалов длины 1, но при этом на каждом
шагу запретим этому интервалу быть расположенным на самом левом месте.
Все остальные места оставим равновероятными. Таким образом, мы располагаем
интервал (t, t+1), где t — случайная величина, равномерно распределённая на
множестве {1, . . . , n−1} вместо {0, . . . , n−1}. Аналогично обычной постановке,
если n = 1, процесс заканчивается. Для данной задачи был получен следующий
результат.
Теорема 2.10. Математическое ожидание случайной величины ξn при n >
2 имеет следующий вид
Γ(n + 1, −1)Γ(n, −1)
E{ξn } = n 1 −−,
eΓ(n + 1)Γ(n)
где Γ(n) — гамма-функция, а Γ(n, −1) — неполная гамма-функция, которая
определяется равенством
Z +∞
Γ(n, −1) =tn−1 e−t dt.
−1
Пятая глава.
В пятой главе диссертации рассматривается задача о парковке интервалов
случайной длины. Предположим, что теперь на каждом шагу, перед тем
как расположить интервал, сначала случайным образом будет определяться
его длина, а уже потом, также случайным образом, определяется место его
расположения. Будем считать, что распределение длины отрезка не зависит
от длины текущего интервала, а его место равномерно распределено среди
всех возможных позиций.
Заметим, что ранее мы изучали не общее занятое место, а суммарное
количество расположенных отрезков, так как все располагаемые отрезки имели
одинаковую длину. Однако в данном случае две обозначенные выше величины
не выражаются однозначно друг через друга. В данной главе мы будем обозначать
за ξn общее занятое место.
Для описанной выше задачи в простейшем случае, когда длина интервала
варьируется от единицы до двойки, был получен следующий результат
Теорема 2.11. Пусть случайная величина l имеет следующее распределение
P{l = 1} = p1 ,
P{l = 2} = p2 = 1 − p1 .
В таком случае математическое ожидание случайной величины ξn для n > 2
имеет следующий вид
1 − p22
1 − p21 + p2 Γ(n + 1, −2p2 ) 1 + p2 Γ(n, −2p2 )
E{ξn } =+n1 +−n−.
2p222p222p22 e2p2 Γ(n + 1)p2e2p2 Γ(n)
Шестая глава
В шестой главе приведены доказательства технических лемм, используемых
в предыдущих главах.
Литература
[1] Rényi A., “On a one-dimensional problem concerning space-filling” // Publi-
cations of the Mathematical Institute of the Hungarian Academy of Sciences.
Vol. 3. P. 109–127. 1958.
[2] Dvoretzky A., Robbins H., “On the “parking” problem” // Publications of
the Mathematical Institute of the Hungarian Academy of Sciences. Vol. 9.
P. 209–226. 1964.
[3] Pinsky R. G., “Problems from the Discrete to the Continuous” // Springer
International Publishing Switzerland. Chapter 3. P. 21–34. 2014.
[4] Clay M. P., Simanyi N. J., “Rényi’s parking problem revisited” // Stochastic
and Dynamics. Vol. 2 (16). 1660006. 2016.
[5] Gerin L., “The Page-Rényi parking process” // Electronic Journal of Com-
binatorics. Vol. 4 (22). P4.4. 2015.
[6] Iльєнко А. Б., Фатенко В. В., “Узагальнення задачi Реньї про
паркування” // Науковi вiстi НТУУ «КПI» : мiжнародний науково-
технiчний журнал. № 4(114). С. 54–60. 2017.
[7] Ананьевский С. М., “Задача парковки для отрезков различной длины”//
Записки научных семинаров ПОМИ. Т.228. Вероятность и статистика.
С. 16–23. 1996.
[8] Ананьевский С. М., “Некоторые обобщения задачи о «парковке»” //
Вестник Санкт-Петербургского университета. Математика. Механика.
Астрономия. Т 3 (61). Вып. 4. С. 525–532. 2016.
[9] Ney P. E., “A random interval filling problem” // Annals of Mathematical
Statistics Vol. 2 (33). P. 702–718. 1962.
[10] Mullooly J. P., “A one dimensional random space-filling problem” // Journal
of Applied Probability, Vol. 5. No. 2. P. 427–435. 1968.
[11] Baryshnikov Y., Gnedin A., “Counting intervals in the packing process” //
The Annals of Applied Probability. Vol. 11. No. 3. P. 863–877. 2001.
[12] Coffman E. G., Leopold Flatto L., and Jelenković P. “Interval packing: the
vacant interval distribution” // The Annals of Applied Probability. Vol. 10.
No. 1. P. 240–257. 2000.
[13] Rhee W. T., Talagrand M. “Packing random intervals” // The Annals of
Applied Probability. Vol. 6. No. 2. P. 572–576. 1996.
[14] Поярков А. П., “Случайные упаковки куба” // Фундаментальная и
прикладная математика. Т. 11. No 5. С. 187–196. 2005.
[15] Mackey M., Sullivan W. G., “Exhaustion of an interval by iterated Rényi
parking”// arXiv:1610.06423 [math.PR]. 2016.
[16] Xu C., Skiena S.,“Marking Streets to Improve Parking Density”// arX-
iv:1503.09057 [physics.soc-ph]. 2015.
[17] Крюков Н. А., “Дискретизация задачи о парковке” // Вестник Санкт-
Петербургского университета. Математика. Механика. Астрономия. Т. 7
(65). Вып. 4, С. 662–677. 2019.
[18] Ананьевский С. М., Крюков Н. А., “Асимптотическая нормальность в
дискретном аналоге задачи о парковке”// Записки научных семинаров
ПОМИ. Т. 495. Вероятность и статистика. C. 9–36. 2020.
[19] Ананьевский С. М., Крюков Н. А., “Задача об эгоистичной парковке”
// Вестник Санкт-Петербургского университета. Математика. Механика.
Астрономия. Т. 5 (63). Вып. 4. С. 549–555. 2018.
[20] Ананьевский С. М., Крюков Н. А., “Асимптотическая нормальность
в задаче об эгоистичной парковке” // Вестник Санкт-Петербургского
университета. Математика. Механика. Астрономия. Т. 6 (64). Вып. 4.
С. 592–607. 2019.
[21] Ананьевский С. М., Крюков Н. А., “Об асимптотической нормальности
в одном обобщении задачи Реньи” // Вестник Санкт-Петербургского
университета. Математика. Механика. Астрономия. Т. 6 (64). Вып. 3.
С. 353–362. 2019.
[22] Крюков Н. А., “Односторонняя эгоистичная парковка”// Записки
научных семинаров ПОМИ. Т. 501. Вероятность и статистика. С. 194–
202. 2021.
[23] Billingsley P., “Probability and Measure” // Third Edition, A Wiley-
Interscience Publication, John Wiley Sons, New York, 1985.
Задача случайного заполнения отрезка впервые была рассмотрена в ра-
боте Реньи [1] в следующей формулировке. На отрезке [0, x] для x > 1 раз-
мещается случайным образом интервал (t, t + 1) единичной длины, тем са-
мым разбивая изначальный отрезок на два отрезка меньшей длины: [0, t] и
[t + 1, x]. Если какой-либо из них имеет длину меньше единицы, он исключа-
ется из дальнейшего рассмотрения. Остальные, в свою очередь, продолжают
заполняться по вышеописанному правилу. По окончании данного процесса
подсчитывается количество размещённых на изначальном отрезке интерва-
лов. Оно обозначается за ξx . Для 0 6 x < 1 значение ξx принимается равным
нулю. Выражение «случайным образом» в вышеописанной задаче означает
что t является равномерно распределённой на [0, x − 1] случайной величиной.
Более того, любое следующее случайное размещение интервала не зависит от
предыдущих.
В работе Реньи [1] был показан следующий результат
Теорема 1.1. Пусть ξx — описанное выше множество случайных величин.
Тогда для любого n > 1 имеет место следующее соотношение
E{ξx } = λx + λ − 1 + o(x−n ), (x → +∞), (1)
где константа λ определена следующим образом
Z∞ Rt 1−e−u
−2 u du
λ= e 0 dt.
Позднее в работе Дворецкого и Роббинса [2] было дано уточнение скорости
сходимости в соотношении (1), а так же изучено поведение дисперсий того
же множества случайных величин
Теорема 1.2. Пусть ξx — описанное выше множество случайных величин.
Тогда имеет место следующее соотношение
x− 32 !
2e
E{ξx } = λx + λ − 1 + O , (x → +∞).
x
Также, существует такая положительная константа λ2 , что
x−4 !
4e
D{ξx } = λ2 x + λ2 + O , (x → +∞).
x
В работе [2] также был представлен результат об асимптотической нор-
мальности последовательности случайных величин ξx :
Теорема 1.3. Последовательность случайных величин
ξx − E {ξx }
p (2)
D {ξx }
слабо сходится к стандартной нормальной случайной величине при x → ∞.
В работе [3] был рассмотрен дискретный аналог задачи о парковке. В нём
на отрезок некоторой целой длины x (будем в таком случае обозначать дли-
ну за n) размещаются интервалы заранее заданной целой длины l, которая
может быть отлична от единичной. Случайная величина t в данной задаче
имеет равномерное распределение на множестве целых чисел {0, . . . , n − l},
а отрезки длиной меньше l исключаются из рассмотрения. При помощи про-
изводящих функций в статье [3] было получено следующее асимптотическое
поведение математических ожиданий E{ξn }
l−1 Z1 l−1
xi
E{ξn } 1
P P
−2 i 2 i
lim =e i=1 e i=1 dx =: λl .
n→+∞ ln
В последнее время задачи о случайном заполнении отрезка вновь привле-
кают внимание математиков. Они были недавно рассмотрены в ряде статей,
в том числе [4]–[8]. В работах [4]–[5] рассматривались дискретные варианты
задачи, в то время как [6]–[8] обращали внимание на непрерывные аналоги.
Аналоги описанных выше задач были так же рассмотрены в работах [9]–
[16].
В разделе 2 описано обобщение Теорем 1.1–1.3 на случай неравномерного
расположения отрезков. В разделах 3,4,5 рассмотрены дискретные аналоги
задачи Реньи. В разделе 3 располагаемые интервалы имеют целую длину
большую единицы, а в разделе 4 располагаемые интервалы имеют длину 1,
но они не могут быть расположены на отрезках достаточно малой длины.
В разделе 5 интервалы имеют случайную длину. Раздел 6 посвящён доказа-
тельству технических Лемм.
Цель диссертационной работы. Основной целью данной диссертации
является обобщение полученных в работах [1, 2] результатов на случаи одного
класса законов распределений случайного размещения интервалов, включа-
ющего в себя равномерный закон, а также получение аналогов асимптотиче-
ских результатов, приведенных в работе [2] для различных моделей дискрет-
ных законов случайного размещения интервалов, обобщающих предложен-
ную в работе [3] модель.
Методы. В настоящей диссертации развиваются методы, приведенные
в работах [1] – [3]. Также используется метод, основанный на вычислении
производящих функций. Для получения предельных распределений исполь-
зуется метод, основанный на получении точных асимптотик моментов.
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая значимость.Работа носит теоретиче-
ский характер. Результаты диссертации могут быть использованы в различ-
ных областях теории вероятностей и математической статистики, в которых
важны оценки числа случайно размещенных интервалов малой длины на от-
резках большой длины.
Результаты и положения, выносимые на защиту.
1. Обобщение результатов, полученных в работах [1, 2] на случай, когда
распределение размещаемого интервала обладает свойством антисим-
метричности.
2. Уточнение асимптотики математических ожиданий и дисперсий в дис-
кретном аналоге задачи о парковке, рассмотренном в работе [3], а также
установление асимптотической нормальности в данной задаче.
3. Вычисление точных значений математических ожиданий для описан-
ной в пункте 2 задачи для расположения интервалов длины 2.
4. Вычисление точных значений математических ожиданий, дисперсий и
третьих центральных моментов в задаче о дискретной парковке машин
длины 1 с дополнительным условием остановки процесса заполнения в
случае, если длина отрезка становится меньше заранее заданного зна-
чения.
5. Установление асимптотической нормальности для описанной в пункте
4 задачи.
6. Вычисление точных значений математических ожиданий в задаче о дис-
кретной парковке машин длины 1 с дополнительным условием запрета
расположения интервала на самом первом месте.
7. Вычисление точных значений математических ожиданий в задаче о дис-
кретной парковке машин, длина которых является случайной величи-
ной, распределённой на множестве {1, 2}.
Степень достоверности. Все полученные в этой диссертационной ра-
боте результаты являются математически достоверными фактами.
Апробация результатов.Результаты диссертации докладывались авто-
ром на Санкт-Петербургском Городском семинаре по теории вероятностей и
математической статистике по руководством академика РАН И. А. Ибраги-
мова (Санкт-Петербург, 22 октября 2021). Материалы диссертации опублико-
ваны в статьях [17]–[22] в рецензируемых журналах, которые входят в список
ВАК.
Читать «Различные задачи случайного заполнения множеств»
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
5 (91 отзыв)
4.6 (92 отзыва)
4.7 (82 отзыва)
4.9 (343 отзыва)
5 (154 отзыва)
0 (13 отзывов)
4.4 (93 отзыва)
4.7 (96 отзывов)
5 (14 отзывов)
