В случае плотного вложения (для него известна верхняя оценка)
функции, представляющие верхнюю и нижнюю границы для веро-
ятностей, убывают при условии
n
→ ∞
экспоненциально быстро,
а множители в показателях экспонент для них заметно различают-
ся. Естественно полагать, что так же обстоит дело и для вложения
с допуском
d
2
. Поэтому особый интерес представляет изучение
скорости убывания вероятности
P
d
m
(
x
n
)
в среднем по всем отрез-
кам
x
n
.
В настоящей работе излагается подход, позволяющий получить
оценки снизу для математического ожидания (по любому заданно-
му распределению для знаков отрезка случайной последовательности
X
n
= [
X
1
, . . . , X
n
]
) вероятности вложения с допуском
d
отрезка после-
довательности
X
n
в случайную равновероятную последовательность.
Теорема 2.
Пусть
X
1
, X
2
, . . . , X
n
— независимые случайные ве-
личины, каждая из которых имеет распределение
P
X
на множестве
A
N
=
{
0
, . . . , N
−
1
}
.
Пусть
X
n
= [
X
1
, . . . , X
n
]
.
Пусть
Y
= [
Y
1
, Y
2
, . . .
]
— последовательность независимых случайных величин
,
равномерно
распределенных на
A
N
,
не зависящая от
X
n
.
Тогда для любых
k
на-
туральных чисел
r
1
, . . . , r
k
,
таких что
r
1
+
. . .
+
r
k
=
n,
E
P
X
P
d
(
d
+1)
n
(
X
n
)
k
i
=1
E
P
X
P
d
r
i
(
d
+1)
(
X
r
i
)
.
(4)
Оценка (4) используется в работе для получения оценок снизу
для средней вероятности плотного вложения и вложения с допус-
ком два отрезка двоичной последовательности длины
n
из диапазона
10
n
30
в начало равновероятной последовательности Бернулли.
Для плотного вложения значения наших нижних оценок оказались в
2–6 раз больше значений, вытекающих из оценок для минимальной
вероятности вложения. При этом указанное отношение возрастает с
увеличением параметра
n
. В то же время значения наших нижних
оценок оказались в 2–6 раз меньше значений, полученных из оценок
для максимальной вероятности вложения, в этом случае указанное от-
ношение также возрастает с увеличением параметра
n
. Похожая кар-
тина наблюдается и для вложения с допуском два. Однако здесь нет
возможности сравнить полученные оценки для средней вероятности
вложения с верхними оценками по причине отсутствия последних.
Доказательство теоремы 1.
Наряду с основным (описанным вы-
ше) способом вложения отрезка последовательности
x
n
в отрезок по-
следовательности
y
m
рассмотрим также вспомогательный способ. При
вспомогательном способе делаем следующее. Сравниваем знаки
x
1
и
y
1
, . . . , y
d
. Если при некотором
j
∈ {
1
, . . . , d
}
x
1
=
y
j
, то сч итает-
ся, что знак
x
1
“вставляется” на
j
-е место отрезка
y
m
(eсли знак
x
1
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012. № 2
5
