совпадает с несколькими из знаков
y
1
, . . . , y
d
, то
x
1
“вставляется” на
самую левую возможную позицию). В противном случае считаем, что
отрезок последовательности
x
n
не может быть вложен вспомогатель-
ным способом в
y
m
. Далее рассуждаем рекурсивно. Пусть знак
x
i
−
1
“вставлен” в
y
m
на
(
j
−
1)
-м месте. Если
x
i
=
y
j
, то “вставляем”
знак
x
i
на
j
-м месте отрезка
y
m
. Если
x
i
=
y
j
, x
i
=
y
j
+1
, то “вста-
вляем”
x
i
на
(
j
+ 1)
-м месте. Если
x
i
=
y
j
, x
i
=
y
j
+1
, x
i
=
y
j
+2
, то
“вставляем”
x
i
на
(
j
+ 2)
-м месте и так далее до знака
y
j
+
d
. Если же
x
i
=
y
j
, x
i
=
y
j
+1
, . . . , x
i
=
y
j
+
d
, то будем считать, что отрезок после-
довательности
x
n
не может быть вложен вспомогательным способом
в
y
m
.
Ясно, что если отрезок
x
n
может быть вложен в отрезок последо-
вательности
y
m
вспомогательным способом, то он может быть вложен
в него и основным способом. Поэтому вероятность
P
m
(
x
n
)
вложения
отрезка
x
n
в отрезок случайной последовательности
Y
m
вспомога-
тельным способом меньше или равна вероятности
P
d
m
(
x
n
)
вложения с
допуском
d
основным способом.
Лемма 1.
Если отрезок последовательности
x
n
состоит из
n
оди-
наковых знаков
,
то вероятности вложения
x
n
в отрезок случайной
равновероятной последовательности
Y
m
основным и вспомогатель-
ным способами совпадают.
Поэтому нижняя оценка вероятности
P
d
m
(
x
n
)
достигается для та-
ких
x
n
.
Доказательство леммы 1.
Рассмотрим отрезок
x
n
= [
a, . . . , a
]
,
который может быть вложен в отрезок последовательности
Y
m
основ-
ным способом. В этом случае множество
{
1
i m
:
Y
i
=
a
}
состоит
не менее, чем из
n
элементов, причем первые
n
из них удовлетворяют
условию (2). Следовательно, знаки отрезка
x
n
могут быть “вставле-
ны” именно на эти первые места. Это означает, что
x
n
вкладывается
в отрезок последовательности
Y
m
вспомогательным способом.
Как мы уже отмечали, если отрезок
x
n
может быть вложен в отре-
зок последовательности
Y
m
вспомогательным способом, то он может
быть вложен в него и основным способом. Таким образом, вероят-
ности вложить
x
n
указанного вида в отрезок последовательности
Y
m
обоими способами совпадают. Лемма 1 доказана.
Вычислим вероятность вложения отрезка последовательности
x
n
в
Y
m
вспомогательным способом. Обозначим через
D
m
(
x
n
)
число де-
терминированных отрезков последовательностей
y
m
= [
y
i
]
m
i
=1
,
в кото-
рые данный отрезок
x
n
может быть вложен вспомогательным спосо-
бом.
6
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012. № 2
