Цепи Маркова (1121219), страница 81
Текст из файла (страница 81)
с начальным распределениеми переходной матрицей P. Докажите, что D(fXm k ) не возрастает по m,где — это инвариантное распределение для матрицы P.Решение. В более общих терминах, пусть (Xm) и (Ym) — это две ц.м.д.в.с одной и той же переходной матрицей P. Тогда расстояние между дискретными распределениями fYm и fXm не убывает по m:и происходит переход от с.в. X и Y к с.в.
X 0 и Y 0 , где д.р.в./в.п.р. fX0 и fY 0выражаются через с fX и fY по формуламPPf (x)pxy ,f (x)pxy ,x∈S Xx∈S YZZfX0 (y) =fY 0 (y) =(3.6.39) fX (x)p(x, y) dx, fY (x)p(x, y) dx.§ 3.6. Элементы теории управления и теории информацииГлава 3. Статистика цепей Маркова с дискретным временем5161)).(3.6.43)Доказательство базируется на понятии выпуклого порядка междуслучайными величинами (или их распределениями). Эта тема (важная дляряда приложений) будет обсуждаться в следующих томах.Соломон Кульбак (1903–1994) начал свою карьеру как преподаватель математики гимназии в своем родном Нью-Йорке, но вскоре перешел в разведывательную службу армииСША (Signal Intelligence Service, SIS, СИС).
Он служил долго и добился выдающихсяуспехов как в СИС, так и в его правопреемнике, Агентстве национальной безопасности(National Security Agency, NSA, НСА). В конце 1950-х гг. Кульбак стал руководителемисследовательских работ в НСА и работал на этой должности вплоть до выхода на пенсиюв 1962 г. После того он стал профессором в университете Джорджтауна. В 1942 г. майораКульбака командировали в Великобританию ознакомиться с тем, как англичане в Блетчлипарке дешифруют сообщения, генерируемые немецкими шифровальными машинами. Он внессвой вклад в работу команды из Блетчли-парка и после возвращения в США возглавиляпонскую секцию НСА. Его очень любили коллеги как по академической работе, так и поработе в спецслужбах, за то что он был «абсолютно бесхитростным, вы всегда знали, что онимеет в виду.»Ричард Лейблер (1914–2003) был американским математиком и криптографом.
Онучаствовал во Второй мировой войне, в битвах при Иводзиме и в операции на Окинаве.Наиболее выдающийся период его жизни связан с Институтом аналитических оборонных исследований (Institute of Defense Analysis) в Принстоне и с НСА. Он участвовал в программе,позволившей команде НСА решить ранее не поддающиеся расшифровке советские разведывательные сообщения, поступавшие в рамках проекта под кодовым названием ВЕНОНА(VENONA).Статья Кульбака и Лейблера (Kullback S., Leibler R.
A. On information and sufficiency// Annals of Mathematical Statistics. 1951. V. 22. P. 79–86), в которой было сформулированопонятие информационной дивергенции, является, по-видимому, наибольшим академическимдостижением авторов. Статья появилась в разгар холодной войны и была немедленнозамечена в Советском Союзе, где существовало собственное мощное криптографическоеподразделение, связанное со спецслужбами. Следует отметить, что контроль за содержанием публикаций в рамках советской системы был, несомненно, более жестким, и статья,написанная авторами, имеющими такой статус, как Кульбак и Лейблер, имела мало шансовна публикацию в открытой академической печати.
Однако в Советском Союзе существовала достаточно развитая сеть журналов и периодических изданий с грифами «секретно»и для «служебного пользования», доступных только сотрудникам определенных учреждений, имеющих так называемый «допуск» (получаемый только после тщательной проверкии только на время выполнения соответствующих служебных обязанностей). Было возможнодаже получить степень кандидата либо доктора наук или быть избранным в Академию наукСССР при очень небольшом числе публикаций, доступных широкой публике. (Таких ученыхчасто называли «закрытыми» академиками; наиболее известным из них был академик АндрейДмитриевич Сахаров.)§ 3.7. Скрытые марковские модели, I.Оценивание состояний марковских цепейТеперь приступим к изучению скрытых марковских моделей (с.м.м.).Рассмотрим следующую ситуацию.
Имеется ц.м.д.в. (X m) на пространствесостояний I, скажем I = {1, . . . , s}, с (полностью или частично) неизвестным начальным распределением = ( i) и (полностью или частично)неизвестной переходной матрицей P = (pij), i, j = 1, . . . , s. В дополнение к этому цепь не является полностью наблюдаемой. Например, можнонаблюдать значения Xtk только в некоторые избранные моменты времениt0 , t1 , .
. . или можно фиксировать только значения b(X 1), b(X2), . . . , гдеb : I → K неизвестная функция состояния, возможно случайная, со значениями в новом «алфавите» K = {1, . . . , κ} (мы знаем, что неизвестногомы не знаем). В типичных приложениях κ < s, а функция b многозначная.§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей519В задаче «без ограничений» пара ( , P) пробегает все множество R (см.соотношение (3.1.5)) или его подмножество Rin (см. соотношение (3.1.6)).Если мы избавимся от неопределенности, связанной с начальным распределением (а именно рассмотрим стационарную ц.м.д.в. с инвариантнымраспределением ), то удобно будет предположить, что P ∈ P IA . Однако мыможем обладать априорной информацией о ( , P), например что матрицаP внедиагональная (т.
е. P ∈ Poff-diag ; ср. с соотношением (3.1.11)) или Pэрмитова (т. е. P ∈ Psymm ; ср. с соотношением (3.1.12)). Функцию b такжеможно до некоторой степени конкретизировать, выделив (известный) классфункций (например, для s = κ функция b может быть перестановкой).В этом случае мы имеем дело с задачей «с ограничениями».Нередко возникает задача интерполяции, когда мы наблюдаем ц.м.д.в.точно, но не во всякие моменты времени: мы видим ее состояния тольков (целые) моменты времени t0 , .
. . , tm , где 0 6 t0 < . . . < tm и tm >> m. Возможна ситуация, когда нужно скомбинировать две задачи, но дляпростоты будем изучать их в отдельности.Задача состоит в том, чтобы оценить и P по фиксированной цепочкенаблюдаемых значений 0 = b(X0), . . . , n = b(Xn) или по заданнойпоследовательности состояний xn1 , xn2 , .
. . , xnm . Глава 3. Статистика цепей Маркова с дискретным временем0= ... из нулей и единиц.Пример 3.7.1. Вы наблюдаете цепочку518nВы подозреваете, что это запись (функции) цепи Маркова (X m) с тремя состояниями, скажем A, B и C:mX0x0Xnxn= b(xm), где X = ... , x = ... .Вы думаете, что цепь симметрична, т. е. ее матрица перехода P = (p ij),i, j = A, B, C, имеет видP=1 − 2pppp1 − 2pppp1 − 2p!1206p6 .Возможны несколько предположений относительно того, какова функцияb: а) на двух состояниях b равна 0, скажем b(A) = b(B) = 0, а наоставшемся состоянии она равна 1: b(C) = 1, или наоборот; б) на двухсостояниях b равна 0 с вероятностью q и 1 с вероятностью 1 − q, в товремя как на оставшемся состоянии она равна 1 с вероятностью 1 (илинаоборот, 0 с вероятностью 1), в) каждая из величин b(A), b(B) и b(C)принимает значение 0 с вероятностями qA , qB и qC или 1 с вероятностями1 − qA , 1 − qB и 1 − qC независимо друг от друга.
Всего имеется 2 возможно-520Глава 3. Статистика цепей Маркова с дискретным временемсти для неслучайной модели (вариант а)), 4 возможности для наполовинуслучайной модели (вариант б)) и (по существу) одна возможность дляполностью случайной модели (вариант в)).
У вас есть также основанияверить, что цепь стационарна, т. е. — это инвариантное распределение= (1/3, 1/3, 1/3).В итоге переходная матрица P определяется параметром p, пробегающим отрезок [0, 1/2] , а для q мы имеем возможности, указанные выше,а именно а), б) и в). Тройка ( , P, b) в контексте этого примера рассматривается как «модель»; если функция b случайна, то, возможно, удобнееговорить о тройке ( , P, Q), где Q представляет набор вероятностей дляслучайных величин b(X0), . . . , b(Xn).Например, состояния A, B и C могут соответствовать определеннымсогласным звукам в (идеализированной) задаче автоматического распознавания речи. Некоторые из этих согласных могут быть распознаны четко,в то время как другие труднее по их спектрограммам отделить одну отдругой.Предположим, что вы хотите сравнить два отдельных семейства моделей:а) семейство моделей с детерминированной (т. е.
неслучайной) функцией b, обозначенной Zдет = (P, bдет ), гдеbдет (A) = bдет (B) = 1 и bдет (C) = 0,и б) полностью случайную модель, обозначенную Z сл = ( , P, Q), где(1 с вероятностью q? ,? = A, B, C независимо друг от другаbсл (?) =0 с вероятностью 1 − q? ,и qA = qB = q1 , qC = q2 .Итак, вычислим суммарные функции правдоподобия:Lдет ( ; Zдет) =nXYxpxi−1 xi [1(i= 1, xi = A или B) + 1(i= 0, xi = C)]i=1(3.7.1)и§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей521числениях.) Для заданного функция Lдет — полином степени n переменной p ∈ [0, 1/2] , в то время как Lсл — полином от переменных p ∈ [0, 1/2]и q1 , q2 ∈ [0, 1] .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
