метод Штейна

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

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

История

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

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

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

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

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

Основной подход

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

Метод Штейна — это способ определить расстояние между двумя распределениями вероятностей с использованием определенной метрики вероятности .

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

$(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|$

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

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

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

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

Предположим теперь, что распределение $Q$ фиксированное распределение; в дальнейшем мы, в частности, будем рассматривать случай, когда $Q$ — стандартное нормальное распределение, которое служит классическим примером.

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

$(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.$

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

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

$(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.}}$

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

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

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

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

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

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

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

$(3.1)\quad ({\mathcal {A}}f)(x)=h(x)-E[h(Y)]\qquad {\text{ for all }}x.$

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

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

Теперь все усилия окупятся только в том случае, если левую часть (3.2) определить легче, чем правую. На удивление, это часто так.

Если $Q$ — стандартное нормальное распределение, и мы используем (2.3), тогда соответствующее уравнение Штейна имеет вид

$(3.3)\quad f'(x)-xf(x)=h(x)-E[h(Y)]\qquad {\text{for all }}x.$

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

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

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

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

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

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

$(4.2)\quad f(x)=-\int _{0}^{\infty }[E^{x}h(Z_{t})-Eh(Y)]\,dt,$

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

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

Обычно пытаются ограничить $f$ и его производные (или различия) с точки зрения $h$ и его производные (или разности), т. е. неравенства вида

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

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

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

$(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 },$

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

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

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

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

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

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

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

$(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) только для функций, где $\|h'\|_{\infty }$ ограничено в силу третьего неравенства (5.2) (и действительно, если $h$ имеет разрывы, поэтому будет $f''$). Чтобы получить оценку, аналогичную (6.1), содержащую только выражения $\|f\|_{\infty }$ и $\|f'\|_{\infty }$, аргументация гораздо сложнее, и результат не так прост, как (6.1); однако это можно сделать.

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

$(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) где функции $h$ непрерывны по Липшицу с константой Липшица 1, поэтому $\|h'\|\leq 1$. Объединение этого результата с (6.1) и последней оценкой в ​​(5.2) доказывает теорему.

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

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

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

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

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

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

Связь с другими методами

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

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

См. также

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

Ссылки

• Барбур, 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). «Оценка остатка в комбинаторной центральной предельной теореме» . Журнал теории вероятностей и смежных областей . 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). «Новый вывод показательного закона в теории вероятностей» . Математический журнал . 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 .
• Tikhomirov, A. N. (1980). "Convergence rate in the central limit theorem for weakly dependent random variables". Teoriya Veroyatnostei i ee Primeneniya . 25 : 800–818. English translation in Тихомиров А.Н. (1981). «О скорости сходимости в центральной предельной теореме для слабозависимых случайных величин». Теория вероятностей и ее приложения . 25 (4): 790–809. дои : 10.1137/1125092 .

Литература

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

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

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

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

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

• Штейн, К. (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: несколько имен: список авторов ( ссылка )

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

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

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