Метод Штейна

Метод Стайна — это общий метод в теории вероятностей для получения границ расстояния между двумя распределениями вероятностей относительно метрики вероятности . Он был введен Чарльзом Стайном , который впервые опубликовал его в 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|}$

Здесь и — вероятностные меры на измеримом пространстве , а — случайные величины с распределением и соответственно, — обычный оператор ожидания, а — набор функций от до набора действительных чисел. Набор должен быть достаточно большим, чтобы приведенное выше определение действительно давало метрику . ${\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):=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.}$

Метод генератора . Если — генератор марковского процесса (см. Barbour (1988), Götze (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. Stein, C. (1972). «Граница ошибки в нормальном приближении к распределению суммы зависимых случайных величин». Труды Шестого симпозиума в Беркли по математической статистике и вероятности, том 2. Том 6. Издательство Калифорнийского университета . С. 583–602. MR  0402873. Zbl  0278.60026.
2. Чарльз Стайн: Инвариант, Прямой и "Претенциозный" Архивировано 2007-07-05 в Wayback Machine . Интервью, данное в 2003 году в Сингапуре
3. Чен, Л. Х. И. (1975). «Пуассоновское приближение для зависимых испытаний». Annals of Probability . 3 (3): 534–545. doi : 10.1214/aop/1176996359 . JSTOR  2959474. MR  0428387. Zbl  0335.60016.
4. Novak, SY (2011). Методы экстремальных значений с приложениями к финансам . Монографии по статистике и прикладной вероятности. Т. 122. CRC Press . Гл. 12. ISBN 978-1-43983-574-6.

Ссылки

• Барбур, А. Д. (1988). «Метод Штейна и сходимость процесса Пуассона». Журнал прикладной вероятности . 25 : 175–184. doi :10.2307/3214155. JSTOR  3214155. S2CID  121759039.
• Барбур, АД (1990). «Метод Штейна для приближений диффузии». Теория вероятностей и смежные области . 84 (3): 297–322. doi : 10.1007/BF01197887 . S2CID  123057547.
• Барбур, А. Д. и Браун, Т. К. (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. дои : 10.1007/BF00533704 . S2CID  121725342.
• Эм, В. (1991). «Биномиальное приближение к биномиальному распределению Пуассона». Statistics & Probability Letters . 11 (1): 7–16. doi :10.1016/0167-7152(91)90170-V.
• Гётце, Ф. (1991). «О скорости сходимости в многомерной ЦПТ». Анналы вероятности . 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. дои : 10.1007/BF01494395. S2CID  119730242.
• Лук, Х. М. (1994). Метод Стейна для гамма-распределения и связанные с ним статистические приложения . Диссертация.
• Новак, С.Ю. (2011). Методы экстремальных значений с приложениями к финансам . Монографии по статистике и прикладной вероятности. Том 122. CRC Press . ISBN 978-1-43983-574-6.
• Stein, C. (1986). Приближенное вычисление ожиданий . Lecture Notes-Monograph Series. Том 7. Институт математической статистики . ISBN 0-940600-08-0.
• Тихомиров А.Н. (1980). «Скорость сходимости в центральной предельной теореме для слабозависимых случайных величин». Теория вероятностей и ее применения . 25 : 800–818. Перевод на английский язык в Тихомиров, АН (1981). "О скорости сходимости в центральной предельной теореме для слабозависимых случайных величин". Теория вероятностей и ее приложения . 25 (4): 790–809. doi :10.1137/1125092.

Литература

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

• Chen, LHY, Goldstein, L., and Shao, QM (2011). Нормальное приближение методом Штейна . www.springer.com. ISBN 978-3-642-15006-7.{{cite book}}: CS1 maint: multiple names: authors list (link)

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

• Barbour, AD; Chen, LHY, ред. (2005). Введение в метод Штейна . Серия заметок лекций, Институт математических наук, Национальный университет Сингапура. Том 4. Singapore University Press. ISBN 981-256-280-X.

Стандартной ссылкой является книга Стайна,

• Stein, C. (1986). Приближенное вычисление ожиданий . Institute of Mathematical Statistics Lecture Notes, Monograph Series, 7. Hayward, Calif.: Institute of Mathematical Statistics. ISBN 0-940600-08-0.

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

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

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

Хотя книга

• Barbour, AD и Holst, L. и Janson, S. (1992). Пуассоновское приближение . Oxford Studies in Probability. Том 2. The Clarendon Press Oxford University Press. ISBN 0-19-852235-5.{{cite book}}: CS1 maint: multiple names: authors list (link)

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

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

• Шелдон М. Росс (1995). Стохастические процессы . Wiley. ISBN 978-0471120629.