«Управление и Оптимизация Производственного Предприятия»
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
М.: Издательство «Экзамен», 2004. 2.1.5. Средние и законы больших чисел Законы больших чисел состоят в том, что эмпирические средние сходятся к теоретическим. В классическом варианте: выборочное среднее арифметическое при определенных условиях сходится по вероятности при росте числа слагаемых к математическому ожиданию. На основе законов больших чисел обычно доказывают состоятельность различных статистических оценок. В целом эта тематика занимает заметное место в теории вероятностей и математической статистике. Однако математический аппарат при этом основан на свойствах сумм случайных величин (векторов, элементов линейных пространств). Следовательно, он не пригоден для изучения вероятностных и статистических проблем, связанных со случайными объектами нечисловой природы. Это такие объекты, как бинарные отношения, нечеткие множества, вообще элементы пространств без векторной структуры. Объекты нечисловой природы все чаще встречаются в прикладных исследованиях. Много конкретных примеров приведено выше в настоящей главе. Поэтому представляется полезным получение законов больших чисел в пространствах нечисловой природы. Необходимо решить следующие задачи. А) Определить понятие эмпирического среднего. Б) Определить понятие теоретического среднего. В) Ввести понятие сходимости эмпирических средних к теоретическому. Г) Доказать при тех или иных комплексах условий сходимость эмпирических средних к теоретическому. Д) Обобщив это доказательство, получить метод обоснования состоятельности различных статистических оценок. Е) Дать применения полученных результатов при решении конкретных задач. Ввиду принципиальной важности рассматриваемых результатов приводим доказательство закона больших чисел, а также результаты компьютерного анализа множества эмпирических средних. Определения средних величин. Пусть X - пространство произвольной природы, x1, x2, x3,...,xn - его элементы. Чтобы ввести эмпирическое среднее для x1, x2, x3,...,xn будем использовать действительнозначную (т.е. с числовыми значениями) функцию f(x,y) двух переменных со значениями в X. В стандартных математических обозначениях: Определение 1. Средней величиной для совокупности x1, x2, x3,...,xn (относительно меры различия f),обозначаемой любым из трех способов: хср = En(f) = En(x1, x2, x3,...,xn; f) , называем решение оптимизационной задачи
Это определение согласуется с классическим: если Х = R1, f(x,y) = (x - y)2, то хср - выборочное среднее арифметическое. Если же Х = R1, f(x,y) = |x - y|, то при n = 2k+1 имеем хср = x(k+1), при n= 2k эмпирическое среднее является отрезком [x(k), x(k+1)]. Здесь через x(i) обозначен i-ый член вариационного ряда, построенного по x1, x2,x3,...,xn, т.е. i-я порядковая статистика. Таким образом, при Х = R1, f(x,y) = |x - y| решение задачи (1) дает естественное определение выборочной медианы. Правда, несколько отличающееся от определения, предлагаемого в курсах "Общей теории статистики", в котором при n = 2k медианой называют полусумму двух центральных членов вариационного ряда (x(k) + x(k+1))/2. Иногда x(k) называют левой медианой, а х(k+1) - правой медианой [7]. Решением задачи (1) является множество En(f), которое может быть пустым, состоять из одного или многих элементов. Выше приведен пример, когда решением является отрезок. Если Х = R1\{х0}, f(x,y) = (x - y)2 , а среднее арифметическое выборки равно х0, то En(f) пусто. При моделировании реальных ситуаций часто можно принять, что Х состоит из конечного числа элементов. Тогда множество En(f) непусто - минимум на конечном множестве всегда достигается. Понятия случайного элемента Определение 2. Теоретическим средним E(x,f) (другими словами, математическим ожиданием) случайного элемента
Это определение, как и для эмпирических средних, согласуется с классическим. Если Х = R1, f(x,y) = (x - y)2, то Е(x,f) = М(x(ω)) - обычное математическое ожидание. При этом М Теоретическое среднее E(x, f) можно определить лишь тогда, когда Существование средних величин. Под существованием средних величин будем понимать непустоту множеств решений соответствующих оптимизационных задач. Если Х состоит из конечного числа элементов, то минимум в задачах (1) и (2) берется по конечному множеству. А потому, как уже отмечалось, эмпирические и теоретические средние существуют. Ввиду важности обсуждаемой темы приведем доказательства. Для строгого математического изложения нам понадобятся термины из раздела математики под названием "общая топология". Топологические термины и результаты будем использовать в соответствии с классической монографией [20]. Так, топологическое пространство называется бикомпактным в том и только в том случае, когда из каждого его открытого покрытия можно выбрать конечное подпокрытие [20, с.183]. Теорема 1. Пусть Х - бикомпактное пространство, функция f непрерывна на Х2 (в топологии произведения). Тогда эмпирическое и теоретическое средние существуют. Доказательство. Функция f(xi, y) от y непрерывна, сумма непрерывных функций непрерывна, непрерывная функция на бикомпакте достигает своего минимума, откуда и следует заключение теоремы относительно эмпирического среднего. Перейдем к теоретическому среднему. По теореме Тихонова [20, с.194] из бикомпактности Х вытекает бикомпактность Х2. Для каждой точки (x, y) из Х2 рассмотрим
Поскольку f непрерывна, то множества U(x,y) открыты в рассматриваемой топологии в Х2. По теореме Уоллеса [20, с.193] существуют открытые (в Х) множества V(x) и W(y), содержащие x и y соответственно и такие, что их декартово произведение V(x)×W(y) целиком содержится внутри U(x, y). Рассмотрим покрытие Х2 открытыми множествами V(x)×W(y). Из бикомпактности Х2 вытекает существование конечного подпокрытия {V(xi)×W(yi), i = 1, 2, ... , m}. Для каждого х из Х рассмотрим все декартовы произведенияV(xi)×W(yi), куда входит точка (x, y) при каком-либо y. Таких декартовых произведений и их первых множителей V(xi) конечное число. Возьмем пересечение таких первых множителей V(xi) и обозначим его Z(x). Это пересечение открыто, как пересечение конечного числа открытых множеств, и содержит точку х. Из покрытия бикомпактного пространства Xоткрытыми множествами Z(x) выберем открытое подпокрытие Z1, Z2, ..., Zk. Покажем, что если
Пусть Zj = Z(x0) при некотором x0. Пусть V(xi)×W(yi),
откуда и следует неравенство (3). Поскольку Х2 - бикомпактное пространство, то функция f ограничена на Х2 , а потому существует математическое ожидание Mf(
а потому функция g(y) = Mf( непрерывна на Х. Поскольку непрерывная функция на бикомпактном множестве достигает своего минимума, т.е. существуют такие точки z, на которых g(z) = inf{g(y), y В ряде интересных для приложений ситуаций Х не является бикомпактным пространством. Например, если Х = R1. В этих случаях приходится наложить на показатель различия f некоторые ограничения, например, так, как это сделано в теореме 2. Теорема 2. Пусть Х - топологическое пространство, непрерывная (в топологии произведения) функция f: X2 f(x,y) < D{f(x,z) + f(z,y)}. (5) Пусть в Х существует точка x0 такая, что при любом положительном R множество {x: f(x, x0) < R} является бикомпактным. Пусть для случайного элемента Тогда существуют (т.е. непусты) математическое ожидание E(x,f) и эмпирические средние En(f). Замечание. Условие (5) - некоторое обобщение неравенства треугольника. Например, если g - метрика в X, а f = gp при некотором натуральном p, то для f выполнено соотношение (5) с D = 2p. Доказательство. Рассмотрим функцию g(y), определенную формулой (4). Имеем f( Поскольку по условию теоремы g(x0) существует, а потому конечно, то из оценки (6) следует существование и конечность g(y) при всех y из Х. Докажем непрерывность этой функции. Рассмотрим шар (в смысле меры различия f) радиуса R с центром в x0: K(R) = {x : f(x, x0) < R}, R > 0. В соответствии с условием теоремы K(R) как подпространство топологического пространства Х является бикомпактным. Рассмотрим произвольную точку х из Х. Справедливо разложение
где
Рассмотрим второе слагаемое в (7). В силу (5)
Возьмем математическое ожидание от обеих частей (8):
В правой части (9) оба слагаемых стремятся к 0 при безграничном возрастании R: первое - в силу того, что
второе - в силу того, что распределение случайного элемента
Пусть U(x) - такая окрестность х (т.е. открытое множество, содержащее х), для которой sup {f(y, x), y Имеем
В силу (9) и (10) при безграничном возрастании R
равномерно по y
Нас интересует поведение выражения в правой части формулы (12) при y
при y
при y
что и доказывает непрерывность функции g(x). Докажем существование математического ожидания E(x,f). Пусть R(0) таково, что
Пусть H - некоторая константа, значение которой будет выбрано позже. Рассмотрим точку х из множества K(HR(0))С - дополнения K(HR(0)), т.е. из внешности шара радиуса HR(0) с центром в х0. Пусть
откуда
Выбирая H достаточно большим, получим с учетом условия (14), что при x
Можно выбрать H так, чтобы правая часть (16) превосходила Сказанное означает, что Argmin g(x) достаточно искать внутри бикомпактного множества K(HR(0)). Из непрерывности функции g вытекает, что ее минимум достигается на указанном бикомпактном множестве, а потому - и на всем Х. Существование (непустота) теоретического среднего E(x,f) доказана. Докажем существование эмпирического среднего En(f). Есть искушение проводить его дословно так же, как и доказательство существования математического ожидания E(x,f), лишь с заменой 1/2 в формуле (16) на частоту попадания элементов выборки xi в шар K(R(0)). Эта частота, очевидно, стремится к вероятности попадания случайного элемента
Поэтому пойдем другим путем, не опирающимся к тому же на вероятностную модель выборки. Положим
Если х входит в дополнение шара K(HR(1)), то аналогично (15) имеем
При достаточно большом H из (17) и (18) следует, что
Следовательно, Argmin достаточно искать на K(HR(1)). Заключение теоремы 2 следует из того, что на бикомпактном пространстве K(HR(1)) минимизируется непрерывная функция. Теорема 2 полностью доказана. О формулировках законов больших чисел. Пусть
при В силу классического закона больших чисел при
в смысле сходимости по вероятности, если правая часть существует (теорема А.Я. Хинчина, 1923 г.). Если пространство Х состоит из конечного числа элементов, то из соотношения (20) легко вытекает (см., например, [7, с.192-193]), что
Другими словами, Если
Однако с прикладной точки зрения доказательство соотношений (21) - (22) не дает достаточно уверенности в возможности использования Замечание. Если в соотношении (20) рассмотреть сходимость с вероятностью 1, то аналогично (21) получим т.н. усиленный закон больших чисел [7, с.193-194]. Согласно этой теореме с вероятностью 1 эмпирическое среднее Если Х не является конечным, например, Х = R1 , то соотношения (21) и (22) неверны. Поэтому необходимо искать иные формулировки закона больших чисел. В классическом случае сходимости выборочного среднего арифметического к математическому ожиданию, т.е.
В этом соотношении в отличие от (21) речь идет о попадании эмпирического среднего Обобщим эту формулировку. Как задать окрестность теоретического среднего в пространстве произвольной природы? Естественно взять его окрестность, определенную с помощью какой-либо метрики. Однако полезно обеспечить на ее дополнении до Х отделенность множества значений Мf(x( Поэтому мы сочли целесообразным определить такую окрестность с помощью самой функции Мf(x( Определение 3. Для любого
Таким образом, в
Соотношение (24) допускает непосредственное обобщение на общий случай пространств произвольной природы. СХЕМА ЗАКОНА БОЛЬШИХ ЧИСЕЛ. Пусть
Аналогичным образом может быть сформулирована и общая идея усиленного закона больших чисел. Ниже приведены две конкретные формулировки "условий регулярности". Законы больших чисел. Начнем с рассмотрения естественного обобщения конечного множества - бикомпактного пространства Х. Теорема 3. В условиях теоремы 1 справедливо соотношение (25). Доказательство. Воспользуемся построенным при доказательстве теоремы 1 конечным открытым покрытием {Z1, Z2, ..., Zk} пространства Х таким, что для него выполнено соотношение (3). Построим на его основе разбиение Хна непересекающиеся множества W1, W2, ..., Wm (объединение элементов разбиения W1, W2, ..., Wm составляет Х). Это можно сделать итеративно. На первом шаге из Z1 следует вычесть Z2, ..., Zk - это и будет W1. Затем в качестве нового пространства надо рассмотреть разность Х и W1, а покрытием его будет {Z2, ..., Zk}. И так до k-го шага, когда последнее из рассмотренных покрытий будет состоять из единственного открытого множества Zk. Остается из построенной последовательности W1, W2, ..., Wk вычеркнуть пустые множества, которые могли быть получены при осуществлении описанной процедуры (поэтому, вообще говоря, m может быть меньше k). В каждом из элементов разбиения W1, W2, ..., Wm выберем по одной точке, которые назовем центрами разбиения и соответственно обозначим w1, w2, ..., wm. Это и есть то конечное множество, которым можно аппроксимировать бикомпактное пространство Х. Пусть y входит в Wj. Тогда из соотношения (3) вытекает, что
Перейдем к доказательству соотношения (25). Возьмем произвольное
Для обоснования этого неравенства рассмотрим все элементы разбиения W1, W2, ..., Wm, имеющие непустое пересечение с внешностью
где минимум берется по центрам всех элементов разбиения, имеющим непустое пересечение с внешностью
В силу закона больших чисел для действительнозначных случайных величин каждая из участвующих в соотношениях (27) и (29) средних арифметических имеет своими пределами соответствующие математические ожидания, причем в соотношении (29) эти пределы не менее
поскольку точки vi лежат вне
и достаточно большом n, обеспечивающем необходимую близость рассматриваемого конечного числа средних арифметических к их математическим ожиданиям, справедливо неравенство (27). Из неравенства (27) следует, что пересечение En(f) с внешностью Если Х не является бикомпактным пространством, то необходимо суметь оценить рассматриваемые суммы "на периферии", вне бикомпактного ядра, которое обычно выделяется естественным путем. Один из возможных комплексов условий сформулирован выше в теореме 2. Теорема 4. В условиях теоремы 2 справедлив закон больших чисел, т.е. соотношение (25). Доказательство. Будем использовать обозначения, введенные в теореме 2 и при ее доказательстве. Пусть r и R,r < R, - положительные числа. Рассмотрим точку х в шаре K(r) и точку y вне шара K(R). Поскольку
то
Положим
Сравним
а в силу неравенства (30)
где Card I(n,r) - число элементов в множестве индексов I(n,r). Следовательно,
где J = Card I(n,r) - биномиальная случайная величина B(n,p) с вероятностью успеха p = P{
где
Выберем R так, чтобы
Тогда
и согласно (31), (32) и (33) при
для любого y вне K(R). Из (34) следует, что минимизировать
с вероятностью не менее 1-2 Пусть
Согласно (36) с вероятностью не менее
при
что и завершает доказательство теоремы 4. Справедливы и иные варианты законов больших чисел, полученные, в частности, в статье [21]. Медиана Кемени и экспертные оценки. Рассмотрим на основе развитой выше теории частный случай пространств нечисловой природы - пространство бинарных отношений на конечном множестве Определение 4. Расстоянием Кемени между бинарными отношениями А и В, описываемыми матрицами ||a(i,j)|| и ||b(i,j)|| соответственно, называется
Замечание. Иногда в определение расстояния Кемени вводят множитель, зависящий от k. Определение 5. Медианой Кемени для выборки, состоящей из бинарных отношений, называется эмпирическое среднее, построенное с помощью расстояния Кемени. Поскольку число бинарных отношений на конечном множестве конечно, то эмпирические и теоретические средние для произвольных показателей различия существуют и справедливы законы больших чисел, описанные формулами (21) и (22) выше. Бинарные отношения, в частности, упорядочения, часто используются для описания мнений экспертов. Тогда расстояние Кемени измеряет близость мнений экспертов, а медиана Кемени позволяет находить итоговое усредненное мнение комиссии экспертов. Расчет медианы Кемени обычно включают в информационное обеспечение систем принятия решений с использованием оценок экспертов. Речь идет, например, о математическом обеспечении автоматизированного рабочего места "Математика в экспертизе" (АРМ "МАТЭК"), предназначенного, в частности, для использования при проведении экспертиз в задачах экологического страхования. Поэтому представляет большой практический интерес численное изучение свойств медианы Кемени при конечном объеме выборки. Такое изучение дополняет описанную выше асимптотическую теорию, в которой объем выборки предполагается безгранично возрастающим ( Компьютерное изучение свойств медианы Кемени при конечных объемах выборок. С помощью специально разработанной программной системы В.Н. Жихаревым был проведен ряд серий численных экспериментов по изучению свойств выборочных медиан Кемени. Представление о полученных результатах дается приводимой ниже табл.5, взятой из статьи [22]. В каждой серии методом статистических испытаний определенное число раз моделировался случайный и независимый выбор экспертных ранжировок, а затем находились все медианы Кемени для смоделированного набора мнений экспертов. При этом в сериях 1-5 распределение ответа эксперта предполагалось равномерным на множестве всех ранжировок. В серии 6 это распределение являлось монотонным относительно расстояния Кемени с некоторым центром (о понятии монотонности см. выше), т.е. вероятность выбора определенной ранжировки убывала с увеличением расстояния Кемени этой ранжировки от центра. Таким образом, серии 1-5 соответствуют ситуации, когда у экспертов нет почвы для согласия, нет группировки их мнений относительно некоторого единого среднего группового мнения, в то время как в серии 6 есть единое мнение - описанный выше центр, к которому тяготеют ответы экспертов. Результаты, приведенные в табл.5, можно комментировать разными способами. Неожиданным явилось большое число элементов в выборочной медиане Кемени - как среднее, так и особенно максимальное. Одновременно обращает на себя внимание убывание этих чисел при росте числа экспертов и особенно при переходе к ситуации реального существования группового мнения (серия 6). Достаточно часто один из ответов экспертов входит в медиану Кемени (т.е. пересечение множества ответов экспертов и медианы Кемени непусто), а диаметр медианы как множества в пространстве ранжировок заметно меньше диаметра множества ответов экспертов. По этим показателям - наилучшее положение в серии 6. Грубо говоря, всяческие "патологии" в поведении медианы Кемени наиболее резко проявляются в ситуации, когда ее применение не имеет содержательного обоснования, т.е. когда у экспертов нет основы для согласия, их ответы равномерно распределены на множестве ранжировок. Таблица 5. Вычислительный эксперимент по изучению свойств медианы Кемени
Увеличение числа испытаний в 10 раз при переходе от серии 1 к серии 5 не очень сильно повлияло на приведенные в таблице характеристики, поэтому представляется, что суть дела выявляется при числе испытаний (в методе Монте-Карло), равном 100 или даже 50. Увеличение числа объектов или экспертов увеличивает число элементов в рассматриваемом пространстве ранжировок, а потому уменьшается частота попадания какого-либо из мнений экспертов внутрь медианы Кемени. А также отношение диаметра медианы к диаметру множества экспертов и число элементов медианы Кемени (среднее и максимальное). Можно сказать, что увеличение числа объектов или экспертов уменьшает степень дискретности задачи, приближает ее к непрерывному случаю, а потому уменьшает выраженность различных "патологий". Есть много интересных результатов, которые здесь не рассматриваем. Они связаны, в частности, со сравнением медианы Кемени с другими методами усреднения мнений экспертов, например, с нахождением итогового упорядочения по методу средних рангов [10]. А также с использованием малых окрестностей ответов экспертов для поиска входящих в медиану ранжировок, с теоретической и численной оценкой скорости сходимости в законах больших чисел.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Величина f(x,y) интерпретируется как показатель различия между x и y: чем f(x,y) больше, тем x и yсильнее различаются. В качестве f можно использовать расстояние в Х, квадрат расстояния и т.п.
(1)
со значениями в Х, его распределения, независимости случайных элементов используем согласно предыдущему пункту настоящей главы, т.е. каноническому справочнику Ю.В. Прохорова и Ю.А. Розанова [19]. Будем считать, что функция f измерима относительно 
-алгебры, участвующей в определении случайного элемента 
при фиксированном y является действительнозначной случайной величиной. Предположим, что она имеет математическое ожидание.
существует при всех 
. Оно может быть пустым множеством, например, если Х = R1\{х0}, f(x,y) = (x - y)2, x0= М(x(ω)). И то, и другое исключается, если Х конечно. Однако и для конечных Х теоретическое среднее может состоять не из одного, а из многих элементов. Отметим, однако, что в множестве всех распределений вероятностей на Х подмножество тех распределений, для которых E(x,f) состоит более чем из одного элемента, имеет коразмерность 1, поэтому основной является ситуация, когда множество E(x,f) содержит единственный элемент [7].
- окрестность в Х2 в смысле показателя различияf, т.е. множество
и 
принадлежат одному и тому же Zj при некотором j, то
(3)
, - совокупность всех тех исходных декартовых произведений из системы {V(xi)×W(yi), i = 1, 2, ... , m}, куда входят точки (x0, y) при различных y. Покажем, что их объединение содержит также точки 
и 
при всех y. Действительно, если (х0, y) входит в V(xi)×W(yi), то yвходит в W(yi), а 
,y) для любого случайного элемента 
X}, то теорема 1 доказана.
R2 неотрицательна, симметрична (т.е. f(x,y) = f(y,x) для любых x и y из X), существует число D > 0 такое, что при всехx, y, z из X
(С) - индикатор множества С. Следовательно,
(7)
(8)
(9)
(10)
(11)
> 0 при R>R(0) и, кроме того, y
K(R(0)). Тогда при R>R(0)
(12)
Тогда
была доказана в теореме 1. Последнее означает, что существует окрестность U1(x) точки х такая, что
(13)
(14)
Тогда имеем
(15)
(16)
(17)
(18)
- независимые одинаково распределенные случайные элементы со значениями в Х. Закон больших чисел - это утверждение о сходимости эмпирических средних к теоретическому среднему (математическому ожиданию) при росте объема выборки n, т.е. утверждение о том, что
(19)
. Однако и слева, и справа в формуле (19) стоят, вообще говоря, множества. Поэтому понятие сходимости в (19) требует обсуждения и определения.
(20)
(21)
является состоятельной оценкой 
.
, то соотношение (21) переходит в следующее:
(22)
. Мы не будем останавливаться на сходимости с вероятностью 1, поскольку в соответствующих постановках, подробно разобранных в монографии [7], нет принципиальных отличий от случая сходимости по вероятности.
, можно записать закон больших чисел так: для любого
(23)
не непосредственно внутрь теоретического среднего E(x,f), а в некоторую окрестность теоретического среднего.
),y) как функции y от минимума этой функции на всем Х.
. В формулировке (23) классического закона больших чисел утверждается, что при любом 
-пятку математического ожидания стремится к 1. Поскольку 
(24)
- независимые одинаково распределенные случайные элементы со значениями в пространстве произвольной природы Х с показателем различия f: X2
(25)
(26)
>0. Рассмотрим некоторую точку b изE(x,f). Доказательство будет основано на том, что с вероятностью, стремящейся к 1, для любого y вне 
выполнено неравенство
(27)
(28)
(29)
(30)
и 
. Выборку 
разобьем на две части. В первую часть включим те элементы выборки, которые входят в K(r), во вторую - все остальные (т.е. лежащие вне K(r)). Множество индексов элементов первой части обозначим I = I(n,r). Тогда в силу неотрицательности f имеем
(31)
}. По теореме Хинчина для 
. Выберем 
так, чтобы при 
было выполнено соотношение
(32)
Выберем r так, чтобы вероятность успеха p > 0,6. По теореме Бернулли можно выбрать 
так, чтобы при 
(33)
(34)
с вероятностью не менее 
имеем
(35)
достаточно внутри бикомпактного шара K(R), при этом En(f) не пусто и
(36)
и 
- сужения 
Согласно доказанной выше теореме 3 найдется 
такое, что
Следовательно, при 
имеем
и его подпространства. Как известно, каждое бинарное отношение А можно описать матрицей ||a(i,j)|| из 0 и 1, причем a(i,j)= 1 тогда и только тогда qi и qj находятся в отношении А, и a(i,j) = 0 в противном случае.