ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Том 55
2019
Вып. 3
УДК 621.391.1 : 519.2
© 2019 г.
В.В. Прелов
ОПТИМАЛЬНЫЕ ВЕРХНИЕ ГРАНИЦЫ
ДЛЯ ДИВЕРГЕНЦИИ КОНЕЧНОМЕРНЫХ РАСПРЕДЕЛЕНИЙ
ПРИ ЗАДАННОМ ВАРИАЦИОННОМ РАССТОЯНИИ1
Рассматривается задача о нахождении максимальных значений дивергенций
D(P ∥ Q) и D(Q∥ P) дискретных распределений вероятностей P и Q со значени-
ями на конечном множестве N = {1, 2, . . . , n} при условии, что задано вариаци-
онное расстояние V (P, Q) между ними и заданы либо распределение вероятно-
стей Q, либо (в случае D(P ∥ Q)) лишь значение минимальной компоненты qmin
распределения Q. Получены точные выражения для указанных максимумов
дивергенций, которые в ряде случаев позволяют выписать для них как явные
формулы, так и простые верхние и нижние границы, причем для максимума
D(P ∥ Q) при заданных V (P, Q) и qmin, а также для максимума D(Q∥ P) при
заданных Q и V (P, Q) явные формулы получены для всех возможных значений
этих параметров.
Ключевые слова: информационная дивергенция, вариационное расстояние, дис-
кретные распределения вероятностей.
DOI: 10.1134/S0555292319030021
Пусть P = {pi, i ∈ N } и Q = {qi, i ∈ N } - два распределения вероятностей
на конечном множестве N = {1, 2, . . . , n}. Напомним, что вариационное расстояние
V (P, Q) между распределениями P и Q определяется равенством
∑
V (P, Q) =
|pi - qi|,
(1)
i∈N
а информационная дивергенция (или просто дивергенция) D(P ∥ Q) распределе-
ния P относительно Q - равенством
∑
D(P ∥ Q) =
pi ln
pi ,
(2)
qi
i∈N
где всегда предполагается, что 0 ln(0/0) = 0 и a ln(a/0) = ∞, если a > 0, а ln(·) - это
натуральный логарифм.
Получению различных нижних границ для минимума дивергенции D(P ∥Q) по
всем распределениям P и Q на N при условии, что задано лишь вариационное рас-
стояние V (P, Q), посвящено много работ (см., например, работу [1] и библиографию
в ней). Среди подобных границ снизу для D(P ∥ Q) отметим хорошо известные нера-
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных
исследований (номер проекта 19-01-00364).
21
венства Пинскера [2, задача 3.17]
V2(P, Q)
D(P ∥ Q) ≥
(3)
2
и Вайды [3]
2 + V (P,Q)
2V (P, Q)
D(P ∥ Q) ≥ ln
-
(4)
2 - V (P,Q)
2 + V (P,Q)
В работе [4] неравенство Пинскера (3) улучшается при условии, что задано не
только вариационное расстояние V (P, Q), но и распределение вероятностей Q, а в [5]
при указанных условиях получено асимптотически точное значение для минимума
D(P ∥ Q) в случае, когда распределение Q стремится к вырожденному.
Если задано только вариационное расстояние V (P, Q) между P и Q, то очевидно,
что дивергенция D(P ∥ Q) может принимать сколь угодно большие значения. Поэто-
му получить нетривиальные верхние границы для дивергенции D(P ∥ Q) возможно
лишь, если помимо вариационного расстояния V (P, Q) имеются какие-либо другие
ограничения на распределения P и Q. В [6, лемма 6.3] показано, что
∑
(pi - qi)2
D(P ∥ Q) ≤
,
qi
i∈N
откуда сразу вытекает следующая верхняя граница для максимума дивергенции
D(P ∥ Q) при условии, что qmin = minqi > 0
i∈N
V2(P, Q)
D(P ∥ Q) ≤
(5)
qmin
Эта верхняя граница улучшена в работах [7, 8], где показано, что
(
)
V2(P, Q)
D(P ∥ Q) ≤ ln
1+
(6)
2qmin
Авторы [7, 8] назвали верхнюю границу (6) “обратным (reverse) неравенством Пин-
скера”.
В настоящей статье мы улучшаем границу (6), показав, что для любых распре-
делений P = {pi, i ∈ N } и Q = {qi, i ∈ N } на конечном множестве N c |N | ≥ 3 и
V (P, Q) = v справедливы неравенства
(
(
)
v)
v
v
D(P ∥ Q) ≤ qmin +
ln 1+
,
если
≥qmin,
(7)
2
2qmin
2
v
а если
≤ qmin, то
2
(
(
)
(
(
)
v)
v
v)
v
D(P ∥ Q) ≤ qmin +
ln 1+
+ qmin -
ln 1-
(8)
2
2qmin
2
2qmin
При этом верхние границы (7), (8) не могут быть улучшены, так как они явля-
ются оптимальными, т.е. их правые части - максимальные значения дивергенции
D(P ∥ Q) при условии, что задано вариационное расстояние V (P, Q) = v и величина
минимальной компоненты qmin распределения Q. Это утверждение является след-
ствием (точную формулировку которого см. ниже) доказываемой здесь теоремы 1,
в которой получено точное выражение для максимума дивергенции D(P ∥ Q) при
условии, что заданы распределение Q и вариационное расстояние V (P, Q).
Для формулировки теоремы 1 введем несколько необходимых определений. Обо-
значим через Ns подмножество N , не содержащее элемент s, т.е. Ns = N \ {s}. Для
22
заданного распределения вероятностей Q = {qi, i ∈ N } и параметра v, 0 ≤ v ≤
≤ 2(1 - qmin), всякое равенство
∑
v
= qi + β, где Is ⊆ Ns,
(9)
2
i∈Is
v
назовем допустимым Is-представлением
, если либо β = 0, либо существует ин-
2
v
декс j ∈ Ns \ Is, такой что 0 < β < qj . Для всякого допустимого Is-представления
2
введем величину
(
(
)
(
v)
v
Ls(Is, v) = qs +
ln 1+
+ (qk - β) ln 1 -
β ),
(10)
2
2qs
qk
где
qk =
min
{qj}.
j: j∈Ns\Is, β<qj
При этом в случае, когда в представлении (9) β = 0 и Is = Ns, по определению
считаем, что второе слагаемое в правой части (10) равно нулю.
Теорема 1. Для любого распределения вероятностей Q = {qi, i ∈ N}, такого
что q1 ≥ q2 ≥ . . . ≥ qn > 0, и любого v, 0 ≤ v ≤ 2(1 - qn), для величины
D(Q, v) = max D(P ∥ Q)
P: V (P,Q)=v
справедливы следующие утверждения:
• Для любого v справедливо равенство
D(Q, v) = max Ls(Is, v),
(11)
s,Is
где Ls(Is, v) определены в (10), а максимум берется по всем s и всем допус}и-{
v
v
мым Is-представлениям
, таким что t ≤ s ≤ n, где t = min i : qi +
≤1 ;
2
2
• Если 0 ≤ v/2 ≤ qn, то
(
(
)
(
(
)
v)
v
v)
v
D(Q, v) = qn-1 +
ln 1+
+ qn -
ln 1-
;
(12)
2
2qn-1
2
2qn
• Если 1 - qn-1 ≤ v/2 ≤ 1 - qn, то
v
(
(
)
(
1-qn -
v)
v
v)
D(Q, v) = qn +
ln 1+
+ 1-qn -
ln
2;
(13)
2
2qn
2
qn-1
• Для любых v справедлива верхняя граница
(
(
)
v)
v
D(Q, v) ≤ qn +
ln 1+
;
(14)
2
2qn
v
∑
• Если qn < v/2 < 1 - qn-1 и
= aiqi + β, где ai ∈ {0, 1}, и либо β = 0, либо
2
i=1
существует индекс j, такой что aj = 0 и 0 < β < qj , то справедлива нижняя
граница
(
(
)
(
v)
v
D(Q, v) ≥ qn +
ln 1+
+ (qj - β) ln 1 -
β );
(15)
2
2qn
qj
23
• Верхняя и нижняя границы в (14) и (15) совпадают, так что
(
(
)
v)
v
D(Q, v) = qn +
ln 1+
,
(16)
2
2qn
v
∑
если
= aiqi при любых ai ∈ {0, 1}.
2
i=1
Доказательство этой теоремы приведено в Приложении.
Следствие. Пусть P = {pi,i ∈ N} и Q = {qi,i ∈ N} - распределения вероят-
ностей на одном и том же конечном множестве N с |N | ≥ 3, и пусть
qmin = minqi > 0.
i∈N
Тогда для величины
D∗(qmin, v) =
max
D(P ∥ Q)
(P,Q): V (P,Q)=v, min
qi=qmin
i∈N
при любом v, 0 ≤ v ≤ 2(1 - qmin), справедливы следующие равенства:
v
• Если
≥ qmin, то
2
(
(
)
v)
v
D∗(qmin, v) = qmin +
ln 1+
;
(17)
2
2qmin
v
• Если
≤ qmin, то
2
(
(
)
(
(
)
v)
v
v)
v
D∗(qmin, v) = qmin +
ln 1+
+ qmin -
ln 1-
(18)
2
2qmin
2
2qmin
Действительно, очевидно, что
(
)
(
)
v
v
D∗(qmin, v) =
max
D(Q, v) ≤ qmin +
ln 1+
,
(19)
Q: min
qi=qmin
2
2qmin
i∈N
так как из (10) и (11) следует, что для любых Q = {qi, i ∈ N } с minqi = qmin и
i∈N
любых v, 0 ≤ v ≤ 2(1 - qmin), справедливо неравенство
(
(
)
v)
v
D(Q, v) ≤ qmin +
ln 1+
2
2qmin
С другой стороны, если v/2 ≥ qmin, то существует распределение Q′ = {q′i, i ∈ N },
∑
q′1
≥ q′2 ≥ ... ≥ q′n > 0, для которого q′n = qmin иv
=
aiq′i при некоторых
2
i=1
ai ∈ {0, 1}, а тогда из (15) следует, что
(
(
)
v)
v
D∗(qmin, v) ≥
D(Q′, v) ≥ qmin +
ln 1+
(20)
2
2qmin
Из (19) и (20) теперь следует (17).
Если же v/2 ≤ qmin, то с одной стороны, из (12) следует, что для любого распре-
деления Q = {qi, i ∈ N }, q1 ≥ q2 ≥ . . . ≥ qn > 0, для которого qn = qmin, справедливо
неравенство
D∗(qmin, v) =
max
D(Q, v) ≤
Q: min
qi=qmin
i∈N
(
(
)
(
(
)
v)
v
v)
v
≤ qmin +
ln 1+
+ qmin -
ln 1-
,
2
2qmin
2
2qmin
24
(
)
(
)
v
v
так как по предположению qn-1 ≥ qn, а функция
x +
ln 1 +
убывает
2
2x
по x. С другой стороны, в случае, когда |N | ≥ 3, существует распределение Q′′ =
= {q′′i , i ∈ N}, q′′1 ≥ q′′2 ≥ . . . ≥ q′′n > 0, для которого q′′n-1 = q′′n = qmin, а тогда из (12)
следует, что
(
(
)
(
(
)
v)
v
v)
v
D∗(qmin, v) ≥
D(Q′′, v) = qmin +
ln 1+
+ qmin -
ln 1-
,
2
2qmin
2
2qmin
что и доказывает равенство (18).
В теореме 1 было приведено точное (а в некоторых случаях и явное) значение для
максимума дивергенции D(P ∥ Q) при условии, что заданы распределение Q и вари-
ационное расстояние V (P, Q), а в следующей теореме приводится явное выражение
для максимума дивергенции D(Q ∥ P ) при тех же условиях.
Теорема 2. Для любого распределения вероятностей Q = {qi, i ∈ N}, такого
что q1 ≥ q2 ≥ . . . ≥ qn > 0, и любого v, 0 ≤ v ≤ 2(1 - qn), для величины
D(Q, v) =
= max D(Q ∥ P ) справедливо равенство
P: V (P,Q)=v
⎧
v
⎨∞,
если
≥qn,
2
D(Q, v) =
(
)
(
)
(21)
v
v
⎩qn ln 1 +v
+ qn-1 ln 1 -
,
если
<qn.
2qn
−v
2qn-1
−v
2
Эта теорема также доказывается в Приложении.
ПРИЛОЖЕНИЕ
Доказательство теоремы 1 основано на следующем утверждении.
Лемма. Существует оптимальное распределение P∗ = {p∗i, i ∈ N} (т.е. рас-
пределение, на котором достигается значение
D(Q, v) = max D(P ∥ Q)), для
P: V (P,Q)=v
которого p∗s = qs + v/2 для некоторого s ∈ N , а все остальные p∗i ≤ qi, i ∈ Ns. При
этом все эти p∗i равны либо нулю, либо соответствующим qi, за исключением,
возможно, лишь одного, скажем, p∗j, j ∈ Ns, такого что 0 < p∗j < qj .
Доказательство. Пусть P = {pi, i ∈ N} - произвольное распределение ве-
роятностей, для которого V (P, Q) = v, и пусть A = A(P, Q) = {i ∈ N : pi > qi}.
Покажем, что в случае, когда A содержит по крайней мере два различных элемен-
та, скажем, k и j, существует другое распределение вероятностей
P = {pi, i ∈ N},
для которого V
P,Q)=vиD
P ∥Q) > D(P ∥Q). Пусть для определенности qk ≥ qj.
Тогда таким распределением
P = {pi, i ∈ N} служит распределение с компонентами
⎧
⎨pi
при i ∈ N \ {k, j},
pi =
qk
при i = k,
⎩
pj + pk - qk
при i = j.
Действительно, очевидно, что V
P,Q) = V (P,Q) и
pk
pj
pj + pk - qk
D(P ∥ Q) - D
P ∥Q) = pk ln
+ pj ln
- (pj + pk - qk) ln
qk
qj
qj
25
Поэтому для доказательства того, что D
P ∥Q) > D(P ∥Q), достаточно воспользо-
ваться неравенством
pk
pj
pj + pk - qk
pk ln
+ pj ln
< (pj + pk - qk) ln
,
qk
qj
qj
справедливость которого немедленно следует их того, что функция
pk + x
pj
pj + x
f (x) = (qk + x) ln
+ pj ln
- (pj + x) ln
pk
qj
qj
строго убывает по x при x ≥ 0, а при x = 0 она равна нулю. Действительно,
qkqj + xqj
f′(x) = ln
< 0,
qkpj + xqk
так как qj < pj , а qj ≤ qk по условию. Поэтому существует оптимальное распре-
деление P∗ = {p∗i, i ∈ N }, для которого множество A(P∗, Q) = {i ∈ N : p∗i > qi}
содержит лишь один элемент, скажем, s, такой что p∗s = qs + v/2, а все остальные
p∗i ≤ qi, i ∈ Ns.
Покажем теперь, что существует оптимальное распределение P∗ = {p∗i, i ∈ N},
которое наряду с первым удовлетворяет и второму утверждению леммы. Для этого
достаточно воспользоваться следующим утверждением: пусть P = {pi, i ∈ N } -
некоторое распределение вероятностей, для которого V (P, Q) = v, ps = qs + v/2,
pi ≤ qi для всех i ∈ Ns и существует два различных индекса k и j из Ns, такие
что 0 < pk < qk и 0 < pj < qj . Тогда существует распределение вероятностей
P = {pi, i ∈ N}, для которого:
1) pi = pi при всех i ∈ N \ {k, j};
2) pk ∈ {0, qk} или pj ∈ {0, qj};
3) V
P,Q) = v;
4) D
P ∥Q) ≥ D(P ∥Q).
Действительно, рассмотрим распределения P(x) = {pi(x), i ∈ N} с компонентами
⎧
⎨pi
при i ∈ N \ {k, j},
pi(x) =
pk - x при i = k,
⎩
pj + x при i = j,
где x ∈ [max{-pj, pk - qk}, min{pk, qj - pj}]. Тогда очевидно, что для всех таких рас-
пределений P (x) имеет место равенство V (P (x), Q) = v, а максимум D(P (x) ∥ Q),
больший или равный D(P(0)∥Q) = D(P ∥Q), достигается на одном из концов ука-
занного выше отрезка значений параметра x, поскольку функция
pk - x
pj + x
(pk - x) ln
+ (pj + x) ln
qk
qj
является выпуклой по x, откуда и следует сформулированное выше утверждение. ▴
Из этой леммы первое утверждение теоремы 1, т.е. формула (11), немедленно )(
β
следует, если заметить, что функция (x - β) ln 1 -
убывает по x.
x
Справедливость формулы (12) также легко следует из утверждения леммы. Дей-
ствительно, если 0 ≤ v/2 < qn, то в Is-допустимом представлении v/2 величина
Is = ∅, а β = v/2. Поэтому очевидно, что
max Ls(Is, v) = max{Ln(∅, v), Ln-1(∅, v)}.
s,Is
26
Замечая, что разность Ln(∅, v) - Ln-1(∅, v), как легко проверить, убывает по v,
а при v = 0 она равна нулю, получаем, что max Ls(Is, v) = Ln-1(∅, v), а это равно-
s,Is
сильно формуле (12). Легко видеть, что формула (12) справедлива и в случае, когда
v/2 = qn.
Для доказательства (13) следует заметить, что в случае, когда 1 - qn-1 < v/2 ≤
≤ 1 - qn, имеем t = min{i : qi + v/2 ≤ 1} = n, и поэтому
(
(
)
v)
v
D(Q, v) = maxLn(In, v) = qn +
ln 1+
+
In
2
2qn
{
v
}
(
1-qn -
v)
2
+ max
1-qn -
ln
=
k: k=n
2
qk
v
(
(
)
(
1-qn -
v)
v
v)
= qn +
ln 1+
+ 1-qn -
ln
2.
2
2qn
2
qn-1
Если же 1 - qn-1 = v/2, то справедливость равенства (13) также легко проверяется
непосредственно.
Верхняя граница (14) немедленно следует из (10) и 11), а нижняя граница (15)
также вытекает из (10 ) и (11), если заметить, что
D(Q, v) ≥ Ln(In, v), где In -
∑
множество индексов суммирования i в сумме v/2 =
aiqi +β, для которых ai = 0.
i=1
Наконец, равенство (16) сразу следует из (14) и (15), так как в этом случае в нижней
границе (15) величина β равна нулю. ▴
Доказательство теоремы 2. Пусть заданы распределение вероятностей
Q = {qi,i ∈ N}, q1 ≥ q2 ≥ ... ≥ qn > 0, и параметр v, 0 ≤ v ≤ 2(1 - qn). Прежде
всего заметим, что первое равенство в (21) почти очевидно, так как в этом случае
легко построить распределение вероятностей P = {pi, i ∈ N }, такое что V (P, Q) = v,
а одна из компонент pi = 0. Действительно, если v удовлетворяет условию 2qn ≤
≤ v ≤ 2(1 - qn-1), то полагаем
P = {q1 - ε1,q2 - ε2,...,qn-2 - εn-2,qn-1 + v/2,0},
∑
где εi, i = 1, 2, . . ., n - 2, таковы что 0 ≤ εi ≤ qi и
εi
= v/2 - qn. Такие εi
∑
i=1
существуют, так как v/2 - qn ≤
qi, поскольку по условию v ≤ 2(1 - qn-1). Если
i=2
же v удовлетворяет условию 2(1 - qn-1) ≤ v ≤ 2(1 - qn), то полагаем
P = {q1 - ε1,q2 - ε2,...,qn-2 - εn-2,0,qn + v/2},
∑
где εi, i = 1, 2, . . . , n - 2, таковы что 0 ≤ εi ≤ qi и
εi
= v/2 - qn-1. Такие εi
i=1
∑
в данном случае тоже существуют, так как v/2 - qn-1 ≤
qi. Таким образом,
первая из формул в (21) доказана.
i=2
Докажем теперь вторую формулу в (21), когда предполагается, что 0 ≤ v/2 < qn.
В этом случае мы вначале хотим показать, что максимум D(Q∥P) достигается на
одном из двух распределений
P1 = {q1, q2, . . ., qn-2, qn-1 - v/2, qn + v/2}
или
P2 = {q1, q2, . . ., qn-2, qn-1 + v/2, qn - v/2},
27
а затем выберем из них оптимальное, т.е. то, на котором достигается значение
D(Q, v).
Пусть P
= {pi, i ∈ N} - некоторое распределение вероятностей, такое что
V (P, Q) = v. Положим
A = A(P,Q) = {i ∈ N : pi > qi},
B = B(P,Q) = {i ∈ N : pi < qi}.
Тогда, как и при доказательстве теоремы 1, нетрудно показать, что для оптималь-
ного распределения P множества A(P, Q) и B(P, Q) содержат лишь по одному эле-
менту, причем либо A(P, Q) = {n} и B(P, Q) = {n - 1}, либо A(P, Q) = {n - 1} и
B(P, Q) = {n}. Действительно, если A(P, Q) содержит по крайней мере два элемента
j и k, j = k, то P не может быть оптимальным распределением. Это утверждение
немедленно следует из неравенства
qj
qk
qk
qj ln
+ qk ln
< qk ln
,
если qk ≤ qj ,
pj
pk
pk - (qj - pj)
которое, в свою очередь, является следствием того, что функция
qj
qk
qk
f (x) = qj ln
+ qk ln
- qk ln
qj - x
pk
pk - x
строго убывает по x, 0 < x < v/2.
Аналогично доказывается, что множество B(P, Q) для оптимального распреде-
ления P тоже содержит лишь один элемент. Наконец, утверждение о том, что опти-
мальным распределением является P1 или P2, теперь следует из того, что
qk
qk
qk ln
и qk ln
qk - v/2
qk + v/2
являются убывающими функциями qk.
Для доказательства второго равенства в (21) нам осталось лишь показать, что на
самом деле оптимальным является распределение P2, т.е. что D(Q ∥ P2) ≥ D(Q ∥ P1).
А это неравенство следует из того, что разность
D(Q ∥ P2) - D(Q ∥ P1)
является возрастающей функцией v, v ∈ [0, 2qn), так как легко проверить, что
(
)[
[D(Q ∥ P2) - D(Q ∥ P1)]′v/2 =
v2/2
(q2n-1 - v2/4)(q2n - v2/4]-1 (q2n-1 - q2n) ≥ 0,
а при v = 0 эта разность равна нулю.
▴
СПИСОК ЛИТЕРАТУРЫ
1. Fedotov A.A., Harremöes P., Topsøe F. Refinements of Pinsker’s Inequality // IEEE Trans.
Inform. Theory. 2003. V. 49. № 6. P. 1491-1498.
2. Чисар И., Кёрнер Я. Теория информации: Теория кодирования для дискретных систем
без памяти. М.: Мир, 1985.
3. Vajda I. Note on Discrimination Information and Variation // IEEE Trans. Inform. Theory.
1970. V. 16. № 6. P. 771-773.
4. Ordentlich E., Weinberger M.J. A Distribution Dependent Refinement of Pinsker’s Inequal-
ity // IEEE Trans. Inform. Theory. 2005. V. 51. № 5. P. 1836-1840.
5. Прелов В.В. О склеивании вероятностных распеделений и оценивании дивергенции че-
рез вариацию // Пробл. передачи информ. 2017. Т. 53. № 3. С. 16-22.
28
6. Csiszár I., Talata Z. Context Tree Estimation for Not Necessarily Finite Memory Processes
via BIC and MDL // IEEE Trans. Inform. Theory. 2006. V. 52. № 3. P. 1007-1016.
7. Sason I., Verdú S. Upper Bounds on the Relative Entropy and Rényi Divergence as a Function
of Total Variation Distance for Finite Alphabets // Proc. 2015 IEEE Information Theory
Workshop (ITW’2015). Jeju, Korea. October 11-15, 2015. P. 214-218.
8. Sason I., Verdú S. f-Divergence Inequalities // IEEE Trans. Inform. Theory. 2016. V. 62.
№ 11. P. 5973-6006.
Прелов Вячеслав Валерьевич
Поступила в редакцию
Институт проблем передачи информации
21.05.2019
им. А.А. Харкевича РАН
После доработки
prelov@iitp.ru
03.07.2019
Принята к публикации
05.07.2019
29
