Цепи Маркова (1121219), страница 90
Текст из файла (страница 90)
Jeff Wu. On the convergence properties of the EM algorithm //Annals Stat. 1983. V. 11. P. 95–103.m→∞k→∞N→∞limПокажите, что для любой начальной точки (0) множество предельныхточек последовательности { (N) }, где (N+1) = A( (N) ), компактно и связно.Решение. Предельные точки образуют замкнутое подмножество компактного множества { ∈ Θ : F ( ) > F ( (0) ) }, поэтому они образуютзамкнутое компактное множество.
В примере 3.9.11 было доказано, чтоусловиеlim || (N+1) − (N) || → 0(3.9.47)(3.9.46)Γ = FA = { ∈ Θ : A( ) = }.Поэтому ∗ не принадлежит C2 . Тогда точка ∗ должна лежать в C1 ; в то жевремя расстояние от нее до C2 меньше . Получаем противоречие, а тогдамножество предельных точек образует связный континуум; ср. с теоремой28.1 из книги [O] .Пример 3.9.12. Предположим, что функция F : Θ → R и отображениеточки в точку A : Θ → Θ взяты из примера 3.9.10, а разрешающее множество Γ совпадает с множеством FA неподвижных точек отображения A:(3.9.45)2.36 dist( ∗ , C2) 63Поэтому существует бесконечная последовательность индексов k (1) << k (2) < .
. . , для которой имеют место неравенства (3.9.44). Предельнаяточка ∗ последовательности { (k (N) ) } является предельной точкой начальной последовательности { (k) } и удовлетворяет соотношению33С учетом условия (3.9.42) из равенства F ( 00) = F ( 0) следует, что 0 —неподвижная точка отображения A. Значит, 00 = 0 , и мы приходимк противоречию. Следовательно, имеет место условие (3.9.47), и множествопредельных точек отображения { (N) } связно.Итог примеров 3.9.10–3.9.12 подведен в следующей теореме.Теорема 3.9.13 (теорема о глобальной сходимости).
Пусть M — мно∈ Θ 7→ M( ) ⊂ Θгозначное отображение точки в множествои F — непрерывно дифференцируемая функция Ляпунова на Θ с разрешающим множеством Γ ⊂ Θ. Зафиксируем алгоритм, порождающий последовательность точек (N+1) = A( (N) ) ∈ M( (N) ) с начальнойточкой (0) . Тогда любая предельная точка ∗ последовательности{ (N) } лежит в множестве Γ, а значения F ( (N) ) монотонно сходятсяк пределу, равному F ( ∗) (откуда следует, что значение F ( ∗) однои то же для всех предельных точек).Предположим вдобавок, что а) отображение A можно продолжить по непрерывности на Θ, а множество Γ взято из формулы(3.9.46), и б) верно соотношение (3.9.47). Тогда множество предельных точек { (N) } компактно и связно.
Далее, предположим, чтонам дополнительно известно, что в) множество предельных точекпоследовательности { (N) } конечно или счетно. Тогда на самом делеэто множество состоит из одной точки, и, значит, последовательность сходится к пределу:и из неравенства (3.9.43) получаем, что).568Глава 3. Статистика цепей Маркова с дискретным временемПриложение IАндрей Андреевич Марков и его времяЦепи Маркова занимают особое место в преподавании теории вероятностей. Они названы именем русского математика, который ввел этопонятие и дал толчок этой элегантной теории в 1910-е гг., за 25 лет дотого, как в 1930-х гг.
было сформулировано определение вероятности в томвиде, в каком оно используется и сегодня. Приведенный ниже краткий биографический очерк основан на доступных авторам источниках. См. такжебиблиографию в статье: Basharin G. P. , Langville A. N. , Naumov V. A. .The Life and Work of A.
A. Markov // Linear Algebra and Applications. 2004.V. 386. P. 3–26.Андрей Андреевич Марков (1856–1922) родился в семье русского чиновника. Отец Маркова, следуя семейной традиции, начал свою карьеруучебой в Рязанской духовной семинарии, но затем поступил на службув лесное отделение Рязанской палаты государственных имуществ, а позже стал частным поверенным. Марков-отец славился своей честностьюи высокими принципами (качества, унаследованные и сыном), но слылчеловеком азартным, имел репутацию заядлого картежника. Семейноепредание гласит, что однажды он даже проиграл в карты все свое имущество — движимое и недвижимое. К счастью, выяснилось, что играл он сшулером, и поэтому проигрыш был признан недействительным. Марковсын, в противоположность ему, любил шахматы и был признан одним излучших игроков своего времени: когда Михаил Чигорин, первый шахматист России, готовился к матчу в 1892 г.
с австрийским маэстро шахматВильгельмом Стейницем, чемпионом мира на тот период, он сыграл тренировочный матч из четырех партий с Марковым, причем Марков выигралодну партию и свел вничью другую (Чигорин потерпел драматическое поражение от Стейница в решающей игре, чем вызвал глубокое разочарование умногочисленных российских шахматных энтузиастов, глубоко пережившихэтот проигрыш.) Марков выиграл у Чигорина еще до этого в 1890 г.,показав прекрасную игру, которую приводят во многих шахматных книгах.В матче Оксфорд–Москва, который проходил по телеграфу в 1916 г., всередине Первой Мировой войны, Марков, играя за Москву, вновь провел570Приложение Iблестящую игру, на этот раз играя против Павла Гавриловича Виноградова,выходца из России, а в то время профессора социальных наук в Оксфорде.Марков был болезненным ребенком, страдал костным туберкулезом,вследствие чего у него не разгибалась одна нога и в детстве он ходилна костылях.
Однако он был очень резвым ребенком и старался играть сдругими детьми, прыгая на одной здоровой ноге. К счастью, перед тем какему исполнилось десять лет, после переезда семьи в Санкт-Петербург,ему сделали удачную операцию, и он стал двигаться почти нормально,чуть-чуть прихрамывая. Он любил ходить пешком, и его любимая поговорка была «пока жив — ходи!». В гимназии он не числился блестящимучеником, хотя и демонстрировал незаурядные способности к математике.(По-видимому, это было наследственной чертой, так как его младший браттакже стал видным математиком.) На последнем году учебы он нашелметод решения линейных дифференциальных уравнений с постояннымикоэффициентами и сообщил об этом известным русским математикам тоговремени В.
Я. Буняковскому, А. Н. Коркину и Е. И. Золотареву. Когда емуответили, что его метод хуже стандартного (излагаемого в современных емукурсах дифференциальных уравнений, вследствие чего хорошо уже известного), его интерес к математике лишь усилился, и в 1874 г. он поступил нафизико-математический факультет Санкт-Петербургского университета.В университете Марков был выдающимся студентом и был отмечен многочисленными премиями и стипендиями, включая императорскуюстипендию. Он всегда получал наивысшие отметки, за исключением богословия (тогда это был один из предметов в расписании) и неорганическойхимии, где его экзаменатором был Д.
И. Менделеев (создатель Периодической системы, также предложивший стандартное 40 % содержаниеалкоголя в водке). Его любимым профессором был П. Л. Чебышёв, с нимМарков был особенно близок и подолгу беседовал после лекций. Марковокончил курс в университете в 1878 г. и получил степень магистра в 1880 г.(эта степень примерно соответствовала современной степени кандидатанаук). Степень доктора наук ему присудили в 1885 г., а в 1896 г.
он былизбран членом Российской академии наук. За свою жизнь он опубликовалболее 120 статей и монографий; из них около трети посвящено теориивероятностей.Цепи Маркова появились в его работе, датируемой 1908 г. (Термин«цепь Маркова» был использован С. Н. Бернштейном1 в 1926 г. В западноевропейский научный обиход этот термин был введен Ж. Адамаром,знаменитым французским математиком. Следует отметить, что само сло1 Cм. Bernstein S. N. Sur l’extension du théoréme limite du calcul des probabilités, etc.//Math. Annalen. 1926. V. 97.
P. 1–59.Андрей Андреевич Марков и его время571во «цепь» встречалось в оригинальных работах Маркова.) Интересно,что Марков не предугадывал многочисленных применений своей теории.Пытаясь проиллюстрировать ее примерами, он проанализировал последовательность из 200 000 букв, взятых из романа в стихах «Евгений Онегин»,написанного А. С.
Пушкиным в 1820 г., а также другую последовательностьиз 100 000 букв, взятых из повести С. Т. Аксакова «Детские годы Багровавнука». («Евгений Онегин» до сей поры, вероятно, наиболее популярноепроизведение в стихах в России, и не так уж редко встречаются люди,способные процитировать этот достаточно длинный текст от начала доконца наизусть.) Марков обнаружил, что чередование гласных и согласныхв этих текстах хорошо аппроксимируется цепью Маркова с подходящимивероятностями перехода. Поскольку компьютеров в те времена не было,он проделал все вычисления вручную, на что ушли месяцы кропотливойработы, в том числе непрерывного отслеживания погрешностей расчетов.Другой пример, изученный Марковым, — это результаты перетасовки карт; он посвятил немало времени соответствующим вычислениям.(Как известно, на развитие теории вероятностей немалое влияние оказалиразличные азартные игры.) Следует отметить, что этот пример стал популярным в тех многих областях знания, на которые повлияло появлениекомпьютеров.Высокие исследовательские стандарты Маркова часто приводили егок столкновениям с коллегами, которых он упрекал в недостатке строгости(одной из его мишеней была Софья Ковалевская).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
