Неравенства Маркова и Бьене-Шебышева

Марков и Бьене-Шебышев неравенства

Глубокое погружение в значение двух границ и в замечательную серию событий, которые привели к их открытию

Не часто вселенная говорит вам, что что-то просто невозможно сделать. Неважно, насколько вы умны или насколько щедры ваш банковский счет, или какой угол вселенной вы считаете своим. Когда вселенная говорит «Невозможно», нет никаких двух путей вокруг этого. В науках такие невозможности часто выражаются в виде ограничений на значение некоторой величины. Известным примером является открытие Альберта Эйнштейна в 1905 году, согласно которому, когда вы отпускаете фотон на свободу в пустоте космического пространства, нет ничего — несомненно ничего — что могло бы обогнать его. Сотни таких ограничений или границ были открыты и доказаны. Вместе они образуют забор вокруг природы реальности.

Неравенства Маркова и Бьенайма-Шебышева — это две такие границы, которые глубоко сформировали наше понимание ограничений, которые природа накладывает на то, насколько часто могут происходить случайные события.

Открытие и доказательство неравенства Маркова приписывается блестящему и страстному принципиальному русскому математику Андрею Андреевичу Маркову (1856–1922).

За неравенство Бьенайма-Шебышева отвечают два человека: гигант теории вероятностей и учитель Маркова — непреклонный Пафнутий Львович Чебышев (1821–1894), а также французский коллега и друг Чебышева Ирене-Жюль Бьенайме (1796–1878).

• Режиссеры Гильермо дель Торо и Тим Бёртон имеют два разных взгляда на искусственный интеллект
• Стивен ДиАнджелис, основатель и генеральный директор компании Enterra Solutions – серия интервью
• Эффект Ломбарда и как он может помочь при нарушении слуха

К открытию этих неравенств — особенно неравенства Бьенайма-Шебышева — привязана такая замечательная история, что просто недостаточно просто вывести математику, не касаясь персонажей и историй, породивших ее. Я постараюсь рассказать эти истории. И, делая это, я поставлю контекст для объяснения математики, которая лежит в основе этих неравенств.

Я начну с неравенства Маркова, затем покажу, как неравенство Бьенайма-Шебышева возникает из нескольких простых переменных замен в неравенстве Маркова. Для дополнительного удовольствия мы заявим нашу большую награду — доказательство Слабого закона больших чисел (WLLN), показав, как WLLN возникает, почти без усилий, из другого набора переменных замен, но уже в неравенстве Бьенайма-Шебышева.

Неравенство Маркова

Имя Маркова ассоциируется с «Цепями Маркова», «Процессами Маркова» и «Моделями Маркова». Строго говоря, марковская цепь — это то, что создал А. А. Марков. Но вклад Маркова в математику выходил далеко за пределы марковских цепей и теории вероятности. Блестящий исследователь, Марков опубликовал более 120 статей, охватывающих широкий круг идей в теории чисел, непрерывных дробей, исчислении и статистике. Кстати, Марков большую часть своих работ публиковал в русскоязычных журналах, в отличие от своего докторского научного руководителя П. Л. Чебышева, который публиковался главным образом в западноевропейских, особенно французских, изданиях.

В 1900 году, в период, когда Марков, вероятно, был на пике своей карьеры, он опубликовал фундаментальную книгу по теории вероятностей под названием «Исчисление вероятностей».

Книга вышла в 4-х изданиях, а также на немецком языке. Марков специально опубликовал третье издание своей книги в 1913 году, чтобы отметить 200-ю годовщину Слабого закона больших чисел. Большая часть материала в третьем издании посвящена Слабому закону больших чисел. Однако в лемме, Марков доказал закон, который оказался настолько важным для статистической науки, что он часто используется в качестве отправной точки для доказательства самого Слабого закона больших чисел.

Марков показал следующее:

Представьте себе любую неотрицательную случайную величину X. X может представлять собой что-то обыденное, например, время пробуждения утром. Или что-то гигантское, например, число звезд в галактике. X может быть дискретным или непрерывным. X может иметь любое распределение вероятностей. Другими словами, X может представлять собой любое неотрицательное случайное явление. Теперь выберите значение – любое значение – из диапазона X. Обозначим это значение как ‘а’. Марков показал, что природа накладывает верхнюю границу на вероятность наблюдения значения X, которое больше или равно выбранному значению ‘а’. И эта верхняя граница уменьшается с ростом ‘а’. Чем больше выбранное значение ‘а’, тем ниже вероятность наблюдения другого значения ‘b’, которое превышает ‘а’. Другими словами, природа не любит выбросы.

Для наглядности рассмотрим следующий график. Он показывает частотное распределение дохода на душу населения в округах двадцати самых богатых штатов США.

Здесь случайная величина X представляет собой доход на душу населения в случайно выбранном округе.

Теперь давайте поработаем с некоторым порогом ‘а’ для дохода на душу населения. На следующей панели изображения красные области представляют X ≥ а, где а = $50000, $70000 и $80000.

Вероятность P(X ≥ а) – это отношение площади красной области к общей площади под гистограммой. Легко видеть, что эта вероятность P(X ≥ а) уменьшается с ростом ‘а’. Она обратно пропорциональна ‘а’. Теорема Маркова накладывает определенную верхнюю границу на эту вероятность, которая обратно пропорциональна значению ‘а’. И это соотношение верно независимо от распределения X.

Но это еще не все, что показал Марков.

В рамках той же неравенства, Марков также показал, что среднее значение X прямо влияет на вероятность наблюдения X >= а. Чем больше среднее значение X, тем выше верхняя граница этой вероятности, и наоборот. Другими словами, по мере того как вероятностная масса X смещается к верхнему концу диапазона X, верхний предел P(X >= а) также увеличивается. Следовательно, если вероятностная масса X смещается к нижнему концу, делая ее “низкой”, то вероятность наблюдения большого значения X уменьшается.

Некоторые из этого могут звучать как обычный здравый смысл, но гениальность Маркова заключается в установлении математически точного соотношения между ‘a’, P(X>=a) и средним значением (также известным как ожидаемое значение) X, обозначенным как E(X). Он показал, что:

Доказательство неравенства Маркова

Существует несколько способов доказать неравенство Маркова. Я расскажу о простой технике, которая работает независимо от того, является ли X дискретной или непрерывной. X должен быть только неотрицательным.

Как и раньше, работаем с некоторым пороговым значением ‘a’, которое вас интересует.

Теперь давайте определим случайную величину I такую, что I = 0, когда 0 ≤ X < a, и I = 1, когда X ≥ a. В статистической терминологии I называется индикаторной переменной.

Рассмотрим случай, когда X ≥ a. Умножим обе стороны на I:

XI ≥ aI

Когда X ≥ a, I = 1. Таким образом, XI = X.

И, следовательно,

X ≥ aI, когда I = 1 (Давайте запомним этот результат).

Поскольку X неотрицательное, 0 ≤ X, и для некоторого положительного ‘a’ X может быть меньше ‘a’, или больше или равно ‘a’. Мы уже рассмотрели случай X больше или равно a. Поэтому рассмотрим случай, когда 0 ≤ X < a.

По определению I, когда X < a, I = 0.

Следовательно, aI = a0 = 0

Поскольку предполагается, что X неотрицательное, то есть X > 0 и aI = 0, X ≥ aI

Таким образом, независимо от того, I = 1 или I = 0, aI <= X.

Применим оператор ожидания E(.) к обеим сторонам этого неравенства:

E(aI) <= E(X)

Вынося константу ‘a’ за скобки:

aE(I) <= E(X)

Давайте поработаем с E(I). Случайная величина I может принимать только два значения: 0 и 1, соответствующие случаям X < a и X≥ a. Вероятность, связанная с каждым событием, равна P(X < a) и P(X >= a) соответственно. Итак,

E(I) = 0P(X < a) + 1P(X >= a) = P(X >= a)

Возвращая этот результат обратно в неравенство aE(I) <= E(X), у нас есть:

aP(X >= a) <= E(X)

И, таким образом:

P(X >= a) <= E(X)/a, что является неравенством, которое доказал Марков.

Неравенство Бьеноме-Чебышева

Неравенство Бьеноме-Чебышева утверждает, что вероятность наблюдения значения, отличающегося на ‘a’ единиц от среднего значения случайной величины, ограничена аналогично неравенству Маркова. Другими словами, природа накладывает верхнюю границу на вероятность P(|X — E(X)| >= a). И эта верхняя граница обратно пропорциональна a² и прямо пропорциональна тому, насколько X распределена вокруг своего среднего значения, или, другими словами, к дисперсии X. Символьно неравенство Бьеноме-Чебышева записывается следующим образом:

Как и в случае с неравенством Маркова, великолепие неравенства Бьеноме-Чебышева заключается в том, что оно не делает никаких предположений о вероятностном распределении X. X может быть нормально распределенной, экспоненциально распределенной или гамма-распределенной. X может быть распределенной в форме тени коровы, и неравенство Бьеноме-Чебышева все равно остается надежным.

Небольшой экскурс в историю неравенства Бьеноме-Чебышева

Захватывающая история связана с открытием неравенства Бьеноме-Чебышева. Сначала есть причина, по которой имя Жюля Бьеноме должно и действительно стоит перед именем Чебышева в этом неравенстве.

В 1853 году французский математик Ирене-Жюль Бьеноме опубликовал одну из самых важных статей в журнале Французской академии наук. В статье Бьеноме рассматривал метод наименьших квадратов Лапласа. Однако, в рамках этой работы, он стал формулировать и доказывать неравенство Бьеноме-Чебышева (которое тогда могло быть только неравенством Бьеноме, так как Чебышев нигде не фигурировал). Но Бьеноме, верный своему скромному характеру и полностью поглощенный задачами метода наименьших квадратов Лапласа, не смог должным образом отметить важность своего открытия, и оно осталось практически незамеченным. И, возможно, это один из самых важных результатов в теории вероятностей мог бы пропасть, если бы Пафнутий Львович Чебышев не родился с атрофированной ногой.

В раннем летнем дне 1821 года, когда 25-летний Бьеноме только начинал свою службу государственным служащим в Министерстве финансов Франции, в деревне, находящейся в 100 милях к югу от Санкт-Петербурга, в имперской России родился Пафнутий Львович Чебышев. Чебышев был одним из девяти детей и с раннего возраста проявлял исключительную способность как в механике, так и в математике. Отец Чебышева был офицером армии, который отбил нападение Наполеона в его катастрофической (для Наполеона, очевидно) атаке на Россию в 1812 году. Ирония истории состоит в том, что всего через два года, в беспорядочном послевоенном времени отступления Наполеона, Жюль Бьеноме помог Наполеону отбиться от русских, австрийцев и пруссаков, наступающих на Париж. Наполеон, конечно же, не сумел защитить Париж и был отправлен в ссылку на остров Эльба.

Вся эта история произошла задолго до рождения Пафнутия Львовича. Но учитывая его военное происхождение и семейную традицию, если бы у него не было врожденной атрофии ноги, П. Л. Чебышев, скорее всего, последовал бы по стопам своих братьев и сестер в русскую армию царя, и история вероятности приняла бы совершенно другой оборот. Но инициация Чебышева в математику и позже в русскую академию не были единственными катализаторами его знакомства с Бьеныаме. И, что более важно, его защитником вклада последнего в неравенство Бьеныаме-Чебышева.

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

Всякий раз при возможности Чебышев путешествовал во Францию и другие западноевропейские столицы, и почти половина его 80 статей была опубликована в западноевропейских журналах. Многие из них появились в Journal des Mathématiques Pures et Appliquées (Журнал чистой и прикладной математики), издаваемом французским математиком Жозефом Лиувиллем. Именно во время своего европейского тура 1852 года Чебышев познакомился с Бьеныаме, взаимовыгодная дружба которого позволила Чебышеву получить доступ к многим европейским ученым и издателям, а также позволила публиковать работы Бьеныаме в ведущих французских и российских журналах.

Конечно, ключевой работой было открытие Бьеныаме в 1853 году неравенства, названного его именем. Это приводит нас к изучению этого неравенства.

Что на самом деле доказал Бьеныаме в своей статье 1853 года:

Предположим, что вы случайным образом выбираете выборку размером N из популяции значений, среднее и дисперсия которых равны соответственно μ и σ². Пусть X_bar будет средним вашей случайной выборки. Кстати, можно показать, что среднее значение выборки X_bar само по себе является случайной величиной со своим собственным математическим ожиданием и дисперсией, равными соответственно μ и σ²/N. Если это смущает вас, не беспокойтесь. Вскоре я покажу, как вывести математическое ожидание и дисперсию среднего значения выборки. Возвращаясь к теме, Бьеныаме показал следующее:

Сейчас вы можете задаться вопросом, когда же Чебышев вступает в веселую сферу открытий Бьеныаме таким образом, что его имя прикрепляется к этому неравенству.

Случается так, что через четырнадцать лет после публикации Бьеныаме своего неравенства Чебышев, совершенно не подозревая о открытии Бьеныаме, публикует другую версию этого неравенства в выпуске 1867 года журнала Жозефа Лиувилля. Имейте в виду, что это была эпоха до Google, до CiteSeer, до телефона. Так что сказать, что ученые того времени не были полностью осведомлены о “предыдущей работе”, едва намекает на масштаб проблемы.

Следует отметить, что Чебышёв, в своей статье, опубликованной в 1874 году, полностью приписывал открытие этого неравенства Бьенаме:

«Простое и строгое доказательство закона Бернулли, которое можно найти в моей заметке под названием: Des valeurs moyennes, является только одним из результатов, легко выведенных из метода господина Бьенаме, который сам привел к доказательству теоремы о вероятностях, из которой закон Бернулли следует непосредственно»

В последующие годы, то, что стало известно как неравенство Чебышёва (или, более точно, неравенство Бьенаме — Чебышёва), является версией, которая просто применяется к любой случайной величине X с математическим ожиданием E(X) и конечной дисперсией Var(X).

Неравенство Бьенаме — Чебышёва утверждает, что для любого положительного значения ‘a’ вероятность P(|X — E(X| ≥ a) ограничена следующим образом:

Доказательство неравенства Бьенаме — Чебышёва

Неравенство, которое Марков доказал (и которое носит его имя) в издании его книги “Исчисление вероятностей” 1913 года, часто используется для доказательства неравенства Бьенаме — Чебышёва. Используя неравенство Маркова в качестве отправной точки, легко доказать результат. Мы доказываем его следующим образом:

Рассмотрим случайную величину X со средним значением E(X). Теперь определим другую случайную величину Z = (X — E(X))². Квадратный член гарантирует, что Z неотрицательна, что позволяет нам применить неравенство Маркова к Z. Допустим, пороговое значение Z, которое мы назовем a². Вероятность того, что наблюдаемое значение Z соответствует или превышает a², равна P(Z >= a²). Применяя неравенство Маркова к Z и a², получаем следующее:

Используя выражение выше, мы можем вывести неравенство Бьенаме — Чебышёва следующим образом:

Уравнение (3) является неравенством Бьенаме-Чебышёва (или просто неравенством Чебышёва).

Вместо работы с произвольным порогом ‘a’, полезно выразить ‘a’ через стандартное отклонение σ X следующим образом:

Вышеуказанное доказательство также открывает прямой путь к доказательству оригинального результата Бьенайме, показанного в его публикации 1853 года, а именно:

Начиная с уравнения (2) и заменяя X на выборочное среднее X_bar и a² на k²σ², мы получаем результат Бьенайме, полученный примерно в 1853 году, следующим образом:

Уравнения (4) и (4a) представляют перед нами увлекательный результат. Они говорят, что вероятность встретить наблюдение, находящееся не менее чем на k стандартных отклонений от среднего, ограничена сверху, и эта верхняя граница обратно пропорциональна k².

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

Когда выражено таким образом, неравенство Бьенайме-Чебышева придает математическое выражение афоризмам вроде “Если звучит слишком хорошо, чтобы быть правдой, вероятно, это так”, или, наиболее известному среди ученых: “Необычные утверждения требуют необычных доказательств”.

Чтобы проиллюстрировать работу этого неравенства, рассмотрим следующий набор данных среднесуточной температуры, записанных в Чикаго 1 января каждого года. В нем содержится 100 наблюдений, охватывающих период с 1924 по 2023 год:

Пунктирная черная горизонтальная линия в центре графика изображает выборочное среднее значение 24,98 F. Цветные горизонтальные линии изображают значения температуры плюс/минус 1,25, 1,5, 1,75 и 2 раза стандартного отклонения выборки данных. Эти линии стандартного отклонения дают нам представление о границах, в пределах которых, скорее всего, будут находиться большинство температур.

Применяя неравенство Бьенайме-Чебышева, мы можем определить верхнюю границу вероятности P(|X — E(X)| ≥ kσ), где X представляет собой наблюдаемую среднюю температуру 1 января в случайно выбранном году. E(X) = 24,98 F, σ = 10,67682 F и k = 1, 1,25, 1,5, 1,75 и 2,0. В следующей таблице указаны эти верхние границы вероятности в столбце 1/k²:

Последний столбец таблицы показывает фактические вероятности наблюдения таких отклонений в выборке данных. Фактические наблюдаемые значения в выборке данных удобно находятся в пределах верхних границ вероятности, сгенерированных неравенством Бьенайме-Чебышева.

Вы могли заметить, что вероятностные границы, генерируемые неравенством Бьенайме-Шебышева, довольно широкие. Например, при k=1 (что соответствует событию, находящемуся в пределах 1 стандартного отклонения от среднего), неравенство расчитывает верхнюю границу вероятности как 1/1² = 1.0, или 100%. Это делает эту конкретную границу практически бесполезной.

Тем не менее, для всех значений k > 1, неравенство является весьма полезным. Его полезность также заключается в том, что оно не предполагает какую-либо конкретную форму распределения случайной величины. Фактически, оно идет даже дальше в своей применимости. В то время как неравенство Маркова требует, чтобы случайное явление производило строго неотрицательные наблюдения, если вы обратите внимание, неравенство Бьенайме-Шебышева не делает таких предположений о X.

Неравенство Бьенайме-Шебышева также дает нам простое и беспроигрышное доказательство Слабого закона больших чисел. Фактически, в 1913 году Марков использовал это неравенство, чтобы продемонстрировать доказательство СЗБЧ в своей книге по теории вероятностей, и это существенно то же самое доказательство, которое используется во многих учебниках сегодня.

Слабый закон больших чисел (и его доказательство)

Предположим, что вы собираете случайную выборку из теоретически бесконечно большой популяции. Пусть размер выборки будет N. У этой случайной выборки есть выборочное среднее X_bar. Поскольку вы имеете дело только с выборкой, а не со всей популяцией, ваше выборочное среднее скорее всего будет находиться на некотором расстоянии от истинного среднего значения популяции μ. Это ошибка в вашем выборочном среднем. Вы можете выразить абсолютное значение этой ошибки как |X_bar — μ|.

СЗБЧ говорит о том, что для любого положительного допуска ϵ на ваш выбор, вероятность ошибки в выборочном среднем, превышающей ϵ, будет стремиться к нулю с увеличением размера выборки N до бесконечности. Не имеет значения, насколько маленьким будет ваш допуск ϵ. P(|X_bar — μ| >= ϵ) будет стремиться к нулю при стремлении размера выборки N к бесконечности.

СЗБЧ имеет богатую историю открытий, которая простирается более трех веков с такими математическими гениями, как Якоб Бернулли в 1713 году и включает таких гигантов, как Де Муавр, Лаплас, Лакруа, Пуассон и наши друзья Бьенайме и Шебышев — которые внесли свой вклад в его развитие. И благодаря неравенству Бьенайме-Шебышева, доказательство СЗБЧ идет так же легко, как вода, текущая вниз по склону.

Доказательство Слабого закона больших чисел

Как и во многих других вещах в статистике, мы начинаем доказательство с получения случайной выборки размера N из популяции. Обозначим эту выборку как X1, X2, X3, …, XN. Полезно думать о X1, X2, X3, …, XN как о наборе из N переменных, как о наборе из N слотов, каждый из которых заполняется случайно выбранным значением из популяции при каждом выборе выборки. Таким образом X1, X2, X3, …, XN сами по себе являются случайными переменными. Кроме того, поскольку каждая из X1, X2, X3, …, XN получает случайное значение, независимое от других, но все из выборочной популяции, они являются независимыми, одинаково распределенными (н.о.р.) случайными переменными.

Для любой случайно выбранной выборки выборочное среднее X_bar может быть вычислено следующим образом:

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

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

Теперь применим неравенство Бьенаме-Шебышева к выборочному среднему X_bar следующим образом:

Как можно так глубоко, так необычайно далеко и так центрально для области статистической науки, как СЗБЧ, может иметь такое невероятно простое доказательство, это одна из тех абсурдностей природы, которую можно только восхищаться. В любом случае, вот вам.

Вместе неравенство Маркова и неравенство Бьенаме-Шебышева, а также Слабый закон больших чисел составляют основу, на которой крупная куча статистической науки уверенно держится. Например, когда вы обучаете статистическую модель (или модель нейронной сети), лучше всего следовать СЗБЧ. Если это не так, оценки коэффициентов не гарантированно сходятся к истинным значениям генеральной совокупности. И это делает вашу технику обучения, ну, в основном бесполезной. СЗБЧ также находит применение в доказательстве другого эпического результата – Центральной предельной теоремы. И это, заслуженно, будет основой моей следующей статьи.

Ссылки и авторские права

Научные статьи

Бьенаме, И. Ж. (1853) Considérations à l’appui de la découverte de Laplace sur la loi de probabilité dans la méthode des moindres carrés,” (“Рассмотрения в поддержку открытия Лапласа о законе вероятности в методе наименьших квадратов.”) C.R. Acad. Sci., Paris 37 309–324. Также опубликовано в “Journal de Mathématiques Pures et Appliquées” (“Журнал чистой и прикладной математики”), Лиувиль, (2) 12 158–176. (1867)

Гели П. Башарин, Эми Н. Лэнгвилл, Валерий А. Наумов, “Жизнь и труды А.А. Маркова”, Линейная алгебра и ее приложения, Том 386, 2004, Страницы 3–26, ISSN 0024–3795, https://doi.org/10.1016/j.laa.2003.12.041.

Брю, Бернар, Франсуа Жонгманс и Юджин Сенета. “I.J. Bienaymé: Family Information and Proof of the Criticality Theorem.” International Statistical Review / Revue Internationale de Statistique 60, no. 2 (1992): 177–83. https://doi.org/10.2307/1403648.

Юджин Сенета “Тристолетняя история Закона больших чисел,” Бернулли, Бернулли 19(4), 1088–1121, (Сентябрь 2013)

Наборы данных

U.S. Bureau of Economic Analysis «Персональный доход по округам, метро и другим районам» в рамках лицензии общественного достояния.

Національна метеорологічна служба «NOAA Онлайн-дані про погоду» для чиказького регіону в рамках ліцензії общественного достоянія.

Изображения

Все изображения в этой статье защищены авторским правом Сачина Дате на условиях CC-BY-NC-SA, если не указаны другие источники и авторские права под изображением.

Спасибо за чтение! Если вам понравилась эта статья, пожалуйста, подпишитесь на меня, чтобы получать советы, инструкции и программные советы по регрессии и анализу временных рядов.