Метод Штейна

Не путать с леммой Штейна.

Метод Штейна - это общий метод теории вероятностей для получения оценок расстояния между двумя распределениями вероятностей относительно метрики вероятности. Он был введен Чарльзом Стейном, который впервые опубликовал его в 1972 году, чтобы получить границу между распределением суммы -зависимой последовательности случайных величин и стандартным нормальным распределением в метрике Колмогорова (равномерной) и, следовательно, доказать не только центральная предельная теорема, но также и оценки скорости сходимости для данной метрики. ${\ displaystyle m}$

• 1 История
• 2 Базовый подход
  • 2.1 Вероятностные метрики
  • 2.2 Оператор Штейна
  • 2.3 Уравнение Штейна
  • 2.4 Решение уравнения Штейна
  • 2.5 Свойства решения уравнения Штейна
  • 2.6 Абстрактная аппроксимационная теорема
  • 2.7 Применение теоремы
• 3 Подключения к другим методам
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Литература

В конце 1960-х годов, неудовлетворенный известными к тому времени доказательствами конкретной центральной предельной теоремы, Чарльз Стейн для своей лекции по статистике разработал новый способ доказательства теоремы. Его основополагающая статья была представлена ​​в 1970 году на шестом симпозиуме в Беркли и опубликована в соответствующих трудах.

Позже его докторская степень. студент Луи Чен Сяо Юнь модифицировал метод, чтобы получить результаты аппроксимации для распределения Пуассона ; поэтому метод Стейна, применяемый к проблеме пуассоновской аппроксимации, часто называют методом Стейна – Чена.

Вероятно, наиболее важным вкладом является монография Стейна (1986), в которой он представляет свой взгляд на метод и концепцию вспомогательной рандомизации, в частности, с использованием взаимозаменяемых пар, а также статьи Барбура (1988) и Гетце (1991), которые представила так называемую генераторную интерпретацию, которая позволила легко адаптировать метод ко многим другим распределениям вероятностей. Важным вкладом была также статья Болтхаузена (1984) о так называемой комбинаторной центральной предельной теореме.

В 1990-х годах этот метод был адаптирован к множеству распределений, таким как гауссовские процессы Барбура (1990), биномиальное распределение Эмом (1991), пуассоновские процессы Барбура и Брауна (1992), гамма-распределение Люка (1994)., и многие другие.

Этот метод приобрел дальнейшую популярность в сообществе машинного обучения в середине 2010-х годов, после развития несоответствия Штейна и различных приложений и алгоритмов, основанных на нем.

Вероятностные метрики

Метод Стейна - это способ ограничить расстояние между двумя распределениями вероятностей с помощью определенной метрики вероятности.

Пусть метрика задана в виде

${\ Displaystyle (1.1) \ quad d (P, Q) = \ sup _ {h \ in {\ mathcal {H}}} \ left | \ int h \, dP- \ int h \, dQ \ right | = \ sup _ {h \ in {\ mathcal {H}}} \ left | Eh (W) -Eh (Y) \ right |}$

Здесь и - вероятностные меры на измеримом пространстве, и - случайные величины с распределением, и, соответственно, - обычный оператор математического ожидания и представляет собой набор функций от до множества действительных чисел. Набор должен быть достаточно большим, чтобы приведенное выше определение действительно давало метрику. ${\ displaystyle P}$${\ displaystyle Q}$ ${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle W}$${\ displaystyle Y}$${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle E}$${\ displaystyle {\ mathcal {H}}}$${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle {\ mathcal {H}}}$

Важными примерами являются метрика полной вариации, в которой мы позволяем состоять из всех индикаторных функций измеримых множеств, метрика Колмогорова (равномерная) для вероятностных мер на действительных числах, где мы рассматриваем все индикаторные функции полупрямой, и липшицева ( Вассерштейн; Канторович первого порядка), где базовое пространство само является метрическим пространством, и мы берем множество как все липшицево-непрерывные функции с липшицевской константой 1. Однако заметим, что не всякая метрика может быть представлена ​​в виде (1.1). ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle {\ mathcal {H}}}$

Ниже приводится сложное распределение (например, распределение суммы зависимых случайных величин), которое мы хотим аппроксимировать гораздо более простым и управляемым распределением (например, стандартным нормальным распределением). ${\ displaystyle P}$${\ displaystyle Q}$

Оператор Штейна

Теперь мы предполагаем, что это фиксированное распределение; В дальнейшем мы, в частности, рассмотрим случай, когда - стандартное нормальное распределение, которое служит классическим примером. ${\ displaystyle Q}$${\ displaystyle Q}$

Прежде всего, нам нужен оператор, который действует на функции из множества действительных чисел и `` характеризует '' распределение в том смысле, что имеет место следующая эквивалентность: ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle f}$${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle Q}$

${\ displaystyle (2.1) \ quad E (({\ mathcal {A}} f) (Y)) = 0 {\ text {для всех}} f \ quad \ iff \ quad Y {\ text {имеет распределение}} Q.}$

Мы называем такой оператор оператором Штейна.

Для стандартного нормального распределения лемма Стейна дает такой оператор:

${\ Displaystyle (2.2) \ четырехъядерный E \ влево (f '(Y) -Yf (Y) \ right) = 0 {\ text {для всех}} f \ in C_ {b} ^ {1} \ quad \ iff \ quad Y {\ text {имеет стандартное нормальное распределение.}}}$

Таким образом, мы можем взять

${\ displaystyle (2.3) \ quad ({\ mathcal {A}} f) (x) = f '(x) -xf (x).}$

Таких операторов, вообще говоря, бесконечно много, и вопрос о том, какой из них выбрать, остается открытым. Однако кажется, что для многих распределений есть особенно хорошее, например (2.3) для нормального распределения.

Есть разные способы найти операторы Штейна.

Уравнение Штейна

${\ displaystyle P}$близко к относительно если разница ожиданий в (1.1) близка к 0. Мы надеемся теперь, что оператор имеет такое же поведение: если тогда, и, надеюсь, если у нас есть. ${\ displaystyle Q}$${\ displaystyle d}$${\ displaystyle {\ mathcal {A}}}$${\ Displaystyle P = Q}$${\ displaystyle E ({\ mathcal {A}} f) (W) = 0}$${\ Displaystyle P \ приблизительно Q}$${\ Displaystyle E ({\ mathcal {A}} f) (W) \ приблизительно 0}$

Обычно можно определить функцию так, чтобы ${\ displaystyle f = f_ {h}}$

${\ displaystyle (3.1) \ quad ({\ mathcal {A}} f) (x) = h (x) -E [h (Y)] \ qquad {\ text {для всех}} x.}$

Мы называем (3.1) уравнением Штейна. Заменяя на и принимая ожидание относительно, мы получаем ${\ displaystyle x}$${\ displaystyle W}$${\ displaystyle W}$

${\ displaystyle (3.2) \ quad E ({\ mathcal {A}} f) (W) = E [h (W)] - E [h (Y)].}$

Теперь все усилия окупаются, только если левую часть (3.2) легче связать, чем правую. Как ни странно, так бывает часто.

Если - стандартное нормальное распределение и мы используем (2.3), то соответствующее уравнение Стейна имеет вид ${\ displaystyle Q}$

${\ displaystyle (3.3) \ quad f '(x) -xf (x) = h (x) -E [h (Y)] \ qquad {\ text {для всех}} x.}$

Если вероятностное распределение Q имеет абсолютно непрерывную (относительно меры Лебега) плотность q, то

${\ displaystyle (3.4) \ quad ({\ mathcal {A}} f) (x) = f '(x) + f (x) q' (x) / q (x).}$

Решение уравнения Штейна

Аналитические методы. Уравнение (3.3) легко решается явно:

${\ Displaystyle (4.1) \ четырехъядерный е (х) = е ^ {х ^ {2} / 2} \ int _ {- \ infty} ^ {x} [h (s) -Eh (Y)] e ^ { -s ^ {2} / 2} \, ds.}$

Генераторный метод. Если является генератором марковского процесса (см. Barbour (1988), Götze (1991)), то решение (3.2) есть ${\ displaystyle {\ mathcal {A}}}$${\ Displaystyle (Z_ {т}) _ {т \ geq 0}}$

${\ Displaystyle (4.2) \ четырехъядерный е (х) = - \ int _ {0} ^ {\ infty} [E ^ {x} h (Z_ {t}) - Eh (Y)] \, dt,}$

где обозначает ожидание по отношению к запускаемому процессу. Однако еще предстоит доказать, что решение (4.2) существует для всех искомых функций. ${\ displaystyle E ^ {x}}$${\ displaystyle Z}$${\ displaystyle x}$${\ displaystyle h \ in {\ mathcal {H}}}$

Свойства решения уравнения Штейна.

Обычно пытаются дать оценки и его производные (или различия) в терминах и его производных (или различиях), то есть неравенства вида ${\ displaystyle f}$${\ displaystyle h}$

${\ displaystyle (5.1) \ quad \ | D ^ {k} f \ | \ leq C_ {k, l} \ | D ^ {l} h \ |,}$

для некоторых специфических (обычно или, соответственно, в зависимости от формы оператора Штейна), где часто является супремум-нормой. Здесь обозначает дифференциальный оператор, но в дискретных настройках он обычно относится к разностному оператору. Константы могут содержать параметры распределения. Если они есть, их часто называют факторами Штейна. ${\ Displaystyle к, l = 0,1,2, \ точки}$${\ displaystyle k \ geq l}$${\ Displaystyle к \ geq l-1}$${\ displaystyle \ | \ cdot \ |}$${\ displaystyle D ^ {k}}$ ${\ displaystyle C_ {k, l}}$${\ displaystyle Q}$

В случае (4.1) для нормы супремума можно доказать, что

${\ displaystyle (5.2) \ quad \ | f \ | _ {\ infty} \ leq \ min \ left \ {{\ sqrt {\ pi / 2}} \ | h \ | _ {\ infty}, 2 \ | h '\ | _ {\ infty} \ right \}, \ quad \ | f' \ | _ {\ infty} \ leq \ min \ {2 \ | h \ | _ {\ infty}, 4 \ | h ' \ | _ {\ infty} \}, \ quad \ | f '' \ | _ {\ infty} \ leq 2 \ | h '\ | _ {\ infty},}$

где последняя оценка, конечно, применима только в том случае, если она дифференцируема (или, по крайней мере, липшицево, что, например, не так, если мы рассматриваем метрику полной вариации или метрику Колмогорова!). Поскольку стандартное нормальное распределение не имеет дополнительных параметров, в этом конкретном случае константы не содержат дополнительных параметров. ${\ displaystyle h}$

Если у нас есть оценки в общей форме (5.1), мы обычно можем рассматривать многие вероятностные метрики вместе. Часто можно начать со следующего шага ниже, если границы вида (5.1) уже доступны (что имеет место для многих распределений).

Абстрактная аппроксимационная теорема

Теперь мы можем ограничить левую часть (3.1). Поскольку этот шаг сильно зависит от формы оператора Штейна, мы непосредственно рассматриваем случай стандартного нормального распределения.

На этом этапе мы могли бы напрямую подключить случайную величину, которую мы хотим аппроксимировать, и попытаться найти верхние границы. Однако часто бывает полезно сформулировать более общую теорему. Рассмотрим здесь случай локальной зависимости. ${\ displaystyle W}$

Предположим, что это сумма случайных величин, таких что и дисперсия. Предположим, что для каждого существует набор, не зависящий от всех случайных величин с. Мы называем это множество «окрестностью». Точно так же пусть будет такой, что все с независимы от всех,. Мы можем думать о них как о соседях по соседству, так сказать, о районе второго порядка. Для набора теперь определите сумму. ${\ Displaystyle W = \ сумма _ {я = 1} ^ {п} X_ {я}}$${\ displaystyle E [W] = 0}$ ${\ displaystyle \ operatorname {var} [W] = 1}$${\ Displaystyle я = 1, \ точки, п}$${\ Displaystyle A_ {я} \ подмножество \ {1,2, \ точки, п \}}$${\ displaystyle X_ {i}}$${\ displaystyle X_ {j}}$${\ displaystyle j \ not \ in A_ {i}}$${\ displaystyle X_ {i}}$${\ Displaystyle B_ {я} \ подмножество \ {1,2, \ точки, п \}}$${\ displaystyle X_ {j}}$${\ displaystyle j \ in A_ {i}}$${\ displaystyle X_ {k}}$${\ displaystyle k \ not \ in B_ {i}}$${\ displaystyle B_ {i}}$${\ displaystyle X_ {i}}$${\ Displaystyle А \ подмножество \ {1,2, \ точки, п \}}$${\ Displaystyle X_ {A}: = \ сумма _ {j \ in A} X_ {j}}$

Используя разложение Тейлора, можно доказать, что

${\ Displaystyle (6.1) \ quad \ left | E (f '(W) -Wf (W)) \ right | \ leq \ | f' '\ | _ {\ infty} \ sum _ {i = 1} ^ {n} \ left ({\ frac {1} {2}} E | X_ {i} X_ {A_ {i}} ^ {2} | + E | X_ {i} X_ {A_ {i}} X_ { B_ {i} \ setminus A_ {i}} | + E | X_ {i} X_ {A_ {i}} | E | X_ {B_ {i}} | \ right)}$

Заметим, что, если мы будем следовать этой линии рассуждений, мы сможем оценить (1.1) только для функций, для которых ограничено из-за третьего неравенства (5.2) (и фактически, если имеет разрывы, то будет). Чтобы получить оценку, подобную (6.1), которая содержит только выражения и, аргумент намного сложнее, и результат не так прост, как (6.1); однако это можно сделать. ${\ Displaystyle \ | ч '\ | _ {\ infty}}$${\ displaystyle h}$${\ displaystyle f ''}$${\ Displaystyle \ | е \ | _ {\ infty}}$${\ Displaystyle \ | е '\ | _ {\ infty}}$

Теорема А. Если это так, как описано выше, мы имеем для метрики Липшица, что ${\ displaystyle W}$${\ displaystyle d_ {W}}$

${\ displaystyle (6.2) \ quad d_ {W} ({\ mathcal {L}} (W), N (0,1)) \ leq 2 \ sum _ {i = 1} ^ {n} \ left ({ \ frac {1} {2}} E | X_ {i} X_ {A_ {i}} ^ {2} | + E | X_ {i} X_ {A_ {i}} X_ {B_ {i} \ setminus A_ {i}} | + E | X_ {i} X_ {A_ {i}} | E | X_ {B_ {i}} | \ right).}$

Доказательство. Напомним, что метрика Липшица имеет вид (1.1) где функции липшицевы с константой Липшица 1, таким образом. Объединение этого с (6.1) и последней оценкой в ​​(5.2) доказывает теорему. ${\ displaystyle h}$${\ Displaystyle \ | ч '\ | \ leq 1}$

Таким образом, грубо говоря, мы доказали, что для вычисления липшицева расстояния между a со структурой локальной зависимости и стандартным нормальным распределением нам нужно знать только третьи моменты и размер окрестностей и. ${\ displaystyle W}$${\ displaystyle X_ {i}}$${\ displaystyle A_ {i}}$${\ displaystyle B_ {i}}$

Применение теоремы

Мы можем рассматривать случай сумм независимых и одинаково распределенных случайных величин с помощью теоремы A.

Предположим, что, и. Мы можем взять. Из теоремы A получаем, что ${\ displaystyle EX_ {i} = 0}$${\ displaystyle \ operatorname {var} X_ {i} = 1}$${\ displaystyle W = n ^ {- 1/2} \ sum X_ {i}}$${\ Displaystyle А_ {я} = В_ {я} = \ {я \}}$

${\ displaystyle (7.1) \ quad d_ {W} ({\ mathcal {L}} (W), N (0,1)) \ leq {\ frac {5E | X_ {1} | ^ {3}} { n ^ {1/2}}}.}$

Для сумм случайных величин другой подход, связанный с методом Штейнса, известен как преобразование нулевого смещения.

• Устройство Линдеберга. Линдеберг (1922) представил устройство, в котором разница представлена ​​как сумма пошаговых различий.${\ displaystyle Eh (X_ {1} + \ cdots + X_ {n}) - Eh (Y_ {1} + \ cdots + Y_ {n})}$

• Метод Тихомирова. Ясно, что подход, основанный на (1.1) и (3.1), не использует характеристические функции. Однако Тихомиров (1980) представил доказательство центральной предельной теоремы, основанное на характеристических функциях и дифференциальном операторе, аналогичном (2.3). Основное наблюдение состоит в том, что характеристическая функция стандартного нормального распределения удовлетворяет дифференциальному уравнению для всех. Таким образом, если характеристическая функция от такова, что мы ожидаем, что и, следовательно, близко к нормальному распределению. Тихомиров заявляет в своей статье, что его вдохновила основополагающая статья Штейна.${\ Displaystyle \ psi (т)}$${\ Displaystyle \ psi '(t) + t \ psi (t) = 0}$${\ displaystyle t}$${\ Displaystyle \ psi _ {W} (т)}$${\ displaystyle W}$${\ Displaystyle \ psi '_ {W} (t) + t \ psi _ {W} (t) \ приблизительно 0}$${\ Displaystyle \ psi _ {W} (t) \ приблизительно \ psi (t)}$${\ displaystyle W}$

• Лемма Штейна
• Несоответствие Штейна

• Барбур, AD (1988). «Метод Штейна и сходимость пуассоновского процесса». Журнал прикладной теории вероятностей. 25: 175–184. DOI : 10.2307 / 3214155. JSTOR   3214155.
• Барбур, AD (1990). «Метод Штейна для диффузионных приближений». Теория вероятностей и смежные области. 84 (3): 297–322. DOI : 10.1007 / BF01197887.
• Барбур, А. Д. и Браун, Т. К. (1992). «Метод Штейна и аппроксимация точечных процессов». Случайные процессы и их приложения. 43 (1): 9–31. DOI : 10.1016 / 0304-4149 (92) 90073-Y.
• Больтаузен, Э. (1984). «Оценка остатка в комбинаторной центральной предельной теореме». Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. 66 (3): 379–386. DOI : 10.1007 / BF00533704.
• Эм, В. (1991). «Биномиальное приближение к биномиальному распределению Пуассона». Статистика и вероятностные письма. 11 (1): 7–16. DOI : 10.1016 / 0167-7152 (91) 90170-V.
• Гётце, Ф. (1991). «О скорости сходимости в многомерной CLT». Летопись вероятности. 19 (2): 724–739. DOI : 10.1214 / AOP / 1176990448.
• Линдеберг, JW (1922). "Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechung". Mathematische Zeitschrift. 15 (1): 211–225. DOI : 10.1007 / BF01494395.
• Лук, HM (1994). Метод Штейна для гамма-распределения и связанные с ним статистические приложения. Диссертация.
• Новак, SY (2011). Экстремальные методы с приложениями к финансам. Монографии по статистике и прикладной теории вероятностей. 122. CRC Press. ISBN   978-1-43983-574-6.
• Стейн, К. (1986). Примерный расчет ожиданий. Конспект лекций-Серия монографий. 7. Институт математической статистики. ISBN   0-940600-08-0.
• Тихомиров, АН (1980). «Скорость сходимости в центральной предельной теореме для слабо зависимых случайных величин». Теория вероятностей и ее применения. 25: 800–818. Английский перевод в Тихомиров, АН (1981). «О скорости сходимости в центральной предельной теореме для слабозависимых случайных величин». Теория вероятностей и ее приложения. 25 (4): 790–809. DOI : 10.1137 / 1125092.

Следующий текст является расширенным и дает исчерпывающий обзор нормального случая.

• Чен, LHY, Голдштейн, Л., и Шао, QM (2011). Нормальное приближение по методу Штейна. www.springer.com. ISBN   978-3-642-15006-7. CS1 maint: несколько имен: список авторов ( ссылка )

Еще одна продвинутая книга, но имеющая некоторый вводный характер, - это

• изд. Барбур, А.Д. и Чен, LHY (2005). Введение в метод Штейна. Серия конспектов лекций, Институт математических наук, Национальный университет Сингапура. 4. Издательство Сингапурского университета. ISBN   981-256-280-Х. CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: дополнительный текст: список авторов ( ссылка )

Стандартный справочник - книга Штейна,

• Стейн, К. (1986). Примерный расчет ожиданий. Конспект лекций Института математической статистики, серия монографий, 7. Хейворд, Калифорния: Институт математической статистики. ISBN   0-940600-08-0.

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

Несмотря на свой возраст, существует несколько стандартных вводных книг о методе Штейна. В следующем недавнем учебнике есть глава (глава 2), посвященная введению метода Штейна:

• Росс, Шелдон и Пекез, Эрол (2007). Второй вариант вероятности. ISBN   978-0-9795704-0-7.

Хотя книга

• Барбур, А.Д., Холст, Л. и Янсон, С. (1992). Пуассоновское приближение. Оксфордские исследования вероятностей. 2. Clarendon Press Oxford University Press. ISBN   0-19-852235-5. CS1 maint: несколько имен: список авторов ( ссылка )

по большей части относится к пуассоновскому приближению, тем не менее, он содержит много информации о генераторном подходе, в частности, в контексте аппроксимации пуассоновского процесса.

В следующем учебнике есть глава (глава 10), посвященная введению метода Пуассона Штейна:

• Шелдон М. Росс (1995). Случайные процессы. Вайли. ISBN   978-0471120629.