Метод второго момента - Second moment method

В математике метод второго момента это техника, используемая в теория вероятности и анализ чтобы показать, что случайная переменная имеет положительную вероятность быть положительным. В более общем смысле, «метод моментов» состоит в оценке вероятности того, что случайная величина колеблется далеко от своего среднего значения, с помощью ее моментов.^[1]

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

Метод первого момента

Метод первого момента - это простое применение Неравенство Маркова для целочисленных переменных. Для неотрицательный, целочисленный случайная переменная Икс, мы можем захотеть доказать, что Икс = 0 с большой вероятностью. Чтобы получить оценку сверху для P (Икс > 0), а значит, оценка снизу для P (Икс = 0), сначала отметим, что, поскольку Икс принимает только целые значения, P (Икс > 0) = P (Икс ≥ 1). С Икс неотрицательно, теперь мы можем применить Неравенство Маркова чтобы получить P (Икс ≥ 1) ≤ E [Икс]. Объединяя их, мы получаем P (Икс > 0) ≤ E [Икс]; метод первого момента - это просто использование этого неравенства.

Метод второго момента

В обратном направлении E [Икс] "большой" не означает, что P (Икс = 0) мала. Однако мы часто можем использовать второй момент, чтобы сделать такой вывод, используя Неравенство Коши – Шварца.

Теорема: Если Икс ≥ 0 является случайная переменная с бесконечной дисперсией, тогда

${\displaystyle \operatorname {P} (X>0)\geq {\frac {(\operatorname {E} [X])^{2}}{\operatorname {E} [X^{2}]}}.}$

Доказательство: С использованием Неравенство Коши – Шварца, у нас есть

${\displaystyle \operatorname {E} [X]=\operatorname {E} [X\,\mathbf {1} _{\{X>0\}}]\leq \operatorname {E} [X^{2}]^{1/2}\operatorname {P} (X>0)^{1/2}.}$

Решение для ${\displaystyle \operatorname {P} (X>0)}$, тогда следует требуемое неравенство. ∎

Метод также может быть использован на границах распределения случайных величин. Кроме того, оценку предыдущей теоремы можно уточнить с помощью так называемого Неравенство Пэли – Зигмунда.. Предположим, что Икс_п представляет собой последовательность неотрицательных случайных величин с действительными значениями, которые сходиться в законе к случайной величине Икс. Если есть конечные положительные постоянные c₁, c₂ такой, что

${\displaystyle \operatorname {E} \left[X_{n}^{2}\right]\leq c_{1}\operatorname {E} [X_{n}]^{2}}$

${\displaystyle \operatorname {E} \left[X_{n}\right]\geq c_{2}}$

держать для каждого п, то из Неравенство Пэли – Зигмунда. это для каждого п и θ в (0, 1)

${\displaystyle \operatorname {P} (X_{n}\geq c_{2}\theta )\geq {\frac {(1-\theta )^{2}}{c_{1}}}.}$

Следовательно, этому же неравенству удовлетворяет Икс.

Пример применения метода

Постановка проблемы

В Просачивание по облигации Бернулли подграф графа грамм по параметру п случайный подграф, полученный из грамм удалив каждый край грамм с вероятностью 1−п, независимо. В бесконечное полное двоичное дерево Т бесконечный дерево где одна вершина (называемая корнем) имеет двух соседей, а каждая другая вершина имеет трех соседей. Метод второго момента можно использовать, чтобы показать, что по каждому параметру п ∈ (1/2, 1] с положительной вероятностью связная компонента корня в перколяционном подграфе графа Т бесконечно.

Применение метода

Позволять K - перколяционная составляющая корня, и пусть Т_п - множество вершин Т что на расстоянии п из корня. Позволять Икс_п быть количеством вершин в Т_п ∩ K. Чтобы доказать, что K бесконечно с положительной вероятностью, достаточно показать, что ${\displaystyle \limsup _{n\to \infty }1_{X_{n}>0}>0}$ с положительной вероятностью. Посредством обратная лемма Фату, достаточно показать, что ${\displaystyle \inf _{n\to \infty }P(X_{n}>0)>0}$. В Неравенство Коши – Шварца дает

${\displaystyle E[X_{n}]^{2}\leq E[X_{n}^{2}]\,E\left[(1_{X_{n}>0})^{2}\right]=E[X_{n}^{2}]\,P(X_{n}>0).}$

Поэтому достаточно показать, что

${\displaystyle \inf _{n}{\frac {E\left[X_{n}\right]^{2}}{E\left[X_{n}^{2}\right]}}>0\,,}$

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

В данном конкретном приложении эти моменты можно рассчитать. Для каждого конкретного v в Т_п,

${\displaystyle P(v\in K)=p^{n}.}$

С ${\displaystyle |T_{n}|=2^{n}}$, следует, что

${\displaystyle E[X_{n}]=2^{n}\,p^{n}}$

это первый момент. Теперь наступает второй момент расчета.

${\displaystyle E\!\left[X_{n}^{2}\right]=E\!\left[\sum _{v\in T_{n}}\sum _{u\in T_{n}}1_{v\in K}\,1_{u\in K}\right]=\sum _{v\in T_{n}}\sum _{u\in T_{n}}P(v,u\in K).}$

Для каждой пары v, ты в Т_п позволять ш (в, и) обозначим вершину в Т который дальше всего от корня и лежит на простом пути в Т к каждой из двух вершин v и ты, и разреши к (v, u) обозначают расстояние от ш в корень. Для того чтобы v, ты чтобы оба были в K, это необходимо и достаточно для трех простых путей из ш (в, и) к v, ты и корень быть в K. Поскольку количество ребер, содержащихся в объединении этих трех путей, равно 2п − к (v, u), мы получаем

${\displaystyle P(v,u\in K)=p^{2n-k(v,u)}.}$

Количество пар (v, u) такой, что к (v, u) = s равно ${\displaystyle 2^{s}\,2^{n-s}\,2^{n-s-1}=2^{2n-s-1}}$, за s = 0, 1, ..., п. Следовательно,

${\displaystyle E\!\left[X_{n}^{2}\right]=\sum _{s=0}^{n}2^{2n-s-1}p^{2n-s}={\frac {1}{2}}\,(2p)^{n}\sum _{s=0}^{n}(2p)^{s}={\frac {1}{2}}\,(2p)^{n}\,{\frac {(2p)^{n+1}-1}{2p-1}}\leq {\frac {p}{2p-1}}\,E[X_{n}]^{2},}$

что завершает доказательство.

Обсуждение

• Выбор случайных величин Икс_п было довольно естественно в этой установке. В некоторых более сложных применениях метода может потребоваться некоторая изобретательность, чтобы выбрать случайные величины. Икс_п для которого аргумент может быть доведен до конца.
• В Неравенство Пэли – Зигмунда. иногда используется вместо Неравенство Коши – Шварца и иногда может давать более точные результаты.
• При (неверном) предположении, что события v, ты в K всегда независимы, есть ${\displaystyle P(v,u\in K)=P(v\in K)\,P(u\in K)}$, а второй момент равен квадрату первого момента. Метод второго момента обычно работает в ситуациях, когда соответствующие события или случайные величины «почти независимы».
• В этом приложении случайные величины Икс_п даны в виде сумм

${\displaystyle X_{n}=\sum _{v\in T_{n}}1_{v\in K}.}$

В других приложениях соответствующие полезные случайные величины интегралы

${\displaystyle X_{n}=\int f_{n}(t)\,d\mu (t),}$

где функции ж_п случайны. В такой ситуации считается, что товарная мера μ × μ и вычисляет

${\displaystyle {\begin{aligned}E\left[X_{n}^{2}\right]&=E\left[\int \int f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\right]\\&=E\left[\int \int E\left[f_{n}(x)\,f_{n}(y)\right]\,d\mu (x)\,d\mu (y)\right],\end{aligned}}}$

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

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

• Бурдзи, Кшиштоф; Адельман, Омер; Пемантл, Робин (1998), «Множества, избегаемые броуновским движением», Анналы вероятности, 26 (2): 429–464, arXiv:математика / 9701225, Дои:10.1214 / aop / 1022855639, HDL:1773/2194
• Лайонс, Рассел (1992), «Случайное блуждание, емкость и просачивание на деревьях», Анналы вероятности, 20 (4): 2043–2088, Дои:10.1214 / aop / 1176989540
• Лайонс, Рассел; Перес, Юваль, Вероятность на деревьях и сетях

1. Теренс Тао (2008-06-18). «Сильный закон больших чисел». Какие новости?. Получено 2009-02-10.