метод Штейна

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

История

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

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

Вероятно, наиболее важными вкладами являются монография Штейна (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|}$

Здесь и – вероятностные меры на измеримом пространстве , а – случайные величины с распределением и соответственно – обычный оператор математического ожидания и – набор функций из множества действительных чисел. Set должен быть достаточно большим, чтобы приведенное выше определение действительно давало метрику . ${\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{ for all }}f\quad \iff \quad Y{\text{ has distribution }}Q.}$

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

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

${\displaystyle (2.2)\quad E\left(f'(Y)-Yf(Y)\right)=0{\text{ for all }}f\in C_{b}^{1}\quad \iff \quad Y{\text{ has standard normal distribution.}}}$

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

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

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

Существуют разные способы поиска операторов Штейна. ^[4]

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

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

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

${\displaystyle (3.1)\quad ({\mathcal {A}}f)(x)=h(x)-E[h(Y)]\qquad {\text{ for all }}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{for all }}x.}$

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

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

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

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

${\displaystyle (4.1)\quad f(x)=e^{x^{2}/2}\int _{-\infty }^{x}[h(s)-Eh(Y)]e^{-s^{2}/2}\,ds.}$

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

${\displaystyle (4.2)\quad f(x)=-\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 k,l=0,1,2,\dots }$ ${\displaystyle k\geq l}$ ${\displaystyle k\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=\sum _{i=1}^{n}X_{i}}$ ${\displaystyle E[W]=0}$ ${\displaystyle \operatorname {var} [W]=1}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle A_{i}\subset \{1,2,\dots ,n\}}$ ${\displaystyle X_{i}}$ ${\displaystyle X_{j}}$ ${\displaystyle j\not \in A_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle B_{i}\subset \{1,2,\dots ,n\}}$ ${\displaystyle X_{j}}$ ${\displaystyle j\in A_{i}}$ ${\displaystyle X_{k}}$ ${\displaystyle k\not \in B_{i}}$ ${\displaystyle B_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle A\subset \{1,2,\dots ,n\}}$ ${\displaystyle X_{A}:=\sum _{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 \|h'\|_{\infty }}$ ${\displaystyle h}$ ${\displaystyle f''}$ ${\displaystyle \|f\|_{\infty }}$ ${\displaystyle \|f'\|_{\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 \|h'\|\leq 1}$

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

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

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

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

${\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 (t)}$ ${\displaystyle \psi '(t)+t\psi (t)=0}$ ${\displaystyle t}$ ${\displaystyle \psi _{W}(t)}$ ${\displaystyle W}$ ${\displaystyle \psi '_{W}(t)+t\psi _{W}(t)\approx 0}$ ${\displaystyle \psi _{W}(t)\approx \psi (t)}$ ${\displaystyle W}$

Смотрите также

• Лемма Штейна
• Расхождение Штейна

Примечания

1. Штайн, К. (1972). «Оценка ошибки нормального приближения распределения суммы зависимых случайных величин». Труды шестого симпозиума Беркли по математической статистике и теории вероятностей, Том 2 . Том. 6. Издательство Калифорнийского университета . стр. 583–602. МР  0402873. Збл  0278.60026.
2. Чарльз Стейн: Инвариант, прямое и «претенциозное». Архивировано 5 июля 2007 г. в Wayback Machine . Интервью, данное в 2003 году в Сингапуре.
3. Чен, LHY (1975). «Приближение Пуассона для зависимых испытаний». Анналы вероятности . 3 (3): 534–545. дои : 10.1214/aop/1176996359 . JSTOR  2959474. MR  0428387. Збл  0335.60016.
4. Новак, С.Ю. (2011). Методы экстремальных значений с применением в финансах . Монографии по статистике и прикладной теории вероятности. Том. 122. ЦРК Пресс . Ч. 12. ISBN 978-1-43983-574-6.

Рекомендации

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

Литература

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

• Чен, Л.Х.И., Гольдштейн, Л., и Шао, К.М. (2011). Нормальное приближение методом Штейна . www.springer.com. ISBN 978-3-642-15006-7.{{cite book}}: CS1 maint: multiple names: authors list (link)

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

• ред. Барбур, А.Д. и Чен, LHY (2005). Введение в метод Штейна . Серия конспектов лекций, Институт математических наук, Национальный университет Сингапура. Том. 4. Издательство Сингапурского университета. ISBN 981-256-280-Х. {{cite book}}: |author=имеет общее имя ( справка )CS1 maint: multiple names: authors list (link)

Стандартным справочником является книга Штейна.

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

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

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

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

Хотя книга

• Барбур А.Д., Холст Л. и Янсон С. (1992). Пуассоновское приближение . Оксфордские исследования вероятности. Том. 2. Издательство Кларендон Пресс Оксфордского университета. ISBN 0-19-852235-5.{{cite book}}: CS1 maint: multiple names: authors list (link)

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

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

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