Цепи Маркова (1121219), страница 24
Текст из файла (страница 24)
1.39), который получается, еслидва непересекающихся цикла, каждый из n вершин, соединить между собойодним ребром. Пусть переходы внутри циклов совершаются с вероятностью 1/3, а единственный переход из одного цикла в другой происходитс вероятностью p 6 1/3. Вероятности петель симметричны, так что этослучайное блуждание обратимо во времени и его стационарное распределение является равномерным распределением.Разобьем теперь множество вершин (состояний) на два непересекающихся подмножества I0 и I1 , где I0 состоит из n вершин первогоцикла, а I1 — из n вершин второго цикла. Спектральнаящель для кажгдедого цикла, рассматриваемого отдельно, равна2(1.13.39)(1.13.41)p(k, l).
Заметим, что в неравенстве (1.13.39) использо-¯ ¯ (i) (E i ϕ − E ϕ) 2 6jное распределение на Ii × Ij , с маргинальными распределениями ˆ i и ˆ ij ,а (1.13.35) является неравенством Коши—Шварца, что легко заметить,если учесть, чтоX(k)p(k, l)=1PX(1.13.40)вано определение ˆ ji , в неравенстве (1.13.40) используется определение ,а в (1.13.41) неравенство Пуанкаре для суженных цепей.Подставляя соотношения (1.13.36) и (1.13.41) в формулу (1.13.33)и вспоминая, что Σ1 = Σ3 , находим(1.13.36)i6=j k∈Ii ,l∈Ij(1.13.35)66¯ ¯ (i) Var i ϕ 6Затем оценим каждую из сумм в отдельности, заметив при этом, что Σ 1 == Σ3 в силу обратимости во времени. Для второй из этих сумм находимh Xi2X(k)p(k, l)¯ ¯ (i) p̄(i, j)Σ2 =(ϕ (k) − ϕ (l)) 6(1.13.34)Xiii6=ji6=j6145221 − cos3nГлава 1.
Цепи Маркова с дискретным временем144. Поскольку1 − cos x > 2x /5 при 0 6 x 6 /2, получаем, что спектральная щель длякаждой суженной цепи составляет не менее чем 16 2 /15n2 (в предположении, что n > 4), поэтому можно взять min = 10n−2 . Цепь-проекция146Глава 1. Цепи Маркова с дискретным временем§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания на графах147Гамильтониан системы Изинга вдоль траектории определяется какH( ) =n−2X[1 − (i) (i + 1)] /2.i=0Иными словами, каждая пара сопряженных противоположных спиноввносит вклад 1.
Мы изучаем конфигурации, отвечающие распределениюБольцмана—Гиббса1( ) = exp (− H( ))(1.13.45)на I. Здесь Z — статистическая сумма (partition function), ачина, обратная температуре.ZРис. 1.39— вели-в этом примере является симметричной цепью с двумя состояниями и вероятностью перехода между состояниями p/n, так что положим ¯ ¯ = 2p/n.= p. Следовательно, постоянная Пуанкаре для случайногоНаконец,блуждания на пенсне равна(1.13.44)Рис.
1.40Один из стандартных способов построения ц.м.д.в. на I со стационарным распределением состоит в использовании динамики Глаубера. Дляi ∈ {1, . . . , n − 1} и отображения : {1, . . . , n − 1} → {−1, 1} обозначимчерез i,+1 (соответственно i,−1) конфигурации, которые согласуются сво всех вершинах, за исключением, возможно, вершины i, где i,+1 (i) = 1(соответственно i,−1 (i) = −1). Переходы ц.м.д.в. определим следующимобразом.1. Выберем i ∈ {1, . . . , n − 1} согласно равномерному распределению.2. Пустьp=exp (− H( i,+1))exp (− H( i,+1)) + exp (− H(Таким образом, = O(n−3).Пример 1.13.5. Одномерная модель Изинга чрезвычайно популярнав физике, где ей посвящена обширная литература. Относительно недавно она привлекла внимание и ученых-компьютерщиков.
Модель можетбыть определена на общем неориентированном графе и охватывает рядинтересных (и сложных) явлений, включающих фазовые переходы и необратимость. Рассматриваются конфигурации спина, получаемые путемприписывания значений ±1 каждой вершине графа; в случае конечногографа общее число конфигураций равно 2|G| , где |G| обозначает мощностьмножества вершин графа. Мы сосредоточим внимание на простом случае,когда граф представляет собой сегмент одномерной целочисленной решетки {1, .
. . , n − 1}; здесь |G| = n − 1. (С физической точки зрения наиболееинтересен случай трехмерной решетки; двумерный случай также находитприложения.) Удобно добавить еще дополнительно две конечные точки 0и n, значения в которых остаются постоянными и равны 1. Пространствоконфигураций будет состоять из 2n−1 «цепочек» ( (1), . . . , (n − 1)), гдекомпонента (i) = ±1, i = 1, . . . , n − 1. Мы будем использовать такжеграничные значения (0) = (n) ≡ 1.
Мощность множества «расширенных» цепочек = ( (0), . . . , (n)) также равна 2n−1 . Это множество будетиграть роль пространства состояний рассматриваемой ц.м.д.в. Иными словами, в данном примере I = { }; см. рис. 1.40.i20.+ 2n23n33n,h 2p= min‘i,−1)).Тогда с вероятностью p новым состоянием будет i,+1 , а с вероятностью1 − p новое состояние — это i,−1 . Для удобства вводим фиксированныеграничные условия в оставшихся вершинах 0 и n.Всюду далее предполагаем, что n четно. Тогда сегмент {1, . .
. , n − 1}имеет центральную точку n/2. Используем этот факт, чтобы образоватьразбиение множества I на два непересекающихся подмножества I 0 и I1 .А именно, представим I в виде объединения непересекающихся множествI0 ∪ I1 , где I0 (соответственно I1) есть множество всех таких конфигураций,что (n/2) = −1 (соответственно (n/2) = 1). Полезно рассмотреть148Глава 1. Цепи Маркова с дискретным временемсужение ц.м.д.в.
на множества I0 и I1 и соответствующую цепь-проекцию(с двумя состояниями); см. рис. 1.41.влетворяет неравенству61. Параметр(ch ) 2 nТогда спектральная щель цепи-проекции ¯ ¯ >Рис. 1.41удо-1. Таким образом, если обозначить(1 + e−2 )nкак k спектральную щель ферромагнитной системы Изинга на [k] , томожно записать рекуррентное соотношениеhi1[k/2],,(1.13.46)k > min223(ch ) n 1 + 3/4(e+ 1)решением которого являетсяnhi3c = 1 + log2 1 + (e2 + 1) .= C(n−c),4В частности, для низких температур T находим асимптотику числашагов в динамике Глаубера для достижения единственного инвариантногораспределенияN ∝ n2 log2 e/T .Эрнст Изинг (1900–1998) был студентом В.
Ленца в Гамбурге. В 1920 г. Ленц предложил модель ферромагнетизма, в которой частицы находятся в узлах решетки, образованнойкристаллом, и «магнитный спин» частицы может принимать два значения: ±1. Две частицы,находящиеся в соседних узлах, взаимодействуют; это взаимодействие зависит от знаков ихспинов и может способствовать тому, чтобы частицы были одинаковы («ферромагнитнаясистема») или противоположны («антиферромагнитная система»).
Ленц полагал, что этамодель является точно решаемой в том смысле, что вероятностное распределение (1.13.45)(или хотя бы некоторые его важные характеристики) можно вычислить, и он предложилИзингу найти решение.Изинг и в самом деле быстро нашел решение в случае одномерной решетки (одномерныемагниты).
Это решение Изинга составило основную часть его кандидатской диссертации(1924 г.), и основывалось оно на прямом применении теоремы Перрона—Фробениуса.§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания на графах149Однако 20-летние попытки найти решение для многомерной модели не увенчались успехом, хотя два голландских физика Крамер и Ваньер все же нашли численное значение такназываемой «критической» температуры для двумерной модели Изинга.
Точное и полноерешение в двумерном случае было впервые дано американским физиком норвежского происхождения Л. Онсагером в 1944 г. Оно оказалось очень сложным, но в то же время и оченьвоодушевляющим. Попытки исследовать размерности три и выше пока не увенчались полнымуспехом, однако им была посвящена блестящая литература, которая оказала влияние намногие области математики и физики (особенно отметим теорию марковских случайныхполей, где одномерное время заменяется многомерным «аргументом»).Термин «модель Изинга» был введен в 1936 г.
в статье «О модели ферромагнетизма Изинга» выдающимся немецким физиком Р. Пайерсом, который в 1930-х гг. переехалв Британию. Ежегодно фиксируется публикация от 500 до 800 статей, в которых модельИзинга используется в задачах из таких различных областей, как нейронные цепи, белковыеструктуры, биологические мембраны и социальное поведение.Между тем Изинг женился и начал карьеру преподавателя гимназии в Германии.
Он былуволен, когда нацисты пришли к власти в 1933 г., однако в 1934–1938 гг. ему удавалосьоставаться на должности преподавателя и директора еврейской школы-интерната под Берлином. В этот период семейство Изингов проживало по соседству с летним домом АльбертаЭйнштейна (дом был покинут владельцами в 1933 г., когда Эйнштейн с семьей переехалв Америку, и использовался для нужд школы); Изингу доставляло удовольствие рассказывать, как он принимает ежедневные ванны в доме Эйнштейна, так как в его собственном домеванной не было.В ноябре 1938 г. школа была ликвидирована нацистами, и вскоре после этого Изингибыли вынуждены оставить Германию. В 1939 г.
они бежали в Люксембург, намереваясь какможно скорее эмигрировать в США; в конце этого же года родился их единственный сынТомас. В мае 1940 г. немцы вторглись в Люксембург, и консульство США было закрытокак раз в тот момент, когда визы Изингов были уже почти готовы. Год спустя большинствоевреев в Люксембурге были интернированы. Изинг и еще несколько человек, как женатыена нееврейках, не были посланы в концлагерь, но привлечены к принудительным работампо демонтированию железной дороги в Лоррейне, относящейся к линии Мажино. Его женаИоганна, чтобы выжить, работала прислугой. Это продолжалось все последующие четырегода.Семья Изингов добралась, наконец, до США в 1947 г., и в течение 1948–1976 гг.
Изингпреподавал физику и математику в университе Брэдли г. Пеория, штат Иллинойс. С годамион стал почетным профессором физики, но никогда уже не возвращался к своим раннимисследованиям. Фактически список его опубликованных статей в области физики состоит изтрех названий: кандидатская диссертация 1924 г., короткая статья 1925 г. (впервые процитированная В. Гейзенбергом в 1928 г., и 603 раза цитировавшаяся в течение 1975 –2001 гг.)и превосходно написанная статья «Гете как физик», Американский журнал физики 18(1950), 235–236. Согласно собственному признанию Изинга, лишь в 1949 г. он узнал изнаучной литературы, что его модель приобрела широкую известность...150Глава 1.
Цепи Маркова с дискретным временем§ 1.14. Геометрическая алгебра цепей Маркова, III.Границы Пуанкаре и ЧигераManhattan Markov Mystery13§ 1.14. Геометрическая алгебра цепей Маркова, III. Границы Пуанкаре и Чигерагеодезической линией из i в j.) Обозначим множество выбранных намипутей G и положим(Из серии «Фильмы, которые не вышли на большой экран».)01=16 ... 6=0<Доказательство неравенства Пуанкаре. Удобно было бы доказатьобобщение оценки (1.13.6) для неприводимой обратимой матрицы вероятностей перехода P, не обязательно эрмитовой. Однако, как мы ужеговорили в § 1.12, благодаря обратимости обе матрицы P и P T задаютэрмитово преобразование в пространствах R l и Cl со взвешенным скалярным произведением h · , · i ; см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
