ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 56

2020

Вып. 2

УДК 621.391.1 : 519.2

М.В. Бурнашев

НОВЫЕ ГРАНИЦЫ В ЗАДАЧЕ ПРОВЕРКИ ГИПОТЕЗ

С ИНФОРМАЦИОННЫМИ ОГРАНИЧЕНИЯМИ¹

Рассматривается задача проверки гипотез, в которой мы не можем наблю-

дать часть данных. Наш помощник наблюдает пропущенные данные и может

передать нам некоторую ограниченную информацию о них. Какая ограничен-

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

В частности, какая минимальная информация достаточна для получения тех

же результатов, как если бы мы непосредственно наблюдали все данные? По-

лучены оценки для величины этой минимальной информации и некоторые по-

добные результаты.

Ключевые слова: проверка гипотез, информационные ограничения, вероятности

ошибки.

DOI: 10.31857/S0555292320020023

§ 1. Введение и основные результаты

1. Постановка задачи. Как и в [1,2], на длине n рассматривается двоичный сим-

метричный канал ДСК(p) с входным и выходным алфавитами E = {0, 1} и неизвест-

ной переходной вероятностью p. Для различения входного и выходного множеств

блоков Eⁿ = {0, 1}ⁿ канала будем обозначать их через Enin и Enout соответственно.

Относительно величины p имеются две гипотезы (одна из которых верна): H₀ : p = p₀

и H₁: p = p₁, где 0 < p₀,p₁ ≤ 1/2.

Обозначим через P(y |x) и Q(y |x) вероятности получить на выходе канала блок

y = (y₁,...,y_n) при условии, что входным был блок x = (x₁,...,x_n) для гипотез H₀

и H₁ соответственно. Тогда

P(y | x) = (1 - p₀)n-d(x,y)pd(x,y)0, Q(y | x) = (1 - p₁)n-d(x,y)pd(x,y)1,

где d(x, y) - расстояние Хэмминга между блоками x и y (т.е. число несовпадающих

компонент этих векторов на всей длине n).

Рассматривается следующая задача минимаксного различения гипотез H₀ и H₁.

Мы (т.е. “статистик”) наблюдаем только блок y ∈ Enout на выходе канала, а наш по-

мощник (“helper”) наблюдает только блок x ∈ Enin на входе канала. Предполагается,

что у нас нет никакой априорной информации о входном блоке x. Ясно, что основы-

ваясь только на выходном блоке y, мы не можем сделать никаких содержательных

заключений относительно неизвестной величины p.

Предположим далее, что для заданной величины R > 0 нашему помощнику раз-

решается заранее разбить все входное пространство Enin = {0, 1}ⁿ на N ≤ 2^Rn произ-

вольных частей {X₁, . . ., X_N } и сообщить нам (каким-то дополнительным образом)

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номер проекта 19-01-00364).

только то, какой части X_i принадлежит входной блок x. Ясно, что только случай

N < 2ⁿ, т.е. R < 1, является интересным (иначе помощник может просто сообщить

нам блок x).

Например, помощник может сообщить статистику точные значения первых Rn

величин x₁, . . . , x_Rn (но тогда ничего не сообщить о последующих величинах x_i).

Однако такой простой способ разбиения входного пространства Enin (на цилиндри-

ческие множества {X_i}) не является, вообще говоря, оптимальным. С точки зрения

статистика входные данные (x₁, . . . , x_n) представляют собой очень сильный мешаю-

щий вектор.

Есть много практических ситуаций, где встречается подобная задача. Например,

в некоторых приложениях входной блок x ∈ Enin представляет собой “мешающий

шум”, который “загрязнил” выходной блок y ∈ Enout, и поэтому нам хотелось бы

“уменьшить” (по возможности) это “загрязнение”, для того чтобы улучшить стати-

стические выводы. Конечно, при этом очень важно качество канала связи от помощ-

ника к статистику. Для упрощения задачи мы рассматриваем здесь только идеали-

зированный случай бесшумного канала с ограниченной пропускной способностью.

Можно также сказать, что оптимальная ограниченная информация о блоке

x ∈ Enin означает оптимальное “сжатие” полной информации о блоке x. Конечно,

это оптимальное “сжатие” зависит от имеющейся априорной информации о переход-

ной вероятности p и используемого критерия качества.

Замечание 1. Ясно, что задача не изменится, если, наоборот, статистик наблю-

дает вход, а помощник - выход канала.

Основываясь на наблюдении y ∈ Enout и номере (индексе) i части X_i, статистик

принимает решение в пользу одной из гипотез H₀ или H₁. Для того чтобы избежать

излишних усложнений, рассмотрим только нерандомизованные методы принятия

решения (при этом существо задачи и результаты сохраняются).

Нас интересуют разбиения {X₁, . . ., X_N } и методы принятия решения, которые

являются асимптотически (при n → ∞) оптимальными. Аналогичные, но значи-

тельно более общие постановки такой задачи рассматривались, например, в [3-8].

Замечание 2. Забегая вперед, отметим, что насколько нам известно, все резуль-

таты в этой области (см., например, [1-8]) имеют вид “можно получить следующие

характеристики проверки гипотез: . . . ”. Нашей целью являются противоположные

результаты, т.е. показать, что “нельзя получить характеристики лучше, чем . . . ”.

Всюду далее log x = log₂ x. Введем шары и сферы в Eⁿ:

B_x(p) = {u : d(x, u) ≤ pn},

x, u ∈ Eⁿ.

(1)

S_x(p) = {u : d(x, u) = pn},

2. Экспоненты вероятностей ошибки и дуальная задача. Пусть выбрано разби-

ение {X₁, . . . , X_N } входного пространства Enin = {0, 1}ⁿ. Тогда общее правило при-

нятия решения можно описать следующим образом. Для каждого элемента разби-

ения X_i выбирается некоторое множество A(X_i) ⊂ Enout, и далее, основываясь на

наблюдении y и известном X_i, принимается решение (A^c = Enout \ A):

y ∈ A(X_i) =⇒ H₀, y ∈ A^c(X_i) =⇒ H₁.

Определим вероятности ошибки 1-го рода α_n и 2-го рода β_n:

α_n = Pr(H₁ |H₀) = max

max P (A^c(X_i) | x) ,

i=1,...,N

x∈Xi

β_n = Pr(H₀ |H₁) = max

max Q (A(X_i) | x) .

i=1,...,N

x∈Xi

Пусть далее γ ≥ 0 - заданная величина. Будем требовать, чтобы для вероятности

ошибки 1-го рода α_n выполнялось условие

α_n = Pr(H₁ |H₀) ≤ 2^-γn.

(2)

Нас интересует минимально возможная (по всем разбиениям {X_i} входного про-

странства Enin и всем решениям) вероятность ошибки 2-го рода min β_n. Мы иссле-

дуем асимптотический случай, когда n → ∞ и N = 2^Rn, где 0 < R < 1 - заданная

постоянная². Тогда для наилучших разбиения {X_i} и решения обозначим

e(γ, R) = lim

log₂

> 0,

(3)

n→∞ n

min β_n

где минимум берется по всем разбиениям {X_i} и решениям, удовлетворяющим усло-

вию (2).

Основной нашей целью являются оценки сверху для функции e(γ, R) (оценки

снизу см. в [1]). В данной статье мы ограничиваемся случаем γ → 0, исследуя функ-

цию e(0, R) = e(R) и связанную с ней функцию r_crit(p₀, p₁) (иногда этот случай

называют задачей Неймана - Пирсона). В отдельной работе мы рассмотрим случай

γ > 0.

Для нас будет удобно рассмотреть также эквивалентную дуальную задачу (без

помощника). Пусть задана величина r, 0 < r < 1, и нам разрешается заранее вы-

брать любое множество X ⊂ Enin, состоящее из X = 2^rn входных блоков. Известно

также, что входной блок x принадлежит выбранному множеству X . Мы наблюдаем

выход канала y и, зная множество X , рассматриваем задачу проверки гипотез H₀

и H₁. Далее мы выбираем множество A и в зависимости от наблюдения y принимаем

решение:

y ∈ A =⇒ H₀, y ∈ A^c =⇒ H₁.

Вероятности ошибок 1-го рода α_n и 2-го рода β_n определяются как

α_n = maxP (Ac | x) , βn = max Q (A | x) .

x∈X

Пусть для вероятности ошибки 1-го рода α_n выполняется условие (2), и мы хотим

выбрать множество X ⊂ Enin мощности X = 2^rn и правило принятия решения та-

ким образом, чтобы достичь минимально возможной вероятности ошибки 2-го рода

min β_n. Для этой дуальной задачи аналогично (3) определим функцию

e_d(γ, r) = lim

log₂

> 0,

(4)

n→∞ n

min β_n

где минимум берется по всем множествам X ⊂ Enin мощности X = 2^rn и всем реше-

ниям.

Следующий результат устанавливает простую связь между функциями e(γ, R) и

e_d(γ, r).

Предложение 1 [1, предложение 1]. Справедливо соотношение

e(γ, 1 - R) = e_d(γ, R),

0 ≤ R ≤ 1, γ ≥ 0.

(5)

В силу предложения 1 и формулы (5) достаточно исследовать функцию e_d(γ, r).

В данной статье мы ограничимся случаем γ → 0, исследуя функцию e_d(0, r).

² Для упрощения формул здесь и далее не будем использовать знак целой части.

Замечание 3. По существу в статье рассматривается случай, когда распределе-

ния P (x, y) и Q(x, y) имеют вид P (x, y) = p(x)P (y | x) и Q(x, y) = p(x)Q(y | x), где

распределение p(x) одно и то же для P (x, y) и Q(x, y). В более общей постановке

задачи это может быть не так.

3. Известный входной блок. Предположим, что мы знаем входной блок x ∈ Enin

(тогда можно считать, что x = 0) и наблюдаем выходной блок y ∈ Enout. Если тре-

буется только α_n → 0, n → ∞ (т.е. γ = 0), и нас интересует только экспонента (по n)

вероятности ошибки 2-го рода β_n, то при n → ∞ в силу центральной предельной

теоремы (или в силу леммы Неймана - Пирсона) оптимальным множеством реше-

ния в пользу H₀ (т.е. p₀) является сферический слой B₀(p₀ + δ) \ B₀(p₀ - δ) в Enout

(см. (1)), где δ > 0 мало. Тогда для экспоненты (по n) вероятности ошибки 2-го

рода β_n имеем

[(

)

]

log β_n =

log

(1 - p₁)(1-p0)ⁿpp0n

+ o(1), n → ∞,

p₀n

и поэтому при n → ∞ получаем

log

= -(1 - p₀)log(1 - p₁) - p₀ log p₁ - h(p₀) + o(1) = D(p₀ ∥p₁) + o(1),

(6)

β_n

где h(p) = -p log p - (1 - p) log(1 - p) и

1-a

D(a ∥ b) = a log

+ (1 - a) log

(7)

1-b

Замечание 4. Величина D(a∥b) из (7) представляет собой расхождение (diver-

gence) для двух бернуллиевских случайных величин с параметрами a и b соответ-

ственно. В русскоязычной литературе D(a ∥ b) чаще называется расстоянием Куль-

бака - Лейблера. Величина D(a∥b) дает наилучшую экспоненту для вероятности

ошибки 2-го рода при заданной вероятности ошибки 1-го рода (т.е. когда ее экс-

понента равна нулю) при проверке простой гипотезы H₀ : p = a против простой

альтернативы H₁ : p = b.

При γ = r = 0 для величины e_d(0, 0) (см. (4)) из (6) получаем

e_d(0, 0) = D(p₁ ∥p₀).

(8)

4. Неизвестный входной блок и критическая скорость. Если мы знаем входной

блок x ∈ Enin и α_n → 0, то наилучшая экспонента e_d(0, 0) вероятности ошибки 2-го

рода β_n дается формулой (8).

Если же мы знаем только, что входной блок x принадлежит множеству X ⊆ Enin

мощности X ∼ 2^rn, то для наилучшего такого множества X экспонента e_d(0, r)

вероятности ошибки 2-го рода β_n определяется формулой (4). Ясно, что

e_d(γ, r) ≤ e_d(γ, 0), γ ≥ 0,

0 ≤ r ≤ 1.

(9)

Функция e_d(γ, r) не возрастает по r. Поэтому возникает естественный вопрос:

существует ли r(γ) > 0, для которого в (9) выполняется равенство, и если да, то

какова максимальная такая скорость r_crit(γ)? Ограничиваясь случаем γ = 0, опре-

делим r_crit(p₀, p₁) = r_crit(p₀, p₁, 0) как (см. (8))

rcrit = rcrit(p0, p1) = sup{r : ed(0, r) = ed(0, 0) = D(p0 ∥ p1)}.

(10)

Иными словами, какова наибольшая мощность 2^rn “наилучшего” множества X ,

для которого можно достичь такой же асимптотической эффективности, как и при

известном входном блоке x (хотя мы и не знаем входной блок x)?

Аналогично введем критическую скорость R_crit для исходной задачи (см. (3))

R_crit(p₀, p₁) = inf{R : e(0, R) = e(0, 1) = D(p₀ ∥p₁)}.

(11)

В силу предложения 1 и (11) имеем

R_crit(p₀, p₁) = 1 - r_crit(p₀, p₁).

(12)

Основной результат статьи составляет

Теорема 1. Если p₁ < p₀ ≤ 1/2, то существует p∗1(p₀) ≤ p₀, такое что для

любого p₁ ≤ p∗1(p₀) справедлива формула

rcrit(p0, p1) = 1 - Rcrit(p0, p1) = 1 - h(p0),

0 < p₁ ≤ p∗1 < p₀ ≤ 1/2.

(13)

Замечание 5. Хотя величина r_crit(p₀, p₁) в (13) совпадает с пропускной способ-

ностью канала ДСК(p₀), ее происхождение (10) связано с функцией e_d(0, r), ана-

логичной функции надежности E(r, p) в теории информации [9, 10]. При этом точ-

ный вид функции E(r, p) до сих пор известен только частично [11]. Поэтому, как и

в [11-13], в доказательстве теоремы 1 используются достаточно недавние результа-

ты о спектре двоичных кодов. Полное описание функции e_d(γ, r) выглядит трудной

задачей.

В §2 приводится граница снизу для r_crit (предложение 2). В §3 выводится общая

формула для вероятности ошибки 2-го рода β_n (лемма 1). В § 4, используя метод

“двух гипотез”, доказывается теорема 1. Но граница сверху (13) для r_crit, вообще

говоря, слабее соответствующей границы снизу из § 2. В § 5 с помощью дополни-

тельных комбинаторных соображений выводится еще одна граница сверху для r_crit

(предложение 3). В § 6 показывается точность границы снизу для r_crit из предложе-

ния 2 при условии, что выполняется некоторое дополнительное условие. В Прило-

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

В статье f ∼ g означает, что n-1 lnf = n-1 lng + o(1), n → ∞, а f ≲ g означает

n-1 lnf ≤ n-1 lng + o(1), n → ∞.

§ 2. Граница снизу для r_crit

Следующий результат следует из [1, предложение 2].

Предложение 2. Для r_crit(p₀,p₁) справедливы оценки снизу

rcrit(p0, p1) ≥ 1 - h(p0), если

0 < p₁ < p₀ ≤ 1/2,

(14)

rcrit(p0, p1) ≥ 1 - h(p0) - D(p0 ∥ p1), если

0 < p₀ < p₁ ≤ 1/2.

(15)

Доказательство. Для заданного r, 0 < r < 1, выберем случайно и равно-

вероятно множество X из X = 2^rn входных блоков x. В [1, предложение 2] было

показано, что если p₀ < p₁ ≤ 1/2, то для любого τ, p₀ ≤ τ ≤ p₁, существует множе-

ство X и метод принятия решения, для которого выполняются неравенства

log

≥ D(τ ∥p₀),

log

≥ min{D(τ ∥ p₁), 1 - h(τ) - r}.

(16)

α_n

β_n

Если достаточно иметь α_n → 0, n → ∞, то полагая в (16) τ = p₀, из (10) получа-

ем (15).

Аналогично, если p₁ < p₀ ≤ 1/2, то меняя в (16) местами p₀ с p₁ и α_n с β_n, для

любого τ имеем

log

≥ min{D(τ ∥ p₀), 1 - h(τ) - r},

log

≥ D(τ ∥p₁).

(17)

α_n

β_n

Если α_n → 0, n → ∞, то полагая в (17) τ = p₀, из (10) получаем (14). ▴

§3. Общая формула для вероятности ошибки 2-го рода β_n

Пусть C_n(r) = {x₁, . . . , x_M } - множество (код) из M = 2^rn различных входных

(кодовых) блоков. Для кода C_n(r) и вероятности ошибки 1-го рода α_n обозначим

через D₀ = D₀(C_n, α_n) ⊆ Enout оптимальное множество решения в пользу H₀, мини-

мизирующее вероятность ошибки 2-го рода β_n. Хотя множество D₀ имеет довольно

сложный вид, можно установить некоторые его свойства, достаточные для доказа-

тельства теоремы 1.

Выберем малое δ > 0, и для каждого x_k, k = 1, . . . , M, введем сферический слой

вEnout

SLxk(p₀,δ) = Bxk(p₀ + δ) \ Bxk(p₀ - δ) = {u : |d(x_k,u) - p₀n| ≤ δn},

(18)

где B_x(p) определено в (1). Для каждого x_k введем также множество

Dxk(δ) = D₀ ∩ SL_x

(p₀, δ).

(19)

Так как необходимо иметь α_n → 0, n → ∞, то оптимальное множество D₀ содержит

“существенную” часть каждого множества SLxk(p₀, δ), k = 1, . . ., M. Для того чтобы

оценить это, заметим, что для любых x_k и u, z ∈ SL_x

(p₀, δ) имеем

)d(z,xk)-d(u,x_k)

P(u | p₀, x_k)

⁽q₀

≤

⁽q₀)2δn, q₀ =1-p₀.

(20)

P(z | p₀, x_k)

p₀

По экспоненциальному неравенству Чебышева (граница Чернова) для любого x_k и

малых δ > 0 получаем

nδ

log P{u ∈ SLxk (p₀, δ) | x_k, p₀} ≤ -

(21)

2p₀q₀

Тогда в силу (18), (19) и (21) для любого x_k имеем

P{Dxk(δ)|p₀, x_k} ≥ 1 - P{u ∈ D₀ |p₀, x_k} - P{u ∈ SL_x

(p₀, δ) | p₀, x_k} ≥

≥1-α_n -e-n2δ²/(2p0q⁰),

(22)

а в силу (20) также имеем

δ₁|SL_x

(p₀, δ)| ≤ |Dxk (δ)| ≤ |SLxk (p₀, δ)|,

(

)2δn

(

)

p₀

(23)

δ₁ =

1-β_n -e-n2δ²/(2p0q⁰)

q₀

Так как D_x

(δ) ⊆ D₀ для любого x_k, то в силу (19), (22) и (23) для вероятности

P(e | p₁, x_i) имеем

{

}

⋃

P(e | p₁, x_i) = P{D₀ | p₁, x_i} ∼ P

D_x

(δ) | p₁, x_k

∼

k=1

{

}

⋃

∼δ₁P

SL_x

(p₀, δ) | p₁, x_i

(24)

k=1

Для t > 0 и каждого x_i введем множество

Dxi(t, p) =

= {u : существует x_k = x_i, такое что d(x_i, u) = tn, d(x_k, u) = pn} .

(25)

Лемма 1. Для вероятности ошибки 2-го рода β_n кода C_n = {x₁,...,x_M} и оп-

тимального решения D₀ в пользу H₀ при n → ∞ справедлива формула

{

[

]

}

∑

log β_n

∼ max

log

|D_x

(t, p₀)|

+ tlogp₁ + (1 - t)log(1 - p₁)

(26)

t>0

i=1

Критическая скорость r_crit(p₀, p₁) определяется формулой (M = 2^rn)

rcrit(p0, p1) = sup {r : F (p0, p1, r) ≤ 0} = inf {r : F (p0, p1, r) > 0} ,

(27)

где

F (p₀, p₁, r) = lim

min

maxF (p0, p1, r, Cn, t),

n→∞

|Cn|≤M

[

]

∑

(28)

1-p₁

F (p₀, p₁, r, C_n, t) =

log

|Dxi (t, p₀)|

+ (p₀ - t) log

- r - h(p₀).

p₁

i=1

Доказательство. Используя (24) при δ = o(1) и δ₁ = eo(n) при n → ∞, имеем

∑

β_n = max

P(e | p₁, x_i) ∼

i=1

{

}

∑

⋃



δ₁

∼

SLxk(p₀,δ)p1, xi

(29)

i=1

k=1

Из (25) и (26) для каждого x_i

{

}

⋃



{⋃



SLxk(p₀,δ)p1, xi

∼P

Dxi(t, p₀)p1, xi

∼

k=1

t>0

{

}

∼ max

ptn1(1 - p₁)(1-t)n|D_x

(t, p₀|

(30)

t>0

Поэтому из (29) и (30) следует формула (26).

Так как

P{SLxi(p₀, δ)|p₁, x_i} ∼ P{d(x_i, u) ≥ p₀n|p₁, x_i} ∼ 2-D(p0 ∥p1)ⁿ,

то правая часть (26) возрастает по r (т.е. по M = 2^rn), начиная с -D(p₁ ∥p₀). По-

этому из (6) и (26) следует, что критическая скорость r_crit равна максимальной

скорости r, такой что

{

[

]

}

minmax

log

|Dxi (t, p₀)|

+ tlogp₁ + (1 - t)log(1 - p₁)

-r≤

{xi}

t>0

i=1

≤ -D(p₀ ∥p₁).

(31)

Заметим, что

1-p₁

D(p₀ ∥ p₁) + t log p₁ + (1 - t) log(1 - p₁) = -h(p₀) + (p₀ - t) log

(32)

p₁

Из (31) и (32) следуют формулы (27), (28). ▴

Отметим, в частности, что из (53) при t = p₀ имеем

F (p₀, p₁, r, C_n, p₀) = o(1), n → ∞.

В анализе соотношений (27), (28) основную трудность составляет оценка мощно-

стей |D_x

(t, p₀)| в (28), которые зависят от геометрии кода C_n. Аналогичная проблема

возникала в [11-13] при исследовании функции надежности E(R, p) канала ДСК(p).

Прямая оценка этих мощностей ведет к весьма громоздким формулам.

§ 4. Граница сверху для r_crit: две гипотезы

Получим простую (но не очень точную) оценку сверху для r_crit(p₀, p₁), используя

популярный в математической статистике (чаще в теории оценивания) метод “двух

гипотез”. Используя для этого формулу (26), выберем из кода C_n(r) = {x₁, . . . , x_M },

M = 2^rn, какие-либо два кодовых слова, скажем, x₁ и x₂ с d(x₁,x₂) = ωn. Можно

считать, что для скорости r > 0 величина ω удовлетворяет ограничениям

0 < ω ≤ ω_min(r),

где величина ω_min(r) будет определена далее. Заменим код C_n(r) кодом C^′ из двух

выбранных кодовых слов C^′ = {x₁, x₂}. Тогда β_n(C) ≥ β_n(C^′). Аналогично (29), (30)

имеем

{



}

β_n(C^′) ∼ 2-D(p0 ∥p1)ⁿ + P

SLx2(p₀,δ)p1, x1

Нас интересует, когда для x₁, x₂ справедливо неравенство

{



}

log P

SLx2(p₀,δ)p1, x1

> -D(p₀ ∥p₁).

(33)

Оценим вероятность в левой части (33). Для d(x_i, x_k) = ωn обозначим

Sxi,x_k (t, p, ω) = {u : d(xi, u) = tn, d(xk, u) = pn, d(xi, xk) = ωn}.

(34)

Тогда (см. Приложение)

log |Sxi,x_k (t, p, ω)| = g(t, p, ω) + o(1), n → ∞,

(35)

{



}

1-p₁

log P

Sxi,x_k (t, p, ω)p1, xi

= g(t, p, ω) - t log

+ log(1 - p₁) + o(1),

p₁

где g(t, p, ω) определено в (78). Поэтому при n → ∞ (см. (76), (77))

{



}

log P

SL_x

(p₀, δ)p1, x1

{



}

maxlog P

S_x

1,x2 (^t,p0,ω)

^p₁, x₁

+ o(1) = f(p₀, p₁, ω) + o(1),

(36)

где

f (p₀, p₁, ω) = maxf (p0, p1, ω, t),

1-p₁

(37)

f (p₀, p₁, ω, t) = g(t, p₀, ω) - t log

+ log(1 - p₁).

p₁

Имеем

ω-t

p₀ + t - ω

1-p₁

f^′t(p₀, p₁, ω, t) = log

- log

-2

f^′′tt(p₀, p₁, ω, t) < 0.

(38)

1-p₀ -t

p₁

В силу (32) и (35)-(37) неравенство (33) принимает вид

maxF (p0, p1, ω, t) > 0,

(39)

где

F (p₀, p₁, ω, t) = f(p₀, p₁, ω, t) + D(p₀ ∥ p₁) =

1-p₁

= g(t, p₀, ω) + (p₀ - t)log

- h(p₀).

(40)

p₁

Если для каких-либо p₀, p₁ и ω выполняется неравенство (39), то справедлива

соответствующая граница сверху (14), (15). Обозначим через t⁰¹ = t⁰¹(p₀, p₁, ω) мак-

симизирующую величину t в (37) (она же остается максимизирующей в (39)). Тогда

f (p₀, p₁, ω) = f(p₀, p₁, ω, t⁰¹(p₀, p₁, ω)).

(41)

Из уравнения f^′t(p₀, p₁, ω, t) = 0 для t⁰¹ из (38) получаем

√

1 + (v₀ - 1)[(ω - p₀)²v₀ - (1 - ω - p₀)² + 1] - 1

t⁰¹ = t⁰¹(p₀, p₁, ω) =

v₀ - 1

(

)₂

(42)

1-p₁

v₀(p₁) =

≥ 1.

p₁

Тогда из (40) и (42) имеем

1-p₁

F (p₀, p₁, ω, t⁰¹) = g(t⁰¹, p₀, ω) + (p₀ - t⁰¹) log

- h(p₀).

(43)

p₁

Можно проверить, что для функции F (p₀, p₁, ω, t⁰¹) из (43) вытекают свойства

F (p₀, p₁, 0, t⁰¹) = 0 и F^′′ωω < 0, ω > 0. Поэтому достаточно проверить неравенство (39)

c t = t⁰¹ только для минимальной для кода C_n(r) величины ω (т.е. для его кодового

расстояния d(C)).

Пусть ω_min(r)n - максимально возможное минимальное расстояние кода C_n(r).

Для величины ω_min(r) известна граница [14, формула (1.5)]

]

^[1

√

r≤h

ω_min(1 - ω_min) ,

ω_min = ω_min(r).

(44)

Рассмотрим два возможных случая: 1) p₁ < p₀ ≤ 1/2 и 2) p₀ < p₁ ≤ 1/2.

1) Случай p₁ < p₀ ≤ 1/2. Полагая r = 1 - h(p₀), обозначим через ω₀ = ω₀(p₀)

корень уравнения (см. (44))

]

√

^[1

1 - h(p₀) = h

ω(1 - ω) .

Тогда неравенство (39) принимает вид (ω₀ = ω₀(p₀))

1-p₁

F (p₀, p₁, ω₀, t⁰¹) = g(t⁰¹, p₀, ω₀) + (p₀ - t⁰¹) log

- h(p₀) > 0.

(45)

p₁

Можно проверить (с помощью Maple), что (45) выполняется, если p₁ ≤ p∗1(p₀),

где

p₀

0,1

0,12

0,15

0,2

0,3

0,4

0,45

0,49

p∗1(p₀)

0,0003

0,003

0,016

0,056

0,17

0,317

0,4

0,48

Если p₀ ≤ 0,20707 (т.е. ω < 0,273), то в [14, формула (1.4)] имеется оценка чуть

более точная (но более громоздкая), чем (44).

2) Случай p₀ < p₁ ≤ 1/2. Можно проверить, что неравенство (39) не выполня-

ется ни при каких p₀ < p₁!

§5. Граница сверху для r_crit: комбинаторика

Приведем еще одну границу сверху для r_crit, по-прежнему основанную на фор-

муле (26), но использующую дополнительные комбинаторные соображения.

1. Комбинаторная лемма. В коде C_n = {x_i} будем называть (x_i, x_j) ω-парой, если

d(x_i, x_j ) = ωn. Будем говорить, что точка y ∈ Eⁿ является (ω, p, t)-покрытой, если

существует ω-пара (x_i, x_j), такая что d(x_i, y) = pn, d(x_j, y) = tn. Обозначим через

K(y, ω, p, t) число (ω, p, t)-покрытий точки y (учитывая кратность покрытий), т.е.

K(y, ω, p, t) =

= |{(x_i,x_j) : d(x_i,x_j) = ωn, d(x_i,y) = pn, d(x_j,y) = tn}|, ω > 0.

(46)

Введем множества (ср. (25))

⋃

Dxi(t, p, ω) = Sxi,x_k (t, p, ω) = {u : существует xk,

x_k

такое что d(x_i, x_k) = ωn, d(x_i, u) = tn, d(x_k, u) = pn}.

(47)

Тогда

⋃

Dxi(t, p) =

Dxi(t, p, ω).

ω>0

Для t > 0 введем величину

m_t(y) = |{x_i : x_i ∈ S_y(t)}|.

(48)

Тогда для любых y, p, t > 0

K(y, t, p) = m_t(y)m_p(y).

(49)

Лемма 2. Для кода {x_i} и ω,p,t > 0 справедлива формула (cм. (46) и (47))

∑

|Dxi (t, p, ω)| ≤

K(y, ω, t, p).

(50)

i=1

y∈Eⁿ

Также, если (cм. (48))

maxmp(y) = 2o(n), n → ∞,

(51)

то для любых ω, t > 0

∑

|Dxi(t, p, ω)| = 2o(n)

K(y, ω, t, p), n → ∞.

(52)

i=1

y∈Eⁿ

Доказательство. Пусть y ∈ Eⁿ и имеется m упорядоченных пар (x_i,x_j)

с d(x_i, x_j ) = ωn и d(x_i, y) = tn, d(x_j , y) = pn. Эти m пар (x_i, x_j ) имеют m₁ ≤ m

различных первых аргументов {x_i}. Тогда y присутствует m раз в правой части (50)

и m₁ раз в левой части, что доказывает формулу (50). Если выполнено условие (51),

то m₁ = meo(n), откуда следует равенство (52). Отметим также, что в силу (49)

имеем

∑

K(y, t, p)

∑

|Dxi (t, p)| =

m_t(y) ∼

m_p(y)

i=1

y: mp(y)≥1

∑

∼M2h(t)n -

m_t(y).

(53)

y: mp(y)=0

Из первого равенства в (53) также следуют формулы (50) и (52). ▴

Формула (53) выглядит простой и привлекательной, однако ее правая часть имеет

вид “большое минус большое”, что неудобно. Отметим, что в (53) нельзя пренебре-

гать последней суммой, так как тогда получим только r_crit ≤ 1, что неинтересно.

2. Еще одна граница сверху для r_crit. Оценим сверху последнюю сумму в (53)

следующим образом. Имеем

∑

m_t(y) ≤ 2h(t)n|{y : mp0 (y) = 0}|.

(54)

y: mp₀(y)=0

Максимум мощности |{y : mp0(y) = 0}| достигается, когда код C является шаром

B₀(τ) радиуса τn, где r = h(τ). Поэтому

max|{y : mp0 (y) = 0}| = 2n - |B0(τ + p0)| ∼ 2h(τ+p0)n, τ + p0 ≥ 1/2,

(55)

max|{y : mp0 (y) = 0}| ∼ 2n, τ + p0 ≤ 1/2.

Если τ + p₀ ≥ 1/2, т.е. если r ≥ h(1/2 - p₀), то из (53)-(55) получаем

∑

[

]

[

]

|Dxi (t, p₀)| ≥ 2h(t)n

M -2h(τ+p0)ⁿ

=2h(t)n

2h(τ)n - 2h(1-τ-p0)ⁿ

∼M2h(t)n,

i=1

если τ > 1 - τ - p₀, т.е. τ > (1 - p₀)/2, или, эквивалентно, если r > h[(1 - p₀)/2].

Поэтому если r ≥ max{h(1/2 - p₀), h[(1 - p₀)/2]} = h[(1 - p₀)/2], то при любом

p₀ = p₁ равенство (28) принимает вид

{

}

1-p₁

F (p₀, p₁, r) = max

h(t) + (p₀ - t) log

- h(p₀) =

t>0

p₁

1-p₁

= h(p₁) + (p₀ - p₁)log

- h(p₀) > 0, p₀ = p₁,

p₁

так как максимум по t достигается при t = p₁. Поэтому это дает следующую границу

сверху для r_crit (более слабую, чем (13)):

rcrit(p0, p1) ≤ h[(1 - p0)/2], p0 = p1.

(56)

Замечание 6. Отметим, что 1 - h(p₀) < h(1/2 - p₀) < h[(1 - p₀)/2], 0 < p₀ < 1/2.

Усилим оценку (56). Наряду с (54) также имеем

∑

m_t(y) ≤ M|{y : mp0(y) = 0}|.

y: mp₀(y)=0

Поэтому если τ + p₀ ≥ 1/2 и t ≥ 1 - τ - p₀, то

∑

[

]

|Dxi (t, p₀)| ≥ M

2h(t)n - 2h(1-τ-p0)ⁿ

∼M2h(t)n.

i=1

В силу (39), (40) необходимо иметь

max f(t, p₀, p₁) > 0,

t≥1-τ -p0

1-p₁

(57)

f (t, p₀, p₁) = h(t) + (p₀ - t) log

- h(p₀).

p₁

Максимум по t ≥ 1-τ -p₀ функции f(t, p₀, p₁) достигается при t = max{p₁, 1-τ -p₀},

так как

maxf (t, p0, p1) = f(p1, p0, p1) > 0, p0 = p1, f(p0, p0, p1) = 0,

1-t

1-p₁

f^′t(t, p₀, p₁) = log

- log

f^′′tt(t, p₀, p₁) < 0,

(58)

p₁

signf^′t(t, p₀, p₁) = sign(p₁ - t).

Поэтому если p₁ ≥ 1 - τ - p₀, то из (57), (58) для p₀ = p₁ получаем

1-p₁

max

f (t, p₀, p₁) = h(p₁) + (p₀ - p₁) log

- h(p₀) > 0.

(59)

t≥1-τ -p0

p₁

Тогда если τ ≥ max{1/2 - p₀, 1 - p₀ - p₁} = 1 - p₀ - p₁, то для p₀ = p₁ выполняется

неравенство (59), откуда следует оценка

τ_crit ≤ 1 - p₀ - p₁, r_crit = h(τ_crit).

(60)

Если же p₁ < 1 - τ - p₀, то максимум в (57) достигается при t = 1 - τ - p₀, и

тогда

max f(t, p₀, p₁) = f(1 - τ - p₀, p₀, p₁).

t≥1-τ -p0

Заметим, что

f (p₀, p₀, p₁) = 0, f′t=p

(t, p₀, p₁) = 0, p₀ = p₁,

f^′′tt(t, p₀, p₁) < 0, signf^′t(t, p₀, p₁) = sign(p₁ - t).

Пусть также p₀ > 1 - τ - p₀ (т.е. τ > 1 - 2p₀). Тогда max

f (t, p₀, p₁) > 0 (доста-

t≥1-τ -p0

точно выбрать t близким к p₀). Тогда

τ_crit ≤ 1 - 2p₀, r_crit = h(τ_crit).

(61)

В результате из (60) и (61) получаем

Предложение 3. При любых p₀,p₁

∈ [0, 1/2] для r_crit справедлива оценка

сверху

τ_crit(p₀, p₁) ≤ min{1 - p₀ - p₁, 1 - 2p₀}, r_crit = h(τ_crit).

(62)

Следствие. Если p₀ = 1/2, то из (62) следует τ_crit(1/2,p₁) = r_crit(1/2,p₁) = 0.

Ранее этот частный результат был получен другим способом в [1, предложение 3].

Там же найдена наилучшая экспонента e_d(γ, r) из (4) для γ ≥ 0, 0 ≤ r ≤ 1.

§ 6. “Потенциальная” аддитивная граница сверху для r_crit

Теорема 1 была доказана, заменяя в формуле (26) экспоненциальное число M

кодовых слов {x_i} двумя ближайшими кодовыми словами (x_i, x_j ). Такой способ

исследования дает оптимальный результат, только если можно выбрать пару (x_i, x_j )

с d(x_i, x_j ) = ωn и малым ω > 0. В рассматриваемой постановке задачи этого сделать

нельзя.

Для того чтобы усилить теорему 1, необходимо рассмотреть в (26) экспоненци-

альное число M кодовых слов {x_i}, что значительно труднее (см. [11-13]). Усилим

теорему 1 при условии, что в формуле (26) можно применить аддитивную аппрок-

симацию.

Предположим, что при n → ∞ для всех {x_i} в формуле (26) справедливо адди-

тивное приближение

}

{⋃



∑

{



}

P SL_x

(p₀, δ)p1, xi

=2o(n)

SLxk(p₀,δ)p1, xi

(63)

k=i

Тогда (см. (36)) при d(x_i, x_k) = ω_ikn

}

{⋃



∑

P SL_x

(p₀, δ)p1, xi

=2o(n)

2f(p0,p1,ωik)ⁿ

k=i

}

∑

{⋃



∑∑

P SLxk(p₀,δ)p1, xi

=2o(n)

2f(p0,p1,ωik)ⁿ.

(64)

i=1

k=i

i=1 k=i

Для того чтобы далее развить соотношение (64), введем некоторые дополнительные

понятия. Спектром (распределением расстояний) B(C) = (B₀, B₁, . . . , B_n) кода C

длины n называется (n + 1)-вектор с компонентами

B_i = |C|-1 |{(x, y) : x, y ∈ C, d(x, y) = i}| , i = 0, 1, . . ., n.

(65)

Иными словами, B_i равно среднему числу кодовых слов y на расстоянии i от ко-

дового слова x. Общее число упорядоченных кодовых пар (x, y) ∈ C с d(x, y) = i

равно |C|B_i. Обозначим также B_ωn = 2b(ω,r)n.

Тогда формулу (64) можно продолжить следующим образом:

}

∑

{⋃



∑

P SL_x

(p₀, δ)p1, xi

=2o(n)M

2[b(ω,r)+f(p0,p1,ω)]n.

i=1

k=i

ω>0

Поэтому (см. (36), (37))

[

}]

∑

{⋃



log

P SL_x

(p₀, δ)p1, xi

i=1

k=i

= r + max{b(ω, r) + f(p0, p1, ω, t)} + o(1),

(66)

ω,t

где f(p₀, p₁, ω, t) определено в (37). Тогда для функции F (p₀, p₁, r) из (28) и (66)

имеем

{

}

1-p₁

F (p₀, p₁, r) = max

b(ω, r) + g(p₀, t, ω) + (p₀ - t) log

- h(p₀)

(67)

ω,t

p₁

В качестве оценки для b(ω, r) в (67) используем какую-либо функцию b_low(ω, r)

со следующим свойством: существует величина ω_max = ω_max(r) > 0, такая что

max

[b(ω, r) - b_low(ω, r)] ≥ 0, r > 0.

(68)

0<ω≤ωmax

Тогда для того чтобы выполнялось неравенство F (p₀, p₁, r) > 0 (см. (27)), доста-

точно, чтобы было справедливо условие (см. (37) и (67))

{

}

1-p₁

min

max

b_low(ω, r) + g(p₀, t, ω) + (p₀ - t)log

- h(p₀)

> 0.

(69)

0<ω≤ωmax

t>0

p₁

Используем в (69) в качестве b_low(ω, r) наилучшую из известных таких функций

μ(r, α, ω), h₂(τ) = h₂(α) - 1 + r, с произвольным α ∈ [δ_GV (r), 1/2] (см. (81), (82)

и теорему 2 в Приложении). Для функции μ(r, α, ω) выполняется условие (68), она

монотонно возрастает по r, и ω_max = G(α, τ), где G(α, τ) определено в (79). Тогда

для того чтобы выполнялось неравенство (69), достаточно, чтобы было справедливо

условие

min

maxK(p0, p1, r, ω, t) > 0,

(70)

0<ω≤ωmax

t>0

где

1-p₁

K(p₀, p₁, r, ω, t) = μ(r, p₀, ω) + g(p₀, t, ω) + (p₀ - t) log

- h(p₀).

(71)

p₁

Заметим, что K(p₀, p₁, r, 0, p₀) = 0. Чтобы избежать громоздких вычислений, поло-

жим t = p₀. Функция K(p₀, p₁, r, ω, p₀) = 0 вогнута по ω, т.е. K^′′(p₀, p₁, r, ω, p₀)_ωω < 0

(проще всего это проверить с помощью Maple). Поэтому минимум по ω достигает-

ся при ω = ω_max = G(α, τ), и условие (70) достаточно проверить для ω = G(α, τ).

Известна полезная формула [11, лемма 4]

μ(r, α, G(α, τ)) = h₂(G(α, τ)) + r - 1, h₂(α) - h₂(τ) = 1 - r.

(72)

Далее рассмотрим только более простой

Случай p₁ < p₀ ≤ 1/2. Положим r = r₀ = 1 - h(p₀) и α = p₀ (заметим, что

тогда δ_GV (r₀) = p₀, τ = 0). Тогда G(α, τ) = 2p₀(1 - p₀), и условие (70) достаточно

проверить для ω = 2p₀(1 - p₀). Из (71), (72) при α = p₀, τ = 0, r = r₀ = 1 - h(p₀),

t = p₀ и ω_max = G(α,τ) = 2p₀(1 - p₀) имеем

K(p₀, p₁, 1 - h(p₀), ω_max, p₀) = h₂(ω_max) + g(p₀, p₀, ω_max) - 2h(p₀),

где

[

]

g(p, p, 2p(1 - p)) = 2p(1 - p) + [1 - 2p(1 - p)]h

1 - 2p(1 - p)

Можно проверить, что при ω₀ = 2p₀(1 - p₀) справедливо равенство

(

)

p²⁰

K(p₀, p₁, 1 - h(p₀), ω₀, p₀) = h₂(ω₀) + ω₀ + (1 - ω₀)h

- 2h(p₀) = 0.

(73)

1-ω₀

Также имеем

(1 - t)² - (1 - ω₀ - p₀)

1-p₁

[K(p₀, p₁, 1 - h(p₀), ω₀, t)]^′t =

log

- log

t² - (ω₀ - p₀)²

p₁

(74)

[K(p₀, p₁, 1 - h(p₀), ω₀, t)]^′′tt < 0.

Поэтому при t = p₀ имеем

1-p₀

1-p₁

[K(p₀, p₁, 1 - h(p₀), ω₀, t)]′t=p

= log

- log

< 0, p₁ < p₀,

(75)

p₀

p₁

Из (73)-(75) следует, что

K(p₀, p₁, 1 - h(p₀), ω₀, t) > 0, t < p₀.

Поэтому неравенство (70) выполняется для любых r > r₀ = 1-h(p₀) и p₁ < p₀ ≤ 1/2.

В результате получаем следующий условный результат.

Предложение 4. Если справедливо аддитивное приближение (63), то тогда

rcrit(p0, p1) = 1 - h(p0), 0 < p1 < p0 ≤ 1/2.

Замечание 7. Можно показать, что теорема 1 и формула (13) справедливы при

любых p₁ < p₀ ≤ 1/2. Для этого можно действовать аналогично [11], используя лем-

му 2 и рассматривая по отдельности случаи равенства в формуле (50) (по существу,

это эквивалентно рассмотренному в § 6 случаю) и неравенства в ней. Доказательство

во втором случае оказывается неоправданно громоздким (и ориентированным толь-

ко на двоичный канал ДСК(p)). По этой причине мы его не приводим. Определенно,

есть более простой способ доказательства.

ПРИЛОЖЕНИЕ

1. Функция g(t, p, ω) и формула (35). Рассмотрим кодовые слова x = 0 и x₁

с d(x, x₁) = w(x₁) = ωn, а также множество Sx,x1 (t, p, ω) из (34). Можно считать,

что x₁ = (1, . . . , 1, 0, . . . , 0), причем x₁ имеет сначала ωn “единиц”, а затем (1 - ω)n

“нулей”. Пусть также u ∈ Sx,x1(t, p, ω) имеет u₁n “единиц” на первых ωn позициях

и u₂n “единиц” на следующих (1-ω)n позициях. Так как u₁+u₂ = t, ω-u₁+u₂ = p, то

t-p+ω

t+p-ω

u₁ =

u₂ =

(76)

и при n → ∞ получаем

^[( ωn⁾⁽(1 - ω)n^)]

log |Sx,x1 (t, p, ω)| =

log

u₁n

u₂n

(

)

⁽u₁

u₂

= ωh

+ (1 - ω)h

+ o(1) = g(t, p, ω) + o(1),

(77)

1-ω

где

)

⁽t+ω-p

⁽t+p-ω⁾

g(t, p, ω) = ωh

+ (1 - ω)h

(78)

2ω

2(1 - ω)

Также имеем

1-ω

(1 - ω)² - (1 - t - p)

2g^′ω(p, t, ω) = -2 log

+ log

ω² - (t - p)²

(1 - t)² - (1 - ω - p)

2g^′t(p, t, ω) = log

g^′′tt(p, t, ω) < 0, g^′′ωω(p, t, ω) ≤ 0.

t² - (ω - p)²

Для корня ω₀ уравнения g^′ω(t, p, ω) = 0 имеем

p-t

ω₀ =

g(t, p, ω₀) = h(t).

1 - 2t

2. Функция μ(R, α, ω). Введем функцию [14] (0 ≤ τ ≤ α ≤ 1/2)

α(1 - α) - τ(1 - τ)

G(α, τ) = 2

√

≥ 0.

(79)

1+2

τ (1 - τ)

Для α, τ, таких что 0 ≤ τ ≤ α ≤ 1/2 и h₂(α) - h₂(τ) = 1 - R, введем функцию [16]

∫

√

P +

P² - 4Qy²

⁽α - ω/2⁾

μ(R, α, ω) = h₂(α) - 2 log

dy - (1 - ω)h₂

1-ω

(80)

P = α(1 - α) - τ(1 - τ) - y(1 - 2y), Q = (α - y)(1 - α - y).

Определим функцию δ_GV (R) ≤ 1/2 (граница Варшамова - Гилберта) как

1 - R = h₂(δGV (R)),

0 ≤ R ≤ 1.

(81)

Важность функции μ(R, α, ω) и ее связь со спектром кода {B_i} определяет сле-

дующий вариант теоремы 3 из [15].

Теорема 2

[15, теорема 3]. Для любого (R, n)-кода и любого α ∈ [δ_GV (R), 1/2]

существуют r₁(R, α) > 0 и ω, 0 < r₁(R, α) ≤ ω ≤ G(α, τ), где h₂(τ) = h₂(α) - 1 + R,

а G(α, τ) определено в (79), такие что

n-1 log B_ωn ≥ μ(R, α, ω) + o(1), n → ∞.

(82)

Для μ(R, α, ω) из (80) справедливо также неинтегральное представление (83)-(85).

Замечание 8. Теорема 2 уточняет теорему 5 из [16] (см. также [12, теорема 2]).

При r₁ = 0 теорема 2 переходит в теорему 5 из [16]. В [15, теорема 3] имеются оценки

для r₁(R, α) > 0.

Предложение

[11, предложение 3]. Для функции μ(R, α, ω) справедливо

представление

⁽α - ω/2⁾

2ω

μ(R, α, ω) = (1 - ω)h₂

- h₂(α) + 2h₂(ω) + ω log

- T(A,B,ω),

(83)

1-ω

где

v² - A

T (A, B, ω) = ω log(v - 1) - (1 - ω) log

v² - B²

v+B

v+A

(v - 1)(B² - A²)

+ B log

- Alog

(84)

v-B

v-A

(v² - B²) ln 2

√

B²ω² - 2a₁ω + a²¹ + a₁

B²

−A

a₁ =

h₂(α) - h₂(τ) = 1 - R, A = 1 - 2α, B = 1 - 2τ,

0 ≤ τ ≤ α ≤ 1/2.

(85)

Для любых α₀(R) ≤ α < 1/2 и ω > 0 имеем

dμ(R, α, ω)

> 0, α₀(R) = h-12(1 - R).

dα

Также для любых α > 0 и R > 0 имеем μ(R, α, 0) = 0 и μ^′ω(R, α, ω)|ω=0 > 0. Кроме

того, для любых 0 ≤ τ ≤ α ≤ 1/2 и 0 < ω < G(α, τ)

μ^′′ω2 (R, α, ω) > 0.

Для любого ω > 0 имеем μ(0, 1/2, ω) = 0.

Автор благодарит Ш. Ватанабе (Shun Watanabe) и рецензента за полезные об-

суждения и конструктивные критические замечания, улучшившие статью.

СПИСОК ЛИТЕРАТУРЫ

1. Бурнашев М.В., Амари Ш., Хан Т.С. О некоторых задачах проверки гипотез с ин-

формационными ограничениями // Теория вероятн. и ее примен. 2000. Т. 45. № 4.

С. 625-638.

2. Бурнашев М.В., Хан Т.С., Амари Ш. О некоторых задачах оценивания с информаци-

онными ограничениями // Теория вероятн. и ее примен. 2001. Т. 46. № 2. С. 233-246.

3. Ahlswede R., Csiszár I. Hypothesis Testing with Communication Constraints // IEEE

Trans. Inform. Theory. 1986. V. 32. № 4. P. 533-542.

4. Han T.S., Kobayashi K. Exponential-type Error Probabilities for Multiterminal Hypothesis

Testing // IEEE Trans. Inform. Theory. 1989. V. 35. № 1. P. 2-14.

5. Ahlswede R., Burnashev M.V. On Minimax Estimation in the Presence of Side Information

about Remote Data // Ann. Statist. 1990. V. 18. № 1. P. 141-171.

6. Han T.S., Amari S. Statistical Inference under Multiterminal Data Compression // IEEE

Trans. Inform. Theory. 1998. V. 44. № 6. P. 2300-2324.

7. Shimokawa H., Han T.S., Amari S. Error Bounds of Hypothesis Testing with Data Com-

pression // Proc. 1994 IEEE Int. Sympos. on Information Theory (ISIT’94). Trondheim,

Norway. June 27 - July 1, 1994. P. 114.

8. Watanabe S. Neyman-Pearson Test for Zero-Rate Multiterminal Hypothesis Testing //

Proc. 2017 IEEE Int. Sympos. on Information Theory (ISIT’2017). Aachen, Germany. June

25-30, 2017. P. 116-120.

9. Elias P. Coding for Noisy Channels // IRE Conv. Rec. 1955. V. 4. P. 37-46. Reprinted in:

Key Papers in the Development of Information Theory. New York: IEEE Press, 1974.

P. 102-111.

10. Gallager R.G. Information Theory and Reliable Communication. New York: John Wiley &

Sons, 1968.

11. Бурнашев M.В. О функции надежности ДСК: расширение области, где она известна

в точности // Пробл. передачи информ. 2015. Т. 51. № 4. С. 3-22.

12. Бурнашев М.В. Спектр кода и функция надежности: двоичный симметричный канал //

Пробл. передачи информ. 2006. Т. 42. № 4. С. 3-22.

13. Бурнашев M.В. Усиление оценки сверху для функции надежности двоичного симмет-

ричного канала // Пробл. передачи информ. 2005. Т. 41. № 4. С. 3-22.

14. McEliece R.J., Rodemich E.R., Rumsey H., Jr., Welch L.R. New Upper Bounds on the

Rate of a Code via the Delsarte-MacWilliams Inequalities // IEEE Trans. Inform. Theory.

1977. V. 23. № 2. P. 157-166.

15. Бурнашев M.В. О границах снизу для спектра двоичного кода // Пробл. передачи

информ. 2019. Т. 55. № 4. С. 76-85.

16. Litsyn S. New Bounds on Error Exponents // IEEE Trans. Inform. Theory. 1999. V. 45.

№ 2. P. 385-398.

Бурнашев Марат Валиевич

Поступила в редакцию

Институт проблем передачи информации

10.04.2020

им. А.А. Харкевича РАН

После доработки

burn@iitp.ru

15.05.2020

Принята к публикации

19.05.2020