МАТЕМАТИКА
УДК 519.119
Н. М. М е ж е н н а я, В. Г. М и х а й л о в
НИЖНИЕ ОЦЕНКИ ДЛЯ ВЕРОЯТНОСТИ
ВЛОЖЕНИЯ С ПРОИЗВОЛЬНЫМ ДОПУСКОМ
Дано обобщение понятия плотного вложения, введенного
Дж. Голичем. Выведены оценки снизу для математического ожи-
дания вероятности вложения с заданным допуском отрезка после-
довательности независимых одинаково распределенных случайных
величин над алфавитом из
N
элементов в начало последовательно-
сти независимых случайных величин, имеющих равномерное распре-
деление на том же алфавите. Эти оценки уточняют известные
оценки для вероятности вложения с заданным допуском и, в част-
ности, для вероятности плотного вложения.
E-mail:
;
Ключевые слова
:
вложение с допуском, последовательность над конеч-
ным алфавитом, нижние оценки.
В работе [1] Дж. Голичввел следующее понятие плотного вложе-
ния последовательности над некоторым алфавитом в начало другой
последовательности над тем же алфавитом. Отрезок последователь-
ности
x
n
= [
x
1
, . . . , x
n
]
плотно вкладывается в отрезок последователь-
ности
y
m
= [
y
1
, . . . , y
m
]
,
если
n m
и найдутся такие натуральные
числа
1 =
j
1
< j
2
< . . . < j
n
m, j
k
+1
−
j
k
∈ {
1
,
2
}
, k
= 1
, . . . , n
−
1
,
(1)
что
x
k
=
y
j
k
, k
= 1
, . . . , n
. Здесь и далее будет использоваться за-
пись
[
z
1
, z
2
, . . . , z
m
]
для обозначения отрезка из первых
m
элементов
последовательности
z
1
, z
2
, . . .
.
В работе [1] получена верхняя граница значений вероятности плот-
ного вложения отрезка заданной двоичной последовательности
x
n
в начало равновероятной последовательности Бернулли и показано,
что эта граница достигается на альтернирующих двоичных после-
довательностях. В работе [2] эта оценка была обобщена на случай
последовательностей над произвольным конечным множеством. При
этом оказалось, что верхняя граница вероятности плотного вложения
отрезка заданной последовательности в начало равновероятной по-
следовательности достигается на последовательностях, в которых нет
совпадений соседних букв. Там же получена нижняя граница для этой
вероятности, она достигается на последовательностях, составленных
из одинаковых знаков.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012. № 2
3
