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

Том 55

2019

Вып. 4

УДК 621.391.1 : 519.72

Б. Накибоглу

АВГУСТИНОВСКАЯ ПРОПУСКНАЯ СПОСОБНОСТЬ

И АВГУСТИНОВСКИЙ ЦЕНТР¹

Для любого канала устанавливается существование и единственность авгу-

стиновского среднего любого положительного порядка для любой функции ве-

роятности на множестве входов. Показано, что августиновское среднее является

единственной неподвижной точкой некоторого оператора, зависящего от поряд-

ка и распределения на входе. Показано, что информация Августина непрерывно

дифференцируема по порядку. Для любого канала и любого выпуклого множе-

ства ограничений с конечной августиновской пропускной способностью установ-

лено существование и единственность августиновского центра и получена соот-

ветствующая граница ван Эрвена - Харремоеса. Введены понятия информации,

пропускной способности, центра и радиуса Августина - Лежандра (АЛ) и дока-

зано, что последние три равны соответствующим величинам Реньи - Галлагера.

Установлено равенство АЛ-пропускной способности и АЛ-радиуса для произ-

вольных каналов, а также существование и единственность АЛ-центра для ка-

налов с конечной АЛ-пропускной способностью. Для всех внутренних точек

множества допустимых ограничений по стоимости получены выражения для

августиновских пропускной способности и центра при наличии ограничений

по стоимости через АЛ-пропускную способность и центр. В качестве примеров

рассмотрены некоторые инвариантные относительно сдвига семейства вероят-

ностей и некоторые гауссовские каналы.

Ключевые слова: расхождение Реньи, информация Реньи, информация Авгу-

стина, августиновское среднее, августиновский центр, августиновская пропуск-

ная способность, пропускная способность и центр при наличии ограничений по

стоимости, информационные величины Августина - Лежандра, информацион-

ные величины Реньи - Галлагера.

DOI: 10.1134/S0555292319040016

§ 1. Введение

Взаимная информация, иногда называемая информацией Шеннона, имеет пер-

востепенную важность при анализе самых разных вопросов передачи информации.

Хотя эта величина определяется без ссылки на задачу оптимизации, она удовле-

творяет следующим двум тождествам, выраженным через расхождение Кульбака -

Лейблера:

I(p; W ) = inf D(p ⊛ W ∥ p ⊗ q) =

(1)

q∈P(Y)

∑

= inf

p(x)D(W (x) ∥ q),

(2)

q∈P(Y)

¹ Работа была частично представлена на Международном симпозиуме IEEE по теории инфор-

мации 2017 г. [1].

где P(Y) - множество всех вероятностных мер на выходном пространстве (Y, Y), p -

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

входов X, а W - функция вида W : X → P(Y). За определение взаимной информа-

ции можно взять любое из этих двух выражений. Можно определить информацию

Реньи порядка α, заменяя в этих выражениях расхождение Кульбака - Лейблера на

расхождение Реньи порядка α. Поскольку расхождение Реньи порядка 1 совпадает

с расхождением Кульбака - Лейблера, информация Реньи порядка 1 равна взаим-

ной информации при обоих определениях, однако, как отмечено Чисаром в [2], для

других порядков эти два определения не равносильны ни определению взаимной

информации, ни друг другу. Обобщение, связанное с выражением (1), называется

информацией Реньи порядка α и обозначается через Igα(p; W ), а обобщение, связан-

ное с выражением (2), называется информацией Августина порядка α и обознача-

ется через I_α(p; W). Аналогично шенноновской пропускной способности при вход-

ном ограничении августиновская пропускная способность порядка α для множества

ограничений A определяется как sup I_α(p; W).

p∈A

Как было недавно показано в [3,4] соответственно, информация Августина по-

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

упаковки для кодов с постоянной композицией в классически-квантовых каналах

без памяти, а информация Августина порядков, больших единицы, - в выражени-

ях для экспоненты ошибки в сильном обращении теоремы кодирования. Для кодов

с постоянной композицией в дискретных стационарных каналах-произведениях этот

факт был неявно отмечен еще в [5, с. 172; 2].

Для кодов с ограничениями по стоимости в (возможно, нестационарных) кана-

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

жениях для экспоненты сферической упаковки и экспоненты ошибки в сильном об-

ращении теоремы кодирования играет августиновская пропускная способность при

наличии ограничений по стоимости. Наблюдение относительно экспоненты сфери-

ческой упаковки для довольно общих моделей канала было сделано Августином

в [6, замечание 36.7(i) и § 36]. Таким образом, августиновские информационные ве-

личины действительно имеют важное операциональное значение, по крайней мере,

для задачи кодирования каналов. Однако основной целью настоящей статьи яв-

ляется изучение информации Августина и августиновской пропускной способности

с точки зрения теории меры. В дальнейшем мы нигде не ссылаемся на задачу коди-

рования каналов или на операциональный смысл августиновских информационных

величин, поскольку считаем, что информацию Августина и августиновскую про-

пускную способность нужно в первую очередь рассматривать как понятия теории

меры. Уже после этого операциональное значение информации Августина и авгу-

стиновской пропускной способности можно устанавливать с помощью теоретико-

информационной техники и результатов анализа с позиций теории меры, как это

сделано в [7].

Во всех предшествующих работах по информации Августина или августиновской

пропускной способности, за исключением работы Августина [6], множество выхо-

дов Y канала W предполагалось конечным [2,3,8-11], что является серьезным недо-

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

для некоторых моделей, интересных с аналитической точки зрения, а также исклю-

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

или пуассоновские модели каналов. Мы проводим анализ для более общей модели

и предполагаем², что выходное пространство (Y, Y) является измеримым простран-

ством, состоящим из множества выходов Y и σ-алгебры Y его подмножеств. В этой

общей постановке наш анализ информации Августина и августиновской пропуск-

² В п. 5.4 вводятся дополнительные предположения, но и они, по существу, выполнены для прак-

тически всех имеющих интерес каналов.

ной способности строится вокруг двух фундаментальных понятий: августиновского

среднего и августиновского центра.

Напомним, что взаимная информация I(p; W) определяется следующим обра-

∑

зом: I(p; W) ≜ p(x)D(W(x)∥q1,p), где q1,p = p(x)W(x). Следовательно, инфи-

мум в (2) достигается на q1,p. Кроме того, непосредственной подстановкой можно

убедиться, что

∑

p(x)D(W (x) ∥ q) = I(p; W ) + D(q1,p ∥ q)

∀q ∈ P(Y).

Таким образом, q1,p - единственная вероятностная мера, на которой достигается ин-

фимум в (2), поскольку расхождение Кульбака - Лейблера для различных вероят-

ностных мер положительно. То же самое верно и для других порядков: для любого

α ∑ R₊ существует единственная вероятностная мера q_α,p, такая что I_α(p;W) =

= p(x)D_α(W(x)∥q_α,p). Мы называем эту вероятностную меру q_α,p августинов-

ским средним порядка α. В [6, лемма 34.2] Августин доказал существование и един-

ственность мер q_α,p для порядков α ∈ (0, 1] и описал важные характеристики этих

мер, являющиеся краеугольным камнем в анализе информации Августина и авгу-

стиновской пропускной способности. Аналогичные соотношения для порядков, боль-

ших 1, выводятся в § 3 (см. лемму 13(d)).

В [12] доказано равенство шенноновской пропускной способности (при отсутствии

ограничений) и шенноновского радиуса³ для любого канала вида W : X → P(Y),

а также существование и единственность шенноновского центра для каналов с ко-

нечной шенноновской пропускной способностью. Используя идеи, уже содержащиеся

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

пропускной способности при наличии ограничений при условии, что множество огра-

ничений выпукло (см. [13, теорема 2]): для любого канала W вида W : X → P(Y)

и выпуклого множества ограничений A

∑

sup

I(p; W ) = inf sup

p(x)D(W (x) ∥ q).

(3)

p∈A

q∈P(Y)p∈A

Ввиду (2) можно интерпретировать (3) как теорему о минимаксе. Кроме того, ес-

ли шенноновская пропускная способность для множества ограничений A конечна,

то существует единственная вероятностная мера q1,W,A, называемая шенноновским

центром для множества ограничений A, такая что

∑

sup I(p; W) = sup

p(x)D(W (x) ∥ q1,W,A).

p∈A

p∈A x

Термин “центр” происходит из названия соответствующей величины для случая от-

сутствия ограничений, рассматривавшегося в [12]. Августин доказал аналогичный

результат для I_α(p; W ) в предположении, что порядок α принадлежит (0, 1], а A -

множество ограничений, определяемое ограничениями по стоимости (см. [6, лем-

ма 34.7]). Аналогичное предложение для I_α(p; W ) при любом α ∈ R₊ и любом вы-

пуклом множестве ограничений A доказывается в § 4 (см. теорему 1). Соответствую-

щую вероятностную меру qα,W,A мы называем августиновским центром порядка α

для множества ограничений A.

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

но часто встречаются при применении августиновской пропускной способности к

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

³ Шенноновский радиус определяется как inf sup D(W (x) ∥ q).

q∈P(Y)x∈X

позволяет получить альтернативную характеризацию августиновских пропускной

способности и центра при наличии ограничений по стоимости. Августин проделал

это в [6, § 35], опираясь на величину, которая ранее применялась для дискретных

каналов Галлагером [14, с. 13-15; 15, § 7.3], а также для различных моделей гаус-

совских каналов⁴ в [14, с. 15, 16; 15, §§ 7.4, 7.5; 16; 17]. Мы называем эту величину

информацией Реньи - Галлагера и изучаем ее в п. 5.3. По сравнению с применением

техники выпуклого сопряжения к шенноновской пропускной способности при на-

личии ограничений по стоимости, проделанным Чисаром и Кёрнером в [5, гл. 8],

анализ Августина в [6, § 35], основанный на информации Реньи - Галлагера, доволь-

но замысловат. В п. 5.2 мы придерживаемся более стандартного подхода, применяя

некоторое обобщение метода из [5, гл. 8], основанное на новой величине, которую мы

называем информацией Августина - Лежандра. Мы покажем эквивалентность этих

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

реме для августиновской пропускной способности при наличии ограничений.

Некоторые из наиболее важных наблюдений, представленных в настоящей ста-

тье, были уже получены ранее в [6, §§ 33-35; 10; 18; 19]. Наши основные достижения

в контексте этих работ перечислены в п. 1.3. Перед этим мы вводим обозначения и

соглашения в п. 1.1 и описываем рассматриваемую модель в п. 1.2.

1.1. Обозначения и соглашения. Скалярное произведение двух векторов μ и q

∑

в R^ℓ, т.е.

μⁱqⁱ, обозначается через μ · q. Вектор из всех единиц размерности ℓ

i=1

будем обозначать через 1 для любого ℓ ∈ Z₊, размерность ℓ будет ясна из кон-

текста. Замыкание, внутреннюю область и выпуклую оболочку множества S будем

обозначать через cl S, intS и chS соответственно; соответствующая топология или

структура векторного пространства будет ясна из контекста.

Для любого множества Y обозначим множество всех его подмножеств через 2^Y,

множество всех вероятностных мер на конечных подмножествах Y - через P(Y), а

множество всех ненулевых конечных мер с тем же свойством - через M⁺(Y). Для

любой меры p ∈ M⁺(Y) множество всех y, таких что p(y) > 0, будем называть

носителем p и обозначать через supp p.

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

обобщенных мер через M(Y), множество всех конечных мер - через M⁺⁰(Y), множе-

ство всех ненулевых конечных мер - через M⁺(Y), а множество всех вероятностных

мер - через P(Y). Пусть μ и q - две меры на измеримом пространстве (Y, Y). Тогда μ

абсолютно непрерывна относительно q, т.е. μ ≺ q, если μ(E) = 0 для любого E ∈ Y,

такого что q(E) = 0; μ и q эквивалентны, т.е. μ ∼ q, если μ ≺ q и q ≺ μ; μ и q взаимно

сингулярны, т.е. μ ⊥ q, если ∃E ∈ Y, такое что μ(E) = q(Y \ E) = 0. Кроме того,

множество мер W на (Y, Y) абсолютно непрерывно относительно q, т.е. W ≺ q, если

w ≺ q для любой w ∈ W, и равномерно абсолютно непрерывно относительно q, т.е.

W ≺^uni q, если для любого ε > 0 существует δ > 0, такое что w(E) < ε для любой

w ∈ W при условии, что q(E) < δ.

∫

Интеграл от измеримой функции f по мере μ будем обозначать через

f μ(dy)

∫

или

f (y) μ(dy). Интегралы по мере Лебега на вещественной прямой обозначаем

∫

через

f dy или

f (y) dy. Если μ - вероятностная мера, то интеграл от f по ме-

ре μ будем называть математическим ожиданием f и обозначать через E_μ[f] или

E_μ[f(y)].

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

кретный смысл будет всегда ясен из контекста. Через ℏ(·) будем обозначать как

⁴ Августин не предполагал ни конкретной модели шума, ни конечности множества выходов. Тем

не менее, гауссовские каналы не охватывались моделью Августина [6, § 35], так как функция сто-

имости в этой модели предполагалась конечной.

∑

шенноновскую энтропию, так и двоичную: ℏ(p) ≜

p(y) ln

для всех p ∈ P(Y) и

p(y)

ℏ(z) ≜ z ln

+ (1 - z) ln

для всех z ∈ [0, 1]. Произведение топологий [20, с. 38],

1-z

σ-алгебр [20, с. 118] и мер [20, теорема 4.4.4] будем обозначать через ⊗, а декартово

произведение множеств [20, с. 38] - через ×. Будем использовать краткие обозна-

чения Xn1 для декартова произведения множеств X₁, . . . , X_n и Yn1 для произведения

σ-алгебр Y₁, . . . , Y_n. Через | · | обозначаем абсолютную величину вещественных чи-

сел и мощность множеств. Знаком ≤ обозначается как обычное отношение для ве-

щественных чисел, так и соответствующее поточечное неравенство для функций и

векторов. Для двух мер μ и q на измеримом пространстве (Y, Y) пишем μ ≤ q, если

μ(E) ≤ q(E) для всех E ∈ Y.

Для a, b ∈ R через a ∧ b будем обозначать минимум a и b. Для f : Y → R и

g: Y → R функция f ∧g - поточечный минимум f и g. Для μ,q ∈ M(Y) мера μ∧q -

dμ ∧ q

dμ

единственная мера, удовлетворяющая ν-п.в. условию

∧

для любой ν,

dν

⋀

такой что μ ≺ ν и q ≺ ν. Для набора F вещественнозначных функций через

f∈F

обозначаем поточечный инфимум функций f в F - расширенную вещественнознач-

ную функцию. Для набора

⋀

некоторой w ∈ P(Y), через

u обозначим инфимум U относительно частичного по-

u∈U

рядка ≤; такая инфимум-мера существует и единственна согласно [21, теорема 4.7.5].

Символ ∨ используется для максимумов и супремумов аналогично символу ∧ для

минимумов и инфимумов.

1.2. Модель канала. Канал W - это функция из множества входов X в множе-

ство всех вероятностных мер на выходном пространстве (Y, Y):

W : X → P(Y).

(4)

Множество Y называется множеством выходов, а Y - σ-алгеброй выходных собы-

тий. Множество всех каналов из множества входов X в выходное пространство

(Y, Y) обозначим через P(Y | X). Для любых p ∈ P(X) и W ∈ P(Y | X) вероятностная

мера с маргинальным распределением на X, равным p, и условным распределением

при условии x, равным W (x), обозначается через p ⊛ W . Вплоть до п. 5.4 мы огра-

ничиваемся рассмотрением входных распределений, принадлежащих P(X), избегая

тонкостей, связанных с измеримостью. Более общий случай входных распределений

из P(X ) рассмотрен⁵ в п. 5.4.

Канал W называется дискретным каналом, если и X, и Y - конечные множе-

ства. Для любого n ∈ Z₊ и любых каналов W_t : X_t → P(Y_t), t ∈ {1, . . ., n}, канал-

произведение W[1,n] : Xn1 → P(Yn1) длины n определяется следующим образом:

⊗

W[1,n](xn1) =

W_t(x_t)

∀xn1 ∈ Xn1.

t=1

Канал-произведение является стационарным, если W_t = W при всех t ∈ {1, . . ., n}

для некоторого W : X → P(Y).

Для любого ℓ ∈ Z₊ ℓ-мерная функция стоимости ρ - это функция из множества

входов в R^ℓ, ограниченная снизу, т.е. функция вида ρ: X → Rℓ≥z для некоторого

⁵ Структуры, описанной в (4), самой по себе недостаточно для существования и единственности

меры p ⊛ W с требуемыми свойствами для всех p ∈ P(X ). Существование и единственность такой

меры p ⊛ W гарантировано для всех p ∈ P(X ), если W - функция вероятностей переходов из (X, X )

в (Y, Y), т.е. элемент P(Y | X ), а не P(Y | X).

z ∈ R. Без ограничения общности будем предполагать⁶, что

inf ρⁱ(x) ≥ 0

∀i ∈ {1, . . . , ℓ}.

x∈X

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

го элемента из X, обозначим через Γexρ, а множество всех ограничений по стоимости,

выполненных для хотя бы одного элемента из P(X), - через Γ_ρ:

{

}

Γexρ ≜

ϱ ∈ Rℓ≥0 : ∃x ∈ X, такой что ρ(x) ≤ ϱ

(5)

{

∑

}

Γρ ≜

ϱ ∈ Rℓ≥0 : ∃p ∈ P(X), такой что

p(x)ρ(x) ≤ ϱ

(6)

Тогда оба множества Γexρ и Γ_ρ имеют непустые внутренние области, причем Γ_ρ явля-

ется выпуклой оболочкой Γexρ, т.е. Γ_ρ = chΓexρ.

Функция стоимости на канале-произведении называется аддитивной, если ее

можно представить в виде суммы функций стоимости на каналах-компонентах. Для

заданных W_t : X_t → P(Y_t) и ρ_t : X_t → Rℓ≥0, t ∈ {1, . . . , n}, обозначим результирую-

щую аддитивную функцию стоимости на Xn1 для канала W[1,n] через ρ[1,n], т.е.

∑

ρ[1,n](xn1) =

ρ_t(x_t)

∀xn1 ∈ Xn1.

t=1

1.3. Предшествующие работы и основные результаты. Приведем подробный спи-

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

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

I. Для всех α ∈ (0, 1) в [6, лемма 34.2] утверждается существование и един-

ственность вероятностной меры q_α,p, такой что I_α(p; W) = D_α(W ∥q_α,p |p), и дана

следующая характеризация q_α,p в терминах оператора⁷ T_α,p(·):

• T_α,p(q_α,p) = q_α,p и q_α,p ∼ q1,p;

• Если q1,p ≺ q и T_α,p(q) = q, то q_α,p = q;

• lim

∥q_α,p - T^jα,p(q1,p)∥ = 0;

j→∞

• D_α(W ∥q |p) ≥ I_α(p; W) + D_α(qα,p ∥q) для⁸ всех q ∈ P(Y).

Мы не смогли проверить корректность доказательства леммы 34.2 из [6]; это обсуж-

дается в [22, Приложение C]. Лемма 13(c) настоящей статьи доказывается⁹ с исполь-

зованием идей Августина из доказательства леммы 34.2 в [6]. Из нашей леммы 13(c)

вытекают все утверждения леммы 34.2 из [6], кроме lim

∥q_α,p -T^jα,p(q1,p)∥ = 0; вме-

j→∞

сто этого в лемме 13(c) установлено равенство lim

∥q_α,p - T^jα,p(qgα,p)∥ = 0 (см. (26)

j→∞

и [22, замечание 6]). В отличие от леммы 34.2 из [6], лемма 13(c) также дает оцен-

ку сверху на D_α(W ∥ q | p). Насколько нам известно, это новая оценка. Верхняя и

нижняя оценки на D_α(W ∥ q | p), полученные в лемме 13(c),(d), таковы:

D1∨α(q_α,p ∥q) ≥ D_α(W ∥q |p) - I_α(p; W) ≥ D1∧α(q_α,p ∥q)

∀q ∈ P(Y).

(7)

⋁

⁶ Августин в [6, § 33] накладывал дополнительное условие

ρ(x) ≤ 1, однако это условие ис-

x∈X

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

⁷ Оператор Tα,p(·), определенный в (20), однозначно задается порядком α и распределением p и

корректно определен для всех q с конечным Dα(W ∥ q | p).

⁸ Строго говоря, в [6, лемма 34.2] приведено неравенство Dα(W ∥ q | p) ≥ Iα(p; W ) +α2 ∥qα,p - q∥².

Однако Августин вначале доказывает вышеуказанное неравенство, а затем с помощью неравенства

Пинскера получает неравенство, приведенное в [6, лемма 34.2].

⁹ Лемму 13(c) можно также доказать, используя идеи доказательства леммы 13(d).

Для случая конечного Y существование q ∈ P(Y), такой что q ∼ q1,p и T_α,p(q) = q,

обсуждалось и другими авторами. Сделаем краткое отступление и укажем на соот-

ветствующие обсуждения этого вопроса о существовании.

• При доказательстве границы сферической упаковки для кодов с постоянной

композицией в дискретных стационарных каналах-произведениях Фано неявно

утверждал существование неподвижной точки, эквивалентной q1,p, для любого

α ∈ (0,1) (см. [23, §9.2, формула (9.24) и с. 292]. Однако в [23, §9.2] Фано не

объяснял, почему такая неподвижная точка должна существовать, и не изучал

ее единственность и связь с q_α,p;

• При доказательстве эквивалентности своей экспоненты сферической упаковки в

случае конечного Y и соответствующей величины, полученной Фано в [23], Ару-

тюнян доказывал существование неподвижной точки, эквивалентной q1,p, для

любого α ∈ (0, 1) (см. [18, формулы (16)-(19)]);

• При обсуждении границ случайного кодирования для дискретных стационар-

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

ждению о существовании для любого α ∈ [1/2, 1) неподвижной точки, эквива-

лентной q1,p (см. [19, формулы (3.15), (3.16) и теорема 3.2]. Однако Полтырев не

формулировал это в виде утверждения о неподвижной точке.

На наш взгляд, основное концептуальное достижение в [6, лемма 34.2] - это ха-

рактеризация августиновского среднего как неподвижной точки оператора T_α,p(·),

эквивалентной q1,p. Границы, такие как (7), вытекают из этого наблюдения с помо-

щью неравенства Йенсена.

II. Для α ∈ (1, ∞) в лемме 13(d) установлено существование и единственность

августиновского среднего q_α,p и доказано, что оно удовлетворяет границе (7) и об-

ладает следующими свойствами:

• T_α,p(q_α,p) = q_α,p и q_α,p ∼ q1,p;

• Если T_α,p(q) = q, то q_α,p = q.

Насколько нам известно, лемма 13(d) является новой. Для случая α ∈ (1, ∞) ни

характеризация q_α,p через T_α,p(·), ни неравенства (7) раньше не были известны,

даже для случая конечного Y.

III. Функция I_α(p; W) из R₊ в [0, ℏ(p)] непрерывно дифференцируема по α со-

гласно лемме 17(e).

IV. В теореме 1 получено следующее минимаксное тождество для любого вы-

пуклого множества ограничений A:

sup

inf

D_α(W ∥q |p) = inf sup D_α(W ∥q |p).

p∈A

q∈P(Y)

q∈P(Y)p∈A

Теорема 1 устанавливает существование и единственность августиновского центра

qα,W,A для любого выпуклого множества A с конечной августиновской пропускной

способностью, а также сходимость {q_α,p(i) }i∈Z

к qα,W,A в топологии полной вари-

ации для любой последовательности {p(i)}i∈Z

⊂ A, такой что lim

Iα(p(i); W ) =

i→∞

= Cα,W,A. Августином этот результат был доказан только для α ∈ (0, 1] и мно-

жеств ограничений, определяемых ограничениями по стоимости (см. [6, лемма 34.7]).

Для случая A = P(X) аналогичные результаты были доказаны в [2, предложение 1]

в предположении, что X и Y - конечные множества, а также в [8, теорема 34] в пред-

положении, что множество Y конечно.

V. Следующая граница в терминах августиновских пропускной способности и

центра, установленная в лемме 21, насколько нам известно, является новой:

sup D_α(W ∥q |p) ≥ Cα,W,A + Dα∧1(qα,W,A ∥q)

∀q ∈ P(Y).

p∈A

Аналогичная граница была выдвинута в качестве гипотезы ван Эрвеном и Харре-

моесом в [8]. Для пропускной способности и центра Реньи эта гипотеза доказана и

обобщена на случай наличия ограничений в [13, леммы 19, 25].

VI. Информация Августина - Лежандра I^λα(p; W), определяемая как I_α(p; W) -

-λ · E_p[ρ], а также соответствующие пропускная способность, центр и радиус, -

новые понятия, не изучавшиеся ранее, кроме случая α = 1. Таким образом, фор-

мально говоря, все утверждения п. 5.2 являются новыми. Анализ, проведенный в

п. 5.2, является стандартным применением техники выпуклого сопряжения для ха-

рактеризации августиновских пропускной способности и центра при наличии огра-

ничений по стоимости. Аналогичный анализ в случае α = 1 проведен в [5, гл. 8]

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

результаты проведенного в п. 5.2 анализа таковы:

• Величина C^λα,W , определяемая как sup I^λα(p; W ), удовлетворяет равенству

p∈P(X)

C^λα,W = supC_α,W,ϱ - λ · ϱ для всех λ ∈ Rℓ≥0 - формула (55);

ϱ≥0

• C_α,W,ϱ = inf

C^λα,W + λ · ϱ для всех ϱ ∈ intΓ_ρ, причем множество всех λ, доставля-

λ≥0

ющих этот инфимум, является непустым, выпуклым и компактным, если C_α,W,ϱ

конечно, - лемма 29;

• C^λα,W = S^λα,W, где S^λα,W определяется как inf sup

D_α(W(x)∥q)-λ·ρ(x), - тео-

q∈P(Y)x∈X

рема 2;

• Если C^λα,W < ∞, то существует единственный АЛ-центр q^λα,W , такой что C^λα,W =

(

)

= sup

D_α

W (x) ∥ q^λα,W

- λ · ρ(x). Кроме того, lim

∥q_α,p - q^λα,W ∥ = 0 для всех

x∈X

i→∞

{p(i)}i∈Z

⊂ P(X), таких что lim

I^λα(p(i); W) = C^λα,W , - теорема 2;

i→∞

• Если C_α,W,ϱ = C^λα,W + λ · ϱ < ∞ для некоторого λ ∈ Rℓ≥0, то q_α,W,ϱ = q^λα,W

- лемма 31;

• Для канала-произведения W[1,n] с аддитивной функцией стоимости C^λ

α,W[1,n]

∑

C^λα,W

для всех λ ∈ Rℓ≥0 и α ∈ R₊, и если какая-либо из этих величин

t=1

⊗

существует, то q^λ

равно

q^λ

- лемма 32.

α,W[1,n]

α,Wt

t=1

VII. Информация Реньи- Галлагера Igλα(p; W) является обобщением информа-

ции Реньи Igα(p; W ) с множителем Лагранжа, поскольку Ig0α(p; W ) = Igα(p; W ). Эта

величина впервые была использована Галлагером в [14] при другой параметризации

и другом масштабировании; в дальнейшем она рассматривалась в [24, § IV; 6; 16; 17;

25-27] также с другими параметризациями и масштабированиями под различными

названиями. Мы выбираем такие же параметризацию и масштабирование, как и для

информации Августина - Лежандра. Наиболее важные результаты анализа в п. 5.3

таковы:

• Cgλα,W = S^λα,W согласно теореме 3, где Cgλα,W определяется как sup Igλα(p;W);

p∈P(X)

(

)

• Если C^λα,W < ∞ и lim

Igα

p(i); W

= C^λα,W, то lim

∥qgλα,p - q^λα,W ∥ = 0 - теорема 3;

i→∞

(

)

• sup D_α(W(x)∥q) - λ · ρ(x) ≥ C^λα,W + D_α

q^λα,W ∥q

для всех q ∈ P(Y) - лемма 35.

x∈X

Насколько нам известно, лемма 35 является новой. В случае, когда α ∈ (0, 1) и⋁

ρ(x) ≤ 1, теорема 3 вытекает из [6, лемма 35.2].

x∈X

При проведении аналогичного анализа в [6, § 35] Августин предполагал функцию

стоимости ограниченной. Однако такое предположение исключает из рассмотрения

такие важные и интересные случаи как гауссовские каналы. Это не вопрос смены

масштабирования: некоторые результаты проделанного Августином анализа, напри-

мер, [6, лемма 35.3(a)], не верны, когда функция стоимости неограничена. Мы не

будем предполагать функцию стоимости ограниченной. Таким образом, наша мо-

дель включает в себя не только модель Августина из [6, § 35], но и другие ранее

изучавшиеся модели: как дискретные [14, с. 13-15; 15, § 7.3; 24, § IV; 26; 27], так и

гауссовские [14, с. 15, 16; 15, §§ 7.4, 7.5; 16; 17; 25].

VIII. Для каналов с несчетным множеством входов шенноновская информация

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

ном пространстве (X, X ), а не через функции вероятности на множестве входов X.

В п. 5.4 обсуждается, как и при каких условиях можно проделать такое обобще-

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

нашего анализа таковы:

• Если W - функция вероятностей переходов из (X, X ) в (Y, Y), т.е. W ∈ P(Y | X ),

и Y счетно порождена, то

- величина I_α(p; W) корректно определена для всех α ∈ R₊ и p ∈ P(X) - фор-

мулы (75), (76) и лемма 37;

- величина I^λα(p; W) корректно определена для всех α ∈ R₊, p ∈ P(X) и λ ∈ Rℓ≥0,

если функция ρ является X -измеримой - формула (77);

• Если W ∈ P(Y | X ), X счетно отделима, Y счетно порождена, а ρ является X -из-

меримой, то

- C^λα,W = sup I^λα(p;W) для всех λ ∈ Rℓ≥0, где A^λ определяется как {p ∈ P(X) :

p∈A^λ

λ · E_p[ρ] < ∞}, - теорема 4;

(

)

- Если C^λα,W < ∞ для некоторого λ ∈ Rℓ≥0, то C^λα,W = sup

D_α

W∥q^λα,W |p

p∈A^λ

−λ · E_p[ρ] - теорема 4;

- C_α,W,ϱ

= sup I_α(p; W) для всех ϱ ∈ intΓ_ρ, где A(ϱ) определяется как

p∈A(ϱ)

{p ∈ P(X) : E_p[ρ] ≤ ϱ}, - теорема 5;

- Если C_α,W,ϱ < ∞ для некоторого ϱ ∈ int Γ_ρ, то C_α,W,ϱ = sup

D_α(W ∥q_α,W,ϱ |p)

- теорема 5.

p∈A(ϱ)

Таким образом, АЛ-пропускная способность и АЛ-центр, так же как и августи-

новские пропускная способность и центр при наличии ограничений по стоимости,

определяемые через функции вероятности, равны соответствующим величинам,

которые можно определить через вероятностные меры на (X, X ) при условии,

что X счетно отделима, а Y счетно порождена.

§2. Предварительные сведения

2.1. Расхождение Реньи.

Определение 1. Для любых α ∈ R₊ и w,q ∈ M⁺(Y) расхождением Реньи

порядка α между w и q называется

⎧

∫ (

)_α (

)1-α

⎪

⎨

ν(dy), α = 1,

α-1

dν

D_α(w ∥q) ≜

∫

[

]

(8)

⎪

⎩

- ln

ν(dy),

α = 1,

dν

где ν - любая мера, такая что w ≺ ν и q ≺ ν.

Обычно расхождение Реньи определяется для пар вероятностных мер (см., на-

пример, [8,28]), а не для пар ненулевых конечных мер. Мы пользуемся этим несколь-

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

хождения Реньи некоторые результаты в более кратком виде (см. следующую лем-

му 1 и п. 5.3). Для пар вероятностных мер определение 1 равносильно обычному

определению, используемому в [8, теорема 5].

Лемма 1 [13, лемма 8]. Пусть α - положительное вещественное число, а w,

q, v - ненулевые конечные меры на (Y, Y).

• Если v ≤ q, то D_α(w ∥ q) ≤ D_α(w ∥ v);

• Если q = γv для некоторого γ ∈ R₊ и либо w - вероятностная мера, либо α = 1,

то D_α(w ∥q) = D_α(w ∥v) - lnγ.

Следующая лемма утверждает, что если оба аргумента расхождения Реньи -

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

Лемма 2 [8, теоремы 3 и 31]. Для любого α ∈ R₊ и любых вероятностных мер

w и q на (Y,Y)

1∧α

D_α(w ∥q) ≥

∥w - q∥².

Для порядков, принадлежащих (0, 1], это неравенство называется неравенством

Пинскера [29,30]. Для порядков, принадлежащих (0, 1), можно оценить расхождение

Реньи сверху через расстояние полной вариации. Для случая α = 1/2 формула (21)

в [31, с. 364] утверждает, что

D1/2(w ∥q) ≤ 2 ln

(9)

2 - ∥w - q∥

Расхождение Реньи порядка α непрерывно по своим аргументам в топологии пол-

ной вариации при условии, что α ∈ (0, 1). Для произвольных порядков имеет место

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

ственной (setwise) сходимости.

Лемма 3 [8, теорема 15]. Для любого α ∈ R₊ функция D_α(w∥q) полунепрерыв-

на снизу по паре вероятностных мер (w, q) в топологии помножественной сходи-

мости.

Лемма 4 [8, теорема 17]. Для любого α ∈ (0,1) функция D_α(w∥q) равномерно

непрерывна по паре вероятностных мер (w, q) в топологии полной вариации.

Расхождение Реньи выпукло по второму аргументу для всех положительных по-

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

выше единицы и совместно квазивыпукло по двум аргументам для всех положи-

тельных порядков.

Лемма 5 [8, теорема 12]. Для любых α ∈ R₊, w,q₀,q₁ ∈ P(Y), β ∈ (0,1) и ν,

таких что (q₀ + q₁) ≺ ν,

D_α(w ∥βq₁ + (1 - β)q₀) ≤ βD_α(w ∥q₁) + (1 - β)D_α(w ∥q₀).

dq1

dq0

Кроме того, равенство имеет место тогда и только тогда, когда

dν

w-почти наверное.

Лемма 6 [8, теорема 11]. Для любых α ∈ (0,1], w₀,w₁,q₀,q₁ ∈ P(Y), β ∈ (0,1)

и ν, таких что (w₀ + w₁ + q₀ + q₁) ≺ ν,

D_α(βw₁ + (1 - β)w₀ ∥βq₁ + (1 - β)q₀) ≤ βD_α(w₁ ∥q₁) + (1 - β)D_α(w₀ ∥q₀).

(10)

Кроме того, при α = 1 равенство имеет место тогда и только тогда, когда

dw0 dq1

dw1 dq0

, а при α ∈ (0,1) равенство имеет место тогда и только то-

dν dν

dw0 dq1

dw1 dq0

гда, когда

и D_α(w1 ∥q₁) = D_α(w0 ∥q₀).

dν dν

Лемма 7 [8, теорема 13]. Для любых α ∈ R₊, w₀,w₁,q₀,q₁ ∈ P(Y) и β ∈ (0,1)

D_α(βw₁ + (1 - β)w₀ ∥βq₁ + (1 - β)q₀) ≤ D_α(w₁ ∥q₁) ∨ D_α(w₀ ∥q₀).

Лемма 8 [8, теоремы 3 и 7]. Для любых w,q ∈ P(Y) функция D_α(w∥q) не убы-

вает и полунепрерывна снизу по α на R₊ и непрерывна на (0, (1∨χ_w,q)], где χ_w,q ≜

≜ sup{α : D_α(w ∥q) < ∞}.

Так как D_α(w ∥ q) =

D1-α(q ∥w) для всех α ∈ (0, 1), то из леммы 8 и фор-

1-α

мулы (9) следует

⎧

⎨D1/2(w ∥q),

если α ∈ (0, 1/2],

D_α(w ∥q) ≤

≤

⎩

D1/2(w ∥q), если α ∈ (1/2, 1),

1-α

≤

∀α ∈ (0, 1).

1-α

2 - ∥w - q∥

Чуть более точную границу см. в [31, формула (24), с. 365].

Если G - σ-подалгебра Y, то для любых w и q из P(Y) равенства w|_G (E) = w(E)

для всех E ∈ G и q|_G (E) = q(E) для всех E ∈ G однозначно определяют вероятностные

(

)

меры w|_G и q|_G на (Y, G). Будем обозначать D_α

w|_G ∥q|_G

через D^Gα(w ∥ q).

Лемма 9 [8, теорема 21]. Пусть Y₁ ⊂ Y₂ ⊂ ... ⊂ Y - возрастающее семейство

)

⋃

σ-алгебр, и пусть Y_∞ = σ

- наименьшая σ-алгебра, содержащая их. Тогда

i=1

для любого порядка α ∈ R₊

lim

DYiα(w ∥q) = Dα∞(w ∥q).

i→∞

2.2. Скошенная вероятностная мера.

Определение 2. Для любого α

∈ R₊ и любых w,q ∈ P(Y), таких что

D_α(w ∥q) < ∞, скошенной вероятностной мерой w^qα порядка α называется

dw^qα

⁽ dw)α ( dq)1-α

≜e(1-α)Dα(w∥q)

dν

Отметим, что wq1 = w для любой q, такой что D₁(w ∥q) < ∞. Для остальных

порядков непосредственной подстановкой можно проверить следующее утвержде-

ние: если D_α(w ∥ q) < ∞, то для любой v ∈ P(Y), такой что D₁(v ∥ w) < ∞ и

D₁(v ∥q) < ∞, справедливо

(

)

D₁

v∥w^qα

+ D_α(w ∥q) =

D₁(v ∥w) + D₁(v ∥q).

1-α

Это тождество используется для вывода следующей вариационной характеризации

расхождения Реньи порядка, отличного от единицы.

Лемма 10 [8, теорема 30]. Для любых w,q ∈ P(Y)

⎧

⎪

inf

D₁(v ∥w) + D₁(v ∥q), α ∈ (0, 1),

⎨

v∈P(Y) 1 - α

D_α(w ∥q) =

⎪

D₁(v ∥w) + D₁(v ∥q), α ∈ (1, ∞),

⎩ s

v∈P(Y) 1 - α

где

D₁(v ∥w) + D₁(v ∥q) равно -∞ при α ∈ (1, ∞) и D₁(v ∥w) = D₁(v ∥q) = ∞.

1-α

(

)

Кроме того, если D_α(w ∥q) конечно и либо α ∈ (0, 1), либо D₁

w^qα ∥w

< ∞, то

(

)

(

)

D_α(w ∥q) =

D₁

w^qα ∥w

+D₁

w^qα ∥q

(11)

1-α

В лемме 8 мы видели, что D_α(w ∥ q) непрерывна по α на замыкании того интер-

вала, где она конечна. Далее в лемме 11 устанавливается аналитичность D_α(w ∥q)

по α на внутренности того интервала, где D_α(w ∥ q) конечна. Лемма 11 т(кже ус)та-

на(ливае) аналитичность, а следовательно, и конечность, функций D1

w^qα ∥w

D₁

w^qα ∥q

на том же интервале. Это позволяет утверждать, что и равенство (11)

справедливо на том же интервале:

(

)

(

)

D_α(w ∥q) =

D₁

w^qα ∥w

+D₁

w^qα ∥q

∀α ∈ (0, χ_w,q).

1-α

Лемма 11. Для любых w,q ∈ P(Y), таких что χ_w,q > 0, где χ_w,q ≜ sup{α :

(

)

(

)

D_α(w ∥q) < ∞}, функции D_α(w ∥q), D₁

w^qα ∥w

и D₁

w^qα ∥q

аналитичны по α на

(0, χ_w,q). Кроме того,

⎧

∑



⎨

(-1)^κ-t

∂^κD_α(w ∥q)

κ!

G^tw,q(φ), φ = 1,



(φ - 1)κ-t+1

(12)



∂α^κ

⎩ t⁼⁰

α=φ

κ! Gκ+1w,q(1),

φ = 1,

где G^tw,q(φ) определяется через множество J_t следующим образом:

J_t ≜ {(j₁, j₂, . . ., j_t) : j_i ∈ Z≥0 ∀i и 1j₁ + 2j₂ + . . . + tj_t = t},

(13)

G^tw,q(φ) ≜

⎧

⎨(φ - 1)Dφ(w ∥ q),

t = 0,

(

[(

)i^])j

≜

∑

-(j₁ +j₂ +. . .+j_t -1)

∏

(-1)

(14)

⎩

E_wq

- ln

, t∈Z₊.

j₁! j₂! . . . j_t!

dν

i=1

Лемма 11, насколько нам известно, является новой; она доказывается в [22, При-

ложение A] с помощью стандартных результатов о непрерывности и дифференци-

руемости параметрических интегралов и формулы Фаа-ди-Бруно для производной

композиции гладких функций.

Заметим, что J₁ = {(1)}, J₂ = {(2, 0), (0, 1)} и J₃ = {(3, 0, 0), (1, 1, 0), (0, 0, 1)}.

Таким образом, с помощью (14) непосредственной подстановкой можно убедиться,

что

G1w,q(φ) = E_wq [ξ],

]

)

[(

)₂

G2w,q(φ) =

[ξ²] - E_wq[ξ]2

E_wq

ξ-E_wq

[ξ]

Ew_φ

]

[(

)₃

G3w,q(φ) =

[ξ³] -

E_wq

[ξ²] E_wq

[ξ] +

E_wq

[ξ]³ =

[ξ]

Ew_φ

Ew^qφ ξ - Ew^q

где ξ = ln

- ln

. Если подставить эти выражения в (12) и использовать тож-

dν

(

)

dw^q

дество ξ =

+ G0w,q(φ) , которое справедливо w^qφ-почти наверное для

φ-1

φ ∈ (0,χ_w,q) \ {1}, получим следующие более краткие выражения для первых двух

производных D_α(w ∥ q) по α:

⎧

(

)

⎪



D₁

w^qφ ∥w

φ = 1,

⎨

∂



(φ - 1)²

D_α(w ∥q)

]



[(

)₂

∂α

⎪1

α=φ

⎩

E_w ln

- D₁(w ∥q)

φ = 1,



∂²



D_α(w ∥q)



∂α²

α=φ

⎧

(

]

)

[(

)₂

⎪

dw^qφ

(

)

[

(

)]₂

⎨

- 2D₁

w^qφ ∥w

D₁

w^qφ

∥w

φ = 1,

Ew^qφ

(φ - 1)³

]

⁼⎪

[(

)₃

⎪1

⎩

E_w ln

- D₁(w ∥q)

φ = 1.

Из аналитичности D_α(w ∥q) на (0, χ_w,q) следует, что для любого φ ∈ (0, χ_w,q)

существует открытый интервал, содержащий φ, на котором D_α(w ∥q) равна степен-

ному ряду, задаваемому производными D_α(w ∥ q) в точке α = φ. Если имеется конеч-

ный набор пар вероятностных мер {(w_i, q_i)}i∈I, то для любого φ, принадлежащего

(0, χwi,qi ) для всех i ∈ I, существует открытый интервал, содержащий φ, на котором

каждая D_α(w_i ∥ q_i) равна степенному ряду, задаваемому производными D_α(w_i ∥ q_i)

в точке α = φ. Если набор пар вероятностных мер бесконечен, то открытого интер-

вала, содержащего φ и принадлежащего всем (0, χwi,qi), может не быть. Следующая

лемма 12 утверждает существование такого интервала, когда D_β (w_i ∥ q_i) равномерно

ограничена при β > φ для всех i ∈ I. Кроме того, лемма 12 дает равномерную по

всем i ∈ I оценку остаточного члена такого степенного ряда на этом интервале.

Лемма 12. Для любых γ,φ,β ∈ R₊, таких что φ ∈ (0,β), и любых w,q ∈ P(Y),

таких что D_β(w ∥q) ≤ γ,



 ∂^κDα(w ∥q)



^{κ! τκ+1κ, φ = 1,



≤



∂α^κ



κ! τκ+1,

φ = 1,

α=φ



∑



(η - φ)ⁱ ∂ⁱD_α(w ∥ q)



Dη(w ∥q) -



≤



∂αⁱ



i=0

α=φ

⎧

[

]

τκ+1|η - φ|^κ

⎪

⎨

κ-1+

φ = 1,

1 - |η - φ|τ

≤

∀η : |η - φ| ≤

⎪τκ+1|η - φ|κ

⎩

φ = 1,

1 - |η - φ|τ

где

⎧

[

]

⎪

1+e(1∨β)γ

⎨

∨

+ γ , φ = 1,

|φ - 1|

φ ∧ (β - φ)

τ ≜

⎪

1+e^βγ

⎩

φ = 1.

1 ∧ (β - 1)

Лемма 12, насколько нам известно, является новой; доказательство, использую-

щее формулу (12) и простейшие свойства вещественных аналитических функций и

степенных рядов, приведено в [22, Приложение A].

2.3. Условное расхождение Реньи и скошенный канал. Понятия условного рас-

хождения Реньи и скошенного канала позволяют записывать многие часто исполь-

зуемые выражения в более кратком виде.

Определение 3. Для любых α ∈ R₊, W : X → P(Y), Q: X → P(Y) и p ∈ P(X)

условным расхождением Реньи порядка α для распределения на входе p называется

∑

D_α(W ∥Q|p) ≜ p(x)D_α(W(x)∥Q(x)).

(15)

x∈X

Если ∃q ∈ P(Y), такая что Q(x) = q для всех x ∈ X, то D_α(W ∥ Q | p) будем обозна-

чать через D_α(W ∥ q | p).

Замечание 1. В работах [11,32] через D_α(W ∥Q|p) обозначено D_α(p⊛W ∥p⊛Q).

При α = 1 это равносильно нашим соглашениям, но в случае α = 1 это уже не

так. Если либо α = 1, либо D_α(W (x) ∥ Q(x)) принимает ∑дно и то же значение

для всех x с положительной p(x), то D_α(p ⊛ W ∥ p ⊛ Q) = p(x)D_α(W (x) ∥ Q(x)),

∑

в противном случае D_α(p ⊛ W ∥ p ⊛ Q) < p(x)D_α(W (x) ∥ Q(x)) при α ∈ (0, 1) и

∑

D_α(p⊛W ∥p⊛Q) > p(x)D_α(W(x)∥Q(x)) при α ∈ (1, ∞). Эти неравенства следуют

из неравенства Йенсена и строгой вогнутости функции натурального логарифма.

Определение 4. Для любых α ∈ R₊, W : X → P(Y) и Q: X → P(Y) скошен-

ным каналом W^Qα порядка α называется функция из {x : D_α(W (x) ∥ Q(x)) < ∞}

в P(Y) следующего вида:

dW^Qα(x)

^[ dW (x)]α [ dQ(x)]1-α

≜e(1-α)Dα(W(x)∥Q(x))

(16)

dν

Если ∃q ∈ P(Y), такая что Q(x) = q для всех x ∈ X, то канал W^Qα будем обозначать

через W^qα.

§ 3. Информация Августина

Основная цель этого параграфа - ввести понятия информации Августина и ав-

густиновского среднего. В п. 3.1 определяется информация Августина порядка α

для распределения на входе p и устанавливается существование и единственность

августиновского среднего для любого распределения на входе p и любого положи-

тельного конечного порядка α. Затем информация Августина анализируется спер-

ва как функция распределения на входе при заданном порядке (п. 3.2), а затем

как функция порядка при заданном распределении на входе (п. 3.3). В заключение

в п. 3.4 мы сравниваем информацию Августина с информацией Реньи, характери-

зуя каждую из этих двух величин через другую. Некоторые из важнейших свойств

информации Августина и августиновского среднего были впервые описаны Авгу-

стином в [6, § 34] для порядков не выше единицы, и именно поэтому мы предлагаем

такие названия для этих величин. Доказательства лемм из этого параграфа можно

найти в [22, Приложение B].

3.1. Существование и единственность августиновского среднего.

Определение 5. Для любых α ∈ R₊, W : X → P(Y) и p ∈ P(X) информацией

Августина порядка α для распределения на входе p называется

Iα(p; W ) ≜ inf Dα(W ∥ q | p).

(17)

q∈P(Y)

Непосредственной подстановкой нетрудно убедиться, что

D₁(W ∥q |p) = D₁(W ∥q1,p |p) + D₁(q1,p ∥q)

∀q ∈ P(Y),

где

∑

q1,p ≜

p(x)W (x).

(18)

Тогда из леммы 2 и формулы (17) вытекает

I₁(p; W) = D₁(W ∥q1,p |p).

Таким образом, для информации Августина порядка 1 имеется выражение в за-

мкнутом виде, равное взаимной информации. Однако для других порядков инфор-

мация Августина не выражается в замкнутом виде. Тем не менее приведенная ниже

лемма 13 устанавливает существование и единственность вероятностной меры q_α,p,

такой что I_α(p; W ) = D_α(W ∥ q_α,p | p) для¹⁰ любого положительного порядка α и

любого распределения на входе p. Кроме того, утверждения (c) и (d) леммы 13

дают альтернативную характеризацию q_α,p как единственной неподвижной точки

оператора T_α,p(·), удовлетворяющей q1,p ≺ q_α,p. Лемма 13(e) дает альтернативную

характеризацию информации Августина для порядков, отличных от единицы.¹¹

Определение 6. Пусть α - положительное вещественное число, и пусть W -

канал вида W : X → P(Y).

• Для любого p ∈ M⁺(X) средняя мера порядка α для распределения на входе p

определяется как

[∑

dμ_α,p

⁽ dW (x))α]^α

≜

p(x)

dν

)

(∑

где ν - любая мера, такая что

p(x)W (x)

≺ν;

• Для любого p ∈ P(X) среднее Реньи порядка α для распределения на входе p

определяется как

μ_α,p

qgα,p ≜

;

(19)

∥μ_α,p∥

• Для любого p ∈ P(X) оператор Агустина T_α,p(·): Q_α,p → P(Y) порядка α для

распределения на входе p определяется как

∑

T_α,p(q) ≜

p(x)W^qα(x)

∀q ∈ Q_α,p,

(20)

где Q_α,p ≜ {q ∈ P(Y) : D_α(W ∥ q | p) < ∞}, а скошенный канал W^qα определен

(

)

в (16). Кроме того, T0α,p(q) = q и Ti+1α,p(q) ≜ T_α,p

T^iα,p(q)

для любого неотрица-

тельного целого i.

¹⁰ Это довольно легко доказать, когда Y - конечное множество. Единственность qα,p следует из

строгой выпуклости расхождения Реньи по второму аргументу, описанной в лемме 5. Если Y ко-

нечно, то P(Y) компактно и существование qα,p следует из полунепрерывности снизу расхождения

Реньи по второму аргументу, вытекающей из леммы 3, и теоремы об экстремуме для полуне-

прерывных снизу функций [33, гл. 3, п. 12.2]. Однако для каналов с произвольными выходными

пространствами P(Y) не компактно, поэтому теорему об экстремуме для доказательства существо-

вания qα,p применить нельзя.

¹¹ Эта альтернативная характеризация используется для доказательства равносильности двух

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

рования.

Лемма 13. Пусть W - канал вида W : X → P(Y), а p ∈ P(X) - распределение

на входе. Тогда

(a) I_α(p; W ) ≤ D_α(W ∥ q1,p | p) ≤ ℏ(p) < ∞ для всех α ∈ R₊, где q1,p определена

в (18);

(b) I₁(p; W ) = D₁(W ∥ q1,p | p). Кроме того,

D₁(W ∥q |p) - I₁(p; W) = D₁(q1,p ∥q)

∀q ∈ P(Y);

(21)

T_α,p(q_α,p) = q_α,p,

lim

∥q_α,p - T^jα,p(qgα,p)∥ = 0,

(22)

j→∞

D₁(q_α,p ∥q) ≥ D_α(W ∥q |p) - I_α(p; W) ≥ D_α(q_α,p ∥q)

∀q ∈ P(Y)

(23)

и q_α,p ∼ q1,p. Кроме того,¹² если q1,p ≺ q и T_α,p(q) = q, то q_α,p = q;

(d) Если α ∈ (1, ∞), то ∃! q_α,p, такая что I_α(p; W ) = D_α(W ∥ q_α,p | p). При этом

T_α,p(q_α,p) = q_α,p,

D_α(q_α,p ∥q) ≥ D_α(W ∥q |p) - I_α(p; W) ≥ D₁(q_α,p ∥q)

∀q ∈ P(Y)

(24)

и q_α,p ∼ q1,p. Кроме того, если T_α,p(q) = q, то q_α,p = q;

(e) Если α ∈ R₊ \ {1}, то

(

)

(

)

D₁

+I₁

Iα(p; W ) =

Wqα,pα ∥W |p

p; Wqα,pα

1-α

⎧

⎨

inf

D₁(V ∥W |p) + I₁(p; V ), α ∈ (0, 1),

V ∈P(Y|X) 1 - α

⎩ sup

D₁(V ∥W |p) + I₁(p; V ), α ∈ (1, ∞),

V ∈P(Y|X)

1-α

(

)

1-α

inf

D₁(V ∥W |p) +

I₁(p; V )

(25)

1-α

V ∈P(Y|X)

Сходимость, описанная в (22), имеет место не только для среднего Реньи qgα,p, но

также и для некоторых других вероятностных мер. В [22, Приложение B, замеча-

ние 6] описано, как можно доказать следующий, более общий результат о сходимости

для любых α ∈ (0, 1) и p ∈ P(X):







lim

^q_α,p - T^jα,p(q)

 = 0, если q ∼ q1,p и esssup_q

∞.

(26)

1,p

^l

^<

j→∞

dq1,p

Утверждение (a) доказывается с помощью леммы 1; неравенство I_α(p; W ) ≤ ℏ(p)

было доказано Чисаром в [2, формула (24)] с помощью других рассуждений. Хоро-

шо известное утверждение (b) доказывается прямой подстановкой. Утверждение (c)

принадлежит¹³ Августину [6, лемма 34.2]. Утверждение (d), насколько нам извест-

но, является новым. Утверждение (e) для случая конечного Y было доказано Чиса-

ром [2, формулы (A24), (A27)].

¹² Заметим, что из одного равенства Tα,p(q) = q на следует, что qα,p = q для всех α ∈ (0, 1).

Рассмотрим, например, двоичный симметричный канал, и пусть q - вероятностная мера, сосредо-

точенная на одном из выходных символов. Тогда Tα,p(q) = q, но qα,p = q при всех p ∈ P(X) и

α ∈ (0,1).

¹³ Точнее говоря, лемма 34.2 из [6] не содержит неравенства D₁(qα,p ∥ q) ≥ Dα(W ∥ q | p)-Iα(p; W ),

а равенство (22) в ней сформулировано для q1,p, а не для q^α,p. Мы не смогли проверить правиль-

ность доказательства Августина этой леммы в [6], подробнее об этом см. в [22, Приложение C].

Определение 7. Для любых α ∈ R₊, W : X → P(Y) и p ∈ P(X) единственная

вероятностная мера q_α,p на (Y, Y), для которой I_α(p; W) = D_α(W ∥q_α,p |p), называ-

ется августиновским средним порядка α для распределения на входе p.

Из леммы 2 и соотношений (21), (23), (24) вытекает следующая граница, анало-

гичная результату Чисара [34, теорема 3.1]:

√

D_α(W ∥q |p) - I_α(p; W)

≥ ∥q_α,p - q∥

∀q ∈ P(Y)

∀α ∈ R₊.

α∧1

Информация Августина и августиновское среднее имеют выражения в замкну-

том виде лишь для α = 1; для других порядков таких выражений нет. Однако из

свойства неподвижности точки T_α,p(q_α,p) = q_α,p, установленного в лемме 13(c), (d),

и из определения оператора T_α,p(·) в (20) вытекает следующее тождество для авгу-

стиновского среднего:

[∑

dq_α,p

⁽ dW (x))α

p(x)

e(1-α)Dα(W(x)∥qα,p)

∀ν : q1,p ≺ ν.

(27)

dν

В п. 3.3 при анализе I_α(p; W ) и q_α,p как функций от α мы используем это тождество

вместо выражения в замкнутом виде.

Лемма 14. Для любого канала-произведения W[1,n]: Xn1 → P(Yn1) длины n и

любого распределения на входе p ∈ P(Xn1) неравенство

(

)

∑

Iα

p; W[1,n]

≤ I_α(p_t; W_t)

(28)

t=1

справедливо для всех α ∈ R₊, где p_t ∈ P(X_t) - маргинальное распределение для p

на X_t. Кроме того, неравенство в (28) обращается в равенство для некоторого

α ∈ R₊ тогда и только тогда, когда q_α,p имеет вид

⊗

q_α,p =

qα,pt .

(29)

t=1

⊗

Если p =

p_t, то (29) имеет место для всех α ∈ R₊, и следовательно, (28)

t=1

обращается в равенство для всех α ∈ R₊.

3.2. Информация Августина как функция входного распределения. Информация

Августина порядка α для распределения на входе p определяется как точная нижняя

грань семейства условных расхождений Реньи, являющихся линейными по p. Тогда

информация Августина вогнута по p как поточечный инфимум семейства вогнутых

функций. В лемме 15 этот результат уточняется с использованием леммы 13.

Лемма 15. Для любых α ∈ R₊ и W : X → P(Y) функция I_α(p;W) вогнута по p,

удовлетворяя неравенствам

(

)

Iα(pβ ; W ) ≥ βIα(p1; W ) + (1 - β)Iα(p0; W ) + βDα∧1

qα,p1 ∥q_α,p

(

)

+ (1 - β)Dα∧1

qα,p1 ∥q_α,p

(30)

(

)

Iα(pβ ; W ) ≤ βIα(p1; W ) + (1 - β)Iα(p0; W ) + βDα∨1

qα,p1 ∥q_α,p

(

)

+ (1 - β)Dα∨1

qα,p0 ∥q_α,p

(31)

Iα(pβ ; W ) ≤ βIα(p1; W ) + (1 - β)Iα(p0; W ) + ℏ(β) -

(

)

-Dα∧1

qα,pβ ∥βqα,p1 + (1 - β)qα,p0

(32)

где p_β = βp₁ + (1 - β)p₀ для любых p₀, p₁ ∈ P(X) и β ∈ [0, 1].

Из леммы 15 следует, что для любого положительного порядка α и любого ка-

нала W информация Августина I_α(p; W ) порядка α непрерывна по распределению

на входе p тогда и только тогда, когда sup I_α(p; W ) конечен.¹⁴ Кроме того, ес-

p∈P(X)

ли sup I_η(p; W ) конечен для некоторого η ∈ R₊, то семейство {I_α(p; W )}α∈(0,η]

p∈P(X)

равномерно равностепенно непрерывно по p на P(X).

Чтобы увидеть, почему конечность sup I_α(p; W) необходима для непрерывно-

p∈P(X)

сти, заметим, что из неотрицательности расхождения Реньи для вероятностных мер

и неравенства (30) следует, что

(

)

qα,p1 ∥q_α,p

Iα(pβ ; W ) - Iα(p0; W ) ≥ β(Iα(p1; W ) - Iα(p0; W )) + βDα∧1

(

)

+ (1 - β)Dα∧1

qα,p1 ∥q_α,p

≥ β(I_α(p₁; W) - I_α(p₀; W)).

С другой стороны, ∥p_β - p₀∥ ≤ 2β. Таким образом, если существует последователь-

ность {p_i}i∈Z

⊂ P(X), такая что lim

Iα(pi; W ) = ∞, то Iα(p; W ) разрывна в любой

i↑∞

точке p ∈ P(X).

Обратное утверждение, т.е. достаточность, можно установить вместе с равносте-

пенной непрерывностью. Для любых p₁, p₂ ∈ P(X), таких что p₁ = p₂, определим s_∧,

s₁ и s₀ как

p₁ ∧ p₀

p₁ - p₁ ∧ p₀

p₀ - p₁ ∧ p₀

s_∧ =

s₁ =

s₀ =

∥p₁ ∧ p₀∥

1 - ∥p₁ ∧ p₀∥

Тогда s_∧, s₁, s₀ ∈ P(X) и s₁ ⊥ s₀. С другой стороны, ∥p₁ - p₀∥ = 2 - 2∥p₁ ∧ p₀∥.

Поэтому

)

⁽2 - ∥p₁ - p₀∥

∥p₁ - p₀∥

p₁ =

s_∧ +

s₁,

)

⁽2 - ∥p₁ - p₀∥

∥p₁ - p₀∥

p₀ =

s_∧ +

s₀.

Следовательно, по леммам 2, 15 получаем

)

⁽∥p₁ - p₀∥

∥p₁ - p₀∥(

)

Iα(p0; W ) - Iα(p1; W ) ≤ ℏ

Iα(s0; W ) - Iα(s1; W )

≤

)

⁽∥p₁ - p₀∥

∥p₁ - p₀∥

≤ℏ

Iα(s0; W )

∀p₁, p₀ ∈ P(X), α ∈ R₊.

Таким образом,

)

⁽∥p₁ - p₀∥

∥p₁ - p₀∥

|I_α(p₀; W ) - I_α(p₁; W )| ≤ ℏ

sup I_η(p; W)

p∈P(X)

∀p₁, p₀ ∈ P(X), α ∈ (0, η].

3.3. Информация Августина как функция порядка. Основная цель этого пункта

- охарактеризовать поведение информации Августина как функции порядка при

¹⁴ Для информации Реньи, обсуждаемой в п. 3.4, аналогичные соотношения уже доказаны в [13,

лемма 16(d), (e)]. Единственной существенной тонкостью является то, что для порядков из (0, 1)

информация Реньи непрерывна по p, даже если выражение для соответствующей пропускной спо-

собности бесконечно, так как информация Реньи квазивогнута, а не вогнута по p для порядков из

(0, 1) (см. [13, лемма 6(a)]).

заданном распределении на входе. В лемме 16 даны предварительные результаты,

облегчающие дальнейший анализ информации Августина как функции порядка;

результаты этого анализа представлены в лемме 17.

Лемма 16. Для любого канала W вида W : X → P(Y) и любого распределения

на входе p ∈ P(X)

(a) D_α(W (x) ∥ q_α,p) ≤ ln

;

p(x)

(b) [p(x)]

α∧1 W

(x) ≤ q_α,p;



dqα,p



|α - 1|

(c)



l

dq1,p

≤

min p(x)

x: p(x)>0

Границы, указанные в лемме 16, получаются из (27) элементарными преобразо-

ваниями.

Лемма 17. Для любого канала W : X → P(Y) и любого распределения на входе

p ∈ P(X) справедливы следующие утверждения:

(a) Либо (α - 1)I_α(p; W ) - строго выпуклая по α функция из R₊ в [-ℏ(p), ∞), либо

∑

dW(x)

Iα(p; W ) =

p(x) ln γ(x) для некоторой γ : X → [1, ∞), такой что

= γ(x)

dq1,p

W (x)-п.н. для всех x ∈ supp p, и q_α,p = q1,p для всех α ∈ R₊;

1-α

(b)

Iα(p; W ) - невозрастающая непрерывная по α функция из R+ в R;

{

}

dqα,p

(d) ln

- равностепенно непрерывное по α семейство функций на R₊;

dq1,p y∈Y

(e) I_α(p; W ) - непрерывно дифференцируемая по α функция из R₊ в [0, ℏ(p)], такая

что



∂



∂



D_α(W ∥q_φ,p |p)

Iα(p; W )



∂α

α=φ

⎧

(

)

⎪

D₁

φ = 1,

⎨

Wqφ,pφ ∥W |p

(φ - 1)²

[

]

(

)₂

∑

⎪

p(x)

dW (x)

⎩

EW(x) ln

- D₁(W(x)∥q1,p)

φ = 1;

dq1,p

(

)

(f) Если функция (α - 1)I_α(p; W ) строго выпукла по α, то функция I₁

(

)

т.е. D₁

∥q_α,p|p

, - монотонно возрастающая и непрерывная по α на R₊;

(

)

∑

(

)

в противном случае I₁

= p(x)lnγ(x) (т.е. D₁

∥q_α,p|p

∑

dW(x)

p(x) ln γ(x)) для некоторой γ : X → [1, ∞), такой что

= γ(x)

dq1,p

W (x)-п.н. для всех x ∈ supp p, и q_α,p = q1,p для всех α ∈ R₊;

(

)

(g) limI1

= limIα(p; W ).

α↓0

(Строгая) выпуклость функции (α - 1)I_α(p; W ) по α на R₊ равносильная (стро-

гой) вогнутости функции sI 1 (p; W ) по s на (-1, ∞) - см. доказательство утвер-

1+s

ждения (f). Вогнутость функции sI 1 (p; W ) по s на (-1, ∞) и утверждения (b), (c)

1+s

леммы 17 были ранее получены Августином в [6, лемма 34.3] для порядков от нуля

до единицы. Утверждения (a) и (d)-(g) леммы 17, насколько нам известно, явля-

ются новыми. Лемма 17 в основном касается информации Августина как функции

порядка при заданном распределении на входе. Утверждение (d), т.е. равностепен- }{

dqα,p

ная непрерывность ln

как семейства функций порядка α, выведено как

dq1,p y∈Y

необходимый инструмент для доказательства непрерывности производной информа-

ции Августина, т.е. утверждения (e). Отметим, что в лемме 16(c) уже установлена

эта равностепенная непрерывность при α = 1.

3.4. Сравнение информаций Августина и Реньи. Информация Августина - не

единственная информационная величина, определяемая через расхождение Реньи,

существуют и другие. По-видимому, наиболее известной среди них благодаря своему

операциональному смыслу, установленному Галлагером в [14], является информация

Реньи, введенная вначале Галлагером¹⁵ [14], а затем Сибсоном [35].

Определение 8. Для любых α ∈ R₊, W : X → P(Y) и p ∈ P(X) информацией

Реньи порядка α для распределения на входе p называется

Igα(p; W) ≜ inf D_α(p ⊛ W ∥p ⊗ q).

(33)

q∈P(Y)

Как отмечено в [35], непосредственной проверкой можно убедиться, что

D_α(p ⊛ W ∥p ⊗ q) =

(

)

(

)

=D_α

p⊛W∥p⊗qgα,p

+D_α

qgα,p ∥q

∀p ∈ P(X), q ∈ P(Y), α ∈ R₊,

где qgα,p - среднее Реньи, определенное в (19). По лемме 2 отсюда получаем

(

)

Igα(p; W) = D_α

p⊛W∥p⊗qgα,p

∀p ∈ P(X), α ∈ R₊,

(34)

(

)

D_α(p ⊛ W ∥p ⊗ q) = Igα(p; W) + D_α

qgα,p ∥q

∀p ∈ P(X), q ∈ P(Y), α ∈ R₊.

(35)

Для порядков, отличных от единицы, выражение в замкнутом виде, приведенное

в (34), равно следующему, которое иногда берется за определение информации Ре-

ньи:

Igα(p; W) =

ln ∥μ_α,p∥, α ∈ R₊ \ {1}.

α-1

Заметим, что в отличие от августиновского среднего порядка α среднее Реньи по-

рядка α имеет выражение в замкнутом виде и для порядков, отличных от единицы.

Кроме того, неравенства (21), (23) и (24) из леммы 13 заменяются равенством (35).

Обсуждение информации Реньи, аналогичное вышеизложенному в этом параграфе

для информации Августина, можно найти в [13].

Информация Реньи порядка 1 равна информации Августина порядка 1 для всех

распределений на входе. Для других порядков это равенство не имеет места для

произвольных распределений на входе. Однако информацию Августина и инфор-

мацию Реньи можно характеризовать друг через друга, используя подходящие ва-

риационные формы. Характеризация информации Августина в вариационном виде

через информацию Реньи особенно полезна, так как информация Августина не име-

ет выражения в замкнутом виде, в то время как информация Реньи имеет. Из этой

характеризации также вытекает другая вариационная характеризация информации

Августина.

Лемма 18. Пусть W - канал вида W : X → P(Y), а p ∈ P(X) - распределение

на входе.

(1-α)Dα(W (x)∥qα,p)

p(x)e

(a) Пусть u_α,p ∈ P(X) имеет вид u_α,p(x) =

тогда

^∑ p(x)e(1-α)Dα(W(x)∥qα,p)длявсехx;

Iα(p; W ) = I^α(uα,p; W ) +

D₁(p∥u_α,p) =

(36)

α-1

¹⁵ Галлагер использует другую параметризацию и ограничивается случаем α ∈ (0, 1).

⎧

⎪

⎨ sup

Igα(u; W) +

D₁(p∥u), α ∈ (0, 1),

u∈P(X)

α-1

(37)

⎪

⎩ inf

Igα(u; W) +

D₁(p∥u), α ∈ (1, ∞);

u∈P(X)

α-1

)

p(x)e(α-1)Dα(W(x)∥qα,p

(b) Пусть a_α,p ∈ P(X) имеет вид a_α,p(x) =

тогда

^∑p(x)e(α-1)Dα(W(x)∥qα,p)длявсехx;

Igα(p; W) = I_α(a_α,p; W) -

D₁(a_α,p ∥p) =

(38)

α-1

⎧

⎪

⎨

inf

Iα(a; W ) -

D₁(a∥p), α ∈ (0, 1),

a∈P(X)

α-1

(39)

⎪

Iα(a; W ) -

D₁(a∥p), α ∈ (1, ∞);

⎩ s

a∈P(X)

α-1

всех x; тогда

⎡

⎤

]_α)

1/α

(∑

^[ dW (x)

Iα(p; W ) =

ln E_ν ⎣

p(x)e(1-α)fα,p (x)

⎦₌

α-1

dν

⎡

⎤

]_α)

1/α

(∑

^[ dW (x)

inf

E_ν ⎣

p(x)e(1-α)f(x)

⎦.

α-1

f: Ep[f]=0

dν

Лемма 18(a) была впервые доказана Полтыревым [19, теорема 3.4] в несколько

другом виде для случая α ∈ [1/2, 1) в предположении, что Y конечно. Формула (39)

леммы 18(b) была впервые получена в [10, теорема 1] для случая конечного Y, од-

нако в [10] не только не было получено выражение для оптимального a_α,p, но и

не утверждалось его существование. Лемма 18(c) была впервые доказана Августи-

ном [6, лемма 35.7] для порядков, меньших единицы.¹⁶

Следующие неравенства получаются как с помощью точки u = p в вариацион-

ной характеризации леммы 18(a), так и с помощью точки a = p в вариационной

характеризации леммы 18(b):

Iα(p; W ) ≥ I^α(p; W ), α ∈ (0, 1],

(40)

Iα(p; W ) ≤ I^α(p; W ), α ∈ [1, ∞).

(41)

Их также можно вывести, используя неравенство Йенсена и вогнутость функции

натурального логарифма.

§ 4. Августиновская пропускная способность

В §3 были определены и изучены информация Августина и августиновское сред-

нее. В этом параграфе мы собираемся сделать это же для августиновской пропуск-

ной способности и августиновского центра. В п. 4.1 устанавливается существование

и единственность августиновского центра для любых выпуклых множеств ограни-

чений с конечной августиновской пропускной способностью и изучаются следствия

существования августиновского центра для заданного порядка и множества ограни-

чений. В п. 4.2 августиновские пропускная способность и центр анализируются как

¹⁶ Утверждение [6, лемма 35.7(d)] вытекает из более сильных неравенств, получаемых с помощью

соотношения (23) и леммы 18(c).

функции порядка для заданного множества ограничений. В п. 4.3 устанавливает-

ся граница на августиновскую пропускную способность выпуклой оболочки набора

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

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

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

дении. Доказательства предложений из данного параграфа содержатся в [22, При-

ложение D].

В [6, §§ 33, 34] Августин провел анализ, аналогичный содержанию настоящего

параграфа, и получил многие из ключевых результатов, такие как существование и

единственность августиновского центра и его непрерывность как функции порядка

(см. [6, леммы 34.6-34.8]), но для порядков не выше единицы. При этом Августин

рассматривал пропускную способность и центр лишь для подмножеств P(X), опре-

деляемых через ограничения по стоимости. Этот важный специальный случай мы

рассматриваем более подробно в § 5.

4.1. Существование и единственность августиновского центра.

Определение 9. Для любых α ∈ R₊, W : X → P(Y) и A ⊂ P(X) августинов-

ской пропускной способностью порядка α канала W для множества ограничений A

называется

Cα,W,A ≜ sup I_α(p; W).

p∈A

Когда множество ограничений A совпадает со всем P(X), августиновская пропускная

способность порядка α обозначается через C_α,W , т.е. C_α,W ≜ Cα,W,P(X).

Используя определение информации Августина I_α(p; W), данное в (17), получаем

следующее выражение для Cα,W,A:

Cα,W,A = sup

inf D_α(W ∥ q | p).

(42)

p∈A

q∈P(Y)

Следующая теорема показывает, что по крайней мере для выпуклых A можно по-

менять порядок инфимума и супремума в данном выражении.

Теорема 1. Для любых порядка α ∈ R₊, канала W вида W : X → P(Y) и вы-

пуклого множества ограничений A ⊂ P(X) имеет место равенство

sup

inf

D_α(W ∥q |p) = inf sup D_α(W ∥q |p).

(43)

p∈A

q∈P(Y)

q∈P(Y)p∈A

Если выражение в левой части (43) конечно, т.е. если Cα,W,A ∈ R≥0, то ∃! qα,W,A ∈

∈ P(Y), называемая августиновским центром порядка α канала W для множества

ограничений A, такая что

Cα,W,A = sup D_α(W ∥qα,W,A |p).

(44)

p∈A

Кроме того, для любой последовательности распределений на входе {p(i)}

⊂ A,

i∈Z+

удовлетворяющей равенству lim

Iα(p(i); W ) = Cα,W,A, соответствующая последо-

i→∞

вательность {q_α,p(i) }

августиновских средних порядка α является последова-

i∈Z+

тельностью Коши в метрике полной вариации на P(Y), а qα,W,A - единственной

предельной точкой этой последовательности Коши.

Наше доказательство теоремы 1 следует программе, предложенной в [12] для

доказательства аналогичного результата в случае α = 1 и A = P(X). Вначале тео-

рема 1 доказывается в предположении, что множество входов конечно, а затем этот

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

множество X конечно, можно также установить существование оптимального рас-

пределения на входе, для которого информация Августина равна августиновской

пропускной способности.

Лемма 19. Для любых порядка α ∈ R₊, канала W вида W : X → P(Y) с ко-

нечным множеством входов X и замкнутого выпуклого множества ограничений

A ⊂ P(X) существует p ∈ A, такое что I_α(p;W) = Cα,W,A, и ∃!qα,W,A ∈ P(Y),

такая что

D_α(W ∥qα,W,A |p) ≤ Cα,W,A

∀p ∈ A.

Кроме того, q_α,p = qα,W,A для всех p∈ A, таких что I_α(p; W) = Cα,W,A.

Если A совпадает с P(X), то выражение в правой части (44) равно радиусу Реньи

S_α,W , который мы сейчас определим. Тогда из теоремы 1 следует C_α,W = S_α,W .

Определение 10. Для любых α ∈ R₊ и W : X → P(Y) радиусом Реньи поряд-

ка α канала W называется

S_α,W ≜ inf sup D_α(W(x)∥q).

q∈P(Y)x∈X

Теорема 1 утверждает существование и единственность августиновского центра

порядка α для выпуклых множеств ограничений с конечной августиновской про-

пускной способностью. Однако вероятностная мера qα,W,A, удовлетворяющая (44),

т.е. августиновский центр порядка α, может в принципе существовать и для невы-

пуклых множеств ограничений.

Определение 11. Множество ограничений A для канала W : X → P(Y) имеет

августиновский центр порядка α тогда и только тогда, когда ∃q ∈ P(Y), такая что

sup D_α(W ∥q |p) = Cα,W,A.

(45)

p∈A

Если Cα,W,A бесконечна, то все вероятностные меры на выходном пространстве

удовлетворяют (45) в силу (42) и неравенства максимина-минимакса. Таким обра-

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

стью порядка α все вероятностные меры на выходном пространстве являются авгу-

стиновскими центрами порядка α. С другой стороны, некоторые множества ограни-

чений не имеют августиновского центра порядка α. Рассмотрим, например, p₁ и p₂,

такие что qα,p1 = qα,p2 и I_α(p₁; W ) = I_α(p₂; W ). Тогда (45) не выполнено ни для

какой вероятностной меры для A = {p₁, p₂}, и A не имеет августиновского центра

порядка α. Лемма 20 утверждает, что если августиновский центр для множества

ограничений с конечной августиновской пропускной способностью существует, то

этот августиновский центр единствен.

Лемма 20. Пусть A ⊂ P(X) - множество ограничений, такое что Cα,W,A ∈

∈ R≥0, а qα,W,A - вероятностная мера, удовлетворяющая (45). Тогда для любой

последовательности {p(i)}i∈Z

⊂ A, такой что lim

Iα(p(i); W ) = Cα,W,A, после-

i→∞

довательность {q_α,p(i) }

августиновских средних порядка α является последо-

i∈Z+

вательностью Коши с предельной точкой qα,W,A, и августиновский центр qα,W,A

порядка α единствен.

Для любого A, имеющего августиновский центр порядка α и конечную Cα,W,A,

из лемм 13(b)-(d) и 20 следует, что

Cα,W,A - I_α(p; W) ≥ Dα∧1(q_α,p ∥qα,W,A)

∀p ∈ A.

Леммы 13(b)-(d) и 20 можно также использовать для вывода нижней границы на

sup D_α(W ∥q |p) через августиновские пропускную способность и центр.

p∈A

Лемма 21. Для любого множества ограничений A, имеющего августиновский

центр порядка α и конечную Cα,W,A, справедливо неравенство

sup D_α(W ∥q |p) ≥ Cα,W,A + Dα∧1(qα,W,A ∥q)

∀q ∈ P(Y).

(46)

p∈A

Заметим, что вид нижней границы (46) в некотором смысле аналогичен грани-

цам (21), (23) и (24). Граница (46) является границей ван Эрвена - Харремоеса¹⁷ при

α ∈ (0,1], но не совпадает с ней при α ∈ (1,∞), поскольку в этом случае имеется

член D₁(qα,W,A ∥ q), а не D_α(qα,W,A ∥ q).

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

Августина, приведенное в (25), и определение августиновской пропускной способно-

сти, получаем следующие выражения:

⎧

⎨sup

inf

D₁(V ∥W |p) + I₁(p; V ), α ∈ (0, 1),

p∈A

V ∈P(Y|X) 1 - α

Cα,W,A =

⎩sup sup

D₁(V ∥W |p) + I₁(p; V ), α ∈ (1, ∞).

p∈A V ∈P(Y |X) 1 - α

Тогда

Cα,W,A = sup sup

D₁(V ∥W |p) + I₁(p; V )

∀α ∈ (1, ∞).

V ∈P(Y|X) p∈A 1 - α

Следующая лемма утверждает, что для α ∈ (0, 1), если множество ограничений A

имеет августиновский центр порядка α, например, когда A выпукло, можно изме-

нить порядок супремума и инфимума, а также заменить инфимум на минимум,

когда августиновская пропускная способность конечна.

Лемма 22. Для любого α ∈ (0,1), если множество ограничений A для канала

W : X → P(Y) имеет августиновский центр порядка α, то

Cα,W,A = inf sup

D₁(V ∥W |p) + I₁(p; V ).

(47)

V ∈P(Y|X) p∈A 1 - α

Если Cα,W,A конечна, то для

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

(

)

(

)

Cα,W,A = sup

D₁

∥W|p

+I₁

(48)

p∈A 1 - α

Лемма 22 доказывается с использованием представления Чисара для информа-

ции Августина, данное в лемме 13(e), и леммы 20. В [36] Блейхут доказал аналогич-

ный результат в предположении, что и X, и Y - конечные множества, а A = P(X).

Даже при таких предположениях из результата Блейхута [36, теорема 16] следуют

равенства (47) и (48) для всех порядков (0, 1), только когда C_α,W - дифференцируе-

мая функция порядка α. Мотивацией Блейхуту служило выражение для экспонен-

ты сферической упаковки, поэтому теорема 16 в [36] сформулирована в терминах

оптимального распределения на входе при данной скорости R ∈ (C0,W , C1,W ) и со-

ответствующего оптимального порядка α^∗(R).

¹⁷ В [8] ван Эрвен и Харремоес предположили, что неравенство sup Dα(W (x) ∥ q) ≥ Cα,W +

x∈X

+ Dα(qα,W ∥ q) справедливо для всех q ∈ P(Y), и доказали эту границу в случае α = ∞ в предполо-

жении, что Y счетно [8, теорема 37]. Мы подтвердили гипотезу ван Эрвена - Харремоеса в [13, лем-

ма 19] и обобщили ее на случай выпуклого множества ограничений для пропускной способности

и центра Реньи в [13, лемма 25]. Краткое обсуждение пропускной способности и центра Реньи

см. в п. 4.4; более полное обсуждение можно найти в [13].

4.2. Августиновские пропускная способность и центр как функции порядка.

Лемма 23. Для любого канала W вида W : X → P(Y) и любого множества

ограничений A ⊂ P(X) справделивы следующие утверждения:

(a) Cα,W,A - неубывающая и полунепрерывная снизу по α функция на R₊;

1-α

(b)

Cα,W,A - невозрастающая и непрерывная по α функция на¹⁸ (0, 1);

(d) Cα,W,A - неубывающая и непрерывная по α функция на (0, 1] и (1, χW,A], где

χW,A ≜ sup{φ : Cφ,W,A ∈ R≥0};

(e) Если sup Igφ(p; W ) ∈ R≥0 для φ > 1, то Cα,W,A - неубывающая и непрерывная

p∈A

по α функция на (0, (1 ∨ χW,A)].

Результаты о непрерывности, представленные в утверждениях (d) и (e), несколь-

ко неудовлетворительны. Хотелось бы либо установить непрерывность Cα,W,A спра-

ва в точке α = 1, когда Cφ,W,A конечна для φ > 1, либо указать канал W и множество

ограничений A, для которых Cφ,W,A конечна для φ > 1 и lim

Cα,W,A > C1,W,A. Нам

α↓1

не удалось ни то, ни другое. Вместо этого мы доказали непрерывность Cα,W,A справа

в точке α = 1, предполагая, что sup Igφ(p; W) конечен для φ > 1.

p∈A

Так как C_φ,W = S_φ,W по теореме 1, а Igφ(p; W ) ≤ S_φ,W для всех p ∈ P(X) со-

гласно (33), то sup Igφ(p; W ) конечен для всех A ⊂ P(X), когда C_φ,W конечна. Таким

p∈A

образом, Cα,W,A - неубывающая и непрерывная по α функция на (0, χW,A] для всех

A ⊂ P(X) при условии, что C_φ,W конечна для φ > 1.

Лемма 21 позволяет использовать непрерывность Cα,W,A по α и лемму 2 для

доказательства непрерывности qα,W,A по α в топологии полной вариации на P(Y).

Лемма 24. Для любого η ∈ R₊, W : X → P(Y) и любого выпуклого A ⊂ P(X),

такого что Cη,W,A ∈ R₊, справедливо неравенство

Dα∧1(qα,W,A ∥qφ,W,A) ≤ Cφ,W,A - Cα,W,A

∀α, φ, таких что 0 < α < φ ≤ η.

Следовательно, если Cα,W,A непрерывна по α на I для некоторого I ⊂ (0, η], то

qα,W,A : I → P(Y) непрерывна по α на I в топологии полной вариации на P(Y).

4.3. Выпуклые оболочки и произведения множеств ограничений. Далее мы рас-

смотрим два вида часто встречающихся множеств ограничений, описываемых че-

рез более простые множества ограничений. В лемме 25 рассматривается выпуклая

оболочка семейства множеств ограничений и граница на августиновскую пропуск-

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

сти индивидуальных множеств ограничений. В лемме 26 рассматривается канал-

произведение для множества ограничений, являющегося произведением выпуклых

оболочек множеств ограничений на каналы-компоненты, имеющие августиновские

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

ся в аддитивной форме, а августиновский центр - в форме произведения.

Лемма 25. Пусть α - положительное вещественное число, W - канал вида

W : X → P(Y), а A(i) - множество ограничений, имеющее августиновский центр

порядка α и конечную Cα,W,A(i) для всех i ∈ T. Тогда

∑

supCα,W,A(i) ≤ Cα,W,A ≤ ln

e^Cα,W,A(i) ,

i∈T

¹⁸ Случай α = 1 мы исключаем, поскольку не хотим предполагать C1,W,A конечной.

(

)

⋃

где A - выпуклая оболочка объединения, т.е. A = ch

A(i)

. Кроме того,

i∈T

• Cα,W,A(i)

= Cα,W,A < ∞ ⇔ sup

D_α(W ∥qα,W,A(i) |p) ≤ Cα,W,A(i)

⇒ qα,W,A =

p∈A

= qα,W,A(i) ;

∑

• Cα,W,A = ln e^Cα,W,A(i)

< ∞ ⇔ qα,W,A(i) ⊥ qα,W,A(j) ∀i = j и |T| < ∞ ⇒

i∈T

∑

e^Cα,W,A(i)

⇒ qα,W,A =

qα,W,A(i) .

i∈T eCα,W,A

Отметим, что если A(i) выпукло, а Cα,W,A(i) конечна, то A(i) имеет единственный

августиновский центр порядка α по теореме 1.

Лемма 26. Для любых α ∈ R₊, канала-произведения W[1,n]: Xn1 → P(Yn1 ) дли-

ны n и множеств ограничений A_t ⊂ P(X_t), имеющих августиновские центры по-

рядка α,

∑

C_α,W

[1,n],A =^Cα,W[1,n],Aⁿ =1

Cα,Wt,At ,

t=1

{

}

где A =

p ∈ P(Xn1) : p_t ∈ chA_t ∀t ∈ {1,...,n}

, т.е. p ∈ P(Xn1) принадлежит A

тогда и только тогда, когда для всех t ∈ {1, . . . , n} его маргинальное распределе-

ние p_t на X_t лежит в выпуклой оболочке A_t. Кроме того, если Cα,Wt,At конечна

⊗

для всех t ∈ {1, . . . , n}, то qα,W[1,n],A = qα,W[1,n],Aⁿ =

qα,Wt,At .

t=1

Замечание 2. Заметим, что выпуклая оболочка любого подмножества A явля-

ется подмножеством A, поскольку A выпукло по определению. В частности, An1 ⊂

∑

⊂ ch An1 ⊂ A. Тогда C_α,W

[1,n],ch A1

= Cα,Wt,At по лемме 26. Кроме того, если

t=1

⊗

Cα,Wt,At конечна для всех t ∈ {1, . . ., n}, то qα,W[1,n],ch Aⁿ =

qα,Wt,At по лемме 25.

t=1

Замечание 3. Множество ограничений An1, описанное в лемме 26, может не быть

выпуклым, но обязано An1 иметь августиновский центр порядка α.

4.4. Сравнения пропускных способностей Августина и Реньи. Используя инфор-

мацию Реньи вместо информации Августина, можно определить пропускную спо-

собность Реньи следующим образом.

Определение 12. Для любых α ∈ R₊, W : X → P(Y) и A ⊂ P(X) пропускной

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

ется

Cgα,W,A ≜ sup Igα(p; W).

p∈A

Когда множество ограничений A совпадает со всем P(X), пропускная способность

Реньи порядка α обозначается через Cgα,W , т.е. Cgα,W ≜ Cgα,W,P(X).

Так как I₁(p; W ) = I^g1(p; W ), то Cg1,W,A = C1,W,A по определению. Для других

порядков утверждать этого нельзя; согласно (40), (41) имеем

Cgα,W,A ≤ Cα,W,A, α ∈ (0, 1],

Cgα,W,A ≥ Cα,W,A, α ∈ [1, ∞).

Из определений информации Реньи и пропускной способности Реньи следует, что

Cgα,W,A = sup

inf D_α(p ⊛ W ∥ p ⊗ q).

p∈A

q∈P(Y)

Для пропускной способности Реньи имеет место теорема о минимаксе [13, теорема 2],

аналогичная теореме 1: Для любого выпуклого множества ограничений A ⊂ P(X)

sup

inf

D_α(p ⊛ W ∥p ⊗ q) = inf sup D_α(p ⊛ W ∥p ⊗ q).

p∈A

q∈P(Y)

q∈P(Y)p∈A

Если Cgα,W,A конечна, то ∃! qgα,W,A ∈ P(Y), называемая центром Реньи порядка α

канала W для множества ограничений A, для которой

(

)

Cgα,W,A = sup D_α

p⊛W∥p⊗qgα,W,A

p∈A

Следовательно, пропускная способность Реньи равна радиусу Реньи при условии,

что A = P(X). Отсюда Cgα,W = C_α,W и qgα,W = q_α,W по теореме 1. Остальные наблю-

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

способности и центра Реньи; ср., например, лемму 21 и [13, лемма 25].

§ 5. Задача при наличии ограничений по стоимости

В §4 мы определили августиновскую пропускную способность для произвольных

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

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

ской пропускной способностью. Представляющие содержательный интерес выпук-

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

основная цель настоящего параграфа - исследовать этот важный частный случай бо-

лее подробно. В п. 5.1 рассматриваются прямые следствия определения августинов-

ской пропускной способности при наличии ограничений по стоимости и уточнения

некоторых приведенных выше. В п. 5.2 определяются и исследуются понятия ин-

формации, пропускной способности, радиуса и центра Августина - Лежандра (АЛ).

Результаты п. 5.2 являются обобщением некоторых результатов из [5, гл. 8] о су-

премуме взаимной информации для дискретных каналов с одним ограничением по

стоимости, т.е. для случая α = 1, |X| < ∞, |Y| < ∞, ℓ = 1. В п. 5.3 определяют-

ся и изучаются понятия информации, среднего, пропускной способности, радиуса и

центра Реньи - Галлагера (РГ). Наиболее важный результат анализа в п. 5.3 - ра-

венство АЛ-пропускной способности и АЛ-центра, соответственно, РГ-пропускной

способности и РГ-центру. В п. 5.4 показано, как можно использовать результаты

пп. 5.1-5.3 для нахождения августиновских пропускной способности и центра для

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

утверждений, представленных в пп. 5.1-5.3, можно найти в [22, Приложение E].

В [6, § 34] Августин рассматривал пропускную способность при наличии огра-

ничений по стоимости C_α,W,ϱ для случая, когда функция стоимости ρ имеет вид

ρ: X → [0,1]^ℓ, а α ∈ (0,1]. Там же были исследованы некоторые величины, тесно

связанные с РГ-информацией и РГ-пропускной способностью, которые впервые по-

явились у Галлагера при изучении экспонент вероятности ошибки в каналах при

наличии ограничений по стоимости [14, § 6; 15, §§ 7.3-7.5]. В отличие от Августи-

на Галлагер не предполагал функцию ρ ограниченной, однако Галлагер ограни-

чивался случаем одного ограничения по стоимости, т.е. случаем ℓ = 1, и не рас-

сматривал РГ-пропускную способность как величину, имеющую самостоятельный

интерес. РГ-информацию и РГ-пропускную способность рассматривали некоторые

другие авторы при изучении вопросов, связанных с ограничениями по стоимости

[24, § IV; 25-27]. Однако, насколько нам известно, для порядков, отличных от еди-

ницы, АЛ-информационные величины, получаемые более прямым применением вы-

пуклого сопряжения, ранее не изучались.

5.1. Августиновские пропускная способность и центр при наличии ограничений

по стоимости. Обозначим множество всех функций вероятности, удовлетворяющих

ограничению по стоимости ϱ, через A(ϱ), т.е.

A(ϱ) ≜ {p ∈ P(X) : E_p[ρ] ≤ ϱ}.

При этом A(ϱ) = ∅ тогда и только тогда, когда ϱ ∈ Γ_ρ, где Γ_ρ определено в (6) как

множество всех допустимых ограничений по стоимости для функции стоимости ρ.

Функция A(ϱ) не убывает по ϱ, т.е. если ϱ₁ ≤ ϱ₂, то A(ϱ₁) ⊂ A(ϱ₂). Августиновской

пропускной способностью порядка α канала W при ограничении по стоимости ϱ

называется

⎧

⎨ sup

Iα(p; W ), если ϱ ∈ Γρ,

C_α,W,ϱ ≜

p∈A(ϱ)

∀α ∈ R₊.

(49)

^⎩-∞,

если ϱ ∈ Rℓ≥0 \ Γ_ρ,

Мы определили C_α,W,ϱ для недопустимых значений ϱ, чтобы иметь возможность

пользоваться стандартными результатами без изменений. Так как множество A(ϱ)

выпукло, для него справедлива теорема 1. Обозначим¹⁹ августиновский центр по-

рядка α канала W при ограничении по стоимости ϱ через q_α,W,ϱ.

Для заданного порядка α августиновская пропускная способность C_α,W,ϱ являет-

ся вогнутой функцией ограничения по стоимости ϱ. Следовательно, если она конечна

во внутренней точке множества Γ_ρ, то она является непрерывной функцией ограни-

чения по стоимости ϱ ниже касательных плоскостей к внутренним точкам Γ_ρ. Эти

наблюдения обобщает следующая

Лемма 27. Пусть W - канал вида W : X → P(Y) с функцией стоимости ρ

вида ρ: X → Rℓ≥0.

(a) Для любого α ∈ R₊ функция C_α,W,ϱ не убывает и вогнута по ϱ на Rℓ≥0 и при

этом либо бесконечна в любой точке из intΓ_ρ, либо конечна и непрерывна на

int Γ_ρ;

(b) Если C_α,W,ϱ конечна на int Γ_ρ для некоторого α ∈ R₊, то для любого ϱ ∈ int Γ_ρ

существует λ_α,W,ϱ ∈ Rℓ≥0, такое что

C_α,W,ϱ + λ_α,W,ϱ · (ϱ- ϱ) ≥ C_α,W,ϱ

∀ϱ ∈ Rℓ≥0

(50)

Кроме того, множество всех таких λ_α,W,ϱ выпукло и компактно;

по (α, ϱ) на (0, 1) × intΓ_ρ в топологии полной вариации на P(Y).

Если функция стоимости для канала-произведения аддитивна, то августинов-

ская пропускная способность при наличии ограничений по стоимости для канала-

произведения равна супремуму суммы августиновских пропускных способностей

при наличии ограничений по стоимости для каналов-компонентов по всем допу-

стимым распределениям стоимости. Кроме того, если существует оптимальное рас-

пределение стоимости, то августиновский центр канала-произведения является про-

изведением мер. Эти наблюдения формализует следующая

Лемма 28. Для любого канала-произведения W[1,n]: Xn1 → P(Yn1) длины n и

любой аддитивной функции стоимости ρ[1,n] : Xn1 → Rℓ≥0 имеет место равенство²⁰

¹⁹ Эта небольшая вольность в обозначениях, которой можно было бы избежать, используя

Cα,W,A(ϱ) и qα,W,A(ϱ) вместо C_α,W,ϱ и q_α,W,ϱ, упрощает обозначения и не приводит к недора-

зумениям.

∑

²⁰ Если Cα,Wt,ϱt = -∞ для всех t ∈ {1, . . . , n}, то сумма

Cα,Wt,ϱt равна -∞, даже если одна

или несколько других Cα,Wt,ϱt равны ∞.

t=1

{

}

∑

C_α,W

sup

ϱ_t ≤ ϱ, ϱ_t ∈ R^ℓ

∀ϱ ∈ Rℓ≥0, α ∈ R₊.

[1,n],ϱ =

Cα,Wt,ϱt :

≥0

t=1

Если C_α,W

[1,n],ϱ ∈^R≥0длянекоторогоα∈R+и∃(ϱ1^,...,ϱn),такиечтоCα,W[1,n],ϱ⁼

∑

⊗

Cα,Wt,ϱt , то qα,W[1,n],ϱ⁼

qα,Wt,ϱt .

t=1

Так как августиновская пропускная способность вогнута как функция ограниче-

∑

ния по стоимости согласно лемме 27(a), то C_α,W

[1,n],ϱ =

C_α,W

t,ϱ/n,

когда W[1,n] -

t=1

стационарный канал и ρ_t = ρ₁ для всех t ∈ {1, . . . , n}. Напротив, если Γρt - за-

мкнутые множества, а Cα,Wt,ϱ - полунепрерывные сверху функции ϱ на множе-

ствах Γρt , то теорема об экстремуме²¹ для полунепрывных функций дает существо-

∑

вание (ϱ₁, . . ., ϱ_n), удовлетворяющих условиям C_α,W

ϱ_t ≤ ϱ.

[1,n],ϱ =

Cα,Wt,ϱt и

t=1

Однако это утверждение о существовании в общем случае не верно - см. пример 3.

5.2. Информационные величины Августина - Лежандра. Августиновскую про-

пускную способность при наличии ограничений по стоимости C_α,W,ϱ и августинов-

ский центр q_α,W,ϱ можно также охарактеризовать, используя выпуклое сопряжение.

В этом пункте мы вводим понятия информации, пропускной способности, центра

и радиуса Августина - Лежандра, позволяющие прийти к более полному понима-

нию этой характеризации. Подходящим методом нам видится стандартное примене-

ние техники выпуклого сопряжения для характеризации августиновской пропускной

способности при наличии ограничений по стоимости. Однако этот метод не являет-

ся общепринятым. Начиная с оригинальной работы Галлагера [14], стандартным

способом применения техники множителей Лагранжа для характеризации августи-

новской пропускной способности стал более подходящий для данного случая метод,

основанный на информации Реньи - см. [6, § 35; 25; 26]. Этот подход обсуждается

в п. 5.3. Теорема 2, приведенная ниже, и теорема 3 из п. 5.3 доказывают эквива-

лентность этих подходов, устанавливая равенство пропускной способности и центра

Августина - Лежандра, соответственно, пропускной способности и центру Реньи -

Галлагера.

Определение 13. Для любых α ∈ R₊, канала W вида W : X → P(Y) с функ-

цией стоимости ρ: X → Rℓ≥0, p ∈ P(X) и λ ∈ Rℓ≥0 информацией Августина - Лежан-

дра порядка α для распределения на входе p и множителя Лагранжа λ называется

I^λα(p; W) ≜ I_α(p; W) - λ · E_p[ρ].

(51)

Заметим, что немедленным следствием определения АЛ-информации является

равенство

inf

I^λα(p; W) + λ · ϱ = ξ_α,p(ϱ),

λ≥0

где ξ_α,p(·): Rℓ≥0 → [-∞, ∞) определяется как

^{I_α(p; W ), ϱ ≥ E_p[ρ],

ξ_α,p(ϱ) ≜

(52)

-∞

в противном случае.

∑

²¹ Рассмотрим функцию f(ϱ₁, . . . , ϱn), равную

Cα,Wt,ϱt , если

ϱt ≤ ϱ и ϱt ∈ Γρt для всех

t=1

t ∈ {1,...,n}, и равную -∞ в противном случае. Выбирая достаточно большое, но ограниченное

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

Тогда информацию Августина - Лежандра I^λα(p; W ) можно также задать в виде

I^λα(p; W) = supξ_α,p(ϱ) - λ · ϱ.

(53)

ϱ≥0

Замечание 4. Заметим, что если функции f : Rℓ≥0 → (-∞, ∞] и f^∗ : (-∞, 0]^ℓ → R

определить как f(ϱ) ≜ -ξ_α,p(ϱ) и f^∗(γ) ≜ I^-γα (p; W ), то f^∗ является выпукло сопря-

женной функцией, т.е. преобразованием Лежандра, для f. Именно по этой причине

мы называем I^λα(p; W ) информацией Августина - Лежандра.

Определение 14. Для любых α ∈ R₊, канала W вида W : X → P(Y) с функ-

цией стоимости ρ: X → Rℓ≥0 и λ ∈ Rℓ≥0 пропускной способностью Августина - Ле-

жандра (АЛ-пропускной способностью) порядка α для множител Лагранжа λ на-

зывается

C^λα,W ≜ sup I^λα(p; W).

(54)

p∈P(X)

Тогда из (52), (53) вытекает

C^λα,W = supC_α,W,ϱ - λ · ϱ

∀λ ∈ Rℓ≥0.

(55)

ϱ≥0

Следовательно, из неравенства максимина-минимакса получаем

C_α,W,ϱ ≤ inf

C^λα,W + λ · ϱ

∀ϱ ∈ Rℓ≥0.

(56)

λ≥0

Поэтому C_α,W,ϱ < ∞ для всех ϱ ∈ Rℓ≥0 при условии, что C^λα,W < ∞ для некоторого

λ ∈ R≥0. Но равенство C^λα,W = ∞ может выполняться для достаточно малых λ,

когда C_α,W,ϱ < ∞ для всех ϱ ∈ Rℓ≥0, - см. пример 1.

Замечание 5. В [6, §§ 33-35], Августин рассмотрел случай, когда функция стои-

мости ρ является ограниченной функцией вида ρ: X → [0, 1]^ℓ. В этом случае C^λα,W <

< ∞ для всех λ ∈ Rℓ≥0 при условии, что C_α,W,ϱ < ∞ для некоторого ϱ ∈ intΓ_ρ, по-

скольку Cα,W,1 < ∞ согласно лемме 27(b), а Cα,W,1 = C_α,W и C^λα,W ≤ C0α,W = C_α,W

для всех λ ∈ Rℓ≥0 по определению.

Неравенство (56) во многих содержательных случаях обращается в равенство,

как показывает следующая лемма. Однако в общем случае оно равенством не явля-

ется - см. пример 2.

Лемма 29. Пусть α ∈ R₊, и пусть W - канал вида W : X → P(Y) с функцией

стоимости ρ: X → Rℓ≥0. Тогда

(a) Cλα,W - выпуклая невозрастающая полунепрерывная снизу по λ функция на

{

}

Rℓ≥0, непрерывная по λ на множестве

λ : ∃ε > 0, такое что Cλ-ε1α,W < ∞

;

(b) Если X - конечное множество, то C_α,W,ϱ = inf

C^λα,W + λ · ϱ;

λ≥0

C^λα,W + λ · ϱ. Если при этом C_α,W,ϱ < ∞, то

λ≥0

существует непустое выпуклое компактное множество значений λ_α,W,ϱ, для

+ λ_α,W,ϱ · ϱ;

(d) Если C_α,W,ϱ конечна и C_α,W,ϱ = C^λα,W +λ·ϱ для некоторых ϱ ∈ Γ_ρ и λ ∈ Rℓ≥0, то

lim

I^λα(p(i); W) = C^λα,W для всех {p(i)}i∈Z

∈ A(ϱ), таких что lim

Iα(p(i); W ) =

i→∞

=C_α,W,ϱ.

Используя определения величин I_α(p; W), I^λα(p; W) и C^λα,W , данные в (17), (51)

и (54), получаем следующее выражение для C^λα,W :

C^λα,W = sup

inf D_α(W ∥ q | p) - λ · E_p[ρ].

(57)

p∈P(X)

q∈P(Y)

АЛ-пропускная способность удовлетворяет теореме о минимаксе, аналогичной

теореме о минимаксе для августиновской пропускной способности, что позволяет

утверждать существование и единственность АЛ-центра в случае, когда АЛ-про-

пускная способность конечна.

Теорема 2. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стоимости

ρ: X → Rℓ≥0 и множителя Лагранжа λ ∈ Rℓ≥0 справедливы равенства

sup

inf

D_α(W ∥q |p)-λ·E_p[ρ] = inf sup D_α(W ∥q |p)-λ·E_p[ρ] =

(58)

p∈P(X)

q∈P(Y)

q∈P(Y)p∈P(X)

= inf sup D_α(W (x) ∥ q) - λ · ρ(x).

(59)

q∈P(Y)x∈X

Если выражение в левой части (58) конечно, т.е. если C^λα,W < ∞, то ∃! q^λα,W ∈

∈ P(Y), называемая центром Августина-Лежандра порядка α канала W для мно-

жителя Лагранжа λ, такая что

(

)

C^λα,W = sup D_α

W∥q^λα,W |p

- λ · E_p[ρ] =

(60)

p∈P(X)

(

)

= sup D_α

W (x) ∥ q^λα,W

- λ · ρ(x).

(61)

x∈X

Кроме того, для любой последовательности распределений на входе {p(i)}

⊂

i∈Z+

⊂ P(X), такой что lim

I^λα(p(i); W) = Cλα,W, соответствующая последователь-

i→∞

ность {q_α,p(i) }

августиновских средних порядка α является последовательно-

i∈Z+

стью Коши в метрике полной вариации на P(Y), а q^λα,W - единственная предельная

точка этой последовательности Коши.

Заметим, что теорема 2 при λ = 0 есть ни что иное, как теорема 1 для A = P(X).

Доказательство теоремы 2 также очень похоже на доказательство теоремы 1, но

вместо леммы 19 оно использует следующую лемму 30. Отметим, что лемма 30 при

λ = 0 также есть ни что иное, как лемма 19 для A = P(X).

Лемма 30. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стоимости

ρ: X → Rℓ≥0 для конечного множества входов X и множителя Лагранжа λ ∈ Rℓ≥0

существует p ∈ P(X), такое что I^λα(p; W ) = C^λα,W , и ∃! q^λα,W ∈ P(Y), такое что

(

)

D_α

W∥q^λα,W |p

- λ · E_p[ρ] ≤ C^λα,W

∀p ∈ P(X).

Кроме того, q_α,p = q^λα,W для всех p∈ P(X), таких что I^λα(p; W) = C^λα,W .

Заметим, что выражение в левой части (58) есть ни что иное, как АЛ-пропускная

способность. Таким образом, теорема 2 устанавливает равенство АЛ-пропускной

способности и АЛ-радиуса, определяемого следующим образом.

Определение 15. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стои-

мости ρ: X → Rℓ≥0 и λ ∈ Rℓ≥0 радиусом Августина - Лежандра порядка α канала W

для множителя Лагранжа λ называется

S^λα,W ≜ inf sup D_α(W(x)∥q) - λ · ρ(x).

(62)

q∈P(Y)x∈X

Если C^λα,W конечна, то из леммы 13(b)-(d), теоремы 2 и определения величины

I^λα(p; W), данного в (51), следует, что

(

)

C^λα,W - I^λα(p; W) ≥ Dα∧1

q_α,p ∥q^λα,W

∀p ∈ P(X).

C помощью леммы 13 и теоремы 2 можно также получить границу, аналогичную

границе из леммы 21. Однако этого мы делать не будем, поскольку несколько более

сильные результаты можно получить, используя характеризацию АЛ-пропускной

способности и АЛ-центра через РГ-пропускную способность и РГ-центр, описанную

в п. 5.3, - см. лемму 35 и последующее обсуждение.

Как следствие леммы 29(c), мы знаем, что если C_α,W,ϱ конечна для некоторо-

го ϱ ∈ intΓ_ρ, то существует по крайней мере один множитель Лагранжа λ_α,W,ϱ,

+ λ_α,W,ϱ · ϱ. Следующая лем-

ма 31 утверждает, что для любого такого множителя Лагранжа соответствующий

АЛ-центр порядка α должен быть равен августиновскому центру порядка α для

ограничения по стоимости ϱ. Таким образом, если существуют несколько λ_α,W,ϱ, та-

+ λ_α,W,ϱ · ϱ, то все они имеют один и тот же АЛ-центр

порядка α.

Лемма 31. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стоимости

ρ: X → Rℓ≥0 и ограничения по стоимости ϱ ∈ Γ_ρ, таких что C_α,W,ϱ < ∞, если

C_α,W,ϱ = C^λα,W + λ · ϱ для некоторого λ ∈ Rℓ≥0, то q_α,W,ϱ = q^λα,W .

Для произведений множеств ограничений в каналах-произведениях августинов-

ская пропускная способность представляется в аддитивном виде, а августиновский

центр - в мультипликативном (когда он существует) по лемме 26. Однако ограниче-

ния по стоимости для аддитивных функций стоимости не имеют вид произведений.

Чтобы вычислить августиновскую пропускную способность при наличии ограниче-

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

сти, требуется провести оптимизацию по допустимым распределениям стоимости

по каналам-компонентам согласно лемме 28. При этом августиновский центр при

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

мощью леммы 28 в виде произведения августиновских центров при наличии ограни-

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

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

стороны, для АЛ-пропускной способности и АЛ-центра имеется значительно более

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

АЛ-пропускная способность аддитивна, а АЛ-центр мультипликативен, если он су-

ществует.

Лемма 32. Для любого канала-произведения W[1,n]: Xn1 → P(Yn1) длины n и

любой аддитивной функции стоимости ρ[1,n] : Xn1 → Rℓ≥0 выполнено равенство

∑

C^λ

C^λα,W

∀λ ∈ Rℓ≥0, α ∈ R₊.

α,W[1,n]

t=1

⊗

Кроме того, если C^λα,W

< ∞, то q^λ

q^λ

[1,n]

α,W[1,n]

α,Wt

t=1

Из аддитивности функции стоимости ρ[1,n] следует, что для любого p ∈ P(Xn1)

∑

E_p[ρ[1,n]] =

Ept [ρ_t],

t=1

где p_t ∈ P(X_t) - маргинальное распределение для p на X_t. Таким образом, из лем-

мы 14 и определения АЛ-информации следует, что

(

)

(

)

∑

I^λα

p; W[1,n]

≤I^λα

p₁ ⊗ . . . ⊗ p_n; W[1,n]

= I^λα(p_t; W_t).

(63)

t=1

Лемма 32 доказывается с помощью соотношения (63) и теоремы 2.

5.3. Информационные величины Реньи - Галлагера. В п. 5.2 была дана характе-

ризация августиновских пропускной способности и центра при наличии ограничений

по стоимости через АЛ-пропускную способность и АЛ-центр. АЛ-пропускная спо-

собность определяется как супремум АЛ-информации. В [14, формулы (103), (116)]

Галлагер (неявно) предложил другую меру информации с множителем Лагранжа.

Через супремум этой информации Августин в [6, леммы 35.4(b), 35.8(b)] охаракте-

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

имости в предположении, что функция стоимости ограничена. Мы называем этот

супремум РГ-пропускной способностью. Основная цель этого пункта - установить

равенство АЛ-пропускной способности и АЛ-центра, соответственно, РГ-пропускной

способности и РГ-центру. Мы также выведем границу ван Эрвена - Харремоеса для

АЛ-пропускной способности и АЛ-центра и применим ее для доказательства непре-

рывности АЛ-центра как функции множителя Лагранжа λ.

Определение 16. Для любых α ∈ R₊, канала W : X → P(Y) с функцией сто-

имости ρ: X → Rℓ≥0, p ∈ P(X) и λ ∈ Rℓ≥0 информацией Реньи - Галлагера (РГ-ин-

формацией) порядка α для распределения на входе p и множителя Лагранжа λ

называется

⎧

(

)

⎨

inf D_α

p⊛We¹

^λ·ρ ∥ p ⊗ q

α ∈ R₊ \ {1},

q∈P(Y)

Igλα

(p; W ) ≜

(64)

⎩ inf D₁(p ⊛ W ∥ p ⊗ q) - λ · E_p[ρ], α = 1.

q∈P(Y)

Если λ - нулевой вектор, то РГ-информация совпадает с информацией Реньи.

Как и для информации Реньи, для РГ-информации имеется выражение в замкнутом

виде через вероятностную меру, доставляющую минимум в ее определении.

Определение 17. Для любых α ∈ R₊, канала W : X → P(Y) с функцией сто-

имости ρ: X → Rℓ≥0, p ∈ P(X) и λ ∈ Rℓ≥0 средней мерой порядка α для распределения

на входе p и множителя Лагранжа λ называется

dμ^λ

[∑

α,p

⁽ dW (x))α]^α

≜

p(x)e(1-α)λ·ρ(x)

dν

Средним Реньи - Галлагера (РГ-средним) порядка α для распределения на входе p и

множителя Лагранжа λ называется

μ^λα,p

qgλα,p ≜

∥μ^λα,p∥

Как μ^λα,p, так и qgλα,p зависят от множителя Лагранжа λ при α ∈ R₊ \ {1}. Кроме

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

(

)

D_α

p⊛We¹

^λ·ρ ∥ p ⊗ q

(

)

(

)

=D_α

p⊛We¹

^λ·ρ ∥ p ⊗ qgλα,p

+D_α

qgλα,p ∥q

α ∈ R₊ \ {1}.

(65)

Тогда по лемме 2 получаем

(

)

Igλα(p; W) = D_α

p⊛We¹

^λ·ρ ∥ p ⊗ qgλα,p

(66)

ln ∥μ^λα,p∥, α ∈ R₊ \ {1}.

(67)

α-1

Ни μλ1,p, ни qgλ1,p не зависят от множителя Лагранжа λ. Кроме того, непосредственной

подстановкой можно убедиться, что

(

)

(

)

D₁(p ⊛ W ∥p ⊗ q) - λ · E_p[ρ] = D₁

p⊛W∥p⊗qgλ1,p

- λ · E_p[ρ] + D₁

qgλ1,p ∥q

(68)

Тогда по лемме 2 получаем

(

)

Igλ1(p; W) = D₁

p⊛W∥p⊗qgλ1,p

- λ · E_p[ρ].

(69)

Используя определения АЛ- и РГ-информации, данные в (51) и (64), с учетом нера-

венства Йенсена и вогнутости функции натурального логарифма получаем

I^λα(p; W) ≥ Igλα(p; W), α ∈ (0, 1],

I^λα(p; W) ≤ Igλα(p; W), α ∈ [1, ∞).

Эти соотношения можно усилить, выражая АЛ- и РГ-информацию друг через друга

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

Лемма 33. Пусть W - канал вида W : X → P(Y) с функцией стоимости

ρ: X → Rℓ≥0, p ∈ P(X) - распределение на входе, а λ ∈ Rℓ≥0 - множитель Лагранжа.

(1-α)Dα(W (x)∥qα,p)+(α-1)λ·ρ(x)

(a) Пусть u^λα,p ∈ P(X) имеет вид u^λα,p(x)

∑

для

p(x)e(1-α)Dα(W(x)∥qα,p)+(α-1)λ·ρ(x)

всех x, тогда

I^λα(p; W) = Igλα(u_α,p; W) +

D₁(p∥u_α,p) =

α-1

⎧

⎪

⎨

sup

Igλα(u; W) +

D₁(p∥u), α ∈ (0, 1),

u∈P(X)

α-1

⎪

⎩ inf

Igλα(u; W) +

D₁(p∥u), α ∈ (1, ∞);

u∈P(X)

α-1

)+(1-α)λ·ρ(x)

(b) Пусть a^λα,p ∈ P(X) имеет вид a^λα,p(x) =p(x)e(α-1)Dα(W(x)∥qα

для

,p )+(1-α)λ·ρ(x)

всех x, тогда

^∑p(x)e(α-1)Dα(W(x)∥qα

(

)

(

)

Igλα(p; W) = I^λα

a^λα,p; W

D₁

a^λα,p ∥p

α-1

⎧

⎪

⎨

inf

I^λα(a; W) -

D₁(a∥p), α ∈ (0, 1),

a∈P(X)

α-1

⎪

I^λα(a; W) -

D₁(a∥p), α ∈ (1, ∞);

⎩ s

a∈P(X)

α-1

×1p(x)>0 для всех x, тогда

⎡

⎤

]_α)

1/α

(∑

^[ dW (x)

I^λα(p; W) =

ln E_ν ⎣

p(x)e(1-α)(fα,p(x)+λ·ρ(x))

⎦₌

α-1

dν

⎡

⎤

(

]_α)1/α

∑

^[ dW (x)

ln inf

p(x)e(1-α)(f(x)+λ·ρ(x))

⎦

Eν^⎣

α-1

f:Ep[f]=0

dν

Лемма 33 при λ = 0 превращается в лемму 18, что обсуждалось ранее в [6,10,19].

Определение 18. Для любых α ∈ R₊, канала W : X → P(Y) с функцией сто-

имости ρ: X → Rℓ≥0 и λ ∈ Rℓ≥0 пропускной способностью Реньи - Галлагера (РГ-про-

пускной способностью) порядка α для множителя Лагранжа λ называется

Cgλα,W ≜ sup Igλα(p; W).

p∈P(X)

Используя определение Igλα(p; W), данное в (64), получаем следующее выражение

для Cgλα,W :

⎧

(

)

⎨

sup

inf D_α

p⊛We¹

^λ·ρ ∥ p ⊗ q

α ∈ R₊ \ {1},

p∈P(X)

q∈P(Y)

Cgλα,W =

⎩ sup

inf D_α(p ⊛ W ∥ p ⊗ q) - λ · E_p[ρ], α = 1.

p∈P(X)

q∈P(Y)

Для РГ-пропускной способности имеет место теорема о минимаксе, аналогичная

теореме о минимаксе для АЛ-пропускной способности, т.е. теореме 2. Поскольку

утверждение и доказательство этих теорем для АЛ-пропускной способности поряд-

ка 1 и РГ-пропускной способности порядка 1 полностью идентичны, мы сформу-

лируем теорему о минимаксе для РГ-пропускной способности лишь для конечных

положительных порядков, отличных от единицы.

Теорема 3. Для любых α ∈ R₊ \ {1}, канала W : X → P(Y) с функцией стои-

мости ρ: X → Rℓ≥0 и множителя Лагранжа λ ∈ Rℓ≥0 справедливы равенства

(

)

sup

inf D_α

p⊛We¹

^λ·ρ ∥ p ⊗ q

(70)

q∈P(Y)

p∈P(X)

(

)

= inf sup D_α

p⊛We¹

^λ·ρ ∥ p ⊗ q

q∈P(Y)p∈P(X)

= inf sup D_α(W (x) ∥ q) - λ · ρ(x).

(71)

q∈P(Y)x∈X

Если выражение (70) конечно, т.е. если Cgλα,W < ∞, то ∃! qgλα,W ∈ P(Y), называемая

центром Реньи -Галлагера порядка α канала W для множителя Лагранжа λ, для

которой

(

)

Cgλα,W = sup D_α

p⊛We¹

^λ·ρ ∥ p ⊗ qgλα,W

(72)

p∈P(X)

(

)

= sup D_α

W (x) ∥ qgλα,W

- λ · ρ(x).

(73)

x∈X

Кроме того, для любой последовательности распределений на входе {p(i)}

⊂

i∈Z+

⊂ P(X), такой что lim

Igλα(p(i); W) = Cgλα,W , соответствующая последователь-

i→∞

{

}

ность

qgλ

средних Реньи -Галлагера порядка α является последователь-

α,p(i) i∈Z+

ностью Коши в метрике полной вариации на P(Y), а qgλα,W - единственная пре-

дельная точка этой последовательности Коши.

Доказательство теоремы 3 в значительной степени аналогично доказательствам

теорем 1 и 2. Вместо лемм 19 или 30 в нем используется следующая

Лемма 34. Для любых α ∈ R₊ \ {1}, канала W : X → P(Y) с функцией стои-

мости ρ: X → Rℓ≥0 для конечного множества входов X и множителя Лагранжа

λ ∈ Rℓ≥0 существует p ∈ P(X), такое что I^λα(p;W) = C^λα,W, и ∃!q^λα,W ∈ P(Y),

такая что

(

)

D_α

p⊛We¹

^λ·ρ ∥ p ⊗ qgλα,W

≤Cgλα,W

∀p ∈ P(X).

Кроме того, qgλα,̃p = qgλα,W для всех p∈ P(X), таких что Igλα(p; W) = Cgλα,W .

Выражение (70) задает РГ-пропускную способность, в то время как (71) задает

АЛ-радиус, определенный в (62). Таким образом, из теорем 2, 3 следует, что

C^λα,W = S^λα,W = Cgλα,W

∀α ∈ R₊, λ ∈ Rℓ≥0.

Кроме того, когда C^λα,W конечна, единственный АЛ-центр, описанный в (61), также

равен единственному РГ-центру, описанному в (73), по теоремам 2 и 3:

q^λα,W = qgλα,W

∀α ∈ R₊, λ ∈ Rℓ≥0, такие что C^λα,W < ∞.

Чтобы не использовать разные названия для одной и той же величины, всюду далее

мы будем формулировать утверждения в терминах АЛ-пропускной способности и

АЛ-центра.

Если C^λα,W конечна, то из формул (65), (66) и теоремы 3 для α ∈ R₊ \ {1}, а

также формул (68), (69) и теоремы 2 для α = 1 следует, что

(

)

C^λα,W - Igλα(p; W) ≥ D_α

qgλα,p ∥q^λα,W

∀p ∈ P(X).

С помощью этих же рассуждений можно также доказать границу ван Эрвена -

Харремоеса для АЛ-пропускной способности.

Лемма 35. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стоимости

ρ: X → Rℓ≥0 и множителя Лагранжа λ ∈ Rℓ≥0, таких что C^λα,W < ∞,

(

)

sup D_α(W(x)∥q) - λ · ρ(x) ≥ C^λα,W + D_α

q^λα,W ∥q

∀q ∈ P(Y).

x∈X

Аналогичный, но более слабый результат можно получить с помощью леммы 13

и тео(емы 2. ) оследний ч(лен соо)ветствующей границы в этом случае будет равен

Dα∧1

q^λα,W ∥q

вместо D_α

q^λα,W ∥q

Из леммы 35 и непрерывности АЛ-пропускной способности C^λα,W как функции λ,

установленной в лемме 29(a), по лемме 2 вытекает непрерывность АЛ-центра q^λα,W

по λ в топологии полной вариации на P(Y).

Лемма 36. Для любых α ∈ R₊, канала W : X → P(Y) с функцией стоимости

< ∞,

(

)

D_α

∀λ₁, λ₂ ∈ Rℓ≥0, таких что λ₀ ≤ λ₁ ≤ λ₂.

{

Кроме того, функция q^λα,W непрерывна по λ на множестве

λ : ∃ε > 0, такое что

}

Cλ-ε1α,W < ∞

в топологии полной вариации на P(Y).

5.4. Информационные величины для функций вероятностей переходов. Мы опре-

делили условное расхождение Реньи, информацию Августина, АЛ- и РГ-информа-

цию лишь для распределений на входе, лежащих в P(X), т.е. для функций вероят-

ности, равных нулю всюду, кроме конечного числа элементов множества X. Однако

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

входов X является несчетно бесконечным множеством, снабженным σ-алгеброй X .

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

можно, с многими входными и выходными антеннами и замиранием, а также пуас-

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

определения информации Августина и АЛ-информации с P(X) на P(X ). Напри-

мер, в аддитивных гауссовских каналах, описанных в примерах 4 и 5, равенство

Iα(p; W ) = Cα,W,ϱ не выполняется для любой функции вероятности p, удовлетворя-

ющей ограничению по стоимости, но выполняется для гауссовского распределения

с нулевым средним и дисперсией ϱ.

Далее мы вначале покажем, что если Y - счетно порожденная σ-алгебра, то опре-

деления условного расхождения Реньи, информации Августина и АЛ-информации

можно обобщить с P(X) на P(X ) при условии, что W и Q - не просто функции

из X в P(Y), а функции вероятностей переходов из (X, X ) в (Y, Y). Затем мы пока-

жем, что если при этом X счетно отделимо, то супремум АЛ-информации I^λα(p; W )

по P(X ) равен АЛ-радиусу S^λα,W (теорема 4). Из этого будет следовать, что авгу-

стиновская пропускная способность при наличии ограничений по стоимости C_α,W,ϱ,

определенная в (49), также равна супремуму информации Августина I_α(p; W ) по

элементам P(X ), таким что E_p[ρ] ≤ ϱ, по крайней мере, для ограничений по стоимо-

сти, принадлежащих внутренней области множества всех допустимых ограничений

(теорема 5).

Вначале напомним определение функции вероятностей переходов. Мы придер-

живаемся определения Богачева [21, определение 10.7.1] с небольшой поправкой:

используем W (E | x) вместо W (x | E).

Определение 19. Пусть (X,X) и (Y,Y) - измеримые пространства. Тогда

функция W : Y × X → [0, 1] называется функцией вероятностей переходов (стоха-

стическим ядром, марковским ядром) из (X, X ) в (Y, Y), если она удовлетворяет

следующим условиям:

(i) Для всех x ∈ X функция W (· | x): Y → [0, 1] является вероятностной мерой на

(Y, Y);

(ii) Для всех E ∈ Y функция W (E | ·): X → [0, 1] является (X , B([0, 1]))-измеримой.

Обозначим множество всех функций вероятностей переходов из (X, X) в (Y, Y)

через P(Y | X ), подразумевая при этом, что множества X и Y будут ясны из кон-

текста. Если W удовлетворяет условию (i), то W : X → P(Y) является каналом, т.е.

W - элемент P(Y |X), даже если W не удовлетворяет условию (ii). Следовательно,

P (Y | X ) ⊂ P(Y | X). В связи с этим наблюдением для удобства будем обозначать

вероятностную меру W(·|x) через W(x), когда это не вызовет разночтений.

Чтобы продолжить определение условного расхождения Реньи с P(X) на P(X),

убедимся в X -измеримости D_α(W (x) ∥ Q(x)) на X и заменим сумму в (15) интегра-

лом. Если (X, τ) - топологическое пространство, а X - ассоциированная с ним боре-

левская σ-алгебра, то для проверки измеримости можно сперва убедиться в непре-

dW(x)

dQ(x)

рывности, каковая имеет место, когда

непрерывны по x для ν-почти

dν

всех y для некоторой вероятностной меры ν, для которой (W(x) + Q(x)) ≺ ν для

всех x ∈ X. Иногда это предположение о W и Q бывает нелегко проверить. С другой

стороны, если W и Q - функции вероятностей переходов из (X, X) в (Y, Y) для счет-

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

измеримых функций и леммы 9, как показывает следующая

Лемма 37. Для любых α ∈ R₊, счетно порожденной σ-алгебры Y подмно-

жеств множества Y и W, Q ∈ P(Y |X) функция D_α(W(·)∥Q(·)): X → [0, ∞] явля-

ется X-измеримой.

Доказательство. Существует последовательность {E_i}

⊂ Y, такая что

i∈Z+

Y = σ({E_i : i ∈ Z₊}), поскольку Y - счетно порожденная σ-алгебра. Положим

Yi ≜ σ({E1, . . . , Ei}), i ∈ Z+.

)

⋃

Тогда Y₁ ⊂ Y₂ ⊂ . . . ⊂ Y, Y = σ

, и из леммы 9 следует, что

i=1

D_α(W(x)∥Q(x)) = lim

∀x ∈ X.

(74)

DYiα(W(x)∥Q(x))

i→∞

С другой стороны, множество Y_i конечно для любого i ∈ Z₊. Таким образом, для

всех i ∈ Z₊ существует Y_i-измеримое конечной разбиение E_i множества Y. Тогда

с учетом определения расхождения Реньи, данного в (8), получаем

⎧

∑

⎪

⎨

(W (E | x))^α (Q(E | x))1-α , α ∈ R₊ \ {1},

α-1

E∈Ei

DYiα(W(x)∥Q(x)) =⎪∑

W (E | x)

⎪

(E | x) ln

α = 1.

⎩ W

Q(E | x)

E∈Ei

Значит, DYiα (W (x) ∥ Q(x)) является X -измеримой функцией для любого i ∈ Z+ со-

гласно [21, теорема 2.1.5(i)-(iv) и замечание 2.1.6], поскольку W (E | x) и Q(E | x) -

X-измеримые функции для всех E ∈ E_i по условию леммы. Тогда из равенства (74)

следует, что D_α(W(x)∥Q(x)) - X-измеримая функция согласно [21, теорема 2.1.5(v)

и замечание 2.1.6].

Определение 20. Для любых α ∈ R₊, счетно порожденной σ-алгебры Y под-

множеств множества Y, W ∈ P(Y | X ) и p ∈ P(X ) условным расхождением Реньи

порядка α для распределения на входе p называется

∫

D_α(W ∥Q|p) ≜ D_α(W(x)∥Q(x))p(dx).

(75)

Если ∃q ∈ P(Y), такая что p-п.н. Q(x) = q, то будем обозначать D_α(W ∥ Q | p) через

D_α(W ∥q |p).

Теперь можно определить информацию Августина и АЛ-информацию для всех

p ∈ P(X) при условии, что W принадлежит P(Y |X) для счетно порожденной Y,

а ρ - X-измеримая функция.

Определение 21. Для любых α ∈ R₊, счетно порожденной σ-алгебры Y под-

множеств множества Y, W ∈ P(Y | X ) и p ∈ P(X ) информацией Августина поряд-

ка α для распределения на входе p называется

Iα(p; W ) ≜ inf Dα(W ∥ q | p).

(76)

q∈P(Y)

Кроме того, для любой X -измеримой функции стоимости ρ: X → Rℓ≥0 и любого

λ ∈ Rℓ≥0 информацией Августина-Лежандра порядка α для распределения на вхо-

де p и множителя Лагранжа λ называется

I^λα(p; W) ≜ I_α(p; W) - λ · E_p[ρ],

(77)

где подразумевается, что если λ · E_p[ρ] = ∞, то I^λα(p; W ) = -∞.

Хотя мы и включили случай λ· E_p[ρ] = ∞ в формальное определение АЛ-инфор-

мации, нас будут интересовать только те p, для которых λ · E_p[ρ] конечно. Введем

множество A^λ всех таких p:

A^λ ≜ {p ∈ P(X) : λ · E_p[ρ] < ∞}.

(78)

Для произвольной σ-алгебры X одноэлементные множества не обязательно из-

меримы, поэтому P(X) не обязательно является подмножеством A^λ. Если X счетно

отделима, то одноэлементные множества лежат в X согласно [21, теорема 6.5.7],

P(X) ⊂ A^λ и sup I^λα(p; W ) ≥ C^λα,W . Противоположное неравенство следует из теоре-

p∈A^λ

мы 2, поэтому получаем sup I^λα(p; W ) = C^λα,W . В следующей теореме 4 формально

p∈A^λ

приведены эти наблюдения, а также аналогичные результаты об АЛ-центре с ис-

пользованием теоремы о минимаксе.

Теорема 4. Пусть X - счетно отделимая σ-алгебра, Y - счетно порожден-

ная σ-алгебра, W - функция вероятностей переходов из (X, X) в (Y, Y), ρ: X → Rℓ≥0

- X-измеримая функция стоимости и α ∈ R₊. Тогда для всех λ ∈ Rℓ≥0 справедливы

равенства

sup

inf

D_α(W ∥q |p) - λ · E_p[ρ] = inf sup D_α(W ∥q |p) - λ · E_p[ρ] =

(79)

p∈A^λ

q∈P(Y)

q∈P(Y)_p∈Aλ

= inf sup D_α(W (x) ∥ q) - λ · ρ(x) =

(80)

q∈P(Y)x∈X

=C^λα,W,

(81)

где множество A^λ определено в (78). Если C^λα,W конечна, то ∃! q^λα,W ∈ P(Y), на-

зываемая центром Августина - Лежандра порядка α функции вероятности пере-

ходов W для множителя Лагранжа λ, такая что

(

)

C^λα,W = sup D_α

W∥q^λα,W |p

- λ · E_p[ρ] =

(82)

p∈A^λ

(

)

= sup D_α

W (x) ∥ q^λα,W

- λ · ρ(x).

(83)

x∈X

Доказательство. Так как P(X) ⊂ A^λ, то из неравенства максимина-мини-

макса следует, что

sup

inf D_α(W ∥ q | p) - λ · E_p[ρ] ≤ sup

inf D_α(W ∥ q | p) - λ · E_p[ρ] ≤

p∈P(X)

q∈P(Y)

p∈A^λ

q∈P(Y)

≤ inf sup

D_α(W ∥q |p) - λ · E_p[ρ] = inf sup D_α(W(x)∥q) - λ · ρ(x).

q∈P(Y)_p∈Aλ

q∈P(Y)x∈X

Таким образом, равенства (79), (80) следуют из равенств (58), (59) теоремы 2, а (81)

- из равенств (59) и (57).

Если C^λα,W конечна, то по теореме 2 существует единственная q^λα,W ∈ P(Y), такая

что

(

)

sup D_α

W (x) ∥ q^λα,W

- λ · ρ(x) = C^λα,W.

x∈X

Теперь равенства (82), (83) вытекают из того факта, что для любой q ∈ P(Y)

sup D_α(W ∥q |p) - λ · E_p[ρ] = sup D_α(W(x)∥q) - λ · ρ(x).

p∈A^λ

x∈X

Пусть A(ϱ) - подмножество P(X ), состоящее из вероятностных мер, удовлетво-

ряющих ограничению по стоимости ϱ:

A(ϱ) ≜ {p ∈ P(X ) : E_p[ρ] ≤ ϱ}.

Тогда A(ϱ) ⊂ A(ϱ), и sup I_α(p; W ) ≥ C_α,W,ϱ, если X счетно отделима. Для огра-

p∈A(ϱ)

ничений по стоимости, принадлежащих int Γ_ρ, противоположное неравенство имеет

место в силу леммы 29(c) и теоремы 4, а значит, sup I_α(p; W ) = C_α,W,ϱ. В сле-

p∈A(ϱ)

дующей теореме 5 формально приведены эти наблюдения, а также аналогичные

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

Теорема 5. Пусть X - счетно отделимая σ-алгебра, Y - счетно порожден-

ная σ-алгебра, W - функция вероятностей переходов из (X, X) в (Y, Y), ρ: X → Rℓ≥0

- X-измеримая функция стоимости и α ∈ R₊. Для любого ϱ ∈ intΓ_ρ справедливы

равенства

sup

inf

D_α(W ∥q |p) = inf sup D_α(W ∥q |p) =

(84)

p∈A(ϱ)

q∈P(Y)

q∈P(Y)p∈A(ϱ)

=C_α,W,ϱ,

(85)

где C_α,W,ϱ определена в (49). Если C_α,W,ϱ ∈ R≥0, то ∃! q_α,W,ϱ ∈ P(Y), называемая

августиновским центром порядка α функции вероятностей переходов W для огра-

ничения по стоимости ϱ, такая что

C_α,W,ϱ = sup D_α(W ∥q_α,W,ϱ |p) =

(86)

p∈A(ϱ)

= sup D_α(W ∥q_α,W,ϱ |p).

(87)

p∈A(ϱ)

Кроме того, q_α,W,ϱ = q^λα,W для всех λ ∈ Rℓ≥0, таких что C_α,W,ϱ = C^λα,W + λ · ϱ.

Доказательство. Так как A(ϱ) ⊂ A(ϱ), то из неравенства максимина-мини-

макса следует, что

sup

inf D_α(W ∥ q | p) ≤ sup

inf D_α(W ∥ q | p) ≤

p∈A(ϱ)

q∈P(Y)

p∈A(ϱ)

q∈P(Y)

≤ inf sup D_α(W ∥ q | p).

q∈P(Y)p∈A(ϱ)

Таким образом, при C_α,W,ϱ = ∞ равенства (84), (85) справедливы согласно (42).

С другой стороны, по теореме 4 для любого λ с конечной C^λα,W существует един-

ственная q^λα,W , удовлетворяющая (83). Следовательно,

(

)

inf

sup D_α(W ∥q |p) ≤ sup D_α

W∥q^λα,W |p

≤

q∈P(Y)p∈A(ϱ)

p∈A(ϱ)

(

)

≤ sup D_α

W∥q^λα,W |p

- λ · E_p[ρ] + λ · ϱ ≤ C^λα,W + λ · ϱ.

p∈A(ϱ)

Кроме того, если C_α,W,ϱ ∈ R, то по лемме 29(c) существует по крайней мере один

λ ∈ Rℓ≥0, такой что C_α,W,ϱ = Cλα,W +λ·ϱ. Поэтому равенства (84), (85) выполнены при

C_α,W,ϱ ∈ R, а (86) выполнено для q_α,W,ϱ = q^λα,W при условии, что C_α,W,ϱ = C^λα,W +λ·ϱ.

С другой стороны, q_α,W,ϱ - вероятностная мера, удовлетворяющая (87) по теореме 1,

и по лемме 31 q_α,W,ϱ = q^λα,W для всех λ, таких что C_α,W,ϱ = C^λα,W + λ · ϱ.

Счетная отделимость X и счетная порожденность Y - довольно слабые условия,

которым удовлетворяют большинство функций вероятностей переходов, рассматри-

ваемых на практике. Поэтому теоремы 4, 5 являются дополнительной мотивацией

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

ций вероятности.

Согласно лемме 29(c), (d) и теореме 5 существование распределения на входе p,

удовлетворяющего условиям E_p[ρ] ≤ ϱ и I_α(p; W ) = C_α,W,ϱ, несущественно для су-

ществования и единственности меры q_α,W,ϱ или ее характеризации через q^λα,W для λ,

удовлетворяющих условию C_α,W,ϱ = C^λα,W + λ · ϱ. Хотя в некоторых специальных

случаях можно доказать существование такого p, в общем случае такого распреде-

ления на входе не существует. Поэтому мы считаем правильным отделять вопрос

о существовании оптимального распределения от обсуждения C_α,W,ϱ и q_α,W,ϱ и их

характеризации через C^λα,W и q^λα,W , что, однако, не является общепринятой практи-

кой [37, теорема 1].

Мы предполагали Y счетно порожденной, чтобы гарантировать корректность

определения условного расхождения Реньи, использованного в (76). Однако чтобы

определить информацию Реньи, не обязательно предполагать, что Y счетно порож-

дена, достаточно структуры функции вероятностей переходов. Напомним, что если

W ∈ P(Y |X), то согласно [21, теорема 10.7.2] для любого p ∈ P(X) существует

единственная вероятностная мера p ⊛ W на (X × Y, X ⊗ Y), такая что

∫

p ⊛ W(E_x × E_y) = W(Ey |x)p(dx)

∀E_x ∈ X , E_y ∈ Y.

Таким образом, Igα(p; W ) корректно определена для любых W ∈ P(Y | X ) и p ∈ P(X ).

К сожалению, для РГ-информации ситуация далеко не столь проста. Чтобы опре-

делить РГ-информацию, используя аналогичный подход, вначале надо показать,

что W e¹

^λ·ρ является переходным ядром (а не функцией вероятностей переходов,

т.е. марковским ядром), а затем установить существование и единственность меры

p⊛We¹

^λ·ρ для всех p ∈ P(Y). Для порядков, больших единицы, полученная мера

является субвероятностной, и в качестве определения РГ-информации можно ис-

пользовать (64). С другой стороны, для порядков между нулем и единицей мера

p⊛We¹

^λ·ρ является σ-конечной для всех p ∈ P(X ), но не обязательно конечной

для всех p ∈ P(X ). Таким образом, для порядков между нулем и единицей можно

использовать (64) как определение РГ-информации только после того как продол-

жить определение расхождения Реньи на σ-конечные меры.

§ 6. Примеры

Здесь мы сперва продемонстрируем некоторые тонкости, указанные в предыду-

щих параграфах, а затем рассмотрим гауссовские каналы и получим выражения в

замкнутом виде для их августиновских пропускной способности и центра.

6.1. Семейства, инвариантные относительно сдвига.

Пример 1 (канал с афинной пропускной способностью). Рассмотрим канал

W : R≥0 → P(B([0,1))) и связанную с ним функцию стоимости ρ: R≥0 → R≥0, име-

ющие вид

dW (x)

= f_⌊x⌋(y - x - ⌊y - x⌋),

dν

ρ(x) = ⌊x⌋,

где ν - мера Лебега на [0, 1), а функции f_i имеют вид

f_i(y) = ei+11y∈[0,e-i-1₎

∀i ∈ Z≥0.

Пусть u_i - равномерное распределение на [i, i + 1), тогда непосредственной подста-

новкой можно убедиться, что Tα,ui(u₀) = u₀. Тогда, используя неравенство Йенсена

и свойство неподвижности точки, получаем²²

D_α(W ∥q |u_i) ≥ D_α(W ∥u₀ |u_i) + Dα∧1(u₀ ∥q).

Таким образом, u₀ - единственное августиновское среднее порядка α для распреде-

ления на входе u_i, т.е. qα,ui = u₀ и I_α(u_i; W ) = D_α(W ∥ u₀ | u_i), а значит, I_α(u_i; W ) =

= i + 1, для всех i ∈ Z₊ и α ∈ R₊. Далее, используя тот факт, что Eui[ρ] = i, за-

ключаем, что C_α,W,ϱ ≥ (ϱ + 1) не только для ϱ ∈ Z≥0, но и для ϱ ∈ R≥0, поскольку

функция C_α,W,ϱ вогнута по ϱ согласно лемме 27(a). С другой стороны, непосред-

ственной подстановкой можно убедиться, что

D_α(W ∥u₀ |p) = E_p[ρ] + 1.

(88)

Итак, I_α(p; W ) ≤ (ϱ + 1) для любого p, удовлетворяющего ограничению по стоимо-

сти ϱ. Следовательно,

C_α,W,ϱ = ϱ + 1,

q_α,W,ϱ = u₀.

Поэтому в силу (55) получаем

^{∞, λ ∈ [0, 1),

C^λα,W =

λ ∈ [1,∞).

Теперь, используя (88) и теорему 4, заключаем, что q^λα,W = u₀ для всех λ ∈ [1, ∞).

Пример 2 (канал с неполунепрерывной сверху пропускной способностью). За-

дадим канал W : R → P(B([0, 1))) и функцию стоимости ρ: R → R≥0, связанную

с ним, как

dW (x)

= f_⌊x⌋(y - x - ⌊y - x⌋),

dν

^{⌊x⌋, x ≥ 0,

ρ(x) =

2^⌊x⌋, x < 0,

где ν - мера Лебега на [0, 1), а функции f_i : [0, 1) → R≥0 имеют вид

⎧

⎨2i+11y∈[0,2-i-1), i > 0,

f_i(y) =

3/21y∈[0,2/3),

i = 0,

⎩

21y∈[0,1/2),

i < 0.

Рассуждениями, аналогичными приведенным выше, получаем, что

^{(ϱ + 1) ln 2, ϱ > 0,

C_α,W,ϱ =

ln 3/2,

ϱ = 0,

^{∞, λ ∈ [0, ln 2),

C^λα,W =

ln 2, λ ∈ [ln 2, ∞).

Следовательно, C_α,W,ϱ = inf

C^λα,W + λ · ϱ для ϱ = 0.

λ≥0

Пример 3 (канал-произведение без оптимального распределения стоимости).

Пусть W₁ и W₂ - каналы, описанные в примерах 1 и 2, а ρ₁ и ρ₂ - связанные с ними

²² См. вывод формул (23), (24) леммы 13(c), (d), приведенный в [22, Приложение B].

функции стоимости. Пусть W[1,2] - произведение этих двух каналов с аддитивной

функцией стоимости ϱ[1,2], т.е.

W[1,2](x₁, x₂) = W₁(x₁) ⊗ W₂(x₂),

ρ[1,2](x₁, x₂) = ρ₁(x₁) + ρ₂(x₂).

Тогда из леммы 28 получаем

{

ϱ + 1 + ln2, ϱ > 0,

C_α,W

[1,2] ,ϱ =

1 + ln

ϱ = 0.

Заметим, что для положительных значений ϱ не существует пары (ϱ₁, ϱ₂), одновре-

менно удовлетворяющей условию C_α,W

[1,2] ,ϱ =^Cα,W1,ϱ1+Cα,W2,ϱ2^{иограничениюпо}

стоимости ϱ₁ + ϱ₂ ≤ ϱ.

6.2. Гауссовские каналы. В дальнейшем будем обозначать гауссовскую вероят-

ностную меру на B(R) с нулевым средним и дисперсией σ² через ϕ_σ2. Допуская

некоторую вольность обозначений, соответствующую функцию плотности вероят-

ности будем обозначать тем же символом:

ϕ_σ2 (x) =

√ e

2σ²

∀x ∈ R.

2πσ

Гауссовские каналы и соответствующие функции вероятностей переходов будем ис-

пользовать взаимозаменяемым образом; по теоремам 4, 5 они имеют одинаковые

августиновскую пропускную способность и центр при наличии ограничений по сто-

имости.

Пример 4 (скалярный гауссовский канал). Пусть W - скалярный гауссовский

канал с дисперсией шума σ², и пусть связанная с ним функция стоимости ρ квад-

ратична, т.е.

∫

W (E | x) = ϕ_σ2 (y - x) dy

∀E ∈ B(R),

ρ(x) = x²

∀x ∈ R.

Августиновские пропускная способность и центр этого канала имеют следующий

вид:

C_α,W,ϱ =

⎧

⎪

αϱ

(θ_α,σ,ϱ)α/2σ(1-α)

⎨

√

α ∈ R₊ \ {1},

2(αθ_α,σ,ϱ + (1 - α)σ²)

α-1

αθ_α,σ,ϱ + (1 - α)σ²

(89)

(

⁼⎪⎪1

ϱ )

⎩

α = 1,

σ²

q_α,W,ϱ = ϕ

(90)

θα,σ,ϱ

√

θ_α,σ,ϱ ≜ σ² +

+ (

)² + ϱσ².

(91)

2α

Кроме того, C_α,W,ϱ непрерывно дифференцируема по ϱ, и ее производная - непре-

рывная убывающая по ϱ биективная функция из R₊ в [0, α/2σ²), имеющая вид

C_α,W,ϱ =

(92)

dϱ

2(αθ_α,σ,ϱ + (1 - α)σ²)

√

(93)

αϱ + σ² +

(αϱ - σ²)² + 4ϱα²σ²

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

гауссовского распределения с нулевым средним и дисперсией ϱ является гауссовским

распределением с нулевым средним и дисперсией θ_α,σ,ϱ, т.е. qα,ϕϱ = ϕ

. Отсюда

θα,σ,ϱ

(

)

(

)

будет следовать, что I_α(ϕ_ϱ; W ) = D_α

W∥ϕ_θ

|ϕ_ϱ

. Величина D_α

W∥ϕ_θ

|ϕ_ϱ

α,σ,ϱ

равна выражению в правой части равенства (89). Для доказательства соотноше-

ний (89), (90) покажем, что эта величина является наибольшим значением инфор-

мации Августина по всем распределениям на входе, удовлетворяющим ограничению

по стоимости ϱ. Следовательно, мы получим C_α,W,ϱ = I_α(ϕ_ϱ; W ) и q_α,W,ϱ = qα,ϕϱ.

Затем проверим (92), используя некоторое тождество, а именно (96), полученное

при выводе равенства qα,ϕϱ = ϕ

θα,σ,ϱ

Непосредственной подстановкой можно убедиться, что

D_α(W(x)∥ϕ_θ) =

⎧

⎪

αx²

θα/2σ(1-α)

⎨

√

α ∈ R₊ \ {1},

2(αθ + (1 - α)σ²)

α-1

αθ + (1 - α)σ²

(94)

⎪

² +x²

−θ

⎩^σ

α = 1.

2θ

σ²

Тогда скошенный канал

α порядка α, определенный в (16), также является гаус-

совским:

∫

(

)

αθ

α (E | x) = ϕ σ2θ

x dy.

αθ+(1-α)σ²

αθ + (1 - α)σ²

Значит, T_α,p(q) является гауссовской вероятностной мерой с нулевым средним, если

p и q таковы. В частности,

Tα,ϕϱ (ϕ_θ) = ϕ₍ αθ

σ²θ

(95)

)²ϱ+

αθ+(1-α)σ²

Следовательно, если ϕ_θ - неподвижная точка оператора Tα,ϕϱ(·), то θ удовлетворяет

следующему равенству:

[

]

( (

) (

1⁾

θ θ² -θ ϱ+

σ²

+ 1-

σ⁴

= 0.

(96)

Величина θ_α,σ,ϱ, определенная в (91), является единственным корнем уравнения (96),

превосходящим σ², при α ∈ R₊, а также единственным положительным корнем при

α ∈ (0,1). Кроме того, с помощью (95) можно убедиться, что Tα,ϕϱ(ϕ_θ2

)=ϕ

α,σ,ϱ

θα,σ,ϱ

т.е. ϕθα,σ,ϱ является неподвижной точкой Tα,ϕϱ (·). Тогда, используя неравенство Йен-

сена и свойство неподвижности точки, получаем²³

(

)

D_α(W ∥q |ϕ_ϱ) ≥ D_α

W∥ϕθα,σ,ϱ |ϕ_ϱ

+ D1∧α(ϕ

∥q)

∀q ∈ P(B(R)).

θα,σ,ϱ

Таким образом, ϕ

является августиновским средним порядка α для распреде-

θα,σ,ϱ

(

)

ления на входе ϕ_ϱ, т.е. qα,ϕϱ = ϕ_θ

и I_α(ϕ_ϱ; W) = D_α

W∥ϕθα,σ,ϱ |ϕ_ϱ

. С другой

α,σ,ϱ

²³ Вывод этого неравенства аналогичен выводу соотношений (23), (24) леммы 13(c), (d), приве-

денному в [22, Приложение B].

стороны, из (94) следует, что

(

)

α(E_p[ρ] - ϱ)

D_α

W∥ϕ_θ

+ I_α(ϕ_ϱ; W)

∀p ∈ P(B(R)).

(97)

α,σ,ϱ

2(αθ_α,σ,ϱ + (1 - α)σ²)

Тогда I_α(p; W ) ≤ I_α(ϕ_ϱ; W ) для всех p, таких что E_p[ρ] ≤ ϱ. Следовательно, C_α,W,ϱ =

= I_α(ϕ_ϱ; W) и q_α,W,ϱ = qα,ϕϱ.

Для случая α = 1 равенство (92) очевидно. Чтобы доказать (92) в случае α ∈

∈ R₊ \ {1}, заметим, что

C_α,W,ϱ =

dϱ

2(αθ_α,σ,ϱ + (1 - α)σ²)

[

]

-α²ϱ

α(θ_α,σ,ϱ - σ²)

θ_α,σ,ϱ =

2(αθ_α,σ,ϱ + (1 - α)σ²)²

2(αθ_α,σ,ϱ + (1 - α)σ²)θ_α,σ,ϱ dϱ

2(αθ_α,σ,ϱ + (1 - α)σ²)

2(αθ_α,σ,ϱ + (1 - α)σ²)²θ_α,σ,ϱ

[

]

( (

) (

1⁾

× θ²

-θ_α,σ,ϱ ϱ+

σ²

+ 1-

σ⁴

θ_α,σ,ϱ.

α,σ,ϱ

dϱ

Тогда (92) выполнено для α ∈ R₊ \ {1}, поскольку θ_α,σ,ϱ - корень уравнения (96).

АЛ-пропускная способность и АЛ-центр этого канала имеют следующий вид:

C^λα,W =

⎧(

√

)

⎪

α - 1 2σ²λ

2σ²λ

⎨

- ln

1λ∈(0, α

), α ∈ R+ \ {1},

α-1

α α

2σ²

(98)

⎪(

√

)

⎩ σ²λ - ln

2eσ²λ

1λ∈(0, 1

)

α = 1,

2σ²

q^λα,W = ϕ_θλ

(99)

α,σ



⁺

 1



θ^λα,σ ≜ σ² +

(100)



^2λ-

Тогда C^λα,W непрерывно дифференцируема по λ, и ее производная - непрерывная

возрастающая по λ биективная функция из R₊ в (-∞, 0], имеющая вид

α - 2σ²λ

C^λα,W = -

λ≤

(101)

dλ

2λ(α + (α - 1)2σ²λ)

2σ²

Выражения (98), (99) для АЛ-пропускной способности и АЛ-центра выводятся с по-

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

шений (55), (92)-(94) и леммы 31.

• Если λ ∈ (0, α/2σ²), то в силу

(93) существует единственное ϱ^λα,W , такое что



C_α,W,ϱ

= λ. Кроме того, согласно (55) ϱ^λα,W удовлетворяет равенству

dϱ

ϱ=ϱ^λ

α,W

C^λα,W = C_α,W,ϱλ

- λϱ^λα,W , так как^d

C_α,W,ϱ убывает по ϱ. Тогда равенство (98)

α,W

dϱ

вытекает из (89), (92). С другой стороны, q^λα,W

= q_α,W,ϱλ по лемме 31, по-

α,W

скольку C_α,W,ϱλ

= C^λα,W + λϱ^λα,W. Тогда (99) вытекает из (90)-(92), (100).

α,W

Кроме того, можно проверить, что ϱλα,W = -

C^λα,W , явным образом решая

dλ



уравнение

C_α,W,ϱ

= λ относительно ϱ^λα,W. Однако нам для проверки

dϱ

ϱ=ϱ^λ

α,W

равенств (98), (99) это явное решение не потребуется.

• Если λ ∈ [α/2σ², ∞), то D_α(W ∥ ϕ_σ2 | p) - λ E_p[ϱ] ≤ 0 в силу (94). С другой сторо-

ны, C^λα,W ≥ 0, так как для вероятностной меры, сосредоточенной в точке x = 0,

АЛ-информация равна нулю. Следовательно, C^λα,W = 0 и q^λα,W = ϕ_σ2 . Таким

образом, верны равенства (98), (99).

Пример 5 (параллельные гауссовские каналы). Пусть W[1,n] - произведение

скалярных гауссовских каналов W_i с дисперсией шума σ_i для i ∈ {1, . . . , n}, а ρ[1,n]

- аддитивные функции стоимости, т.е.

[

]

∫

∏

W[1,n](E|xn1) =

ϕ_σ2

(y_i - x_i) dyn1

∀E ∈ B(Rⁿ),

E i⁼¹

∑

ρ[1,n](xn1) =

x2i

∀xn1 ∈ Rⁿ.

i=1

В силу леммы 28 августиновская пропускная способность при наличии ограничений

по стоимости канала W[1,n] удовлетворяет равенству

Cα,W[1,n],ϱ =

sup

Cα,Wi,ϱi .

ϱ1,...,ϱn:

^∑ ϱi≤ϱ

Так как все Cα,Wi,ϱi непрерывны, строго вогнуты и возрастают по ϱi, то супре-

мум достигается в единственной точке (ϱα,1, . . . , ϱ_α,n). Тогда q_α,W

[1,n],ϱ =

qα,W1,ϱα,1 ⊗

⊗... ⊗ qα,Wn,ϱα,n по лемме 28. Кроме того, так как Cα,Wi,ϱi непрерывно дифферен-

цируемы по ϱ_i, эту единственную точку (ϱα,1, . . . , ϱ_α,n) можно найти через усло-



вия на производные:

Cα,Wi,ϱi



= λ_α для всех i с положительными ϱ_α,i и



dϱi

ϱi=ϱα,i



Cα,Wi,ϱi



≤ λ_α для всех i с нулевыми ϱ_α,i для некоторого λ_α ∈ R₊. Та-

dϱi

ϱi=ϱα,i

ким образом, используя равенство (93), получаем, что оптимальное распределение

стоимости, т.е. (ϱα,1, . . ., ϱ_α,n), удовлетворяет равенству

|α - 2σ2iλ_α|

ϱ_α,i =

(102)

2λ_α(α + 2(α - 1)σ2iλ_α)

∑

для некоторого λ_α, однозначно задаваемому условием ϱ_α,i = ϱ, поскольку выра-

i=1

жение в правой части (102) не возрастает по λ_α для каждого i. Следовательно,

∑

Cα,W[1,n],ϱ =

Cα,Wi,ϱα,i

(103)

i=1

⊗

qα,W[1,n],ϱ =

(104)

θα,σi,ϱα,i

i=1

где θ_α,σ,ϱ определено в (91). Используя те же ограничения на оптимальность рас-



пределения стоимости через производные, т.е.

Cα,Wi,ϱi



= λ_α для всех i



dϱi

ϱi=ϱα,i



с положительными ϱ_α,i и

Cα,Wi,ϱi



≤ λ_α для всех i с нулевыми ϱ_α,i, а также

dϱi

ϱi=ϱα,i

равенство (92) вместо (93), получаем следующую альтернативную характеризацию

θα,σi,ϱα,i через σi и λα, не зависящую явно от величин ϱα,i:



σ2i+



θα,σi,ϱα,i = σⁱ +



(105)

^2λ_α -

Используя лемму 32, АЛ-пропускную способность и АЛ-центр канала W[1,n] мож-

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

щим образом:

∑

C^λ

α,W[1,n]

α,Wi

i=1

⊗

q^λ

α,W[1,n]

α,Wi

i=1

Августиновские пропускную способность и центр при наличии ограничений по

стоимости, а также АЛ-пропускную способность и АЛ-центр векторных гауссовских

каналов с многими входными и выходными антеннами можно исследовать, исполь-

зуя этот же подход, с помощью сингулярных разложений матриц.

§ 7. Обсуждение

Так же, как и информация Реньи, информация Августина является обобщением

взаимной информации, определяемым чрез расхождение Реньи. Однако в отличие

от информации Реньи порядка α информация Августина порядка α не имеет вы-

ражения в замкнутом виде, кроме случая порядка 1. Поэтому некоторые свойства

информации Августина, такие как ее непрерывная дифференцируемость как функ-

ции порядка α, существование и единственность августиновского среднего q_α,p по-

рядка α, а также границы (7), доказывать труднее. Но когда эти фундаментальные

свойства информации Августина уже установлены, анализ августиновской пропуск-

ной способности становится довольно очевидным и весьма похожим на аналогичный

анализ для пропускной способности Реньи, представленный в [13].

Для вычисления августиновской пропускной способности при наличии ограниче-

ний по стоимости через величину Igλα(p; W ), которую мы называем РГ-информацией,

ранее была применена техника выпуклого сопряжения. Хотя такой подход успешно

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

по стоимости через РГ-пропускную способность, он не является стандартным и до-

вольно сложен. Более стандартный подход, основанный на понятии АЛ-информации

I^λα(p; W), представлен в п. 5.2. Насколько нам известно, АЛ-информация ранее не

использовалась и не изучалась, тем не менее получаемая пропускная способность

оказалась идентична пропускной способности, связанной с РГ-информацией. В свете

этого наблюдения оптимальность подхода, основанного на РГ-информации, кажется

более наглядной.

Наше изучение информации Августина и августиновской пропускной способно-

сти было первоначально мотивировано их операциональным значением в задаче ко-

дирования каналов [6]. Мы исследовали это операциональное значение более по-

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

тами для двух семейств каналов без памяти - при ограничениях на композицию и

при наличии ограничений по стоимости [7]. В целом, вывод границы сферической

упаковки для каналов без памяти в [7] аналогичен выводу границы сферической

упаковки для каналов-произведений в [38] за исключением использования августи-

новских пропускной способности и центра вместо пропускной способности и центра

Реньи.

Автор выражает благодарность Фатьме и Мехмету Накибоглу за гостеприим-

ство, без которого эта работа не была бы возможной. Автор также благодарит

М. Далаи за указание на неявное утверждение Фано о неподвижной точке в [23]

и Г. Васкеса-Вилара за указание на работу Полтырева [19] о границе случайного

кодирования. Кроме того, автор благодарит рецензента за внимательнейшую рецен-

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

в первоначальной версии статьи.

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

Nakiboğlu B. The Augustin Center and the Sphere Packing Bound for Memoryless Chan-

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

June 25-30, 2017. P. 1401-1405.

Csiszár, I. Generalized Cutoff Rates and Rényi’s Information Measures // IEEE Trans.

Inform. Theory. 1995. V. 41. № 1. P. 26-34.

Dalai M. Some Remarks on Classical and Classical-Quantum Sphere Packing Bounds: Rényi

vs. Kullback-Leibler // Entropy. 2017. V. 19. № 7. P. 355 (11 pp.).

Mosonyi M., Ogawa T. Divergence Radii and the Strong Converse Exponent of Clas-

sical-Quantum Channel Coding with Constant Compositions // arXiv:1811.10599v4

[quant-ph], 2018.

Csiszár, I. and Körner, J., Information Theory: Coding Theorems for Discrete Memoryless

Systems, Cambridge, UK: Cambridge Univ. Press, 2011.

Augustin U. Noisy Channels // Habilitation Thesis. Universität Erlangen-Nürnberg, 1978.

Avaliable at http://bit.ly/2ID8h7m.

Nakiboğlu B. The Sphere Packing Bound for Memoryless Channels // arXiv:1804.06372v2

[cs.IT], 2018.

van Erven T., Harremoës P. Rényi Divergence and Kullback-Leibler Divergence // IEEE

Trans. Inform. Theory. 2014. V. 60. № 7. P. 3797-3820.

Shayevitz O. A Note on a Characterization of Rényi Measures and Its Relation to Composite

Hypothesis Testing // arXiv:1012.4401v2 [cs.IT], 2010.

10.

Shayevitz O. On Rényi Measures and Hypothesis Testing // Proc. 2010 IEEE Int. Sympos.

on Information Theory (ISIT’2010). Austin, Texas, USA. June 13-18, 2010. P. 894-898.

11.

Verdú S. α-Mutual Information // Proc. 2015 Information Theory and Applications Work-

shop (ITA’2015). San Diego, CA, USA. Feb. 1-6, 2015. P. 1-6. Available at http://ita.

ucsd.edu/workshop/15/files/paper/paper_374.pdf.

12.

Kemperman J.H.B. On the Shannon Capacity of an Arbitrary Channel // Indag. Math.

1974. V. 77. № 2. P. 101-115.

13.

Nakiboğlu B. The Rényi Capacity and Center // IEEE Trans. Inform. Theory. 2019. V. 65.

№ 2. P. 841-860.

14.

Gallager R.G. A Simple Derivation of the Coding Theorem and Some Applications // IEEE

Trans. Inform. Theory. 1965. V. 11. № 1. P. 3-18.

15.

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

Sons, 1968.

16.

Ebert P.M. Error Bounds for Parallel Communication Channels. Tech. Rep. № 448. Research

Lab. of Electronics, MIT. Cambridge, MA, USA. 1966. Available at https://dspace.mit.

edu/handle/1721.1/4295.

17.

Richters J.S. Communication over Fading Dispersive Channels. Tech. Rep. № 464. Research

Lab. of Electronics, MIT. Cambridge, MA, USA. 1967. Available at https://dspace.mit.

edu/handle/1721.1/4279.

18.

Арутюнян Е.А. Оценки экспоненты вероятности ошибки для полунепрерывного кана-

ла без памяти // Пробл. передачи информ. 1968. Т. 4. № 4. С. 37-48.

19.

Полтырев Г.Ш. Границы случайного кодирования для дискретных каналов без памя-

ти // Пробл. передачи информ. 1982. Т. 18. № 1. С. 12-26.

20.

Dudley R.M. Real Analysis and Probability. Cambridge: Cambridge Univ. Press, 2002.

21.

Bogachev V.I. Measure Theory. Berlin: Springer, 2007.

22.

Nakiboğlu B. The Augustin Capacity and Center // arXiv:1803.07937v3 [cs.IT], 2018.

23.

Fano R.M. Transmission of Information: A Statistical Theory of Communications. New

York: M.I.T. Press, 1961.

24.

Arimoto S. Computation of Random Coding Exponent Functions // IEEE Trans. Inform.

Theory. 1976. V. 22. № 6. P. 665-671.

25.

Oohama Y. The Optimal Exponent Function for the Additive White Gaussian Noise Channel

at Rates above the Capacity // Proc. 2017 IEEE Int. Sympos. on Information Theory

(ISIT’2017). Aachen, Germany. June 25-30, 2017. P. 1053-1057.

26.

Oohama Y. Exponent Function for Stationary Memoryless Channels with Input Cost at

Rates above the Capacity // arXiv:1701.06545v3 [cs.IT], 2017.

27.

Vazquez-Vilar G., Martinez A., Guillén i Fàbregas A. A Derivation of the Cost-Constrained

Sphere-Packing Exponent // Proc.

2015

IEEE Int. Sympos. on Information Theory

(ISIT’2015). Hong Kong, China. June 14-19, 2015. P. 929-933.

28.

Rényi A. On Measures of Entropy and Information // Proc. 4th Berkeley Sympos. on

Mathematical Statistics and Probability. Berkely, CA, USA. June 20 - July 30, 1960. Berkely:

Univ. of California Press, 1961.

29.

Csiszár I. Information-type Measures of Difference of Probability Distributions and Indirect

Observations // Studia Sci. Math. Hungar. 1967. V. 2. № 3-4. P. 299-318.

30.

Gilardoni G.L. On Pinsker’s and Vajda’s Type Inequalities for Csiszár’s f-Divergences //

IEEE Trans. Inform. Theory. 2010. V. 56. № 11. P. 5377-5386.

31.

Shiryaev A.N. Probability. New York: Springer, 1995.

32.

Polyanskiy Y., Verdú S. Arimoto Channel Coding Converse and Rényi Divergence // Proc.

48th Annual Allerton Conf. on Communication, Control, and Computation. Sept. 29 -

Oct. 1, 2010. Allerton, IL, USA. P. 1327-1333.

33.

Колмогоров А.Н., Фомин С.В. Элементы теори функций и функционального анализа.

М.: Наука, 1968.

34.

Csiszár I. A Class of Measures of Informativity of Observation Channels // Period. Math.

Hungar. 1972. V. 2. № 1-4. P. 191-213.

35.

Sibson R. Information Radius // Z. Wahrsch. Verw. Gebiete. 1969. V. 14. № 2. P. 149-160.

36.

Blahut R.E. Hypothesis Testing and Information Theory // IEEE Trans. Inform. Theory.

1974. V. 20. № 4. P. 405-417.

37.

Kostina V., Verdú S. Channels with Cost Constraints: Strong Converse and Dispersion //

IEEE Trans. Inform. Theory. 2015. V. 61. № 5. P. 2415-2429.

38.

Nakiboğlu B. The Sphere Packing Bound via Augustin’s Method // IEEE Trans. Inform.

Theory. 2019. V. 65. № 2. P. 816-840.

39.

Krantz S.G., Parks H.R. A Primer of Real Analytic Functions. Boston: Birkhäuser, 2002.

40.

Munkres J.R. Topology. Upper Saddle River, NJ: Prentice Hall, 2000.

41.

Rudin W. Principles of Mathematical Analysis. New York: McGraw-Hill, 1976.

42.

Bertsekas D.P., Nedić A., Ozdaglar A.E. Convex Analysis and Optimization. Belmont, MA:

Athena Sci., 2003.

43.

Komiya H. Elementary Proof for Sion’s Minimax Theorem // Kodai Math. J. 1988. V. 11.

№ 1. P. 5-7.

44.

Sion M. On General Minimax Theorems // Pacific J. Math. 1958. V. 8. № 1. P. 171-176.

Накибоглу Барыш

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

Средневосточный технический университет,

22.03.2018

Анкара, Турция

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

bnakib@metu.edu.tr

20.08.2019

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

12.11.2019