А.Н. Соболевский - Конкретная теория вероятностей (1119908), страница 11
Текст из файла (страница 11)
. . , |A|). Некоторую непоследовательность в выборе знаков в определениях H(p) (п. 7.8)и D(µkp) (п. 7.10) допускают для того, чтобы обе величины были положительными.Следствием п. 7.10 является следующий аналог закона больших чисел, в котором рассматривается сходимость не сумм случайных величин, а типов строк, вместо расстояния фигурируетотносительная энтропия, а сходимость происходит с экспоненциальной скоростью.7.15. Для сколь угодно малого δ > 0 полная вероятность множества строк, типы которых отличаются от p по относительной энтропии не менее, чем на δ, стремится к нулю:|A|−1P(D(ν(s)kp) > δ) 6 Cn+|A|−1 e−nδ −−−−→ 0.n→∞J Действительно, для любого такого типа µ, что D(µkp) > δ, имеем P(µ) < e−nδ согласно|A|−1п.
7.10, а полное число таких типов не превышает Cn+|A|−1 . I7.16. Теорема Санова. Пусть Π — непустое замкнутое подмножество вероятностногосимплекса, совпадающее с замыканием своей внутренности, и D(Πkp) := minµ∈Π D(µkp).Тогда1− log P(ν(s) ∈ Π) −−−−→ D(Πkp).n→∞npcA = {a, b, c}ppbµ?ΠpaJ Пусть Πn — множество тех типов n-буквенных слов, которые лежат в Π. Смысл топологического условия на Π в том, чтобы множество Πn было непустым и величина D(Πn kp)стремилась к D(Πkp) при n → ∞; это условие при желании нетрудно ослабить.
Если оновыполнено, то из п. 7.15 следует оценка сверху|A|−1P(ν(s) ∈ Πn ) 6 Cn+|A|−1 e−nD(Πn kp) .Для оценки снизу можно использовать тот класс µ?n ∈ Πn , на котором D(µkp) достигаетминимума на Πn . Тогда|A|−1P(ν(s) ∈ Πn ) > (Cn+|A|−1 )−1 exp(−nD(Πn kp))согласно п. 7.10. IМожно получить и результат о концентрации вероятности внутри Π, аналогичный п. 7.15.7.17. Если область Π выпукла, то минимум D(µkp) достигается на ней в единственнойточке µ? .
Для любого δ > 0 условная вероятность множества строк внутри Π, типы которыхотличаются от µ? по относительной энтропии не менее, чем на δ, стремится к нулю:P(D(ν(s)kp) > δ + D(Πkp))6 P (n) e−nδ −−−−→ 0,n→∞P(ν(s) ∈ Π)где P (n) — функция степенного роста по n.7.18. Еще раз случайное блуждание. В примере «ленивого случайного блуждания»положим pa = P(X = −1), pb = P(X = 0), pc = P(X = 1) и введем частоты νa , νb , νc ,имеющие аналогичный смысл. Тогда среднее смещение X n = νc − νa является аффиннойфункцией на вероятностном симплексе, а множество Π, выделяемое, например, условиемνc − νa 6 α < pc − pa , очевидно удовлетворяет условиям теоремы Санова, причем в точкеµ? выполнено равенство µ?c − µ?a = α (почему?).
Значения координат µ? находятся изуравненийln(µa /pa ) + 1 − ξ + η = 0,ln(µb /pb ) + 1 − ξ = 0,ln(µc /pc ) + 1 − ξ − η = 0,которые возникают как условия оптимальности в задаче минимизации относительной энтропии с ограничениями µa +µb +µc = 1 (множитель Лагранжа ξ) и µc −µa = α (множительЛагранжа η). Для определения значений ξ и η получаемpa e−1+ξ−η + pb e−1+ξ + pc e−1+ξ+η = 1,pc e−1+ξ+η − pa e−1+ξ−η = α.8. Большие уклонения II: теорема КрамераВ этой лекции устананавливается принцип больших уклонений для суммы большого числанепрерывных случайных величин (как всегда, независимых и одинаково распределенных).
Это— теорема Краме́ра, один из самых ранних результатов в теории больших уклонений (ГаральдКрамер, 1938). Поскольку в непрерывном случае неясно, как построить подходящий аналог теории типов, здесь используется более прямой подход, а полученный результат ближе к нашему«источнику вдохновения» — закону больших чисел (лекция 4).8.1.
Пусть X1 , X2 , . . . , Xn — набор n независимых, одинаково распределенных скалярныхслучайных величин.Начнем с простого рассуждения, позволяющего почти «из ничего» получить знакомую экспоненциальную асимптотику вероятности большого уклонения: P(a 6 X n 6 b) ∼ e−ns(a,b) . Точныйсмысл употребленного здесь знака «грубой асимптотики» ∼ определяется следующим образом:1ln P(a 6 X n 6 b) = s(a, b) для любых a < b, где s(a, b) > 0.n→∞ n8.2.
− limДоказательство сформулированного утверждения проводится в два этапа (пп. 8.3, 8.4), второй изкоторых — хорошо известная и полезная лемма о субаддитивных числовых последовательностях.8.3. Последовательность неотрицательных чисел − ln P(a 6 X n 6 b) субаддитивна:для любых n, n0 > 1− ln P(a 6 X n+n0 6 b) 6 − ln P(a 6 X n 6 b) − ln P(a 6 X n0 6 b).J Неотрицательность очевидна, поскольку вероятности всегда заключены между 0 и 1.Заметим, что неравенства1a 6 X n+n0 =(X1 + X2 + · · · + Xn + Xn+1 + Xn+2 + . . . Xn+n0 ) 6 bn + n0заведомо выполнены, если имеют место неравенства11a 6 X n = (X1 + X2 + · · · + Xn ) 6 b, a 6 0 (Xn+1 + Xn+2 + · · · + Xn+n0 ) 6 bnn(действительно, домножим первое из них на n/(n+n0 ), второе на n0 /(n+n0 ) и сложим).
Поэтому событие {a 6 X n+n0 6 b} включает в себя событие, заданное двумя последними неравенствами, т. е. его вероятность не меньше, чем вероятность этого последнего события. Онав свою очередь, благодаря независимости случайных величин X1 , . . . , Xn , Xn+1 , . .
. , Xn+n0 ,может быть представлена как произведение:1P(a 6 X n+n0 6 b) > P(a 6 X n 6 b, a 6 0 (Xn+1 + · · · + Xn+n0 ) 6 b) =n1= P(a 6 X n 6 b) P(a 6 0 (Xn+1 + · · · + Xn+n0 ) 6 b).nЛогарифмируя это произведение и учитывая, что величина (Xn+1 + · · · + Xn+n0 )/n0 распределена так же, как X n0 , после перемены знака получим требуемое неравенство. I8.4. Пусть hn > 0, n = 1, 2, . . . — субаддитивная последовательность, т.
е. hn+n0 6 hn + hn0для любых n, n0 > 1. Тогда последовательность hn /n имеет конечный предел.J Зафиксируем некоторое натуральное число n0 > 1 и представим произвольное n > 1в виде n = qn0 + r, где q — частное, а r — остаток от деления n на n0 : в частности,0 6 r < n0 . Из субаддитивности следует, что hn = hqn0 +r 6 hqn0 + hr 6 h(q−1)n0 + hn0 + hr 6. . . 6 qhn0 + hr (при r = 0 считаем h0 = 0). Имеем1q111hn 6hn + hr 6hn + hr .nqn0 + r 0 nn0 0 nПоскольку max hr = max{h0 , h1 , . . . , hn0 −1 } конечен и не зависит от n, второе слагаемое вправой части при переходе n → ∞ исчезает, и для произвольного n0 > 1 получаем11lim sup hn 6hn .n0 0n→∞ nДанный верхний предел неотрицателен, поскольку hn > 0, и потому конечен.
Обозначимего s и заметим, что s 6 hn0 /n0 для любого n0 , и потому11s 6 lim infhn0 6 lim sup hn 6 s,n0 →∞ n0nn→∞так что в действительности limn→∞ hn /n = s. IПри выводе результата п. 8.2 не было сделано никаких предположений о характере распределения Xi , не требовалось даже, чтобы для этих случайных величин был выполнен закон большихчисел.
В частности, если Xi распределены по Коши, то s(a, b) ≡ 0 (почему?), и в этом случаеполученный результат, конечно, несет мало информации. Наша очередная задача — выразитьs(a, b) через распределение вероятности случайных величин Xi и при этом выделить условия, прикоторых s(a, b) > 0, т. е.
результат п. 8.2 нетривиален.Следующее эвристическое рассуждение показывает, чего нужно ожидать. Допустим, что случайные величины Xi имеют функцию плотности вероятности p(x), и обозначим функцию плотностивероятности величины X n через pn (x). Исходя из только что полученного результата, естественно∗предположить, что pn (x) ∼ e−nκ (x) . ПоэтомуZ b∗P(a 6 X n 6 b) ∼e−nκ (x) dx ∼ exp(−n min κ ∗ (x)),aa6x6bтак что s(a, b) = − limn→∞ ln P(a 6 X n 6 b)/n = mina6x6b κ ∗ (x).
Задача, таким образом, заключается в вычислении функции κ ∗ .8.5. Пусть распределение вероятности случайных величин Xi обладает функцией плотности вероятности p(x) и характеристической функцией ϕ(s) = eη(s) , где η — характеристический показатель (п. 3.11). Повторяя вычисления п. 4.7, получаем для величиныX n = (X1 + X2 + · · · + Xn )/n характеристическую функцию ϕn (s) = (ϕ(s/n))n = enη(s/n) ифункцию плотности вероятности, выраженную через обратное преобразование Фурье:ZZZ11n−isx−isx+nη(s/n)pn (x) =eϕn (s) ds =eds =e−n[iux−η(u)] du,2π2π2πгде в интеграле произведена замена переменной s = nu.Нас интересует асимптотика последнего интеграла при n → ∞. Для ее получения допустим,что переменная u может изменяться на всей комплексной плоскости, и продеформируем контуринтегрирования так, чтобы облегчить оценку интеграла. Соответствующее построение описано вкурсах комплексного анализа и называется «методом перевала».
Напомним основные идеи этогометода.RРассмотрим при n 1 интеграл enΦ(u) du, где Φ аналитическая функция. Вклад в этотинтеграл от участка контура интегрирования, проходящего через точку u, определяется двумяфакторами: абсолютной величиной подынтегрального выражения enΦ(u) в этой точке и его осцилляциями вдоль контура интегрирования. При больших n быстрые осцилляции из-за измененияаргумента функции enΦ(u) , т. е.
Im Φ(u), вдоль контура, приводят к взаимному сокращению вкладов от разных точек и уменьшению абсолютной величины интеграла. Поэтому контур желательнопровести так, чтобы вдоль него исчезала производная Im Φ. При этом условии наибольший вклад винтеграл внесут те точки, в которых абсолютная величина подынтегрального выражения, а значити Re Φ(u), достигает вдоль контура своего максимума. Поскольку в точке максимума производная Re Φ также исчезает, из аналитичности функции Φ (т. е.
независимости ее производной отнаправления дифференцирования) следует, что в такой точке Φ0 (u) = 0.Поскольку функция Re Φ гармоническая, такие точки u∗ являются для нее седловыми, или«точками перевала»: при движении через седловую точку в одних направлениях Re Φ проходитлокальный максимум, а в других — локальный минимум. Если Φ00 (u∗ ) 6= 0, условие Im Φ = constвыделяет два направления наискорейшего изменения Re Φ; контур надо проводить в том из них, вкотором Re Φ имеет локальный максимум. В остальной части контура осцилляции можно специально не подавлять, поскольку при больших n вклад этой части по абсолютному значению и такпренебрежимо мал по сравнению с вкладом от точек перевала, в которых Re Φ достигает наибольших значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
