Различные задачи случайного заполнения множеств тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат наук Крюков Николай Алексеевич

• Крюков Николай Алексеевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Крюков Николай Алексеевич

Оглавление:

1. Введение

2. Обобщение задачи Реньи о парковке

3. Задачи о дискретной парковке в классической постановке

4. Задачи о дискретной парковке в эгоистичной постановке

5. Размещение интервалов случайной длины

6. Приложение

Введение диссертации (часть автореферата) на тему «Различные задачи случайного заполнения множеств»

1 Введение

Задача случайного заполнения отрезка впервые была рассмотрена в работе Реньи [1] в следующей формулировке. На отрезке [0, х] для х > 1 размещается случайным образом интервал (£,£ + 1) единичной длины, тем самым разбивая изначальный отрезок на два отрезка меньшей длины: [0, £] и \Ь + 1, х]. Если какой-либо из них имеет длину меньше единицы, он исключается из дальнейшего рассмотрения. Остальные, в свою очередь, продолжают заполняться по вышеописанному правилу. По окончании данного процесса подсчитывается количество размещённых на изначальном отрезке интервалов. Оно обозначается за £х. Для 0 ^ х < 1 значение £х принимается равным нулю. Выражение «случайным образом» в вышеописанной задаче означает что £ является равномерно распределённой на [0, х — 1] случайной величиной. Более того, любое следующее случайное размещение интервала не зависит от предыдущих.

В работе Реньи [1] был показан следующий результат

Теорема 1.1. Пусть £х — описанное выше множество случайных величин. Тогда для любого п > 1 имеет место следующее соотношение

Е{£х} = Ах + Л — 1 + о(х—п), (х ^ (1)

где константа Л определена следующим образом

<х> г

—2 / аи

Л = / в 0 " М.

Позднее в работе Дворецкого и Роббинса [2] было дано уточнение скорости сходимости в соотношении (1), а так же изучено поведение дисперсий того же множества случайных величин

Теорема 1.2. Пусть £х — описанное выше множество случайных величин. Тогда имеет место следующее соотношение

Е{£х} = Лх + Л — 1 + О^, (х ^

Также, существует такая положительная константа Л2, что

Б{£х} = Л2х + Л2 + О( (—) | , (х ^ +ю).

х

В работе [2] также был представлен результат об асимптотической нормальности последовательности случайных величин £х:

Теорема 1.3. Последовательность случайных величин

ix - E {Ы

слабо сходится к стандартной нормальной случайной величине при х ^ то.

В работе [3] был рассмотрен дискретный аналог задачи о парковке. В нём на отрезок некоторой целой длины х (будем в таком случае обозначать длину за п) размещаются интервалы заранее заданной целой длины I, которая может быть отлична от единичной. Случайная величина £ в данной задаче имеет равномерное распределение на множестве целых чисел {0,... ,п — /}, а отрезки длиной меньше I исключаются из рассмотрения. При помощи производящих функций в статье [3] было получено следующее асимптотическое поведение математических ожиданий Е{^п}

г-1 1 г-1

ж"

r E{in} -2 Е W 2 Е f , Л

lim —--= e i=1 e i=1 dx =: Л/.

In J

0

В последнее время задачи о случайном заполнении отрезка вновь привлекают внимание математиков. Они были недавно рассмотрены в ряде статей, в том числе [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] в рецензируемых журналах, которые входят в список ВАК.

2 Обобщение задачи Реньи о парковке

Рассмотрим следующее обобщение описанной в прошлом разделе задачи. Пусть интервалы (£,£ + 1) размещаются на отрезке [0,х] отличным от равномерного образом. Будем считать, что распределения располагаемых интервалов не зависят от конкретного отрезка, а только от его длины. В таком случае нам достаточно определить семейство распределений

р = {Рх}х>1 ,

где Рх — некоторое распределение на отрезке [0, х—1]. Тогда интервал (£, £+1) располагается на отрезке [0, х] таким образом, чтобы случайная величина £ имела распределение Рх. Обозначив за (х) общее количество размещённых на изначальном отрезке [0,х] единичных интервалов, эти случайные величины удовлетворяют следующему соотношению.

(х) = 0, х < 1, & (1) = 1,

&(х + 1) = 1 + &(п(х)) + &(£ — п(х)), х > 0,

где п(х) — случайная величина, имеющая распределение Рх. В данном разделе мы будем считать, что распределения Рх имеют соответствующие плотности рх. В данном разделе мы хотим показать, что при определённом условии на плотности рх распределения случайных величин (х) не зависят от конкретных мер Рх.

Теорема 2.1. Рассмотрим два множества случайных величин ^1(£) и £2(£), которые определены при неотрицательных £ следующим образом:

б(£) = Ш = 0, £ < 1 6(1) = €2(1) = 1

6(£ +1) = 1 + Ыт(£)) + €1(£ — П1 (£)), £ > 0 6(£ + 1) = 1 + 6М£)) + 6(£ — П2(£)), £ > 0,

где множества случайных величин п1(£) и п2(£) независимы и соответственно имеют плотности р1;г(х) и р2Дх), определённые на отрезке [0,£] и удовлетворяющие следующему соотношению:

2

р^(и)+ Рм(£ — и) = £, Уи е [0, £], Уг = 1,2. (3)

Тогда распределения случайных величин €1(£) и £2(£) совпадают для всех положительных £.

Доказательство Теоремы 2.1: Определим два вспомогательных набора случайных величин

n(t) = /ni^ ni(i) < 2-niU \t - ni(t), ni(t) > 2,

n (t) i n2(t)- n2(t) < 2,

П2(t) 11 - 42(t), »2« > 2.

Покажем, что в силу (3)

ni (t) = n2 (t) = n*(t) vt ^ o,

где n*(t) — равномерно распределённая на отрезке [0, 2] случайная величина. Заметим, что носителем случайных величин ni (t) и n2(t) является отрезок [0, t/2]. Теперь изучим их распределения. Зафиксируем интервал < a,b >С [0,t/2]. Вероятность попасть в этот интервал равна

P (ni(t) G< a, b >) = P (ni(t) G< a, b >) + P (ni(t) G< t - b,t - a >) =

pb çt-a pb pt-a 2

= pi,t(u)du + / pM(u)du = pM(u)du + / - - pi,t(t - u)du = Ja Jt-b Ja Jt-b t

= J (pi,t(u) + 2 - pi,t(u)^ du = (b - a)- = P (n*(t) G< a, b >).

Аналогично ведёт себя распределение случайной величины n2(t). Построим по набору n* (t) аналогичный набор случайных величин £*(t):

£*(t) = 0 t< 1, £ *(1) = 1,

£*(t + 1) = 1 + £*(n*(t))+ £*(t - n*(t)),

и покажем, что для любого натурального п при £ ^ п

Ы0 = £'((). (4)

Доказывать это будем по индукции по п. База при п = 1 следует напрямую из определения.Пусть для п = т это верно. Докажем для п = т + 1. Пусть (£ + 1) ^ (т + 1). Не умаляя общности можно считать, что £ > 0. Значит, £1(£ + 1) и £*(£ + 1) можно представить в следующем виде:

£1(£ + 1) = 1 + £1 (П1 (£)) + £1(£ — П1(£)), (5)

£ *(£ + 1) = 1 + £ *(п*(£)) + £ *(£ — п*(£)). (6)

Докажем следующее равенство:

ii(ni (t)) + ii(t - ni(t)) = ii(ni (t)) + ii(t - ni (t)).

Заметим, что при ni(t) ^ f верно ni(t) = ni(t), и равенство очевидно. А при n(t) > 2 имеет место соотношение n(t) + ni (t) = t, и значит

ii(ni(t)) + ii(t - ni(t)) = ii(t - ni(t)) + ii(ni(t)).

Тогда соотношение (5) можно переписать в виде

ii(t + 1) = 1+ ii(ni(t))+ ii(t - ni(t)).

Так как ni (t) = n*(t), имеет место равенство

ii(t + 1)== 1 + ii(n* (t)) + ii(t - n*(t)).

Теперь заметим, что по определению случайной величины n*(t),

n*(t) < t - n*(t) < t < m.

Значит, можно применить индукционное предположение:

ii(n *(t)) = С *(n*(t)).

Таким образом,

ii(t - n*(t)) = С *(t - n*(t)).

ii(t + 1)== 1+ i*(n*(t))+ С*(t - n*(t)). (7)

Наконец, из равенства (6) получаем требуемое соотношение (4). Так как данное утверждение верно при всех натуральных п, то равенство (4) верно при всех положительных £. Аналогично, при всех положительных £ верно равенство

«2(0= € '(£). (8)

А из равенств (4) и (8) следует утверждение изначально поставленной теоремы. □

Следствие 1. Пусть Р1, Р2 — два семейства мер, удовлетворяющих соотношению (3). Тогда для любого х ^ 0 случайные величины (х) и «р2 (х) имеют одинаковые распределения.

Данное следствие является прямой переформулировкой Теоремы 2.1.

Следствие 2. Пусть Р — семейство мер, удовлетворяющее соотношению (3). Тогда последовательность случайных величин

£р (х) — Е {£р (х)} V® {£р (х)}

слабо сходится к стандартной нормальной случайной величине при х ^ то.

Доказательство Следствия 2: Определим дополнительную систему мер 2 = {Ог}х>ъ где — равномерное распределение на отрезке [0, х — 1]. Заметим, что в таком случае плотности дх распределений удовлетворяют соотношению (3). Значит, согласно Следствию 1, случайные величины

£р (х) — Е {£р (х)} V® {£р (х)}

распределены так же как случайные величины

£а(х) — Е{£а(х)} V® {£2(х)} .

А предел таких случайных величин показан в Теореме 1.3. □

3 Задачи о дискретной парковке в классической постановке

Пусть п, I — два натуральных числа. Будем случайно помещать на отрезок [0,п] интервалы длины I таким образом, чтобы начало и конец интервала были целыми числами. В случае п < I такое невозможно, и процесс считается завершённым. Иначе поместим интервал (£, £+/), где £ — случайная величина, равномерно распределённая на множестве {0,... ,п — /}. Он разбивает изначальный отрезок на два: [0,£] и [£ + /,п], которые заполняются независимо по аналогичному правилу. Как только процесс завершается, что означает, что все оставшиеся свободными отрезки имеют длину меньше чем /, обозначим за £П;/ суммарную длину расположенных интервалов.

Более формально задачу можно поставить следующим образом. Зафиксируем некоторое натуральное число I ^ 2 и рассмотрим последовательность случайных величин £П;/ :

бо,1 = ... = €/—1,1 = 0, (9)

бп,1 := I + £„,, + бП—„п—ц при п > 3, (10)

где 6п>/ и — независимые копии случайных величин 6„,1 и 6-^-1,1

соответственно, а — независимая случайная величина, не зависящая от равновероятно принимающая значения 0,..., п — I.

Следующая Теорема описывает поведение математических ожиданий случайных величин 6,1

Теорема 3.1. Для описанных выше случайных величин бп,1 и любого Т > 1 верно соотношение

Е {бп,1} = 1X1 п + /2Л1 — I + о(Т—п), (п ^ (11)

где константа Л/ имеет вид

1-1 1 г-1 —2 £ 1 [ 2 £ ^ Л1 = е -1 Ч е-1 • ... (12)

0

Замечание 1. Приблизительные значения констант Л/ таковы

Л2 = е2 — 1

2е2

Лз « 0.274551, Л4 « 0.200973, Лв « 0.158455.

Замечание 2. Данная теорема является уточнением полученного в книге [3] результата (Теорема 3.1, стр. 21). В теореме 3.1, [3] представлено выражение для Е {£П;/} с точностью 0(1/п), в то время как в Теореме 3.1 точность выражения для Е {£П;/} равна о(е-п).

Доказательство Теоремы 3.1: Доказательство этой теоремы аналогично доказательству Теоремы 3.1 из книги [3], однако в конце уделяется больше внимания анализу полученной производящей функции.

Зафиксируем некоторое натуральное значение / ^ 2. Пусть Еп,/ = Е(£П;/). Опустим для удобства индекс / и будем писать далее Еп вместо Еп,/ и £п вместо £П;/. Очевидно, что из начальных условий (9) на последовательность £п следуют начальные условия на Еп:

Ео = ... = Е/-1 = 0.

А из соотношения (10) следует рекуррентное соотношение на эту последовательность:

1 П+1-/

Еп+1 = 1 +--—^-7 / (Ег + Еп+1-г-/) .

п + 2 — /

г=0

Его можно переписать в следующем виде:

2 п+1-/ Еп+1 = 1 +--"7,-7 У]

п + 2 — /

¿=0

Определив вспомогательную последовательность $п:

п

п

¿=0

можно получить следующие условия на последовательность $п:

$о = ... = ^/-1 = 0, 2

5П+1 = Бп +--——-5П+1-/ + /, п > / - 1. (13)

П + 2 — /

Перепишем рекуррентное соотношение (13) в следующем виде:

(п + 1)5П+1 - (/ - 1)5П+1 = п^п - (/ - 2)^п + 25П+1-/ + /п - (/2 - 2/).

Для вычисления последовательности 5П будем использовать метод производящей функции. Введём вещественную переменную г, домножим уравнение

выше на гп+1, и сложим все полученные выражения по п от I — 1 до бесконечности.

то то то то

— (I — 1) V 5ип = г2 V п5п^п—1 — (I — 2)г V

пЗ^ — (I — 1) ^ = г2 п^п^п—1 — (I — 2)г ^ Д

п=1 п=1 п=1—1 п=1—1

то то то

+ 2г1 ^ Дпгп + 1г ^ пгп — (I2 — 21) ^ гп.

пг + 1г > пг — (Г — 21) > г

п=0 п=1 — 1 п=1

Зная начальные значения последовательности Дп, все суммы в выражении выше можно заменить на суммы по всем неотрицательным целым п:

то то то то

^2 пДпгп—1 — (I — 1) ^ Дпгп = г2 ^ п^г^1 — (I — 2)г ^

п=1 п=0 п=1 п=0

„1 гп , 1 + 2г 1 1г п2 г

+2г ^ Дпгп + 1г1 -г.--(I2 — 21)- ,

(1 — г)2 1 — г

что равносильно следующему

то то то то

г ^ пДпгп—1 — (I — 1) ^ Дпгп = г2 ^ п^г^1 — (I — 2)г ^ Д

то 7.1

+2*^ Дпгп +

п=1 п=0 п=1 п=0

1г

(1 — г )2'

п=0 1 '

Определив производящую функцию последовательности £п, и её производную

то

п

п=0 то

С (г) = ^ пДпгп—1

п=1

уравнение выше можно записать как дифференциальное уравнение:

1^1

) — (I — 1)С(г) = г2С(г) — (I — 2)гС(г) + 2*1 ) +

(1 — г)2'

что эквивалентно следующему равенству

1

(г — г2)С(г) — (2*1 — г (I — 2) + I — 1)ВД = 77^-. (14)

(1 — г )2

Обозначим правую часть этого равенства за ). Решим сначала однородное уравнение, соответствующее уравнению (14):

(г - г2)И'(г) - (2г/ - (/ - 2)г + (/ - 1))И(г) = 0,

Откуда можно получить следующее уравнение:

(/п(И(г)))' = 2г' - (/ - 2)г,+ (/ - 1) = -21-^ + ^ + ,

г - г2 1 - г г 1 - г

решением которого является набор функций

/-1

/п(И(г)) = с* — 2 ^ - + (/ - 1) 1п(г) - 3/п(1 - г),

¿=1 г

где с* — вещественная константа. Таким образом

г-1

z"

H (z ) =

i-i ^ Zr cz1 1e -=1

(1 - г)3

для некоторой константы с. Значит, функция ) представима в виде произведения И (г )К (г), где функция К (г) является решением следующего уравнения:

(г - г2)И(г)К'(г) = ). Подставив в него ) и И (г), получим

'-1 г

-2 У —

/ 2 ^ 1 7 /

Сг 6 •=1 -К'(г) = /г

(1 -г )2 '' (1 -г)2'

'-1 i 2 - -

cK'(z) = /в i=1 i ,

'-1 r 'z 2 - $

cK(z) = c2 + / / в i=1 i dx. Jo

Перемножив функции H(z) и K(z), получим общее выражение для G(z):

'-1 i / '-1 i N

^ -2EZr / , ,z 2£t, z 1e i=1 c2 + /Je i=1 dx

G(z) = ■ 0

(1 - z)

Заметим, что исходя из начального условия,

G(z)

0 = Si_ i =

zl-1

= С2.

z=0

Таким образом, функция ) равна

'-1 г г

_9 V — 9 V —

7 /- 1 9 ^ г ('2 9 ^ г 7

, ч /г1 1е г=1 п е г=1 аж , ч ОД —--. (15)

(1 - г)3

Теперь выразим производящую функцию последовательности Еи через функцию ). Из определения £и следует, что

е — ^ _ ^ 1

-^и ^и ^ и—1-

Домножив это равенство на ги и сложив по п от одного до бесконечности, получим соотношение

Е (г) — Е0 — ОД — 30 — ),

где Е(г) — производящая функция последовательности Еи. Так как Е0 — 50 — 0, то их можно убрать. Тогда мы получим следующее выражение для функции Е(г):

г-1 г г-1 г

^ , Ч ^ /г1—1е 9 _=1 _ /0 е9 _ От , ч

Е (г) — (1 — г )ОД —-—^-. (16)

(1 — г )9

Теперь необходимо разложить функцию Е(г) в ряд. Для этого определим ещё одну функцию:

'-1 _ л2 1—1 г

2 Г2 о X

^ \ 1-9 —^ т Г 9Е Ъ /(г) — г1 9е / е г=1 аж,

и перепишем с её помощью функцию (16):

р (г) — ^^ / (г). (17)

(1 — г)9

Мы знаем разложение функции г/(1 — г)9 в ряд:

/г

(1 — г)

9

/

пг и.

и=0

Пусть функция / (г) имеет следующее разложение в ряд

то

/(г) —

¿=0 14

0

Подставив эти разложения в формулу (17), получим следующее выражение для ЕП:

п / п \ п

Еп = / X] с»(п - г) = / I ^ сЛ п - / ^ гсг-

¿=0 \ ¿=0 / ¿=0 Заметим, что при п ^ то,

п то „ 1—1 1 „1

г-1 , г-1

-2 12 1 г 2£ Х-

с

с с = /(1) = е 1=1 е 1=1 1 ^ж = Л/,

¿=0 ¿=0 0 п то

^^ ^ ^ гc¿ = /'(1) = 1 - /Л/.

¿=0 ¿=0

Изучим скорости вышеозначенных сходимостей. Для этого введём четыре вспомогательные функции

то

И(ж) = е2х1/ = ^ Ыкжк,

к=0

то

^(ж) = е-= ^ Ы,*жк,

к=0

¿ то

^¿(ж) = ^ И (ж) = ^ ^ жк, .7=1 к=0

¿ то

^¿(ж) = ^ И (ж) = ^ ^ жк. 7=1 к=0

Константы можно оценить следующим образом (здесь и далее [ж] обозначает целую часть вещественного числа ж)

I | ^ ^

[к/г]! ^[к//]Г Теперь по индукции докажем, что

2к (к + 1)¿—1 1 ^ [к/2</]! .

База для г = 1 доказана выше. Переход можно доказать следующим образом

, ,,, , 2.а + l)¿ 2к-.

1 К.' 1 |Ы+1,к-7 1 <

7=0 .=0 [^¿/]! [к - а//]!

к ( Ь. I 1 Л ¿—1 ок < 2к £

(к + 1)¿—1 2к (к + 1)

.=0 [к^+1 /]! [к^+1/]! '

Аналогичным образом можно показать что

2к (к + 1)—1 1 ^ [к/2*/]1 .

Функция ](г) может быть записана следующим образом

/(г) — г1—^—1(г) / W—1(ж)аж.

0

Для констант с в таком случае верна следующая оценка

—1,к—г—11 к—1 + 1)1—9 2к—*—1(к — г)

k -1 1 1 k -1 2«(i + 1)1 -2 -i - ^ -2

„ ' K/21-1/

i=0 i=0

El _ | Iwi-i,k-i-i| . 2 (

k - i ^ [i/2/-1/]! [(k - i - 1)/2/-1/]! 2k-1^2/-2

<

[(k - 1)/2//]!'

Покажем, что |ck| = o(T-k) для любого положительного T.

Tk2k+1-/(k + 2 - /)2/-2 Tc+/-12c(c + 1)2/-2

lim |ckTk| < lim -—-^-—^-< lim -r ; ;j1, ;-

k—то1 k ^ k—то [(k + 1 - /)/2//]! c—то [c/2//]!

T 2l/k+/—122l/k (2//k + 1)2/-2 ^ lim -—-

k—>-то k!

= Ti-1 lim (T2'' + 22l/)k(2'/k + 1)2'-2 = 0.

k—то k!

что заканчивает доказательство теоремы. □

Отдельно можно рассмотреть случай / = 2. Тогда выражения для £n,2 можно выписать явно.

Теорема 3.2. Для описанных выше случайных величин 6,2 верно соотношение

n n Г(п + 1, -2) (-2)n+1 2 Г(п + 1, -2) E Un,2> = n -

з2 n! n! e2 n!

Доказательство Теоремы 3.2: Сохраним обозначения из доказательства Теоремы 3.1. Можно воспользоваться уже полученным соотношением (15). Получаем, что

G(z ) =

2ze 2z J0Z e2xdx z - ze-

(1 - z)3 (1 - z)3 '

Разложим функцию О в ряд. Для этого заметим, что

то

значит,

1то

--= > г

1 — г - ¿=0

3

, то \ 3 то

1

(1 - г 53 = г] = £

¿=0 ¿=0

Также,

-2г _ ^ (-2)" „¿

г .

1 - е-2г = - Е

Перемножив эти два ряда, получим

¿=1 г!

¿=1

1 - е-2^ то ^2) то то =-£ -г- ^ ¿1=: ^=£ ^

где

с = _ ^ (-2)^С;2-¿+2 (-2)¿—1(п - г + 2)(п - г + 1)

сп = г! = ^ г! '

¿=1 ¿=1

Получаем, что ряд функции О(г) равен

то / п (-2)¿—1(п - г + 2)(п - г + 1)

О(г ) = гЕ Е

п=1 \ ¿=

то / п—1 = £ (£

Таким образом,

гп

г!

п=1 \¿=1

то /п-1 (--^п - г + 1)(п - г)

г

п=2 \¿=1

г п.

ЕЕ {« = Е

п-1, 1

(-2)¿—1(п - г + 1)(п - г)

г!

¿=0 ¿=1

Отсюда можно получить выражение для Е {£п}

Е1 ,, п-1 (-2Г-1(п - г + 1)(п - г) п-2 (-2Г-'(п - г)(п - г - 1)

Е } = £-¿!--£-¿1-

¿=1 ¿=1

(-2)п-1 п-2 2(--^п - г) п-1 2(-2)¿—1(п - г)

+ ^ 2(-2) (п - г) = ^

(п -1)! ^ г! ^ г!

ч 7 ¿=1 ¿=1

Докажем следующую формулу:

п-1 c¿ - 1(п-г^ сп- есГ(п + 1, с) 1/есГ(п + 1,с) % ^ г = г(п + 1) + с V ОД п

¿=1

п

сп песГ(п +1, с) есГ(п + 1,с) п , .

= ~т +--,---,---. (18)

п! сп! п! с

Для этого воспользуемся формулой для усечённой гамма-функции

п ¿

c¿

Г(п + 1, с) = п!е-

г!

¿=0

и распишем с её помощью левую часть формулы (18)

¿ 1 п- 1 ¿ п- 1 ¿

с 1 (п - г) п с4 с4

п-1 ¿_ 1 / .4 п-1 ¿ п-1 ¿_ 1

^ 1 (п - г) ^ ^ с^ ^ c¿ 1

^ И = (г - 1)!

¿=1 ¿=1 ¿=1 4 7

п ^ п \ п 2 ^

п I c¿ сМ V c¿

с \ ^ г! 1 пм ^ г!

\ ¿=0 / ¿=0

п ¿' п_1 п 2 ¿'

п с' п с' 1 с'

= с ^ г! с (п - 1)! ^ г!

¿=0 1 у ¿=0

с п л п 1 л

пе , с с п с

= — п!е-с> ----> -

п!с г! с г!

¿=0 ¿=0

с п—1 ¿

е л ч п с

Г(п+ м - п -£ *

сГ(п) ' с г!

¿=0 п1

_1/есГ(п + 1,с) \ п-, с!

= с1 Г(п V - ^ г!.

Последнюю сумму можно вычислить следующим образом

Еп 1 c¿ сп ^ c¿ сп ес -с"^ c¿ сп - есГ(п + 1,с)

г! = п - ^ г! = Г(п + 1) - Г(п + 1)п!е ^ г! = Г(п + 1) .

¿=0 ¿=0 \ / \ / ¿=0 V '

Таким образом, мы доказали формулу (18). Подставив в неё с = -2 получим

п Г(п + 1, -2) (-2)п+1 2 Г(п + 1, -2)

Е {?п} = п--2-1---1---2-I-.

е2 п! п! е2 п!

□

Также, можно получить аналогичный результат для асимптотического поведения дисперсий случайных величин £п,/

Теорема 3.3. Для описанных выше случайных величин £и,1 верно соотноше-

ние

м} — К0(п — /)+ о(1).

где константа К0 имеет вид

1-1 1 г-1 г

—9 - И 9 - Т

К0 — е г=1 / е г=1

((1 — г)9 — 2(1 — г)г1)

+ 2(1 — г)^0 + (1 — г) ^ Ьиг^ аг

и=1 )

— 4е г=1

г-1 1 г-1 г

—9Е г Г 9Е тг-г1

е

г=1

1- г

х

/г1

г-1 г г-1 г

_9 V 2 9 у^ у_

1е г=1 е г=1 ау „ 0

0 У (1 — г )(Лг/9 — /) + А1 /г

(1 — г)

(1 — г)

V

/

и константы Zl—1, и Ьи определены следующим образом

Zl—l — - (Л9(14/9 — 9/ + 1) + Л1 (6 — 18/) + 6)

6

^0 — (/Л1 — /)9,

Ьи — (/Л1 п + /9Л1 — /)9

Замечание 3. Константа К0 конечна, так как по правилу Лопиталя

Нш

х-> 0

г-1 г г-1 г

—9 ^ 2 9 ^ у_

/г1—1е г=1 г / е г=1 г ау 0

(1 — г)

Л1 /г

(1 — г)

— Л1

Л1/9 /.

Доказательство Теоремы 3.3: Определим функцию

6(п) — Е {&} — (/Л1 п + /9Л1 — /).

Согласно Теореме 3.1, 6(п) — о(е—и), и значит ряд ^6(п)ги абсолютно сходится на всей вещественной прямой. Как и в доказательстве предыдущей

9

3

Теоремы мы можем опустить индекс /. Определим вспомогательную последовательность

Ьи — Е{(6 — (/Л1 п + /9Л1 — /))9} .

Заметим, что

} — Е {(6 — Е{&})9} — Е {(6 — (/Лщ + /9Л1 — /) — 6(п))9}

— Ьи — 26(п)Е {6} + 69(п) — Ьи + о(е—и).

Значит, достаточно найти асимптотическое поведение последовательности Для п ^ / имеет место следующее соотношение

Ьи — Е {(6 — (/Л1 п + /9Л1 — /))9} — Е {Е {(6 — (/Л1 п + /9Л1 — /))91г}} —

— Е{Е{((6—1 — (/Л1 (г — 1) + /9Л1 — /))

+ (6+1—1—г — (/Л1 (п + 1 — г — /) + /9Л1 — /)))9 |г}} —

— Е |е {(6—1 — (/Л1 (г — 1) + /9Л1 — /))91г} + Е <^{(6+1—1— — (/Л1 (п + 1 — г — /) + /9Л1 — /))91 г} + 2е| Е{(6—1 — (/Л1 (г — 1) + /9Л1 — /))91г}

х Е{(6+1—1—г — (/Л1 (п + 1 — г — /) + /9Л1 — /))9—'|г} 1

(п

и1

п + 1 — /^ 0

г=0

+ Ьи—1—г + 26(г)6(п — / — г).

Определим вспомогательную последовательность

и— 1

аи — 2 ^^ 6(г)6(п — / — г).

¿=0

Тогда последовательность Ьи при п ^ / удовлетворяет следующему рекуррентному соотношению:

2 и—1

Ьи — —-+ «и. (19)

п + 1 /

¿=0

Для п < / мы знаем, что

Ьи — (/Л1 п + /9Л1 — /)9. 20

Определим последовательность Дп = Хл=0 Для этой последовательности, согласно соотношению (23) при п ^ / верно соотношение

п^п - (/ - 1)^п - (п - 1)^п-1 + (/ - 2)^п-1 = 2^п-/ + (п +1 - /)«2(п).

Вычислим производящую функцию последовательности Дп. Для этого до-множим равенство, написанное выше, на гп и сложим по п ^ /.

то то то то

пгп - (/ - 1) V ^пгп - V п^п+1 + (/ - 2) V ^п+1

£ п^п - (/ - 1) £ ^пгп - £ п^пгп+1 + (/ - 2) £ Д

п=/ п=/ п=/—1 п=/—1

тото

= 2 £ Дпгп+/ + £(п + 1 - /)«2(п)гп.

п=0 п=/

Определим неполную производящую функцию последовательности Дп

то

О(г) = £ Дпгп.

п=/

Её производная равна

О' (г) = £ пДпгп—

п=/

и следовательно

2/

гО'(г) - (/ - 1)О(г) - г2О'(г) - (/ - 1)Д/—1/ + (/ - 2)гО(г) + (/ - 2)Д/—1/

/-1 то

= 2г/О(г) + 2 £ Дпгп+/ + £(п + 1 - /)«2(п)гп,

п=0 п=/

что можно переписать следующим образом

/-1 то

(г-г2)О'(г )-(2г/-г (/-2)+/-1)О(г) = Д/—^+2 £ Дпгп+/+£(п+1-/)«2(п)гп.

п=0 п=/

Левая часть данного уравнения аналогична левой части уравнения (14). Значит, функция О(г) в данном случае также представима в виде произведения И (г )К (г), где

И (г ) =

'-1 г -2 У —

/-1 2 , г сг 1е г=1

(1 — г)3

а К (г) удовлетворяет уравнению

/1

(г - г2)И(г)К'(г) = Д/—1*/ + 2 £ Дпгп+/ + £(п + 1 - /)«2(п)гп.

п

п=0 п=/

Преобразуем его следующим образом

'-1 г

7 _ 2 £ Т / — 1 С»

С71 е г=1 , ----, ---

е ) = + 2 ^ + ^(п + 1 - -Ып)гп,

п=0 п=/

/_1 то

К'(г) = + 2 ^ + £(п + 1 _ /)«2(п)гп_7,

(1 _ -г )2

1—1 г

_ -2 £ т

се г=1

(1 _ г)2

1—1- г

_ -2 £ - г

се г=1

(1 _ г)

_ ■2 £ 4 г

се г=1

(1 _ г)

п=0 п=/

71

К'(*) = (1 _ + 2(1 _ г) ^

п/

п=0 то

7

+ (1 _ г)5> + 1 _ /)«2(п)гп_7,

п=/

71

) = (1 _ + 2^о _ 7 + ^

П=1

то

+ (1 _ г)5> + 1 _ /)«2(п)гп_7.

п

=7

Значит, производная функции К (г) представима в виде сК'(*) = е г=1 г ((1 _ г)2 _ 2(1 _ г) + 2(1 _ г+ (1 _ г) ^

п=1

г- • ТО

1-1 2 —

+ е г=1 г 1(1 _ г)2 ^(п + 1 _ /)«2(п)гп_7

п

=7

Изучим это представление. Так как мы знаем значения Ьп при п < /, первое слагаемое можно преобразовать следующим образом

7_1 7_1

^ = ^(/Л/п + /2Л/ _ /)2гп,

п=1 п=1

^о = Ьо = (/Л/ _ /)2,

7_1 73

= ^(/Л/ п + /2Л/ _ /)2 = -6 (Л2(14/2 _ 9/ + 1) + Л/(6 _ 18/) + 6) .

п=06

Для вычисления второго найдём производящую функцию последовательности 6(п) используя производящую функцию последовательности Е {6},

приведённую в доказательстве Теоремы 3.1.

00

00

п=0

то

£ ¿(п)гп = £ Е {£п} гп - £(/Л/п + /2Л/ - /)гп

п=0 п=0

'-1 • '-1 • —2 Е ^ ^ 2 Е /г/—1е 1=1 1 / е 1=1 1 ¿ж

00

(1 — г)2

1-1 • 1-1 • _2 V 21 -г 2 V

7 /_ 1 2 ^ 1 Р 2 ^ 1 ,

/г 1е 1=1 J е 1=1 аж

£(/Л/п + /2Л/ - /)гп

п=0

(1 - г)2

(1 - г)(Л//2 - /) + Л//г (1 - г)2 '

Тогда вторую сумму можно записать следующим образом

£(п + 1 - /)«2(п)гп—/ = 2 £(п + 1) £ ¿(г)£(п - г); (/

=/

п=0

¿=0

= 2г

г-1 • г-1 • —2 Е ^ ^ 2 £ /г/—1е 1=1 1 / е 1=1 1 ¿ж

_0_

(1 - г)2

\2\'

(1 - г)(Л//2 - /) + Л//г (1 — г)2

/ /

+2

1-1 • 1-1 • _2 V 21 ^ 2 V X1

/г 1е •=1 J е •=1 аж

\

(1 - г)2

(1 - г)(Л//2 - /) + Л//г (1 - г)2

V

/

Таким образом, функция сК(г) представима в виде

х '-1 • Г 2 - 21 сК'(ж) = е •=1 1

X

((1 - г)2 - 2(1 - г)г^ Д/—1 + 2(1 - г+ (1 - г) £ ^ ¿г

п=1

х '-1 ^ + 2 / ге21=1^

0

х

( !

'-1 • '-1 —2 ^ 4- -г 2 ^ Д-

/г/—1е •=1 1 / е •=1 1 ¿к

\ 2 '

(1 — г )(Л//2 — /) + Л//г

(1 — г)

(1 — г)

¿г

/ У

х '-1 • + 2 X е2 £ *

0

х

/

'-1 • '-1 —2£ т £ 2£ т

\

/г/ 1е •=1 1 / е •=1 1 ¿ж

(1 - г)

(1 - г)(Л//2 - /) + Л//г (1 - г)

V

¿г

/

+ С.

Заметим, что так как разложение функции О(г) в ряд начинается с коэффициента с номером /, то С = 0. Таким образом,

О(г) =

-2 V 41 /-1 2 ^ 1 г1 1е

(1 - г)3

К0(г

2

где

Ко (ж) =

[ 2^г-

/ е г=1

X

((1 _ г )2 _ 2(1 _ г )г7) + 2(1 _ г )Яо + (1

7_1 \ _ г) Ьпгп ¿г

п=1 /

х г-1 г Г 2 - г!

+ 2 ге -

о

X

^/

'-1 г '-1 г _2 ^ г- -г 2 ^ к-

/г7_1е -=1 - / е -=1 - ¿к

_о_

(1 _ г)

\2\ '

(1 _ г)(Л,/2 _ /) + Л,/г (1 _ г)

¿г

/ У

х '-1 г + 2 / е2 £ ^

о

X

/

г-1 г г-1 г

_2 - г- I 2 -

\

/г7 1е -=1 - / е -=1 - ¿ж

_о_

(1 _ г)

(1 _ г)(Л,/2 _ /) + Л,/г

(1 _ г)

¿г.

V /

Исследуем второе слагаемое в этой сумме. Проинтегрировав его по частям,

2

получим

х '-1 • ' 2 - 41

К0(ж) = е •=1

х| ((1 - г)2 - 2(1 - г)г/) Д/—1 + 2(1 - г+ (1 - г) £ ¿пгп^ ¿г

п=1 )

/ '-1 г '-1 г \

'-1 • 2Т, х-

+ 2же 1=1 1

2

_2 V ^ х 2 V 4. , /_ 1 2 г г 2 1 ,

/ж/ 1е •=1 J е •=1 ¿г 0

(1 - ж)

(1 - ж)(Л//2 - /) + Л//ж (1 - ж)

V

/

х '-1 • ( 2 £ 41 - 4 е 1=1 1

0

/

хг

¿=1

'-1 • '-1 г

_2 V 41 2 2 V У-

у /_1 2 ^ г Г 2 ^ г 7

/г/ 1е •=1 е •=1 ¿у . . ,л „

0 У (1 - г)(Л//2 - /) + Л//г

(1 - г)

(1 - г)

V

/

¿г.

Домножив обе части выражения для функции О(г) на (1 - г) получим

00

Д/г/ + £ Ьпгг

п=/+1

'-1 г

-2 V — /- 1 2 ^ г

г/ 1е •=1

(1 — г )2

-К0(2

Используя рассуждения, аналогичные приведённым в доказательстве Теоремы 3.1, можно получить соотношение

г-1

-2

Ьп = е ~<=11К0(1)п - | г/ 2е ^ 1 К0(г

г-1 - ^

+ 0(1)

2=1

'-1 '-1 '-1 -2 V 1 -2 V 1 -2 V 1

е г=11К0(1)п - /е г=11 К0(1) - е 1К0(1) + о(1).

2

Заметим что из определения Л/ следует, что

1

_2£ 1 Ко := е -=1-Ко(1)

г-1 1 г-1 г

_2 --г 2 - г-

= е

1

е

1

/1

х

((1 _ г)2 _ 2(1 _ г)г^ £/_1 + 2(1 _ г)£о + (1 _ г) ^ Ьпгп ¿г

п=1

' -1 г Г '-1 г '2 - 7 I ™/_2„_2 £ * Г е2£ V¿г

+ 2 Л//2 - / + / ж е -=1

о

'-1 1 ' -1 г _2£{ [ 2£ гт

_ 4е г=1 е г=1 о

/

£

х > г"

¿=1

/г/

1

-1 г -1 г _2£г-1 2^

е г=1 е г=1

о

\

¿у

(1 _ г)

(1 _ г)(Л//2 _ /) + Л//г (1 _ г)

V

/

¿г.

2

2

Написанное выше выражение для константы Ко можно записать следующим

образом

Ко = е г=1

'-1 1 '-1 г _2 Е1 2 £ г-

-=1

X

^((1 _ г)2 _ 2(1 _ г)г/) Я/_1 + 2(1 _ г+ (1 _ г) Е ¿г

+ 2 (Л//2 _ / + / ((/ _ 2)Л/ _ 2(/ _ 1)Л/ + 1))

'-1 1 ' -1 г _2£1 [ 2£ гт

- 4е г=1 е г=1 о

/

/

Е

хг

¿=1

/г/

-1 г -1 г _2 £ г- ^ 2 у У-

_1 г с ^ г 1

1е г=1 е г=1 «у „

о у (1 _ г)(Л//2 _ /) + Л//г

(1 - г)

(1 - г)

V

/

¿г.

е

2

2

Значит,

Ко = е г=1

'-1 1 '-1 г _2 е-Г 2 е г-

г=1

х ^((1 _ г)2 _ 2(1 _ г)г/) Я/_1 + 2(1 _ г)Яо + (1 _ г) Е ¿пгп^

Список литературы диссертационного исследования кандидат наук Крюков Николай Алексеевич, 2022 год

Литература

[1] Renyi A., "On a one-dimensional problem concerning space-filling" // Publications 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., "Renyi's parking problem revisited" // Stochastic and Dynamics. Vol. 2 (16). 1660006. 2016.

[5] Gerin L, "The Page-Renyi parking process" // Electronic Journal of Combinatorics. Vol. 4 (22). P4.4. 2015.

[6] ¡льенко А. Б., Фатенко В. В., "Узагальнення задачi Рены про парку-вання" // HayKOBi BicTi НТУУ «КП1» : м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 Jelenkovic 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"// arXiv: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.