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

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

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

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

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

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

С другой стороны, то, что E[ X ] «большое», не означает напрямую, что Pr( X = 0) мало. Однако мы часто можем использовать второй момент для вывода такого вывода, используя неравенство Коши – Шварца .

Теорема . Если X ≥ 0 — случайная величина сконечная дисперсия, тогда $$\Pr(X>0)\geq {\frac {(\operatorname {E} [X])^{2}}{\operatorname {E} [X^{2}]}}.$$

Доказательство

Используя неравенство Коши–Шварца , имеем $$\operatorname {E} [X]=\operatorname {E} [X\,\mathbf {1} _{\{X>0\}}]\leq \operatorname {E} [X^{2}]^{1/2}\Pr(X>0)^{1/2}.$$Решение для $\Pr(X>0)$, тогда следует желаемое неравенство. КЭД

Этот метод также можно использовать для определения пределов распределения случайных величин. Кроме того, оценку предыдущей теоремы можно уточнить с помощью так называемого неравенства Пэли–Зигмунда . Предположим, что X _n представляет собой последовательность неотрицательных действительных случайных величин, которые по закону сходятся к случайной величине X . Если существуют конечные положительные константы c ₁ , c ₂ такие, что $${\begin{aligned}\operatorname {E} \left[X_{n}^{2}\right]&\leq c_{1}\operatorname {E} [X_{n}]^{2}\\\operatorname {E} \left[X_{n}\right]&\geq c_{2}\end{aligned}}$$

справедливы для любого n следует , то из неравенства Пэли–Зигмунда , что для любых n и θ в (0, 1) $$\Pr(X_{n}\geq c_{2}\theta )\geq {\frac {(1-\theta )^{2}}{c_{1}}}.$$

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

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

Настройка проблемы

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

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

Пусть K — компонент перколяции корня, а Tn _— множество вершин T , находящихся на расстоянии n от корня. Пусть X _n количество вершин в T _n ∩ K. — Чтобы доказать, что K бесконечно с положительной вероятностью, достаточно показать, что $\limsup _{n\to \infty }1_{X_{n}>0}>0$ с положительной вероятностью. По обратной лемме Фату достаточно показать, что $\inf _{n\to \infty }\Pr(X_{n}>0)>0$. Шварца Неравенство Коши – дает $$\operatorname {E} [X_{n}]^{2}\leq \operatorname {E} [X_{n}^{2}]\,\operatorname {E} \left[(1_{X_{n}>0})^{2}\right]=\operatorname {E} [X_{n}^{2}]\,\Pr(X_{n}>0).$$Поэтому достаточно показать, что $$\inf _{n}{\frac {\operatorname {E} \left[X_{n}\right]^{2}}{\operatorname {E} \left[X_{n}^{2}\right]}}>0\,,$$то есть второй момент ограничен сверху константой, умноженной на квадрат первого момента (и оба ненулевые). Во многих приложениях метода второго момента не удается точно вычислить моменты, но тем не менее можно установить это неравенство.

В данном конкретном приложении эти моменты можно вычислить. каждого конкретного v в T _n Для $$\Pr(v\in K)=p^{n}.$$

С $|T_{n}|=2^{n}$, отсюда следует, что $$\operatorname {E} [X_{n}]=2^{n}\,p^{n}$$это первый момент. Теперь наступает второй момент расчета.

$$\operatorname {E} \!\left[X_{n}^{2}\right]=\operatorname {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}}\Pr(v,u\in K).$$

Для каждой пары v , u в Tn _пусть , w ( v , u ) обозначает вершину в T которая находится дальше всего от корня и лежит на простом пути в T к каждой из двух вершин v и u , и пусть k ( v , u ) обозначают расстояние от w до корня. Для того чтобы v , u оба находились в K , необходимо и достаточно, чтобы три простых пути от ( v , u ) до v , u и корень находились в K. w Поскольку количество ребер, содержащихся в объединении этих трех путей, равно 2 n − k ( v , u ) , получаем $$\Pr(v,u\in K)=p^{2n-k(v,u)}.$$

Число пар ( v , u ) таких, что k ( v , u ) = s , равно $2^{s}\,2^{n-s}\,2^{n-s-1}=2^{2n-s-1}$, для s = 0, 1, ..., n . Следовательно, $$\operatorname {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}}\,\operatorname {E} [X_{n}]^{2},$$что завершает доказательство.

Обсуждение

• Выбор случайных величин X _n в этой схеме был вполне естественным. В некоторых более сложных приложениях метода может потребоваться некоторая изобретательность, чтобы выбрать случайные величины X _n, для которых можно провести рассуждение.
• Неравенство Пэли – Зигмунда иногда используется вместо неравенства Коши – Шварца и иногда может давать более точные результаты.
• При (неверном) предположении, что события v , u в K всегда независимы, имеем $\Pr(v,u\in K)=\Pr(v\in K)\,\Pr(u\in K)$, а второй момент равен квадрату первого момента. Метод второго момента обычно работает в ситуациях, когда соответствующие события или случайные величины «почти независимы».
• В этом приложении случайные величины X _n задаются как суммы $$X_{n}=\sum _{v\in T_{n}}1_{v\in K}.$$ В других приложениях соответствующие полезные случайные величины являются интегралами. $$X_{n}=\int f_{n}(t)\,d\mu (t),$$ где функции f _n случайны. В такой ситуации рассматривается произведение меры µ × µ и вычисляется $${\begin{aligned}\operatorname {E} \left[X_{n}^{2}\right]&=\operatorname {E} \left[\iint f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\right]\\&=\operatorname {E} \left[\iint \operatorname {E} \left[f_{n}(x)\,f_{n}(y)\right]\,d\mu (x)\,d\mu (y)\right],\end{aligned}}$$ где последний шаг обычно обосновывается с помощью теоремы Фубини .

Ссылки

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