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

Том 55

2019

Вып. 1

УДК 621.391.1 : 519.72

В.В. Прелов

ОБ ЭКСТРЕМАЛЬНЫХ ЗНАЧЕНИЯХ ЭНТРОПИИ РЕНЬИ

ПРИ СКЛЕИВАНИИ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ¹

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

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

α-склеивания этой величины с другой случайной величиной, имеющей заданное

распределение вероятностей.

DOI: 10.1134/S0134347519010029

Энтропия Реньи H_λ(P ) положительного порядка λ = 1 дискретного распределе-

ния вероятностей P = {p₁, p₂, . . . , p_n} определяется равенством (см. [1, 2])

∑

H_λ(P) =

p^λi, λ > 0, λ = 1.

(1)

1-λ

i=1

Величину H_λ(P ) называют также энтропией Реньи дискретной случайной величи-

ны X с распределением вероятностей P . В случае, когда P = {p, 1-p}, вместо H_λ(P )

будем использовать обозначение h_λ(p), т.е.

[

]

h_λ(p) =

p^λ + (1 - p)^λ

(2)

1-λ

Заметим, что для любого P = {p₁, p₂, . . . , p_n} и любого λ > 0, λ = 1, справедливы

неравенства

0 ≤ H_λ(P) ≤ lnn и H_λ(P) → H(P) при λ → 1,

∑

где H(P ) = - p_i ln p_i - энтропия Шеннона.

i=1

Напомним также, что α-склеиванием двух дискретных распределений вероят-

ностей P = {p₁, p₂, . . . , p_n} и Q = {q₁, q₂, . . ., q_n} называется совместное распреде-

ление вероятностей P_XY случайных величин X и Y со значениями в множестве

{1, 2, . . ., n}, такое что Pr{X = Y } = α, а маргинальные распределения, соответ-

ствующие этому P_XY , равны, соответственно, P_X = P и P_Y = Q.

Для фиксированных распределения вероятностей P = {p₁, p₂, . . . , p_n} и действи-

тельных чисел λ и α, где λ > 0, λ = 1 и 0 ≤ α ≤ 1, введем величины

H_min(P, λ, α) = inf

H_λ(Q),

(3)

H_max(P, λ, α) = supH_λ(Q),

(4)

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

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

где нижние и верхние грани в (3), (4) берутся по всевозможным распределениям

вероятностей Q = {q₁, q₂, . . . , q_n}, для которых существует их α-склеивание с рас-

пределением P .

Заметим, что аналогичная задача для энтропии Шеннона рассматривалась в [3],

а подобная задача для энтропии Шеннона в случае, когда вместо условия существо-

вания α-склеивания P и Q вводилось условие на их вариационное расстояние, рас-

сматривалась в [4]. В настоящей статье получены явные формулы для H_min(P, λ, α)

для всех возможных значений параметров P , λ и α. Для H_max(P, λ, α) явные форму-

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

интервалов значений α получены лишь некоторые верхние и нижние границы. Сра-

зу заметим, что полученные здесь формулы для H_min(P, λ, α) и H_max(P, λ, α) вполне

аналогичны соответствующим формулам для подобных величин в случае энтропии

Шеннона, приведенных в [3], однако доказательство явных формул для H_min(P, λ, α)

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

ющих формул в [3].

Переходя к формулировке результатов статьи, будем всегда считать, что распре-

деление вероятностей P = {p₁, p₂, . . . , p_n}, n ≥ 2, задано, причем вероятности p_i

упорядочены по убыванию, так что p₁ ≥ p₂ ≥ . . . ≥ p_n > 0.

Предложение 1. Пусть распределение вероятностей P = {p₁,p₂,...,p_n} и

действительные числа λ, λ > 0, λ = 1, и α, 0 ≤ α ≤ 1, заданы. Тогда

• Если 0 ≤ α ≤ p_n, то

H_min(P, λ, α) = h_λ(p_n - α);

(5)

• Если pk+1 < α ≤ p_k, k = 1, 2, . . . , n - 1, то

⎧

p_k + pk+1

^⎨h_λ(α - pk+1), если pk+1 < α ≤

H_min(P, λ, α) =

(6)

p_k + pk+1

^⎩h_λ(p_k - α),

если

<α≤p_k;

∑

• Если

p_i < α ≤ p_i, k = 1, 2, . . ., n - 1, то

i=1

[

]

∑

H_min(P, λ, α) =

ln (1 + p1 - α)λ + pλi + (α - pi)λ

(7)

1-λ

i=2

i=1

Доказательство этого предложения основано на использовании понятия вы-

пуклости функций по Шуру. Напомним основные нужные нам определения и факты

(см. [5]). Если x = (x₁, . . . , x_n) ∈ Rⁿ , где Rⁿ - n-мерное евклидово пространство,

то через x^↓ = (x↓1, . . . , x^↓n) обозначается вектор из Rⁿ , содержащий те же компо-

ненты, что и x, но записанные в порядке убывания, так что x↓1 ≥ x↓2 ≥ . . . ≥ x^↓n.

Пусть x = (x₁, . . . , x_n) и y = (y₁, . . . , y_n) - два вектора из Rⁿ. Говорят, что вектор x

мажорируется вектором y (или что y мажорирует x), и записывают x ≺ y, если

выполняются два условия:

∑

x^↓i ≤

y^↓i,

1 ≤ k ≤ n - 1,

(8)

i=1

∑

x^↓i =

y^↓i.

(9)

i=1

Действительнозначная функция ϕ(·), заданная на множестве A ⊂ Rⁿ, называется

выпуклой по Шуру, если из условия x ≺ y на A следует неравенство ϕ(x) ≤ ϕ(y).

Если же из условия x ≺ y на A следует ϕ(x) ≥ ϕ(y), то функция ϕ(·) называ-

ется вогнутой по Шуру. Если функция ϕ(·) выпукла по Шуру, то очевидно, что

функция -ϕ(·) вогнута по Шуру.

Справедливо также следующее утверждение (см. [5]): если I ⊂ R - некоторый

∑

интервал, а g : I → R - выпуклая (в обычном смысле) функция, то ϕ(x) = g(x_i)

i=1

является выпуклой по Шуру функцией на Iⁿ, т.е. x ≺ y ⇒ ϕ(x) ≤ ϕ(y). Из этого

утверждения немедленно следует, что энтропия Реньи H_λ(Q) при любом λ > 0,

λ = 1, является вогнутой по Шуру функцией от распределения вероятностей Q.

Поэтому для нахождения H_min(P, λ, α) достаточно найти допустимое распределение

вероятностей Q^∗ = {q∗1, q∗2, . . ., q^∗n} (т.е. распределение вероятностей, для которого

существует α-склеивание с заданным распределением P = {p₁, p₂, . . . , p_n}), такое

что Q^∗ мажорирует любое другое допустимое распределение вероятностей Q. Любое

допустимое распределение вероятностей Q = {q₁, q₂, . . . , q_n} является маргинальным

для некоторой допустимой матрицы совместного распределения (т.е. матрицы M =

= ∥p_ij ∥ni,j=1 с неотрицательными элементами p_ij , такими что

∑

p_ij = p_i, i = 1, . . ., n,

p_ii = α,

j=1

i=1

где P = {p₁, p₂, . . . , p_n} - заданное распределение вероятностей).

Докажем теперь формулы (5)-(7).

1. Пусть 0 ≤ α ≤ p_n. Покажем, что в этом случае распределение вероятностей

Q^∗ = {q∗1, q∗2, . . . , q^∗n}, задаваемое допустимой матрицей M^∗ = ∥p^∗ij∥ni,j=1, где

⎧

для i = j = n,

⎪

⎨

p_i

для всех i = n и j = n,

p^∗ij =

(10)

⎪pn - α

для i = n и j = j₀,

⎩

в остальных случаях,

где j₀ - любое натуральное число, меньшее n, мажорирует любое другое допусти-

мое распределение вероятностей Q = {q₁, q₂, . . . , q_n}, откуда сразу будет следовать

справедливость формулы (5). Для этого, очевидно, достаточно доказать, что для

любого допустимого распределения вероятностей Q = {q₁, q₂, . . . , q_n} справедливо

неравенство

max

q_i ≤ 1 - p_n + α.

(11)

1≤i≤n

Действительно, для любой допустимой матрицы M = ∥p_ij∥ni,j=1 и любого j, 1 ≤

≤ j ≤ n, имеем

∑

q_j =

p_ij =

p_ij + p_jj ≤ 1 - p_j + α ≤ 1 - p_n + α,

i=1

i: i=j

откуда и следует (11).

p_k + pk+1

2. Пусть теперь pk+1 < α ≤

для некоторого k = 1, 2, . . . , n - 1. В этом

случае распределение вероятностей Q^∗ = {q∗1, q∗2, . . . , q^∗n}, задаваемое допустимой

∥i,j=1^{сэлементами}

⎧

p_i

для всех i = k + 1 и j = k + 1,

⎪

⎨

p_k + pk+1 - α

для i = k и j = k + 1,

p^∗ij =

(12)

⎪α-pk+1

для i = j = k,

⎩

в остальных случаях,

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

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

max

q^∗i = 1 - α + pk+1,

1≤i≤n

поскольку из условия

p_k + pk+1

pk+1 < α ≤

следует, что

1-α+pk+1 ≥α-pk+1.

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

стей Q^∗ мажорирует любое другое допустимое распределение вероятностей Q =

{q₁, q₂, . . . , q_n}, в рассматриваемом случае (а значит, и для доказательства первой

из формул в правой части (6)) достаточно показать, что

max

q_i ≤ 1 - α + pk+1.

(13)

1≤i≤n

Действительно, для любого допустимого Q = {q₁, q₂, . . . , q_n}, очевидно, имеем

max

q_i =

max

(1 - (p_i - x) - (α - x)),

(14)

1≤i≤n

i,x≤min{pi,α}

если в матрице совместного распределения M = ∥p_ij ∥ni,j=1, задающего это распреде-

ление Q, элемент p_ii равен x. Оптимизируя правую часть (14) по i и x при заданных

ограничениях, легко устанавливаем, что

max

q_i ≤ 1 - α + pk+1,

1≤i≤n

что и доказывает (13).

p_k + pk+1

3. Пусть

< α ≤ p_k для некоторого k = 1,2,...,n - 1. В этом случае

распределение вероятностей Q^∗ = {q∗1, q∗2, . . . , q^∗n}, задаваемое допустимой матрицей

M^∗ = ∥p^∗ij∥ni,j=1 с элементами

⎧

⎪pi

для всех i = k и j = k,

⎨

p_k - α

для i = k и некоторого j = k,

p^∗ij =

(15)

⎪α

для i = j = k,

⎩

в остальных случаях,

мажорирует любое другое допустимое распределение вероятностей Q = {q₁, q₂,

...,q_n}. Доказательство этого утверждения вполне аналогично рассмотренному вы-

ше случаю 2. Отсюда сразу следует справедливость второй формулы в правой ча-

сти (6).

∑

4. Пусть, наконец,

p_i < α ≤

p_i для некоторого k = 1, 2, . . ., n - 1. В этом

i=1

случае снова легко проверить,что распределение вероятностей Q^∗ = {q∗1, q∗2, . . . , q^∗n},

где

⎧

⎪1 + p1 - α для i = 1,

⎪

⎨pi

для i = 2, 3, . . . , k,

q^∗i =

∑

(16)

⎪α - ps для i = k + 1,

⎪

⎩ s⁼¹

для i = k + 2, . . . , n,

задаваемое допустимой матрицей M^∗ = ∥p^∗ij∥ni,j=1 с элементами

⎧

⎪pi

для i = j = 1, 2, . . . , k,

⎪

∑

⎪α - ps для i = j = k + 1,

⎨

s=1

p^∗ij =

(17)

⎪

^∑ p_s - α для i = k + 1 и j = 1,

⎪

s=1

⎪

p_i

для i = k + 2, . . . , n и j = 1,

⎩

в остальных случаях,

мажорирует любое другое допустимое распределение вероятностей Q = {q₁, q₂,

...,q_n}. Отсюда следует справедливость формулы (7). ▴

Следствие. Пусть F(P) = F(p₁,p₂,...,p_n) - любая неотрицательная ограни-

ченная и вогнутая по Шуру функция от распределения вероятностей P

= {p₁, p₂, . . . , p_n}, и пусть

F_min(P, α) = minF(Q),

(18)

где минимум берется по всевозможным распределениям вероятностей Q

= {q₁, q₂, . . . , q_n}, для которых существует их α-склеивание с P. Тогда из доказа-

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

Q^∗ = {q∗1, q∗2, . . . , q^∗n} (на которых достигается минимум в правой части (18)) яв-

ляются маргинальными для совместных распределений вероятностей (10), (12),

(15) и (17) для соответствующих интервалов значений параметра α. В частно-

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

Реньи, так и для энтропии Шеннона и “энтропии степени λ”

(

)

∑

H^λ(P) = (21-λ)-1

p^λi - 1

λ > 0, λ = 1.

i=1

Замечание 1. Отметим, что H_min(P, λ, α) ≤ H_λ(P) для всех возможных значений

P = {p₁,p₂,...,p_n} и α за исключением лишь случая, когда p₁ > 1/2 и p₂ < α < p₁.

В этом последнем случае для некоторых значений p₁, p₂ и α может быть справедливо

противоположное неравенство H_min(P, λ, α) > H_λ(P ), например, оно верно, если p₁

достаточно велико, а α близко к 1/2. Действительно, легко проверить, что во всех

случаях (кроме указанного выше, когда p₁ > 1/2 и p₂ < α < p₁) маргинальные рас-

пределения Q^∗, задаваемые матрицами совместного распределения (10), (12), (15)

и (17) для соответствующих значений параметра α, мажорируют распределение P ,

откуда и следует, что H_min(P, λ, α) ≤ H_λ(P).

В общем случае найти точное значение для H_max(P, λ, α) не удается, но в следую-

щем предложении приводятся достаточные условия на параметры P и α, при кото-

рых H_max(P, λ, α) принимает свое максимальное значение log n, а также приводятся

верхние и нижние границы для H_max(P, λ, α) при других значениях параметров P

и α. В формулировке этого предложения используется функция f_n(x, λ), 0 ≤ x ≤ 1,

λ > 0, λ = 1, задаваемая равенством

[

]

f_n(x, λ) =

x^λ + (n - 1)1-λ(1 - x)^λ

(19)

1-λ

Предложение 2. Пусть заданы распределение вероятностей P

= {p₁, p₂,

...,p_n}, p1 ≥ p2 ≥ ... ≥ pn > 0, и величины λ, λ > 0, λ = 1, и α, 0 ≤ α ≤ 1.

Тогда справедливы следующие утверждения:

• Если

-p_n ≤α≤

+ (n - 1)p_n, то

H_max(P, λ, α) = lnn;

(20)

• Если p₁ > 1 -

и 0≤α<p₁ +

- 1, то

p₁ - α

H_max(P, λ, α) ≤ f_n(a₁, λ), где a₁ =

;

(21)

n-1

• Если 1 -

+ p_n < α ≤ 1, то

α-p_n

H_max(P, λ, α) ≤ f_n(a₂, λ), где a₂ =

;

(22)

n-1

1 - p1 - (n - 1)pn

• Если

≤α≤

- p_n, то

H_max(P, λ, α) ≥ f_n(b₁, λ), где b₁ = α + p_n;

(23)

n-1

(n - 1)²

• Если

+ (n - 1)p_n ≤ α ≤

p₁ +

p_n, то

H_max(P, λ, α) ≥ f_n(b₂, λ), где b₂ = α - (n - 1)p_n.

(24)

Доказательство. Первое утверждение этого предложения следует из того,

что допустимое совместное распределение, задаваемое матрицей M = ∥p_ij∥ni,j=1, где

⎧

⎨α_i

для i = j = 1, 2, . . . , n,

p_ij =

p_i - α_i

⎩

для i = 1, . . . , n и j ∈ {1, . . . , n} \ {i},

n-1

∑

а параметры α_i, i = 1, . . . , n, удовлетворяют условиям 0 ≤ α_i ≤ p_i и

α_i = α, имеет

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

i=1

∑

nα_j

1 - pj - αi

q_i =

p_ij =

i = 1,2,...,n,

n-1

i=1

если

-p_n ≤α≤

+ (n - 1)p_n.

Доказательство остальных утверждений этого предложения (неравенств (21)-(24))

вполне аналогично доказательству соответствующих неравенств предложения 3 в [3]

и поэтому здесь не приводится. ▴

Замечание 2. Нетрудно показать, что при всех возможных значениях P и α спра-

ведливо неравенство H_max(P, λ, α) ≥ H_λ(P). Действительно, если α <

- p_n, то

допустимое совместное распределение, задаваемое матрицей ∥p_ij∥ni,j=1, где

⎧

⎪α

при i = j = 1,

⎪

⎪p1 - α

при i = 1 и j = n,

⎨

p₂

при i = 2 и j = n - 1,

p_ij =

⎪pi

при i = k и j = k - 1 для k = 3, 4, . . . , n - 1,

⎪

⎪pn

при i = n и j = 1,

⎩

при остальных значениях i и j,

∑

имеет маргинальное распределение Q = {q₁, q₂, . . . , q_n} с q_j =

p_ij, которое, как

i=1

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

H_max(P, λ, α) ≥ H_λ(Q) ≥ H_λ(P).

Если же α >

+ (n - 1)p_n, то допустимое совместное распределение, задаваемое

матрицей ∥p^′ij ∥ni,j=1, где

⎧

⎨αpi

при i = j = 1, . . . , n,

p^′ij =

(1 - α)p_i

⎩

при i = 1, . . . , n и j ∈ {1, . . . , n} \ {i},

n-1

∑

также имеет маргинальное распределение Q^′ = {q′1, q′2, . . . , q^′n} с q^′j =

p^′ij, которое

i=1

тоже, как нетрудно убедиться, мажорируется распределением P , и поэтому снова

имеем

H_max(P, λ, α) ≥ H_λ(Q^′) ≥ H_λ(P).

Наконец, если

-p_n ≤α≤

+ (n - 1)p_n, то согласно предложению 2 имеем

H_max(P, λ, α) = lnn ≥ H_λ(P)

при любом P .

Пример. Пусть n = 2 и P

= {p, 1 - p}, где p ≥ 1/2. В этом случае для

H_max(P, λ, α) нетрудно получить явные выражения при всех возможных значени-

ях α, 0 ≤ α ≤ 1. А именно:

H_max(P, λ, α) = ln2, если p -

≤α≤

- p,

(25)

H_max(P, λ, α) = f2,(p - α, λ), если 0 ≤ α < p -

(26)

H_max(P, λ, α) = f₂(α + p - 1, λ), если

- p < α ≤ 1,

(27)

где f_n(x, λ) определено в (19). Действительно, формула (25) немедленно следует

из (20), а формула (26) - из того, что при 0 ≤ α < p -

распределение вероятностей

Q = {1 - p + α,p - α}, как легко проверить, является допустимым и мажорирует-

ся любым другим допустимым распределением. Наконец, формула (27) следует из

того, что при

- p < α ≤ 1 распределение вероятностей Q = {α + p - 1,2 - α - p}

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

пределением вероятностей.

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

1. Rényi A. On Measures of Entropy and Information // Proc. 4th Berkeley Sympos. on Mathe-

matical Statistics and Probability. Berkely, CA, USA. June 20 - July 30, 1960. Berkely: Univ.

of California Press, 1961. V. 1. P. 547-561.

2. Aczél J., Daróczy Z. On Measures of Information and Their Characterizations. New York:

Academic Press, 1975.

3. Прелов В.В. Об одной экстремальной задаче для энтропии и вероятности ошибки //

Пробл. передачи информ. 2014. Т. 50. № 3. С. 3-18.

4. Ho S.W., Yeung R.W. The Interplay between Entropy and Variational Distance // IEEE

Trans. Inform. Theory. 2010. V. 56. № 12. P. 5906-5929.

5. Marshall A.W., Olkin I., Arnold B.C. Inequalities: Theory of Majorization and Its Applica-

tions. New York: Springer, 2011.

Прелов Вячеслав Валерьевич

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

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

14.11.2018

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

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

prelov@iitp.ru

13.12.2018

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

09.01.2019