Введение 4
Содержание 6
1. Общая постановка задачи 8
1.1. Постановка задачи о парковке 8
1.2. Регулярность 11
2. Задача о неравномерной парковке 15
2.1. Постановка задачи 15
2.2. Полученные результаты 15
3. Задача об эгоистичной парковке 20
3.1. Постановка задачи 20
3.2. Полученные результаты 20
4. Задача о дискретной парковке 35
4.1. Постановка задачи 35
4.2. Полученные результаты 36
Заключение 43
Список литературы 44
Купить

Задача о случайной парковке впервые упоминается в работе Реньи [1], опубликованной в 1958 году. В ней он исследовал асимптотику математического ожидания количества интервалов единичной длины, размещённых на отрезке, длина которого стремится к бесконечности. Позднее исследование этой задачи продолжилось, и в работе [3] за ав­торством Дворецкого и Роббинса была доказана асимптотическая нор­мальность этих случайных величин.
Изначальная постановка задачи следующая. Пусть у нас есть отрезок [О,ж]. На этот отрезок случайным образом размещается отрезок еди­ничной длины. То есть, вводится случайная величина ц, равномерно распределённая на отрезке [0, х — 1], и размещённый отрезок имеет кон­цы [ц, ц +1]. Размещённый отрезок разбивает изначальный на два : [0, ц] и [ц + 1, ж]. Затем эти отрезки рассматриваются независимо друг от дру­га, и на них также случайным образом размещаются отрезки длины 1. Процесс завершается, когда длины незаполненных отрезков становятся меньше единицы. В конце за Nx обозначается количество размещённых отрезков.
Эта задача приобрела следующую интерпретацию. Пусть у нас есть улица длины х, на которой паркуются машины длины 1. Причём каж­дая следующая машина случайно выбирает для себя место так, чтобы не пересекаться с уже припаркованными. Тогда Nx — количество при­паркованных машин. Из-за этой интерпретации задача и получила на­звание ’’задача о парковке”.
В работе Реньи [1] было установлено, что для любого п ^ 1 верно ра­венство
ENx = Хх + А — 1 + О(х~п) (х щ то).
Также в данной работе было дано интегральное выражение для кон­станты А:
А = [ е“2 й dudt « 0.748.
Jo
Позже, в работе Дворецкого и Роббинса [3] получено уточнение выра­жения для математического ожидания
„ ч ч (/2е (х 2)
ENx = Хх + А — 1 + о| | — )
х
Также в этой работе было доказано, что для дисперсии существует кон­станта А2, такая что
( ( 4с ) (x-4)
DNx = А2ж + А2 + О I | — )
х J
Купить