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