Решение задачи Монжа-Канторовича для одного класса функционалов с приложением к пуассоновской аппроксимации тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Рузанкин, Павел Сергеевич

• Рузанкин, Павел Сергеевич
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Рузанкин, Павел Сергеевич

Глава 1. Введение и формулировка основных результатов

Глава 2. Решение задачи Монжа-Канторовича для рассматриваемого класса функционалов

2.1. Предварительные замечания и следствия из теоремы 1.

2.2. Доказательство теоремы 1.

2.3. Доказательство предложений 1-2.

Глава 3. Построение ближайших случайных величин и оптимального множества

3.1. Построение ближайших случайных величин.

3.2. Построение оптимального множества.

Глава 4. Пуассоновская аппроксимация биномиального распределения

4.1. Доказательство теоремы 2.

Введение диссертации (часть автореферата) на тему «Решение задачи Монжа-Канторовича для одного класса функционалов с приложением к пуассоновской аппроксимации»

История задачи Монжа-Канторовича (ЗМК) берет свое начало с постановки Монжем в 1781г. задачи о наиболее рациональной перевозке земли:

Разбить два равновеликих объема на бесконечно малые части и сопоставить их между собой так, чтобы сумма произведений длин путей на объем частиц была минимальной. Какова наименьшая стоимость перевозки, при перемещегсии по каким путям стоимость будет наименьшей?

Современная формулировка ЗМК была предложена J1.B. Канторовичем (см.

Пусть на полном сепарабельном метрическом пространстве (U, г) заданы две вероятностные борелевские меры Р и Q, и М - пространство всех вероятностных борелевских мер р, на U х U с фиксированными маргиналами х U) = Р(-), х •) = Q(-). Требуется определить значение к(Р, Q) = inf{ [ /(у, z)p(dy, dz) : p. € M}, (1)

JUxU где f - заданная функция, и найти меру р. £ М (если таковая существует), на которой достигается эта нижняя грань.

Задача Монжа-Канторовича обобщалась и изучалась представителями различных математических школ с использованием разнообразных методов. В настоящее время можно говорить о ЗМК как о целом круге задач с приложениями в различных областях математики: в дифференциальной геометрии, функциональном анализе, линейном программировании, теории вероятностей, математической статистике, теории информации и кибернетики, статистической физике и др. (см. обзор и библиографию в [8]).

Отметим, что наиболее распространенными направлениями исследований ЗМК являются отыскание как можно более простых представлений для решений в виде так называемых теорем двойственности, а также получение по возможности более точных оценок для значений функционала к. Решение ЗМК в явном виде оказалось возможным получить лишь в некоторых частных случаях. Так, например, если U = R - вещественная прямая с естественной метрикой и /(у, z) = д(у - z), где д - выпуклая функция (см. [15]), то k(P,Q)= [ д{у — z)dH(y, z) — f g{F~\u) - G~\u))du, J R2 J 0 где F и G - функции распределений P и Q соответственно, и G~l - кван-тильные преобразования F и G, Н(у, z) = min{F(?/), G(z)}. Для некоторых специальных классов распределений в R" также получены полные решения этой задачи (см. [8]).

Мы будем рассматривать функционал к(Р, Q) в (1) для ядер вида /(у, г) = I{r(y, z) > t), где через 1 обозначена индикаторная функция и t - произвольная неотрицательная постоянная. В этом случае выражение (1) есть так называемое расстояние Штрассена-Дадли: p(t,P,Q)=inf{P(r&r,)>t)}, (2) где инфимум берется по всем случайным величинам £ и 77, заданным на одном вероятностном пространстве, с распределениями Р и Q соответственно. Структура расстояния р по существу близка к структуре так называемых минимальных метрик (см. [3]), однако для него выполняется лишь аналог неравенства треугольника: p(t, Рь Р2) < р(оЛ, Л, Р3) + />(( 1 - a)t, Р3, Р2) при всех 0 < а < 1.

Отметим, что по существу в терминах расстояния р сформулированы многие результаты, связанные с исследованием скорости сходимости в так называемом принципе инвариантности Донскера-Прохорова (см., например, [9],[10],[18],[19]), а также в различных версиях пуассоновской аппроксимации процессов частных сумм (см. [1],[20]).

Определим также функционал

P{t, Р, Q) = sup{Р{А) - Q{At) : А замкнуто в 17}, (3) где А* = {у € U : inf{|£ — у\ : z £ А} < it}. В 1965г. В.Штрассен доказал теорему двойственности (которая легко следует из теоремы 11 в [22]) p(t,P,Q) = 0(t,P>Q) (4)

В 1968 г. Р.Дадли (см. [16]) привел иное доказательство соотношения (4), ослабив при этом требование полноты U. Результаты работы [22] обобщались также и другими авторами (см. библиографию в [21]). Заметим также, что из (4) следует, что р(О, Р, Q) - это расстояние полной вариации между Р и Q, а inf{2 : p(t, Р, Q) < t} - расстояние Прохорова, метризующее слабую сходимость мер (см. [7]).

Далее мы ограничим наше рассмотрение случаем, когда U — R- вещественная прямая с естественной метрикой. Соотношение (4) является полезным для обоснования таких свойств функционала р как непрерывность справа по t (см. Предложение 4), однако оно не дает нам способа вычисления значения этого функционала для конкретных распределений Р и Q. Центральный результат работы, позволяющий получить явное представление расстояния Штрассена-Дадли в одномерном случае, состоит в следующем (см. [23],[24],[27]): Теорема 1. Пусть t > 0. Тогда

Pit, Р, Q) = Ит 5(3,) - 1 = Ит Г(у) - 1, где функции S иТ задаются соотношениями lim S(y) = Ит Т(у) = 0, (5) у—^—оо у—> — ОО dS{y) = max{dF(y),T(y + dy - t) - S(y)}, (6) dT(y) = max{dG(y)} S(y + dy - t) - T(y)} (7) при всех у, и требованием непрерывности функций S и Т слева. Функции S и Т, удовлетворяющие перечисленным условиям, существуют и задаются этими условиями единственным образом.

Соотношения (6) и (7) означают следующее: S(y + w) = S(y) + P([y, у + к,)) + sup (Tiy + v-^-S^-Pdyiy + v))^, (8)

0<D<W

T(y + w) = T(y) + Q({y,y + w)) + sup (S(y + v-t)-T(y)-Q({yty + u)))+ (9)

0<v<w при всех у и w > 0. Символом (-)4 обозначена положительная часть числа, т.е. (•)+ = тах{-, 0}.

Вычислив функции S и Т, несложно построить ближайшие в смысле (2) случайные величины. Построение ближайших в этом смысле случайных величин описано в пункте 3.1. Если распределения Р и Q принадлежат классу показательных, либо нормальных законов, а также некоторым другим специальным классам, то функции S и Т нетрудно вычислить в явном виде (см. [23],[24]):

Предложение 1. Пусть 0 < и < v. Обозначим через Еи и Ev показательные распределения с параметрами и и v соответственно. Тогда при всех t > 0

Предложение 2. Пусть 0 <о<т,аиЬ- некоторые числа. Обозначим через Nj и N2 нормальные распределения с дисперсиями а2 и г2 и математическими ожиданиями а и Ъ соответственно. Тогда

М, = • + 4 " $ (7 - Л - \+ 2(а-2 - г-2) log ^ где У1 = -г2 V -^у2 о — т и Ф - функция распределения стандартного нормального закона.

Замечание. В силу соотношения (4) функционал р(£, Р, Q) будет непрерывен по аргументам Р и Q в метрике полной вариации. Поэтому, устремив в последнем предложении т —<т, можно вычислить расстояние р между нормальными случайными величинами с одинаковой дисперсией. Пусть jVx и iV2 нормальные распределения с математическими ожиданиями а и b соответственно и дисперсией а2. Тогда где Ф - функция распределения стандартного нормального закона.

Важным приложением теоремы 1 является оценка расстояния р между биномиальным и сопровождающим пуассоновским распределениями. Обозначим через В биномиальное распределение с параметрами п,р, а через Z - пуассо-новское распределение с параметром Л = пр.

Один из первых результатов, связанных с данной проблемой, был получен Ю. В. Прохоровым в 1953 г (см. [6]). Им было доказано, что р(0, В, Z) < ср, где с - абсолютная постоянная. Позже Л. Ле Кам установил (см. [14]), что также выполнено p(0,B,Z) < пр2. Комбинируя эти два неравенства, получим

А. Барбур и П. Холл в [12] показали, что имеет место аналогичная оценка снизу.

В работах [1], [11]-[13],[17],[20] при исследовании потраекторной близости процесса частных сумм и соответствующего пуассоновского процесса были получены, как частные случаи, оценки расстояния p(t, В, Z) для произвольного t. Наиболее сильные оценки потраекторной близости содержатся в работе И. С. Борисова [1]. В частности, где CiAAA ~ абсолютные положительные постоянные, а символом [t\ обозначено наибольшее целое число, не превосходящее 1

Однако для аппроксимации биномиального распределения в некотором диапазоне значений n, р, t эти оценки уже не являются оптимальными. Так П. Майор в [20] доказал, что для любого р < п~найдутся абсолютные положи

0, если \а — b\ < t, если \а — Ъ\ > р(0, В, Z) < min{cp, пр2}. тельные постоянные С и К, для которых имеет место неравенство p(C,B,Z) < Хехр f-i^logra) . (10)

При доказательстве (10) оценивается вероятность

PQS-r,\>C), где в качестве случайных величин £ и rj берутся квантильные преобразования F~1(lo) и G1(oj) случайной величины ы, равномерно распределенной на отрезке (0,1). Такое задание случайных величин может и не быть оптимальным в смысле (2) при различных значениях параметров nyp,t. Доказательство следующего утверждения (см. [27],[25]) опирается на теорему 1. Теорема 2. Пусть р < 1/2 и t > 1 целое. Тогда p{t1B,Z)<-exр|| nput<np\ (11) p(t, В, Z) < exp | j nPu t > wP2i (12) p{t,B,Z)<exP<! nt(log-Ar-2^1 l при еЧр2 < t < ^ f1, (13) \ np2 J \ logi pit, B, Z) = P([n + £ + 1, oo)) < exp | — (тг + t) log Vl^Jl I npu t > ^ , (14) i €■ ttp j or)

Кроме того, ' p(t, В, Z) > exp <( —4

15)

ЗАМЕЧАНИЕ. Неравенство (15) показывает, что в некотором диапазоне значений п, t оценки (12), (13) имеют неулучшаемый порядок логарифмической асимптотики. Оценка (14) также точна в этом смысле, так как

Р([п +£ + 1, оо)) = 6 = ехр <-(п +£ + 1) log П + t + 1 -пр 1, (16) v/2n(n + t +1) I епР ) где e~l/12(n+t+2) < 0 < le-i/i2(n-t-t+i) Последнее равенство установлено в доказательстве теоремы 2.

Проведем сравнение утверждения теоремы 2 с оценкой (10).

1. В отличие от результата П. Майора, теорема 2 содержит оценки расстояния p(t, В, Z) для всех t > 1.

2. Для того, чтобы применение теоремы 1 имело смысл, достаточно, чтобы пр3 —> 0, в то время как для выполнения неравенства (10) необходимо, чтобы пръ!2 < 1.

3. Для любого фиксированного t в силу неравенств (13), (14) равномерно для всех р < п~2!ъ имеем p{t,B,Z) <ir1exp|-JT2V/n(logft)3|, где Ki и К2 - легко вычисляемые абсолютные положительные постоянные. Таким образом, при фиксированном t и р < и-2/3 верхняя оценка для p(t, B,Z) в теореме 2 имеет большую, чем в неравенстве (10), скорость убывания, причем в силу (15) эта оценка неулучшаема с точностью до постоянных Кг и

О структуре работы. Диссертация состоит из четырех глав и списка литературы. Нумерация теорем, лемм и предложений сквозная. Нумерация формул также сквозная. Список литературы составлен последовательно по двум алфавитам - русскому и латинскому. Работы автора помещены в конце списка.

Автор выражает искреннюю благодарность своему научному руководителю И.С. Борисову за постановку задачи и полезные замечания.

ГЛАВА 2.

Решение задачи Монжа-Канторовича для рассматриваемого класса функционалов

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

1. Борисов И.С. (1996). Пуассоновская аппроксимация процесса частных сумм в банаховых пространствах. Сиб. мат. журнал 37 № 4, 723-731.

2. Добру шин Р. Л. (1970). Задание системы случайных величин при помощи условных распределений. Теория вероят. и ее примен. 15 №3, 469-497.

3. Золотарев В.М. (1986). Современная теория суммирования независимых случайных величин. М.: "Наука".

4. Канторович Л.В. (1942). О перемещении масс. Докл. АН СССР. 37 №7-8, 227-229.

5. Канторович Л.В. (1948). Об одной проблеме Монжа. Успехи матем. наук 3 №2, 225-226.

6. Прохоров Ю.В. (1953). Асимптотическое поведение биномиального распределения. Успехи мат. наук 8 №3, 135-142.

7. ПРОХОРОВ Ю.В. (1956). Сходимость случайных процессов и предельные теоремы теории вероятностей. Теория вероят. и ее примен. 1 №2, 177-237.

8. Рачев С.Т. (1984). Задача Монжа-Канторовича о перемещении масс и ее применение в стохастике. Теория вероят. и ее примен. 29 №4, 625-653.

9. САХАНЕНКО А.И. (1984). Скорость сходимости в принципе инвариантности для разнораспределенных случайных величин с экспонециальными моментами // Труды Института математики СО АН СССР, том 3, Новосибирск, "Наука", с. 4-49.

10. САХАНЕНКО А.И. (1985). Оценки в принципе инвариантности // Труды Института математики СО АН СССР, том 5, Новосибирск, "Наука", с. 27-44.

11. Adell J.A., de le Cal J. (1994). Coupling methods in Poisson approximation of binomial processes. (Preprint / Universidacl de Zaragoza).

12. Barbour A.D., Hall P. (1984). On the rate of Poisson convergence. Math, proc. Camb. Phill. Soc. 95, 473-480.

13. BORISOV I.S. (1993). Strong Poisson and mixed approximations of sums of independent random values in Banach spaces. Siberian Adv. Math. 3 №2, 1-13.

14. Le Cam L. (1970). Remargues sur le theoreme limit central dans les espaces localement convexes // Les Probabilities sur les Structures Algebriques, C.N.R.S., Pans, 233-249.

15. Cambanis S., Simons G., Stout W. (1976). Inequalities for Ek(X,Y) when the marginals are fixed. Z. Wahrscheintlichkeitstheor. verw. Geb. 36 №4, 285-294.

16. Dudley R.M. (1968). Distances of probability measures and random variables. Ann. Math. Stat. 39 №5, 1563-1572.

17. SKALA H.J. (1993). The existence of probability measures with given marginals. Ann. Probab. 21 №1, 136-142.

18. Strassen V. (1965). The existence of probability measures with given marginals. Ann. Math. Statist. 36 №2, 423-439.23. рузанкин П.С. (2000). Решение задачи Монжа-Канторовича для одного класса функционалов. Докл. РАН 370 №4, 443-444.

19. Рузанкин П.С. (2001). Построение оптимального совместного распределения двух случайных величин. Теория вероят. и ее примен. 46 №2, 275-296.

20. РУЗАНКИН П.С. (2001). О пуассоновской аппроксимации биномиального распределения. Сиб. мат. журнал 42 №2, 414-424.

21. Рузанкин П.С. (1997). Точность аппроксимации в теореме Пуассона. // Материалы XXXV международной студенческой конференции "Студент и научно-технический прогресс". Математика, Новосибирск, с. 92.

22. Рузанкин П.С. (1999). Об оптимальном задании случайных величин. // Материалы XXXVII международной студенческой конференции "Студент и научно-технический прогресс". Математика, Новосибирск, с. 130-131.