Елементы теории статистических решений (байесовы и минимаксные решенииа) 2005 [векторный файл]

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Радиотехнический факультет Кафедра теоретических основ радиотехники

Секция “Современная математика в инженерном образовании”

Ченцов А.Г.

ЭЛЕМЕНТЫ ТЕОРИИ СТАТИСТИЧЕСКИХ РЕШЕНИЙ (БАЙЕСОВЫ И МИНИМАКСНЫЕ РЕШЕНИЯ)

Екатеринбург – 2005

Содержание Введение 1

4

Функция среднего риска

10

2 Байесовы решения.

11

3

17

Статистическая игра

4 Правило выравнивания

22

5 Проблема обнаружения заданного состояния

24

Литература

30

3

Введение Рассматриваются вопросы, связанные с применением минимаксных решающих правил к решению задачи определения неизвестного состояния Природы. Упомянутое рассмотрение приводит к статистической игре А.Вальда; один из игроков — статистик, другой — Природа. Предметом борьбы этих игроков являются усредненные потери при принятии неверных решений, т.е. риск, сопутствующий тем или иным зафиксированным априорному распределению вероятностей состояния Природы и рандомизированному (это существенно) решающему правилу статистика. Усредненные потери интерпретируются как плата статистика Природе; уменьшить эту плату он и стремится, действуя в условиях, когда априорное распределение на пространстве состояний неизвестно. Этой основной, для данной работы, игровой задаче имеет смысл предпослать конструкции, связанные с байесовыми решениями. В этом последнем случае вышеупомянутое априорное распределение полагается известным. Это позволяет поставить и затем решить (на принципиальном уровне) более простую в идейном отношении задачу минимизации средних потерь. Разумеется, получаемое качество зависит от априорного распределения. В наших построениях наиболее интересен случай, когда это распределение является наихудшим для статистика в смысле величины упомянутых средних потерь. Такое распределение на пространстве состояний называют наименее благоприятным. Известно, что искомое минимаксное решение (рандомизированное, вообще говоря, т.е. использующее в качестве “действий” стохастические процедуры выбора) является байесовым в условиях, когда априорное распределение наименее благоприятно. Это свойство является простым следствием разрешимости статистической игры А.Вальда в смысле седловой точки. Данное свойство можно отнести к необходимым условиям экстремума, понимаемого здесь как реализация минимакса; не следует, вообще говоря, использовать это свойство в качестве достаточного условия. Основное достоинство применяемого ниже минимаксного критерия и решений, его реализующих, состоит, грубо говоря, в следующем: с Природой можно довольно успешно “играть”, не зная ее замыслов, поскольку и у статистика, и у Природы есть хотя бы одна пара действий, именуемых обычно стратегиями, для которой чье-то одностороннее отступление (в выборе своего действия) от соответствующей компоненты пары не улуч4

шает (а, зачастую, ухудшает) результат “отступника”, если только его партнер сохраняет свое действие неизменным. Возникающая ситуация может иллюстрироваться, в смысле поверхности значений средних потерь, поверхностью, отвечающей седлу лошади. Упомянутая выше пара стратегий именуется седловой точкой. Важно, что упомянутые участники конфликта (игроки) могут разыгрывать компоненты этой седловой точки независимо. Логику такого независимого поведения можно проиллюстрировать на примере более простой матричной игры (имеется в виду игра, разрешимая в классе чистых стратегий): дана матрица   1 2 3 A =  a b 4 , c d 5 строки которой выбирает игрок I (аналогичный статистику), а столбцы — игрок II (аналогичный Природе). Вещественные числа a,b,c,d произвольны. Итак, предположим, что выбором строки матрицы A ведает одно лицо, а выбором столбца — другое. Будем называть их игроками I и II соответственно: I выбирает строку, а II — столбец A. В результате упомянутого независимого выбора реализуется число Aı, , интерпретируемое как плата, которую игрок I отдает игроку II. Возникает борьба ↓ı Aı, ↑ , которую мы и будем формализовать как матричную игру. Каждую пару (ı, ), ı ∈ 1, 3 ,  ∈ 1, 3 , называем партией. Среди всех партий выделяем (ı∗ , ∗ ), где ı∗ = 1, ∗ = 3; в самом деле A1, ≤ A1,3 ≤ Aı,3 при всяком выборе ı ∈ 1, 3 и  ∈ 1, 3. Данная система неравенств характеризует (ı∗ , ∗ ) = (1, 3) как седловую точку (в чистых стратегиях): мы получили партию, характеризуемую свойством устойчивости. Именно, ни один из игроков не имеет стимула отступать в одиночку от согласованного (казалось бы) поведения, сводящегося к разыгрыванию партии (ı∗ , ∗ ). Вспомним, однако, что игроки действуют изолированно, общих целей не имеют; их заботы — совсем, казалось бы, в другом. 5

Так, игрок I может оценивать выбор строки ı ∈ 1, 3 числом υ ı = max Aı, ; ∈1,3

имеем υ 1 = 3, υ 2 ≥ 4, υ 3 ≥ 5. Ясно, что строка 1, т.е. стратегия ı∗ = 1, в этом смысле предпочтительнее для I. Игрок II при выборе столбца  ∈ 1, 3 может руководствоваться правилом максимизации числа 4

υ  = min Aı, , ı∈1,3

где  ∈ 1, 3. Тогда υ 1 ≤ 1, υ 2 ≤ 2, υ 3 = 3. Ясно, что выбор ∗ = 3 для него (с этих позиций) представляется наиболее предпочтительным. Стало быть, оптимизируя гарантии достигаемого результата (а именно такой смысл имеют числа υ ı , ı ∈ 1, 3 и υ  ,  ∈ 1, 3) игроки I и II “невольно” приходят к разыгрыванию седловой точки (ı∗ , ∗ ) = (1, 3); воистину “все дороги ведут в Рим” (к седловой точке), если только эти “дороги” разумны, а сама седловая точка существует (заметим попутно, что все седловые точки эквивалентны по результату). Последнее обстоятельство наиболее серьезно. Так, например, матричная игра, определяемая в виде   1 0 A= 0 2 не имеет седловых точек в чистых стратегиях. Можно, однако, ввести расширение матричных игр, используя т.н. смешанные стратегии. Для последней игры с матрицей A эти стратегии задаются в виде пар p = (p1 , p2 ) и q = (q1 , q2 ) неотрицательных чисел со свойствами p1 + p2 = 1,

q1 + q2 = 1;

действие этих наборов, т.е. смешанных стратегий, задается операцией, подобной определению математического ожидания в теории вероятностей в условиях статистической независимости на выбор ı ∈ 1, 2 и  ∈ 1, 2; именно, матрицу A заменяем функцией двух переменных A(p, q) =

2 X 2 X ı=1 =1

6

pı Aı, q ,

аргументы выбираются из множества (симплекса) S = {(x, y) : x ∈ [0, 1], y ∈ [0, 1], x + y = 1}. Для игры с функцией потерь A всегда существует пара (p∗ , q∗ ),

p∗ = (p∗1 , p∗2 ) ∈ S,

q∗ = (q1∗ , q∗2 ) ∈ S,

обладающая свойствами: при p ∈ S и q ∈ S A(p∗ , q) ≤ A(p∗ , q∗ ) ≤ A(p, q∗ ). Итак, здесь существует седловая точка (это суждение относится не только к нашей матричной игре, связанной с A, но и к произвольной матричной игре). С этим свойством связано существование цены игры. Для выяснения этого введем гарантии стратегий p ∈ S и q ∈ S, учитывая, что A(p, q) = p1 q1 + 2p2 q2 = = p1 q1 + 2p2 (1 − q1 ) = 2p2 + (p1 − 2p2 )q1 ≤ 2p2 + max ({0; p1 − 2p2 }). Выражение в правой части есть A(p, qp ) для некоторого qp ∈ S; qp = (1, 0) при p1 − 2p2 > 0 и qp = (0, 1) для p1 − 2p2 ≤ 0. Стало быть, 2p2 + max({0; 1 − 3p2 }) = max A(p, q). q∈S

Это число обозначим через V (p). Минимизация данного выражения сводится к минимизации функции f , f (x) = 2x + max({0; 1 − 3x}), на отрезке [0, 1]. При x ∈ [0, 1/3] имеем f (x) = 2x + (1 − 3x) = 1 − x. Для x ∈ [1/3, 1] имеем 2 f (x) = 2x ≥ . 3 Стало быть, у нас V = min V (p) = min max A(p, q) = min f (x) = p∈S

p∈S q∈S

x∈[0,1]

и при этом p∗ = ( 32 , 13 ) доставляет равенство 2 V = V (p∗ ) = ; 3 7

2 3

p∗ есть минимаксная смешанная стратегия. С другой стороны, имеем из представления для A(p, q) A(p, q) = p1 q1 + 2(1 − p1 )q2 = 2q2 + p1 (q1 − 2q2 ) ≥ 2q2 − max({0; 2q2 − q1 }); выражение в правой части реализуется в виде A(pq , q) для следующей смешанной стратегии pq ∈ S: при q1 − 2q2 < 0 имеем pq = (1, 0); если же q1 − 2q2 ≥ 0, то pq = (0, 1). При этом V (q) = min A(p, q) = 2q2 − max({0; 2q2 − q1 }) = 2q2 − max({0; 3q2 − 1}). p∈S

Теперь уже можно ввести функцию g, g(x) = 2x − max({0; 3x − 1}), на отрезке [0, 1], которую следует максимизировать для определения V = max V (q) = max g(x). q∈S

x∈[0,1]

Заметим, что при x ∈ [0, 13 ] g(x) = 2x ≤ 23 , для x ∈ [ 31 , 1] g(x) = 2x − 3x + 1 = 1 − x ≤ 23 . Стало быть V = 23 и при этом q∗ = ( 32 , 13 ) реализует равенство 2 V = V (q∗ ) = . 3 Мы получили важное свойство: наша матричная игра в смешанных стратегиях имеет (и это хорошо известно: см. [1 − 3]) цену V = V = 23 , что, кстати гарантирует и существование седловой точки; эта седловая точка определяется парой (p∗ , q∗ ). В самом деле, имеем цепочку равенств 4 1 1 6 2 + 2 · · = = = V = V. 9 3 3 9 3 Далее, фиксируя p∗ , мы получаем следующую зависимость от q ∈ S A(p∗ , q∗ ) = p∗1 q∗1 + 2p∗2 q∗2 =

2 2 A(p∗ , q) = (q1 + q2 ) = . 3 3 Стало быть, изменяя q игрок II не добивается преимуществ в сравнении с q∗ , если только игрок I сохраняет (минимаксную) стратегию p∗ . Напротив, если зафиксировать q∗ , то 2 2 A(p, q∗ ) = (p1 + p2 ) = . 3 3 8

Снова имеем свойство: отступая от p∗ игрок I ничего не выигрывает (хотя и не проигрывает — в рассматриваемой игре), если игрок II придерживается стратегии q∗ . Идея устойчивости реализована здесь в весьма “безразличной”, на первый взгляд форме. Сравним, однако, действие (p∗ , q∗ ) с действием пары (p0 , q0 ), p0 ∈ S, q0 ∈ S, определяемой в виде 1 1 p0 = ( , ), 2 2

1 1 q0 = ( , ). 2 2

Имеем (с одной стороны) равенство A(p0 , q0 ) = 41 + 12 = 34 ; если же теперь (с другой стороны) сравнить A(p0 , q0 ) и A(p0 , q 0 ), где q 0 = (0, 1), то получаем равенство A(p0 , q0 ) =

3 < 1 = A(p0 , q 0 ). 4

Итак, игрок II имеет стимул к одностороннему изменению стратегии q0 . В свою очередь, для стратегии p0 = (1, 0) игрок I имеет неравенство A(p0 , q0 ) =

3 1 < = A(p0 , q0 ). 2 4

Мы видим, что и у игрока I есть стимул к одностороннему изменению смешанной стратегии. Стало быть, пара (p0 , q0 ) не обладает важнейшей чертой седловой точки: эта пара не реализует идею устойчивости. Мы рассмотрели, конечно, только два простейших примера матричной игры. Рассматриваемое далее введение в теорию статистических игр Вальда будет построено в значительной мере на аналогии с матричной игрой. Отличие, с идейной точки зрения, будет связано лишь с тем, что игрок I, выбирающий у нас строку матрицы, будет располагать некоторой информацией о выборе столбца игроком II. Эта информация будет реализована в виде сигнала, который на практике оказывается зашумленным. Мы рассматриваем далее “дискретный” вариант статистической игры, т.е. далеко не самый общий случай. Вместе с тем, это позволяет реализовать вышеупомянутые события, определяемые посредством A и A в “матричном” случае, без привлечения тонких математических методов, связанных, в частности, с топологией и теорией меры.

9

1

Функция среднего риска

Рассмотрим следующую содержательную задачу, связанную с проблемой принятия решений в условиях статистической неопределенности. Пусть S, X и D — три непустых конечных множества, характеризующих пространства состояний, наблюдений и решений соответственно. Выбор s ∈ S характеризуется действиями “природы”, а выбор d ∈ D — действиями статистика как лица, принимающего решение (ЛПР). Последний знает наблюдение x ∈ X, некоторым образом связанное с s; поэтому в простейшем случае выбор ЛПР можно трактовать как функцию из X в D. Мы исходим из предположения о том, что зависимость x от s является статистической. Именно, после реализации s конкретный выбор x ∈ X является экспериментом, вероятностное распределение в котором есть X (qs (x) ≥ 0; x ∈ X), qs (x) = 1. (1.1) x∈X

Иными словами, задана стохастическая матрица Q, характеризующая реализацию наблюдения x в условиях, когда задано s ∈ S. Если d ∈ D — конкретное решение, принятое на основании x, то качество этого решения характеризуется числом Π(s, d) (потери ЛПР, связанные с решением d в условиях реализации состояния s). Итак, дана матрица потерь Π (нам удобно интерпретировать ее как функцию двух переменных) Π : S × D −→ R.

(1.2)

Заметим, что зачастую множества S и D совпадают по смыслу решаемой задачи (проверка гипотез, оценивание), но сейчас нам это предположение не требуется. Поскольку выбор s ∈ S и реализация x ∈ X непредсказуемы, одно только значение Π(s, d) матрицы Π не характеризует качество действий ЛПР. Мы ориентируемся на ситуацию, когда выбор s ∈ S может быть охарактеризован как эксперимент с некоторым распределением вероятностей X µ(s) = 1. µ = (µ(s) ≥ 0, s ∈ S), (1.3) s∈S

Если δ, δ : X −→ D, — решающее правило статистика (т.е. ЛПР), то вместо конкретного исхода в реализации значений матрицы (1.2) можно ориентироваться на математическое ожидание XX R(δ, µ) = Π(s, δ(x))qs (x)µ(s); (1.4) s∈S x∈X

10

Можно было бы принять (1.4) в качестве значения платежной функции в антагонистической игре [1] – [3] двух лиц: “природы” и ЛПР. К сожалению, класс решающих правил упомянутого типа зачастую недостаточен для удовлетворительного решения возникающей игры. Поэтому, следуя Вальду [4], мы вводим расширение этого класса. Именно, пусть взамен множества 4 всех отображений из X в D допустимо использовать мно˜ всех отображений из X в множество всевозможных вероятжество 4 ˜ — множество всех рандомизированных ностных распределений на D (4 ˜ также можно рассматривать решающих правил; см. [4, 5]). Элементы 4 как стохастические матрицы; средний риск (1.4) заменяется при этом величиной XXX Π(s, d)ηx (d)qs (x)µ(s), R(η, µ) = (1.5) s∈S x∈X d∈D

˜ Можно рассматривать (1.5) как платежную функгде η = (ηx )x∈X ∈ 4. цию, причем в игре, возникающей таким образом, непременно существует решение в смысле седловой точки; см. [4, 5]. Мы будем исследовать решение в упомянутом смысле. Отметим, что математическая постановка такого рода достаточно традиционна [4] – [7]. Нас будет в большей степени интересовать реализация минимаксных стратегий ЛПР; с целью построения соответствующего алгоритма мы и ввели “квантованный” вариант задачи, в котором множества S, X и D конечны.

2

Байесовы решения.

Если Γ — непустое конечное множество, то через P0 (Γ) обозначаем множество всех функций ν : Γ −→ [0, 1] (2.1) со свойством: сумма всех ν(γ), γ ∈ Γ, есть 1. Итак, P0 (Γ) есть множество всех элементарных вероятностей (ЭВ) на Γ. Каждую функцию (2.1) можно, конечно, рассматривать как неотрицательный вектор в конечномерном пространстве. Для нас существенны множества P0 (S), P0 (X) и P0 (D). Отображение Q : S −→ P0 (X) фиксируем, получая фактически стохастическую матрицу наблюдений; при этом 4 qs (x) = Q(s)(x), s ∈ S, x ∈ X, 11

˜ как множев содержательных рассуждениях раздела 1. Определяем 4 ˜ есть фактически стоство всех отображений из X в P0 (D); элементы 4 хастические матрицы решений. Уточняя (1.5), вводим ˜ × P0 (S) −→ R R: 4 ˜ ∀µ ∈ P0 (S) по следующему естественному правилу: ∀η ∈ 4 XXX 4 R(η, µ) = Π(s, d)η(x)(d) Q(s)(x)µ(s).

(2.2)

(2.3)

s∈S x∈X d∈D

Средний риск (2.3) можно связать со следующей простейшей динамической моделью цепи Маркова. Именно, рассмотрим три момента времени t0 < t1 < t2 . В момент t0 производится случайное испытание, определяемое (начальным) распределением µ. В результате испытания реализуется состояние u(0) = s ∈ S. Используя Q в качестве переходной вероятности, осуществляем в момент t1 случайное испытание, определяемое распределением Q(s) = Q(u(0)) = qu(0) . В результате реализуется u(1) = x ∈ X. ˜ как новую переходную вероятность, мы в момент Далее, используя η ∈ 4 t2 осуществляем новое случайное испытание, определяемое распределением η(x) = η(u(1)). При этом реализуется u(2) = d ∈ D. Стало быть u = (u(0), u(1), u(2)) ∈ S × X × D можно рассматривать как реализацию простейшего марковского процесса с дискретным временем. По существу же такое представление определяет в достаточно простой форме решение задачи о байесовом риске: µ ∈ P0 (S) задано и требуется решить задачу ˜ R(η, µ) −→ min, η ∈ 4.

(2.4)

В целях полноты изложения рассмотрим решение задачи (2.4), фиксируя ζ ∈ P0 (S) (универсально по отношению к µ ∈ P0 (S)). Если µ ∈ P0 (S), то введем µ ⊗ Q ∈ P0 (S × X) (2.5) по правилу: при s ∈ S и x ∈ X полагаем 4

(µ ⊗ Q) (s, x) = µ(s) Q(s)(x). Если κ ∈ P0 (S × X), то (X − mg)[κ] ∈ P0 (X) определяется условием: при x∈X X 4 (X − mg)[κ](x) = κ(s, x). (2.6) s∈S

12

В частности, можно комбинировать (2.5), (2.6), получая при µ ∈ P0 (S) в виде 4 q[µ] = (X − mg)[µ ⊗ Q] ∈ P0 (X) безусловную элементарную вероятность на X: при x ∈ X X q[µ](x) = µ(s) Q(s)(x).

(2.7)

s∈S

Введем теперь апостериорную ЭВ на S, используя для несущественных преобразований зафиксированное ранее ζ. Однако, предварительно удобно ввести специальное понятие спектра ЭВ: если H — непустое конечное множество и γ ∈ P0 (H), то 4

(Sp)[γ] = {h ∈ H| γ(h) 6= 0}.

(2.8)

Нам, в частности, понадобятся (в том числе и в связи с (2.7)) варианты, отвечающие случаям H = X и H = S. Если µ ∈ P0 (S), то функцию p[µ] : X −→ P0 (S)

(2.9)

определяем следующим условием: 

4

∀x ∈ (Sp)[q[µ]] : p[µ](x) =

 (µ ⊗ Q)(s, x)  q[µ](x)

 s∈S

&

(2.10)

  4 & ∀x ∈ X \ (Sp)[q[µ]] : p[µ](x) = ζ . Заметим, что в силу (2.6), (2.7) имеем ∀µ ∈ P0 (S) ∀x ∈ X X q[µ](x) = (µ ⊗ Q)(s, x). s∈S

Тогда, в частности, получаем при µ ∈ P0 (S), s ∈ S и x ∈ X неравенство (µ ⊗ Q)(s, x) ≤ q[µ](x). Это означает в силу (2.8), что ∀µ ∈ P0 (S) ∀x ∈ X \ (Sp)[q[µ]] ∀s ∈ S (µ ⊗ Q)(s, x) = 0. 13

(2.11)

Из (2.8), (2.11) легко следует, что ∀µ ∈ P0 (S) ∀x ∈ X \ (Sp)[q[µ]] ∀s ∈ S (µ ⊗ Q)(s, x) = p[µ](x)(s)q[µ](x) = 0.

(2.12)

Если же µ ∈ P0 (S), x ∈ (Sp)[q[µ]] и s ∈ S, то в силу (2.10) (µ ⊗ Q)(s, x) = p[µ](x)(s)q[µ](x).

(2.13)

С учетом (2.12), (2.13) получаем теперь ∀µ ∈ P0 (S) ∀x ∈ X ∀s ∈ S (µ ⊗ Q)(s, x) = µ(s)Q(s)(x) = p[µ](x)(s)q[µ](x). ˜ ∀µ ∈ P0 (S) Из (2.3) и (2.14) следует, что ∀η ∈ 4 X  X X R(η, µ) = q[µ](x) η(x)(d) Π(s, d)p[µ](x)(s) . x∈X

(2.14)

(2.15)

s∈S

d∈D

Если µ ∈ P0 (S) и x ∈ X, то введем в рассмотрение непустое множество X 4 Dµ0 [x] = {d0 ∈ D | Π(s, d0 )p[µ](x)(s) ≤ (2.16) s∈S

≤

X s∈S

Декартово произведение

Π(s, d)p[µ](x)(s) ∀d ∈ D}. Q x∈X

Dµ0 [x] всех множеств (2.16) (при переборе

всех x ∈ X) очевидным образом непусто. Полезно, однако, ввести некоторое расширение этого множества; при µ ∈ P0 (S) введем 4 ˜ 0 [µ] = ˜ | (Sp)[η(x)] ⊂ D0 [x] ∀x ∈ X}. 4 {η ∈ 4 µ

(2.17)

Смысл введения (2.17) поясняется следующим простым рассуждением, вытекающим из (2.8): если H — непустое конечное множество, γ ∈ P0 (H) и f есть отображение из H в вещественную прямую R, т.е. вещественнозначная в/з функция на H, то X X f (h)γ(h) = f (h)γ(h). h∈H

h∈(Sp)[γ]

˜ 0 [µ], то в силу (2.15) – (2.17) Если теперь µ ∈ P0 (S) и η 0 ∈ 4 X X R(η 0 , µ) = q[µ](x) min Π(s, d)p[µ](x)(s). x∈X

d∈D

14

s∈S

(2.18)

Введем теперь в рассмотрение естественное погружение нерандомизиро˜ т.е. погружение 4 в 4. ˜ Если d ∈ D, то ванных решающих правил в 4, Kd ∈ P0 (D) определяется условиями 4 4 ˜ = (Kd (d) = 1) & (Kd (d) 0 ∀d˜ ∈ D \ {d});

(2.19)

(2.19) соответствует использованию символа Кронекера. Если же ϕ ∈ 4, то 4 ˜ δϕ = (Kϕ(x) )x∈X ∈ 4. (2.20) Соотношение (2.20) позволяет ввести традиционное определение среднего риска в классе нерандомизированных стратегий как частный случай (2.3), (2.15): если ϕ ∈ 4 и µ ∈ P0 (S), то 4

R(ϕ, µ) = R(δϕ , µ) =

XX

Π(s, ϕ(x)) Q(s)(x)µ(s) =

(2.21)

s∈S x∈X

=

X

q[µ](x)

x∈X

При µ ∈ P0 (S) мы в виде

Q x∈X

Y

X

Π(s, ϕ(x))p[µ](x)(s).

s∈S

Dµ0 [x] имеем непустое подмножество 4, т.е. Y

Dµ0 [x] 6= ∅ :

x∈X

Dµ0 [x] ⊂ 4;

(2.22)

x∈X

более того, в силу (2.21) имеем погружение множества в левой части ˜ 0 [µ]. Приведем соответствующее хорошо известное рассужде(2.22) в 4 ние на этот счет. Итак, пусть µ ∈ P0 (S) и Y ϕ∈ Dµ0 [x]. x∈X

Тогда, в частности, (см. (2.22)), ϕ ∈ 4, значения оператора ϕ — суть элементы множеств (2.16), причем в силу (2.8) и (2.19), ∀x ∈ X (Sp)[δϕ (x)] = (Sp)[Kϕ(x) ] = {ϕ(x)}. Но, по выбору ϕ, имеем, что ϕ(x) ∈ Dµ0 [x] ∀x ∈ X. 15

(2.23)

Это означает, что (см. (2.16)) ∀x ∈ X X X Π(s, ϕ(x))p[µ](x)(s) = min Π(s, d)p[µ](x)(s). d∈D

s∈S

(2.24)

s∈S

Вернемся к (2.15) при η = δϕ . Тогда X X R(δϕ , µ) = q[µ](x) Π(s, ϕ(x))p[µ](x)(s). x∈X

s∈S

Поэтому с учетом (2.16), (2.21), (2.23) и (2.24) мы получаем равенство X X R(ϕ, µ) = R(δϕ , µ) = q[µ](x) min Π(s, d)p[µ](x)(s), d∈D

x∈X

s∈S

˜ в силу (2.20). Мы имеем, конечно, с учетом (2.15) и произгде δϕ ∈ 4 Q 0 вольности выбора µ и ϕ, свойство: ∀µ ∈ P0 (S) ∀ϕ ∈ Dµ [x] x∈X

X x∈X

q[µ](x) min d∈D

X

Π(s, d)p[µ](x)(s) ≤ inf R(η, µ) ≤ R(δϕ , µ) = ˜ η∈4

s∈S

= R(ϕ, µ) =

X

q[µ](x) min d∈D

x∈X

X

(2.25)

Π(s, d)p[µ](x)(s);

s∈S

(2.25) обращается, стало быть, в систему равенств и, с учетом (2.21), ∀µ ∈ P0 (S) X X inf R(η, µ) = inf R(ϕ, µ) = q[µ](x) min Π(s, d)p[µ](x)(s). (2.26) ˜ η∈4

ϕ∈4

d∈D

x∈X

s∈S

Q

Из (2.16) мы имеем, конечно, ∀µ ∈ P0 (S) ∀ϕ ∈

x∈X

Dµ0 [x]

˜ 0 [µ]. δϕ ∈ 4 ˜ 0 [µ] 6= ∅; в силу (2.18) ∀µ ∈ P0 (S) ∀η 0 ∈ 4 ˜ 0 [µ] Стало быть, 4 R(η 0 , µ) = inf R(η, µ). ˜ η∈4

(2.27)

˜ 0 [µ] состоит только из решеИтак, при µ ∈ P0 (S) непустое множество 4 ний задачи (2.4) и, в правой части (2.27), будем заменять inf на min. С 16

учетом Q 0 (2.25) и (2.26) имеем, что, при µ ∈ P0 (S), непустое множество Dµ [x] состоит только из решений задачи x∈X

R(ϕ, µ) −→ min,

ϕ ∈ 4;

(2.28)

в соответствующей (задаче (2.28)) части (2.26) будем заменять inf на min, т.е. ∀µ ∈ P0 (S) X X min R(η, µ) = min R(ϕ, µ) = q[µ](x) min Π(s, d)p[µ](x)(s). (2.29) ˜ η∈4

ϕ∈4

d∈D

x∈X

s∈S

В (2.29) мы имеем минимум среднего риска, т.е. глобальный экстремум задачи минимизации среднего риска в условиях известного априорного распределения. Эту величину называем байесовым риском.

3

Статистическая игра

Рассмотрим теперь постановку статистической игры, в которой участвует лицо, принимающее решение, или кратко ЛПР, именуемое далее игроком I, а также Природа, именуемая далее игроком II. Мы называем также ЛПР статистиком; в его распоряжении находятся всевозможные ˜ Игрок II распоряжается выбором µ ∈ P0 (S). Средний стратегии η ∈ 4. риск R(η, µ) есть плата в антагонистической игре, т.е. “деньги”, которые игрок I “передает” игроку II (Природе). Из (2.3) следует, что R удовлетворяет всем условиям теоремы фон Неймана (см. [1] – [3]). Дело в том, что R можно рассматривать в виде сужения билинейной непрерывной функции на декартово произведение выпуклых компактов (соответствующие топологии определяются при этом традиционно как топологии покоординатной сходимости для используемых в построении конечномерных пространств). Отметим здесь только определения выпуклых комбинаций в смысле “объемлющих” конечномерных пространств. ˜ η2 ∈ 4 ˜ и α ∈ [0, 1], то Если η1 ∈ 4, ˜ αη1 + (1 − α)η2 ∈ 4 есть отображение из X в P0 (D), для которого при каждом x ∈ X (αη1 + (1 − α)η2 )(x) 17

есть отображение d 7−→ αη1 (x)(d) + (1 − α)η2 (x)(d) : D −→ [0, 1]; если же µ1 ∈ P0 (S), µ2 ∈ P0 (S) и β ∈ [0, 1], то βµ1 + (1 − β)µ2 ∈ P0 (S) определяется (традиционно) в виде s 7−→ βµ1 (s) + (1 − β)µ2 (s) : S −→ [0, 1]. Из теоремы фон Неймана следует, что 4

V = min max R(η, µ) = max min R(η, µ). ˜ µ∈P0 (S) η∈4

˜ µ∈P0 (S) η∈4

(3.1)

Заметим, что (3.1) следует и из результатов Вальда (см. [4]); однако, в данном случае (и в настоящее время) проще извлекать это равенство из общих теорем о минимаксе [1] – [3], [5] – [7]. Напомним хорошо известные [1] – [7] следствия (3.1), для чего введем в рассмотрение следующие две функции гарантии: ˜ −→ R, v∗ : 4

v∗ : P0 (S) −→ R.

(3.2)

Именно, мы полагаем, что 4

4

(v ∗ = ( max R(η, µ))η∈4˜ ) & (v∗ = (min R(η, µ))µ∈P0 (S) ), ˜ η∈4

µ∈P0 (S)

(3.3)

используя индексную форму записи функций (см. например, [8]). Отметим, что каждая из функций (3.2), (3.3) непрерывна в смысле соответствующих топологий покоординатной сходимости. Рассматриваем следующую пару экстремальных задач: v ∗ (η) −→ min, v∗ (µ) −→ max,

˜ η ∈ 4;

(3.4)

µ ∈ P0 (S).

(3.5)

Разумеется (3.4) — задача игрока I, а (3.5) — задача игрока II. Из (3.1), (3.3) мы получаем, что V = min v ∗ (η) = max v∗ (µ); ˜ η∈4

µ∈P0 (S)

(3.6)

задачи (3.4) и (3.5) находятся, стало быть, в двойственности, формируемой в (3.6). Этот факт является следствием теоремы фон Неймана. 18

Сейчас, однако, мы приведем ряд важных следствий, связанных с понятием седловой точки, которое определяет оптимальное поведение в игре на минимакс – максимин среднего риска. Эта игра имеет смысл своеобразной борьбы ↓η R(η, µ) ↑µ (3.7) статистика и природы. Введем в рассмотрение множества 4 ˜ | v ∗ (η 0 ) = V }, ˜0 = {η 0 ∈ 4 4 I 4

P0II (S) = {µ0 ∈ P0 (S) | v∗ (µ0 ) = V }.

(3.8) (3.9)

Каждое из множеств (3.8), (3.9) непусто. При этом (3.8) определяет множество всех решений задачи (3.4), а (3.9) — множество всех решений задачи (3.5). Решения в смысле (3.8), (3.9) соответствуют “индивидуальной” оптимальности (в смысле гарантий) для игроков I и II соответственно. Однако, соотношения (3.1), (3.6) придают этим решениям важное новое качество, связанное с фундаментальным понятием седловой точки [1] – [3] рассматриваемой стохастической игры [4, 5]. Итак, вернемся к (3.7), но будем рассматривать это явление с позиции двух игроков “сразу”, полагая в основу нашего нового понятия принцип устойчивости. Напомним определение седловой точки (см. [1] – [3]). ˜ и µ∗ ∈ P0 (S), то пара (η ∗ , µ∗ ) ∈ 4 ˜ × P0 (S) называется Если η ∗ ∈ 4 ˜ ∀µ ∈ P0 (S) седловой точкой, если ∀η ∈ 4 R(η ∗ , µ) ≤ R(η ∗ , µ∗ ) ≤ R(η, µ∗ ).

(3.10)

Через S обозначаем множество всех седловых точек нашей стохастической игры. Итак, у нас S есть множество всех пар ˜ µ∗ ∈ P0 (S), (η ∗ , µ∗ ), η ∗ ∈ 4, ˜ µ ∈ P0 (S). Расобладающих свойством (3.10) при произвольных η ∈ 4, смотрим связь множеств (3.8) – (3.10). Заметим, что на самом деле эта связь возникает в общем случае антагонистических игр, обладающих седловой точкой (см. [1] – [3], [7]), но мы ограничиваемся случаем рассматриваемой здесь игры (3.7). Отметим хорошо известное в общей теории игр ˜ 0 × P0 (S) и при Предложение 3.1 Имеет место равенство S = 4 I II 0 0 0 0 ˜ ∀µ ∈ P (S) этом ∀η ∈ 4 I II R(η 0 , µ0 ) = V. 19

(3.11)

˜ 0 × P0 (S) есть множество всех упоПримечание. Напомним, что 4 I II рядоченных пар ˜ 0 , µ0 ∈ P0 (S). (η0 , µ0 ), η0 ∈ 4 I II Стало быть, утверждается, что седловыми точками рассматриваемой статистической игры являются всевозможные пары оптимальных стратегий из множеств (3.8), (3.9) соответственно. ˜ 0 × P0 . Тогда можно Доказательство предложения. Пусть u ∈ 4 II I ˜ 0 и µ0 ∈ P0 (S), для которых u = (η 0 , µ0 ). Из (3.8), (3.9) указать η 0 ∈ 4 I II имеем, что v ∗ (η 0 ) = v∗ (µ0 ) = V. (3.12) ˜ ∀µ ∈ P0 (S) Из (3.3), (3.12) вытекает, что справедливо ∀η ∈ 4 R(η 0 , µ) ≤ V ≤ R(η, µ0 ).

(3.13)

Тогда, в частности, имеем при η = η 0 и µ = µ0 равенство V = R(η 0 , µ0 ).

(3.14)

˜ ∀µ ∈ P0 (S) Из (3.13), (3.14) следует ∀η ∈ 4 R(η 0 , µ) ≤ R(η 0 , µ0 ) ≤ R(η, µ0 ).

(3.15)

˜0 Мы установили, что (см. (3.10), (3.14), (3.15)) при всяком выборе η0 ∈ 4 I и µ0 ∈ P0II (S) имеют место следующие два свойства: 1) R(η0 , µ0 ) = V ; 2) (η0 , µ0 ) ∈ S. Это означает, в частности, что справедливо (3.11) и, кроме того, ˜ 0 × P0 (S) ⊂ S. 4 (3.16) I II ˜ и Выберем произвольно u∗ ∈ S. Тогда можно указать (см. (3.10)) η∗ ∈ 4 ˜ µ∗ ∈ P0 (S), для которых u∗ = (η∗ , µ∗ ) и ∀η ∈ 4 ∀µ ∈ P0 (S) R(η∗ , µ) ≤ R(η∗ , µ∗ ) ≤ R(η, µ∗ ). Из (3.3), (3.6), (3.17) имеем, в частности, что V ≤ v ∗ (η∗ ) ≤ R(η∗ , µ∗ ) ≤ v∗ (µ∗ ) ≤ V. Это означает, что все неравенства обращаются в равенства, т.е. v ∗ (η∗ ) = R(η∗ , µ∗ ) = v∗ (µ∗ ) = V. 20

(3.17)

˜ 0 и µ∗ ∈ P0 (S), а тогда Из (3.8), (3.9) следует, что η∗ ∈ 4 I II ˜ 0 × P0 (S), u∗ ∈ 4 I II чем и завершается обоснование вложения ˜ 0 × P0 (S). S⊂4 I II ˜ 0 × P0 (S), ч.т.д.  С учетом (3.16) получаем требуемое равенство S = 4 I II Из предложения 3.1 видно, что игроки I, II могут разыгрывать седловую точку, не имея каждый информации о выборе стратегии партнером: ˜ 0, игроку I (статистику) следует выбирать произвольный элемент η 0 ∈ 4 I а игроку II (Природе) — любой элемент µ0 ∈ P0II (S); равенство (3.11) обеспечивает при этом одно и то же (оптимальное в игровом смысле) значение потерь, равное V , т.е. цене игры. Итак, игрокам следует “просто” решать (каждому) свои задачи (3.4), (3.5) соответственно. ˜ 0 и µ∗ ∈ P0 (S), то Отметим следующий важный момент: если η ∗ ∈ 4 I II (η ∗ , µ∗ ) ∈ S, а потому выполнено (3.10), что, в частности, означает: R(η ∗ , µ∗ ) = min R(η, µ∗ ); ˜ η∈4

(3.18)

стало быть, η ∗ есть решение задачи (2.4) в условиях, когда (в (2.4)) µ = µ∗ . Иными словами, минимаксная стратегия статистика (рандомизированное решающее правило η ∗ в (3.18)) есть байесово решение в условиях, когда Природа использует наименее благоприятное априорное распределение. В (3.18) мы имеем необходимое условие оптимальности для задачи (3.4), но, вообще говоря, не достаточное (возможен случай, когда при µ = µ∗ ∈ P0II (S) решение задачи (2.4) не будет решением задачи (3.4)). Здесь полезно сделать замечание о проблеме рандомизации решающих правил статистика. Мы знаем уже, что среди байесовых решающих правил (см. задачу (2.4)) всегда имеется нерандомизированное: (2.29) говорит об эквивалентности по результату двух упомянутых решающих правил, если только известно априорное распределение µ ∈ P0 (S); последнее может, в частности, быть элементом множества (3.9), т.е. наименее благоприятным распределением. С другой стороны, из (3.18) видно, что минимаксное решающее правило — байесово для наименее благоприятного априорного распределения. Хотелось бы, чтобы это минимаксное правило оказалось нерандомизированным; некоторый намек на это содержится в (2.29). Тем не менее, это, вообще говоря, не так, ибо 21

(3.18) является всего лишь необходимым условием оптимальности. Грубо говоря, минимаксное решающее правило может оказаться “не тем” байесовым правилом, для которого имеет место нерандомизированность.

4

Правило выравнивания

В этом разделе мы остановимся на одном свойстве (см., например, [5]), характерном для минимаксных решающих правил статистика. Это свойство связано с поведением т.н. условных рисков. Последние определяют˜ то ся следующим образом: если s ∈ S и η ∈ 4, XX XX 4 Π(s, d)η(x)(d)qs (x) = Π(s, d)η(x)(d)Q(s)(x). (4.1) rs (η) = x∈X d∈D

x∈X d∈D

Содержательный смысл величины (4.1) состоит в следующем: в условиях, когда ЛПР (игрок I) выбрал решающее правило η, а Природа использует конкретный выбор s ∈ S мы можем определить средние потери; они и определяют величину (4.1). Из (1.5) и (4.1) имеем ∀µ ∈ P0 (S) X R(η, µ) = rs (η)µ(s). (4.2) s∈S

Здесь (в (4.2)) осуществляется усреднение условных рисков (4.1). Полезно напомнить (см. (2.8)) следующее понятие спектра µ ∈ P0 (S): 4

(SP)[µ] = (Sp)[µ] = {s ∈ S | µ(s) 6= 0};

(4.3)

множество (4.3) определяет, для каждой наперед выбранной априорной элементарной вероятности на S, существенную (для определения средних потерь) часть множества S. Справедлива следующая, подобная рассматриваемой в [5], ˜ 0 и µ∗ ∈ P0 (S). Тогда ∀s1 ∈ (SP)[µ∗ ] Теорема 4.1 Пусть η ∗ ∈ 4 I II ∗ ∀s2 ∈ (SP)[µ ] rs1 (η ∗ ) = rs2 (η ∗ ). (4.4) Доказательство. Допустим противное: для некоторых s1 ∈ (SP)[µ∗ ] и s2 ∈ (SP)[µ∗ ] равенство (4.4) нарушено. Тогда можно утверждать, что существуют u ∈ (SP)[µ∗ ] и v ∈ (SP)[µ∗ ], для которых ru (η ∗ ) < rv (η ∗ ) 22

(4.5)

(для s1 и s2 , обеспечивающих нарушение (4.4), в качестве u следует выбрать тот элемент из {s1 ; s2 }, для которого условный риск, отвечающий η ∗ , меньше). Введем µ∗∗ ∈ P0 (S) по следующему правилу 4

(µ∗∗ (s) = µ∗ (s) ∀s ∈ S \ {u; v}) & 4

(4.6)

4

& (µ∗∗ (u) = 0)&(µ∗∗ (v) = µ∗ (u) + µ∗ (v)). Сравним теперь R(η ∗ , µ∗ ) и R(η ∗ , µ∗∗ ), используя (4.2). Тогда с учетом (4.6) R(η ∗ , µ∗∗ ) = R(η ∗ , µ∗ ) + ru (η ∗ )(µ∗∗ (u) − µ∗ (u)) + rv (η ∗ )(µ∗∗ (v) − µ∗ (v)) = = R(η ∗ , µ∗ ) + rv (η ∗ )µ∗ (u) − ru (η ∗ )µ∗ (u) =

(4.7)

= R(η ∗ , µ∗ ) + (rv (η ∗ ) − ru (η ∗ ))µ∗ (u) > R(η ∗ , µ∗ ), поскольку µ∗ (u) > 0 (см. (4.3)) и выполнено (4.5). С другой стороны, в силу предложения 3.1 (η ∗ , µ∗ ) ∈ S. Тогда, как видно из (3.10) R(η ∗ , µ∗ ) = max R(η ∗ , µ). µ∈P0 (S)

(4.8)

Соотношения (4.7), (4.8) взаимно противоречивы. Полученное противоречие доказывает свойство выравнивания условных рисков (см. (4.4)). Следствие 4.1 Пусть ∃µ0 ∈ P0II (S) : (SP)[µ0 ] 6= {s} ∀s ∈ S. Тогда ˜ 0 ∃s1 ∈ S ∃s2 ∈ S \ {s1 } : rs (η 0 ) = rs (η 0 ). ∀η 0 ∈ 4 1 2 I Доказательство. Выберем µ0 ∈ P0II (S) со следующим свойством: (SP)[µ0 ] не является синглетоном (одноэлементным множеством). Тогда можно указать s1 ∈ (SP)[µ0 ] и s2 ∈ (SP)[µ0 ], для которых s1 6= s2 ; по определению ЭВ (см. (1.1)) спектр µ0 — непустое множество, см. (4.3). ˜ 0 . Тогда можно использовать теорему 4.1 при следующей Пусть η 0 ∈ 4 I ее конкретизации: η ∗ = η 0 и µ∗ = µ0 . Требуемое свойство η 0 вытекает из (4.4). 

23

5

Проблема обнаружения заданного состояния

В этом разделе рассмотрим частный случай общей постановки, когда S = D и, кроме того, множество S (а, стало быть, и D) двухэлементно, т.е. является неупорядоченной парой [9] несовпадающих объектов. Не ограничивая общности, полагаем, что S = D = {0; 1},

(5.1)

т.е. элементами S являются числа 0, 1 и только они. Кроме того, для упрощения последующих рассуждений допустим, что какие-либо штрафы за правильные решения отсутствуют, а неверные решения штрафуются неотрицательными значениями потерь. Это означает (при условии (5.1)), что Π(0, 0) = Π(1, 1) = 0. (5.2) Разумеется, (5.1), (5.2) определяют более простую задачу, при решении которой мы сможем получить больше дополнительной информации. В ˜ ∀µ ∈ P0 (S) этом частном случае, как видно из (1.5), ∀η ∈ 4 X R(η, µ) = (Π(0, 1)η(x)(1)q0 (x)µ(0) + Π(1, 0)η(x)(0)q1 (x)µ(1)). (5.3) x∈X

Наряду с (5.3), упростим с учетом (5.2) выражение для байесова риска: ∀µ ∈ P0 (S) min R(η, µ) = min R(ϕ, µ) = (5.4) =

X

˜ η∈4

ϕ∈4

q[µ](x) inf({Π(1, 0)p[µ](x)(1); Π(0, 1)p[µ](x)(0)}).

x∈X

Итак, в (5.4) нам надлежит, для целей вычисления байесова риска, при каждом x ∈ X выбирать среди чисел Π(1, 0)p[µ](x)(1) и Π(0, 1)p[µ](x)(0) наименьшее, после чего следует осуществить усреднение по x при использовании ЭВ q[µ]. Вернемся к (2.16). Если µ ∈ P0 (S) и x ∈ X, то: 1) Dµ0 [x] = {0}, если выполнено неравенство Π(1, 0)p[µ](x)(1) < Π(0, 1)p[µ](x)(0); 24

(5.5)

2) Dµ0 [x] = {1}, если выполнено неравенство Π(0, 1)p[µ](x)(0) < Π(1, 0)p[µ](x)(1);

(5.6)

3) Dµ0 [x] = {0; 1} = D, если имеет место равенство Π(0, 1)p[µ](x)(0) = Π(1, 0)p[µ](x)(1).

(5.7)

Из 1) – 3) имеем очень простое правило построения байесова решения в нерандомизированном или в рандомизированном вариантах. Рассмотрим сначала нерандомизированную версию (напомним, что байесовы решения мы определяем в условиях известного априорного распределения µ ∈ P0 (S)). В (2.23) указан рецепт построения нерандомизированного байесова решающего правила ϕ ∈ 4. В нашем конкретном случае (5.1), (5.2) это означает следующее. Именно, ϕ ∈ 4 следует для реализации (2.23) определить так: при условии (5.5) следует полагать ϕ(x) = 0, в случае (5.6) следует полагать ϕ(x) = 1, при условии (5.7) (ϕ(x) = 0) ∨ (ϕ(x) = 1)

(5.8)

(конкретный выбор 0 или 1 в (5.8) не важен, если верно (5.7)); разумеется, здесь x ∈ X. Обратимся теперь к (2.17) с тем, чтобы извлечь рандомизированную, вообще говоря, версию байесова правила. Из 1) – 3) вытекает, что при ˜ 0 [µ], где µ ∈ P0 (S) задана и известна ЛПР, имеет место выборе η0 ∈ 4 полная определенность выбора решений в случаях 1) и 2): для x ∈ X при выполнении (5.5) η0 (x) = K0 , (5.9) если же выполняется (5.6), то имеем η0 (x) = K1 ;

(5.10)

в (5.9), (5.10) имеем фактически повторение логики нерандомизированного решения для случая Π(0, 1)p[µ](x)(0) 6= Π(1, 0)p[µ](x)(1).

(5.11)

Если же x ∈ X таково, что (5.11) нарушено, т.е. верно (5.7), то любая ЭВ на D = {0; 1} может использоваться в качестве η0 (x), т.е. при всяком выборе λ ∈ P0 (D) можно полагать (в условиях (5.7)) η0 (x) = λ. 25

(5.12)

Итак, (5.9), (5.10), (5.12) определяют рандомизированное байесово правило; при этом конкретная реализация (5.12) несущественна. Обратимся теперь к конкретизации минимаксного решающего правила, используя то обстоятельство, что оно должно быть байесовым в условиях, когда Природа использует наименее благоприятное априорное распределение. Тогда, как легко видеть, наше последнее рассуждение (см. обсуждение (5.9) – (5.12)) доставляет следующий вывод (см. (3.18)). ˜ 0 , то для характеризации η ∗ (x) при x ∈ X следует выЕсли η ∗ ∈ 4 I брать и зафиксировать µ∗ ∈ P0II (S). Затем для построения Dµ0 ∗ [x], x ∈ X, следует использовать в (5.5) – (5.7) замену µ −→ µ∗ . В результате снова, при x ∈ X, получаем три случая: 1) Dµ0 ∗ [x] = {0}, если Π(1, 0)p[µ∗ ](x)(1) < Π(0, 1)p[µ∗ ](x)(0); 2) Dµ0 ∗ [x] = {1}, если Π(0, 1)p[µ∗ ](x)(0) < Π(1, 0)p[µ∗ ](x)(1); 3) Dµ0 ∗ [x] = {0; 1}, если Π(0, 1)p[µ∗ ](x)(0) = Π(1, 0)p[µ∗ ](x)(1). Теперь, в принципе, можно использовать правило, подобное (2.17). Следует только сделать одну оговорку: действовать в духе правила, определяющего (2.17), существенно при наблюдениях x ∈ X, для которых q[µ∗ ](x) 6= 0 (напомним в этой связи (2.7)). Если принять, что Q(s)(x) 6= 0 ∀s ∈ S ∀x ∈ X,

(5.13)

то, поскольку, µ∗ ∈ P0 (S), непременно q[µ∗ ](x) > 0 ∀x ∈ X.

(5.14)

Ограничимся в дальнейшем рассмотрении случаем (5.13), который имеет место во многих практических задачах. Тогда (т.е. при условии (5.13), которое далее предполагается выполненным) оказывается, что при µ = µ∗ каждое решение задачи (2.4) в самом общем ее случае обязано быть элементом (2.17). В целях полноты изложения мы проверим это для упомянутого общего случая задачи (2.4). 26

Итак, пусть в условиях раздела 2, при фиксации µ∗ ∈ P0 (S) выбрано ˜ для которого произвольно η0 ∈ 4, R(η0 , µ∗ ) = inf R(η, µ∗ ); ˜ η∈4

(5.15)

заметим, что в правой части (5.15) на самом деле достигается минимум. Покажем, что ˜ 0 [µ∗ ]. η0 ∈ 4 (5.16) В самом деле, допустим противное: ˜ 0 [µ∗ ]. η0 ∈ /4

(5.17)

Это означает в силу (2.17), что ∃ x ∈ X : (Sp)[η0 (x)] \ Dµ0 ∗ [x] 6= ∅.

(5.18)

Пусть (см. (5.18)) теперь x∗ ∈ X как раз таково, что (Sp)[η0 (x∗ )] \ Dµ0 ∗ [x∗ ] 6= ∅. Выберем произвольную точку d∗ ∈ (Sp)[η0 (x∗ )] \ Dµ0 ∗ [x∗ ]. В силу (2.8) имеем для η0 (x∗ ) ∈ P0 (D) свойство η0 (x∗ )(d∗ ) > 0.

(5.19)

Заметим и следствие (5.14): у нас q[µ∗ ](x∗ ) > 0.

(5.20)

Из (2.15) вытекает, что ∗

R(η0 , µ ) =

X

X  X ∗ q[µ ](x) η0 (x)(d) Π(s, d)p[µ ](x)(s) . ∗

x∈X

В составе суммы (5.21) присутствует, в частности, слагаемое X  X q[µ∗ ](x∗ ) η0 (x∗ )(d) Π(s, d)p[µ∗ ](x∗ )(s) . d∈D

(5.21)

s∈S

d∈D

s∈S

27

(5.22)

Нас будет интересовать второй сомножитель (5.22). Заметим, что, в силу непустоты множеств вида (2.16), у нас D \ {d∗ } 6= ∅

(5.23)

(по выбору d∗ ). С учетом (5.23) имеем для выражения (5.22) представление X  X q[µ∗ ](x∗ ) η0 (x∗ )(d) Π(s, d)p[µ∗ ](x∗ )(s) = (5.24) s∈S

d∈D

h X = q[µ∗ ](x∗ ) (η0 (x∗ )(d∗ ) Π(s, d∗ )p[µ∗ ](x∗ )(s))+ s∈S

+

X

η0 (x∗ )(d)

X

i Π(s, d)p[µ∗ ](x∗ )(s) .

s∈S

d∈D\{d∗ }

Напомним, что каждое множество (2.16) непусто. Стало быть, у нас Dµ0 ∗ [x∗ ] 6= ∅.

(5.25)

По выбору d∗ имеем с очевидностью свойство Dµ0 ∗ [x∗ ] ⊂ D \ {d∗ }. С учетом (5.25) выберем произвольно d∗ ∈ Dµ0 ∗ [x∗ ],

(5.26)

получая, в частности, d∗ ∈ D \ {d∗ }. Согласно (2.16) и (5.26) имеет место свойство X X Π(s, d∗ )p[µ∗ ](x∗ )(s) = min Π(s, d)p[µ∗ ](x∗ )(s) < (5.27) d∈D

s∈S

<

X

s∈S

Π(s, d∗ )p[µ∗ ](x∗ )(s).

s∈S

˜ С учетом (5.27) изменим η0 до некоторого другого правила η00 ∈ 4. Будем полагать, что 4

η00 (x) = η0 (x) ∀x ∈ X \ {x∗ }, 28

(5.28)

и определим отображение η00 (x∗ ) ∈ P0 (D) по следующему правилу 4

4

(η00 (x∗ )(d) = η0 (x∗ )(d) ∀d ∈ D \ {d∗ ; d∗ })&(η00 (x∗ )(d∗ ) = 0)&

(5.29)

4

&(η00 (x∗ )(d∗ ) = η0 (x∗ )(d∗ ) + η0 (x∗ )(d∗ )). В силу оптимальности η0 (см. (5.15)) имеем неравенство R(η0 , µ∗ ) ≤ R(η00 , µ∗ ).

(5.30)

Покажем, однако, что (5.30) невозможно, ориентируясь на оценку величины (5.22). Однако, предварительно заметим, что X X X η00 (x)(d) Π(s, d)p[µ∗ ](x)(s)). R(η00 , µ∗ ) = q[µ∗ ](x)( (5.31) x∈X

s∈S

d∈D

Из (5.21), (5.28), (5.31) вытекает, что h X  X R(η00 , µ∗ )−R(η0 , µ∗ ) = q[µ∗ ](x∗ ) η00 (x∗ )(d) Π(s, d)p[µ∗ ](x∗ )(s) − s∈S

d∈D

(5.32)

X i X − η0 (x∗ )(d) Π(s, d)p[µ∗ ](x∗ )(s) . s∈S

d∈D

Из (5.29), (5.32) следует, что h X R(η00 , µ∗ ) − R(η0 , µ∗ ) = q[µ∗ ](x∗ ) η00 (x∗ )(d∗ ) Π(s, d∗ )p[µ∗ ](x∗ )(s)+ s∈S

+η00 (x∗ )(d∗ )

X

Π(s, d∗ )p[µ∗ ](x∗ )(s)−

s∈S

−η0 (x∗ )(d∗ )

X

∗

∗

Π(s, d∗ )p[µ ](x∗ )(s) − η0 (x∗ )(d )

s∈S

X s∈S

i Π(s, d )p[µ ](x∗ )(s) = ∗

∗

h X = q[µ∗ ](x∗ ) (η0 (x∗ )(d∗ ) + η0 (x∗ )(d∗ )) Π(s, d∗ )p[µ∗ ](x∗ )(s)− s∈S

29

−η0 (x∗ )(d∗ )

X

∗

∗

Π(s, d∗ )p[µ ](x∗ )(s) − η0 (x∗ )(d )

s∈S

X

i Π(s, d )p[µ ](x∗ )(s) = ∗

∗

s∈S

h X i X = q[µ∗ ](x∗ ) η0 (x∗ )(d∗ ) Π(s, d∗ )p[µ∗ ](x∗ )(s)− Π(s, d∗ )p[µ∗ ](x∗ )(s) . s∈S

s∈S

(5.33)

С учетом (5.19), (5.20), (5.27) и (5.33) получаем неравенство R(η00 , µ∗ ) − R(η0 , µ∗ ) < 0,

(5.34)

т.е. R(η00 , µ∗ ) < R(η0 , µ∗ ), что противоречит (5.30). Полученное, при условии (5.17), противоречие (см. (5.30), (5.34)) показывает, что (5.17) невозможно и, стало быть, верно (5.16), т.е. принцип выбора на основе (2.17) является исчерпывающим в вопросах построения байесовых решений (напомним здесь, однако, о предположении (5.13)). Теперь уже можно вернуться к соотношениям 1) – 3), придерживаясь условия (5.13). Мы видим, что реальная рандомизация в упомянутом частном случае двухальтернативной задачи может возникать только для наблюдений x ∈ X, для которых Π(0, 1)p[µ∗ ](x)(0) = Π(1, 0)p[µ∗ ](x)(1); см. в этой связи (2.17).

Список литературы [1] Дж. фон Нейман, О.Моргенштерн. Теория игр и экономическое поведение. М.: Наука, 1970. [2] Дж. Мак-Кинси. Введение в теорию игр. М.: Физматгиз, 1960. [3] Г.Оуэн. Теория игр. М.: Мир, 1971. [4] А. Вальд. Статистические решающие функции // В сб. Позиционные игры, М.: Наука, 1967. [5] А.А.Боровков. Математическая статистика. Дополнительные главы. М.: Наука, 1984. 30

[6] Д.Блэкуэлл, М.А.Гиршик. Теория игр и статистических решений. М.: ИЛ, 1958. [7] Р.Д.Льюис, Х.Райфа. Игры и решения. М.: ИЛ, 1961. [8] Дж. Варга. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. [9] К.Куратовский, А.Мостовский. Теория множеств. М.: Мир, 1970.

31