А.Н. Соболевский - Конкретная теория вероятностей (1119908), страница 10
Текст из файла (страница 10)
В этой лекции нас будетинтересовать, напротив, относительное распределение вероятности по тем реализациям, которыенаходятся «вдали» от области концентрации вероятности. Говорят, что такие реализации характеризуются большими уклонениями от наиболее вероятных.7.1. Пример. Набор случайных величин X1 , X2 , . . .
, Xn , каждая из которых принимает значение 1 с вероятностью p и −1 с вероятностью 1 − p, можно интерпретировать какслучайное блуждание по целым точкам числовой прямой, начинающееся из начала координат: смещение за k шагов по определению равно X1 +X2 +· · ·+Xk , 1 6 k 6 n. Согласнозакону больших чисел (лекция 4), распределение вероятности среднего смещения X n за nшагов концентрируется на неслучайном значении EX = 1 · p + (−1) · (1 − p) = 2p − 1.Рассмотрим большое уклонение случайного блуждания, т.
е. событие вида X n = α, гдеα 6= 2p − 1 (или, точнее, вида {|X n − α| 6 ε} при малом ε > 0, поскольку случайнаявеличина X n может принимать лишь рациональные значения, а параметр α можно выбратьлюбым вещественным). О таком событии закон больших чисел утверждает лишь то, чтоего вероятность стремится к нулю. Однако, интересно (а для некоторых приложений иважно) выяснить скорость этой сходимости.Кроме того, закон больших чисел утверждает, что относительная доля шагов вправо вреализации случайного блуждания при больших n стремится к p.
Аналогично обстоит делои для т. н. «ленивого» случайного блуждания, когда Xi может принимать с положительными вероятностями три значения ±1 и 0: доли шагов вправо, влево и «на месте» стремятсяк соответствующим вероятностям.Если произошло большое уклонение указанного вида, то нетрудно сообразить, что дляобычного случайного блуждания доля шагов вправо должна составить (1 + α)/2. Однакодля «ленивого» блуждания фиксации одного параметра α уже недостаточно для определения предельных значений долей шагов вправо, влево и «на месте», и для их нахождениянеобходимо привлекать дополнительные идеи.Оказывается, что и «невероятные» события происходят определенным наиболее вероятным образом, т. е.
при подходящей перенормировке концентрация вероятности наблюдается и вне области наиболее вероятных реализаций. Результаты такого типа называются принципами большихуклонений.7.2. Пусть X = (X1 , X2 , . . . , Xn ) — совокупность независимых одинаково распределенных случайных величин.В этой лекции будем предполагать, что каждая из них может принимать конечное множество различных значений, природа которых несущественна.
Чтобы подчеркнуть это (ивыявить связь последущих рассмотрений с теорией информации), примем, что значениямислучайных величин Xi являются не числа, а произвольные символы a, b, . . . , z, образующиеконечный алфавит A. Вероятности символов обозначим pa , a ∈ A, а их общее число валфавите — |A| и будем предполагать, что |A| > 1.Кроме этого, в данной лекции, в отступление от принятой в курсе общей системы обозначений,некоторые случайные величины будут обозначаться строчными буквами.7.3. Каждая реализация совокупности случайных величин X образует случайную nбуквенную строку s = a1 a2 . . .
an в алфавите A. Поскольку величины Xi независимы,вероятность этой строки P(s) = P(a1 a2 . . . an ) равна произведению pa1 pa2 . . . pan . В совокупности вероятности строк образуют распределение на множестве An , число элементовкоторого с ростом n растет экспоненциальным образом, как |A|n .7.4. Обозначим νa (s) относительную частоту буквы a в строке s, т. е. число вхожденийбуквы a в строку s, деленное на n. Тогда νa (s) есть случайная величина, принимающаязначения от 0 до 1. По закону больших чисел (лекция 4) ее распределение при n → ∞сосредотачивается на неслучайном значении pa .7.5. Чтобы описать структуру распределения вероятности по множеству An , определенного в п.
7.3, назовем типом строки s набор ν(s) = (νa (s), νb (s), . . . , νz (s)). Разумеется,для любой строки числа, составляющие ее тип, образуют распределение вероятности посимволам алфавита A. Однако в отличие от исходного распределения p = (pa , pb , . . . , pz ),в котором вероятности pa , a ∈ A, могут быть произвольными вещественными числами изотрезка (0, 1), вероятности νa (s) необходимо являются рациональными числами.|A|−17.6.
Число различных возможных типов равно Cn+|A|−1 и представляет собой многочленстепени |A| − 1 от n.J Доказательство проводится стандартным комбинаторным подсчетом «распределений шаров по ящикам»: каждый тип можно представить одной и только одной строкой вида•• | • || •••• | •••,где |A| − 1 вертикальных черт разделяют «ящики», соответствующие различным буквамалфавита, перечисляемым слева направо, а n точек изображают отдельные символы строкибез учета их порядка (на схеме n = 10 и |A| = 5, причем относительная частота первой12, второй — 10, третьей — нулю и т. д.).
Каждая из таких строк состоит избуквы равна 10n + |A| − 1 символов, ровно |A| − 1 из которых должны быть вертикальными чертами. IПоскольку число всех возможных строк |A|n растет экспоненциально по n, а число возможныхтипов растет лишь как конечная степень n, следует ожидать, что и число строк внутри каждоготипа растет по n также экспоненциально.7.7. Зафиксируем тип µ = (µa ), a ∈ A, и положим m = (ma ) = (nµa ) = nµ. Тогда, обобщая обычные рассуждения при выводе биномиального коэффициента, получаем формулудля числа строк, относящихся к типу µ:|{s : ν(s) = µ}| =n!.ma ! mb ! .
. . mz !7.8. По формуле Стирлинга n! = nn e−nальную асимптотику по n, получим|{s : ν(s) = µ}| =√2πn [1 + O( n1 )]. Учитывая только экспоненци-nn · e−nn!=≈ ma mbz−ma −mb −···−mzma ! mb ! . . . mz !ma mb . . . mmz ·e1= (e−µa log µa e−µb log µb . . . e−µz log µz )n = enH(µ) ,= ma mbzµa µb . . .
µmzгдеH(µ) = H(µa , µb , . . . , µz ) := −Xµa log µa > 0.a∈AФункция H(·) может быть определена не только для типа µ, но и для произвольного распределения вероятности. Она называется энтропией по Шеннону данного распределениявероятности.7.9. Более точная оценка |{s : ν(s) = µ}| при конечных n дается следующими неравенствами, которые включают степенной предэкспоненциальный множитель:|A|−1(Cn+|A|−1 )−1 enH(µ) < |{s : ν(s) = µ}| < enH(µ) .J Заметим, чтоnn = (ma + mb + · · · + mz )n =Xka +kb +···+kz =nn!mka mkb . .
. mkz z ,ka ! kb ! . . . kz ! a bпричем наибольшим слагаемым этой суммы является то, в котором k = m. Действительно,если для некоторого слагаемого kr > mr + 1 и ks 6 ms − 1, то при уменьшении kr иувеличении ks на единицу это слагаемое умножится на коэффициент11krkrms >> 1.ks + 1 mrmrС другой стороны, слагаемые в этой сумме находятся во взаимно однозначном соответствии|A|−1с возможными типами, и поэтому их общее число равно Cn+|A|−1 . Поэтомуn!n!|A|−1mzmzbbmma mmmma mm< nn < Cn+|A|−1b .
. . mzb . . . mz .ma ! mb ! . . . mz ! ama ! mb ! . . . mz ! aОтсюда следуют неравенстваnnn!nn|A|−1(Cn+|A|−1 )−1 ma mb< ma mb,mz <zma mb . . . mzma ! mb ! . . . mz !ma mb . . . mmzа из них вытекают искомые оценки. IТеперь можно вычислить распределение вероятности по различным типам.7.10. Все строки, относящиеся к типу µ, в соответствии с определением п. 7.3 имеютmza mbодну и ту же вероятность pma pb .
. . pz . Поэтому вероятность того, что случайная строкапринадлежит типу µ, удовлетворяет оценкам (проверьте!)|A−1(Cn+|A|−1 )−1 e−nD(µkp) < P(ν(s) = µ) < e−nD(µkp) ,где введена относительная энтропия распределения µ по отношению к распределению pXµaD(µkp) :=µa log.paa∈AДля лучшего понимания полученных результатов необходимо разобраться в свойствах энтропииШеннона и относительной энтропии.7.11. Пусть алфавит A содержит всего две буквы a, b, так что µb = 1 − µa и H(µ) =H(µa ) = −µa ln µa − (1 − µa ) ln(1 − µa ). Полагая 0 ln 0 = 0 по непрерывности, получаем,что функция H(µa ) обращается в нуль при µa = 0 или µa = 1. Ее производные имеют вид−1H 0 (µa ) = − ln µa − 1 + ln(1 − µa ) + 1 = ln(1 − µa ) − ln µa , H 00 (µa ) = −µ−1< 0,a − (1 − µa )т. е.
функция H(µa ) выпукла вверх на отрезке 0 6 µa 6 1 и достигает максимальногозначения ln 2 при µa = 1 − µa = 21 . Заметим, что график этой функции симметриченотносительно замены µa 7→ 1 − µa , переставляющей концы отрезка, и имеет в этих концахвертикальные касательные.7.12. Множество распределений вероятностиnoXp = (pa , pb , . . . , pz ) : pa > 0 для всех a ∈ A,pa = 1a∈Aобразует вероятностный симплекс размерности |A| − 1 (см. рис.
к п. 7.16), грани которого в свою очередь также являются вероятностными симплексами меньших размерностей(проверьте!). В частности, при |A| = 2 вероятностный симплекс представляет собой отрезок (ср. п. 7.11). Энтропия по Шеннону H(µ) — гладкая, строго выпуклая вверх функцияна вероятностном симплексе, достигающая максимального значения ln |A| на равномерномраспределении и симметричная относительно действия группы перестановок вершин симплекса.7.13.
Вспомогательный факт из выпуклого анализа. Предположим, что Φ(p) —непрерывно дифференцируемая выпуклая функция векторного аргумента. Тогда для всехµ имеет место неравенствоΦ(µ) > Φ(p) + ∇Φ(p) · (µ − p),причем если функция Φ строго выпукла (т. е. ее график не содержит линейных участков,ср. У1.1), то равенство возможно только при µ = p.Φ(p)Φ(µ)Φ(p) + ∇Φ(p) · (µ − p)pµJ См.
рисунок. IP7.14. Функция Φ(p) = a∈A pa log pa строго выпукла. Если векторы µ и p — распределения вероятности, тоD(µkp) = Φ(µ) − Φ(p) − ∇Φ(p) · (µ − p)и поэтому D(µkp) > 0, причем равенство достигается лишь при µ = p.J Очевидно, d2 (p log p)/dp2 = 1/p > 0 при p > 0. Функция Φ(p) является суммой выпуклых слагаемых и поэтому сама выпукла. Заметим теперь, что ∂ Φ(p)/∂pa = log pa + 1, ивычислим правую часть доказываемого равенства:XΦ(µ) − Φ(p) − ∇Φ(p) · (µ − p) =[µa log µa − pa log pa − (log pa + 1)(µa − pa )] =a∈A=Xa∈A[µa log µa − pa log pa − µa log pa + pa log pa ] =Xa∈Aµa logµa= D(µkp),paпосколькуPa∈Aµa =Pa∈Apa = 1. IТаким образом, относительная энтропия D(µkp) есть мера несовпадения распределений µ и p,обращающаяся в нуль тогда и только тогда, когда ее аргументы совпадают (хотя ее нельзя считать«расстоянием», потому что при µ → p она стремится к нулю не линейно, а квадратично — это какбы «деформированный» квадрат расстояния).В частности, энтропия Шеннона H(p) с точностью до знака и постоянного слагаемого − ln nсовпадает с относительной энтропией D(pku) по отношению к равномерному распределению u =111( |A|, |A|, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
