Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

Подождите немного. Документ загружается.

= v

i + 1

i+1

i + 2

i+2

j + 1

j+1

´x

t+1

´x

t+1

i + 1

i + 2

j + 1

Рис. 2. Спаривание частиц. Взаимно спаренные частицы обозначены чер-

ными кружками и соединены прямыми линиями, а дефекты — белы-

ми кружками. В момент t частицы i и j спарены, тогда как в момент

t + 1 x-частица i становится неспаренной, а ´x-частица j спаривается с

x-частицей i + 1. Неспаренные в момент t частицы i + 2 и j + 1 спарива-

ются в момент t + 1

Говорят, что две пары частиц пересекают друг друга, если пря-

мые линии, соединяющие позиции частиц из одной пары, пересека-

ются, т.е.

• ⋆

⋆ •

(здесь взаимно спаренные частицы обозначены оди-

наковыми символами).

x-дефект в x

вместе с ближайшим к нему

´x-дефектом в ´x

(

◦

или

◦

) назовем d-парой, если |x

− ´x

| < v , эта пара дефектов не

пересекается с другими взаимно спаренными частицами, и интервал

, ´x

) не содержит других дефектов. Будем говорить, что d-пара

(i, j) меньше чем d-пара (n, m), если |i| < |n|, или i < n — в случае

|i| = |n|. Заметим, что ситуация i = n и j 6= m может произойти, в

отличие от ситуации i 6= n и j = m.

Приведем два примера. В наборе

◦ • •

• •

две первых x-частицы

вместе с первой ´x-частицей образуют x-тройку, несмотря на нали-

чие дополнительной спаренной частицы в интервале между ними.

С другой стороны, набор

• ◦

◦ •

не содержит ни троек, ни d-пар.

Пара конфигураций (x

, ´x

) называется правильной, если она не

содержит x- или ´x-троек, d-пар и п ересекающихся взаимно спарен-

ных частиц.

Если имеется несколько ближайших ´x-дефектов, то выбирается тот, который

имеет минимальный индекс.

218

Правильность пары конфигураций (x

, ´x

) в момент t в общем

случае не препятствует тому, что под действием динамики в мо-

мент (t + 1) пара (x

t+1

, ´x

t+1

) может оказаться неправильной. В част-

ности, могут возникнуть тройки обоих типов и d-пары, например

•

• ◦

−→

•

• ◦

или

◦

◦◦

−→

◦

◦◦

. Здесь важно, что ввиду сохране-

ния порядка частиц пересекающиеся взаимно спаренные частицы не

могут появиться.

Лемма 6.1. Пусть пара конфигураций (x

, ´x

) не имеет пересека-

ющихся взаимно спаренных частиц. Тогда тройки одного типа не

могут иметь общих элементов.

Поэтому все тройки одного типа могут быть устранены одновре-

менно. Под устранением x- или ´x-тройки будем понимать следую-

щее: бывший дефект спаривается с частицей из другого процесса, а

спаренная ранее частица становится неспаренной:

◦ •

•

−→

• ◦

•

Устранение d-пары еще проще: дефекты «аннигилируют» друг

друга, образуя спаренную пару частиц:

◦

−→

•

. Во всех случаях

позиции частиц сохраняются, а меняются только их «роли».

В результате конструкция динамического каплинга состоит из

следующих шагов.

1. Каждая x-тройка рекурсивно устраняется:

◦ •

•

−→

• ◦

•

2. Каждая ´x-тройка рекурсивно устраняется:

•

◦ •

−→

•

• ◦

3. Наименьшая

d-пара рекурсивно устраняется:

◦

−→

•

Лемма 6.2. Описанная процедура каплинга корректно определе-

на, приводит к марковскому процессу пар и у довлетворяет услови-

ям (A1) – (A3).

Чтобы объяснить необходимость рекурсий, заметим, что простран-

ственные сегменты, на которых расположены спаренные частицы,

могут пересекаться. Поэтому устранение x- или ´x-тройки может при-

вести к созданию новой тройки того же типа:

◦ • •

• •

−→

• ◦ •

• •

−→

• • ◦

• •

Порядок d-пар может меняться после каждой процедуры рекурсии.

219

Заметим теперь, что при рекурсиях в процедуре каплинга де-

фект может сдвинуться на произвольно большое расстояние от его

начальной позиции:

• • ··· • •

◦ • • ··· • •

−→

• • ··· • •

• • ··· • • ◦

Обозначим через ρ

(x, I) плотность x-дефектов в конечном сег-

менте I, а через ρ

(x) := ρ

(x, R) — верхний предел величин ρ

(x, I

взятый по всем возможным наборам вложенных конечных сегментов

, длины которых стремятся к бесконечности.

Говорят, что каплинг двух марковских процессов x

, ´x

почти

удачен, если верхняя плотность x-дефектов ρ

(x) стремится к нулю

по времени почти наверное. Это определение существенно отлича-

ется от принятого определения удачного каплинга (см., например,

[14]), которое, грубо говоря, означает, что рассматриваемые процес-

сы со временем стремятся друг к другу.

Применяя понятие почти удачного каплинга к рассматриваемым

процессам с запретами, получаем следующий условный результат.

Лемма 6.3. Пусть x, ´x ∈ X с ρ(x) = ρ(´x) > 0, и предположим,

что имеет место почти удачный каплинг (x

, ´x

), удовлетворяю-

щий дополнительному условию о том, что расстояния между вза-

имно спаренными частицами равномерно ограничены сверху вели-

чиной γ(t) = o(t). Тогда

|V (x, 0, t) − V (´x, 0, t)|

t→∞

−→ 0.

7. Схема доказательства основных

эргодических результатов

Начнем с двух технических результатов.

Лемма 7.1. Супремум |W

| := x

− ´x

по всем взаимно спарен-

ным частицам при динамическом каплинге (см. раздел 6) процессов

, ´x

) равномерно ограничен величиной v для любого t ∈ Z

Лемма 7.2. Пусть ρ(x) = ρ(´x) и пусть при каплинге ∀i, j най-

дется такой (случайный) момент времени t

< ∞, что x

> ´x

для любого t ≥ t

. Тогда каплинг почти успешен.

220

При наших предположениях (стандартный) удачный каплинг

может не существовать (например, в случае чисто детерминирован-

ной постановки с двумя равнораспределенными начальными кон-

фигурациями, сдвинутыми друг относительно друга). Поэтому лем-

ма 7.1 не может быть применена непосредственно для сравнения ско-

ростей частиц. Тем не менее оказывается, ч то это не является серьез-

ным препятствием и даже отсутствие удачного каплинга может быть

использовано в качестве диагностического средства.

Идея доказательства теоремы 5.1 состоит в следующем. Рассмот-

рим две произвольных допустимых конфигурации x, ´x одинаковой

плотности ρ > 0. Если предположить, что имеется почти удачный

динамический каплинг процесса пар с начальными условиями x, ´x,

то по лемме 7.1 выполняются условия леммы 6.3, откуда следует, что

|V (x, 0, t)−V (´x, 0, t)|

t→∞

−→ 0. Применение леммы 4.3 доказывает наше

утверждение.

Предположим теперь, что нет почти удачного динамического кап-

линга. Определим новые случайные величины:

:= x

− ´x

, i, j ∈ Z, t ∈ Z

Тогда

V (x, i, t) − V (´x, j, t) = W

/t − W

/t.

Согласно лемме 4.3 средние скорости разных частиц в одной кон фи-

гурации стремятся друг к другу со временем. Поэтому достаточно

рассмотреть случай i = j = 0. Для W

возможны три следующих

ситуации.

(a) li m

t→∞

/t = 0. Тогда |V (x , 0, t) − V (´x, 0, t)| ≤

≤ |W

|/t + |W

|/t

t→∞

−→ 0, что по следствию 4.4 влечет совпа-

дение средних скоростей.

(b) lim sup

t→∞

/t > 0. Тогда ∀i ∈ Z i -я частица x-процесса со вре-

менем обгонит любую частицу ´x-процесса, исходно располо-

женную правее точки x

. Это наблюдение вместе с услови-

ем равенства плотностей позволяет применить лемму 7.2, со-

гласно которой каплинг почти успешен. С другой стороны, по

Удачный каплинг — когда почти все частицы со временем оказываются спа-

ренными.

221

лемме 7.1 расстояния между взаимно спаренными частицами

не могут превысить величины v. Поэтому по лемме 6.3

имеем |V (x, 0, t) − V (´x, 0, t)|

t→∞

−→ 0, что противоречит предпо-

ложению (b).

t→∞

/t < 0. Меняя роли процессов x

, ´x

, возвращаемся

к случаю (b).

Поэтому только предположение (a) может иметь место.

Идея доказательства теоремы 5 состоит в построении для каждо-

го значения плотности специального семейства конфигураций, оста-

ющегося инвариантным под действием динамики. Показывается, что

для любой конфигурации из этого семейства все частицы двигают-

ся с постоянной скоростью, которая явно вычисляется. Применяя

теперь ре зультат теоремы 5.1 о том, что конфигурации одинаковой

плотности имеют одинаковые средние скорости, получаем требуемое

утверждение.

222

Литература

1. Angel O. The Stationary Measure of a 2-type Totally Asymmetric

Exclusion Process // J. Combin. Theory Ser. A. 2006. V. 113. N. 4.

P. 625–635. [arXiv/0501005 math.CO].

2. Blank M. Ergodic properties of a simple deterministic traﬃc ﬂow

model // J. Stat. Phys. 2003. V. 111. N. 3–4. P. 903–930.

3. Blank M. Hysteresis phenomenon in deterministic traﬃc ﬂows //

J. Stat. Phys. 2005. V. 120. N. 3–4. P. 627–658. [math.DS/0408240].

4. Blank M. Travelling with/against the Flow. Deterministic Diﬀusive

Driven Systems // J. Stat. Phys. 2008. V. 133. N. 4. P. 773–796.

[arXiv:0810.2205 math.DS].

5. Blank M. Metric properties of discrete time exclusion type processes

in continuum // J. Stat. Phys. 2010. V. 140. N. 1. P. 170–197.

[arXiv:0904.4585 math.DS].

6. Бланк М. Л., Пирогов С. А. О квазиуспешном каплинге марков-

ских процессов // Пробл. передачи информ. 2007. Т. 43. № 4.

С. 51–67.

7. Borodin A., Ferrari P. L., Sasamot o T. Large time asymptotics of

growth models on space-like paths II: PNG and parallel TASEP //

[arXiv:0707.4207 math-ph], 2007.

8. Chowdhury D., Santen L., Schadschneider A. Statistical physics of

vehicular traﬃc and some related systems // Physics Reports. 2000.

V. 329. P. 199–329. [arXiv:0007053 cond-mat].

9. Comtet A., Majumdar S. N., Ouvry S., Sabhapandit S. Integer

partitions and exclusion statistics: limit shapes and the largest parts

of Young diagrams // J. Stat. Mech. 2007. P10001.

[arXiv:0707.2312].

10. Evans M. R., Rajewsky N., Speer E. R. Exact solution of a cellular

automaton for traﬃc // J. Stat. Phys. 1999. V. 95. P. 45–98.

11. Evans M. R., Ferrari P. A., Mallick K. Matrix representation of the

stationary measure for the multispecies TASEP // [arXiv:0807.0327

math.PR], 2008.

223

12. Gray L., Griﬀeath D. The ergodic theory of traﬃc jams // J. Stat.

Phys. 2001. V. 105. N. 3–4. P. 413–452.

http://psoup.math.wisc.edu/traﬃc/

13. Корнфельд И. П., Синай Я. Г., Фомин С. В. Эргодическая тео-

рия. М.: Наука, 1980.

14. Liggett T. M. Interacting particle systems. N.Y.: Springer-Verlag,

1985.

15. Maerivoet S., De Moor B. Cellular Automata Models of Road Traﬃc

// Physics Reports. 2005. V. 419. N. 1 P. 1–64.

[arXiv:physics/0509082].

16. Nagel K., Schreckenberg M. A cellular automaton model for freeway

traﬃc // J. Physique I. 1992. V. 2. P. 2221–2229.

17. Penrose M. D. Existence and spatial limit theorems for lattice and

continuum particle systems // Probab. Surveys. 2008. V. 5. P. 1–36.

224

225

Е. В. Гасникова

О возможной динамике в модели расчета

матрицы корреспонденций

1. ВВЕДЕНИЕ

После работ ряда крупных биологов первой половины прошло-

го века, а также работ Е. Т. Джейнса (конца 50-х годов XX века) [1],

А. Дж. Вильсона (конца 60-х годов ХХ века) [2], И. Пригожина с кол-

легами, Г. Хакена (70-е годы XX века) [3, 4] в литературе достаточно

прочно укрепилась концепция о плодотворности перенесения термо-

динамического формализма (см., например, [5–14] и цитированную

там литературу) на различные макросистемы (в частности, встречаю-

щиеся в экономике, биологии, социальной сфере [2–4; 15–24]). В Рос-

сии систематические исследования в этом направлении были пред-

приняты Л. Н. Розоноэром в начале 1970-х [25] (см. также [26–34] и

цитированную там литературу). Упомянутая концепция часто исполь-

зуется для нахождения равновесия макросистемы. А именно, по ана-

логии с феноменологической термодинамикой, вводится вероятност-

ное распределение на множестве состояний, в которых может пребы-

вать макросистема. Такое распределение может, например, совпадать

с инвариантной мерой эргодической динамической системы, порож-

дающей рассматриваемую макросистему [11], или с финальным (рав-

ным стационарному) распределением эргодического (например, мар-

ковского) случайного процесса, порождающего рассматриваемую

макросистему [35–40]. Если размерность макросистемы увеличивает-

ся, то, как правило, распределение сосредотачивается в окрестности

наиболее вероятного макросостояния

. Таким образом, с ростом вре-

мени наблюдения за макросистемой и размерности макросистемы

следует ожидать нахождения макросистемы с большой вероятностью

в малой окрестности наиболее вероятного макросостояния вне зави-

Заметим, что отмеченное обстоятельство (концентрация) может быть по-разному

обосновано (как правило, достаточно элементарных комбинаторных соображений и

формулы Стирлинга [1, 2, 30, 33].

226

симости от того, в каком состоянии макросистема находилась сначала

(иначе говоря, большую часть времени (иногда, и просто, на больших

временах) макросистема будет пребывать в малой окрестности наи-

более вероятного макросостояния). Естественно поэтому под равно-

весием макросистемы понимать наиболее вероятное макросостоя-

ние. Задача нахождения наиболее вероятного макросостояния часто

сводится (асимптотически по размерности системы) к задаче макси-

мизации энтропийно подобного функционала при ограничениях (в

термодинамике таким образом можно получить статистики Больцма-

на, Ферми–Дирака, Бозе–Эйнштейна [1, 5]). Подробнее о приложени-

ях этой концепции см., например, [1, 2, 30, 33; 41–45].

2. ВОЗМОЖНАЯ ДИНАМИКА, ПРИВОДЯЩАЯ В АСИМПТОТИКЕ

(ПО ВРЕМЕНИ) К СТАТИЧЕСКОЙ МОДЕЛИ А. ДЖ. ВИЛЬСОНА

РАСЧЁТА МАТРИЦЫ КОРРЕСПОНДЕНЦИЙ

Рассмотрим для начала более простой пример, иллюстрирую-

щий формализм, описанный во введении.

Пример 1 (кинетика социального неравенства [23, 46]).

В городе живет

1N 

(например, 10 000) пронумерованных жителей.

У каждого i-го жителя есть в начальный (нулевой) момент времени

целое (неотрицательное) количество рублей

 

(монетками,

достоинством в один рубль). Со временем пронумерованные жители

(количество которых не изменяется, так же как и суммарное

количество рублей) случайно разыгрывают свое имущество. Пусть в

момент времени

0t 

r-й житель имеет

рублей, а l-й житель –

рублей. Тогда

   

;km

p t t o t  

есть вероятность того, что жители с

Укажем некоторые часто встречающиеся в приложениях [41–45] формализмы, также

приводящие к задачам оптимизации энтропийно подобных функционалов: принцип

наибольшего правдоподобия (при оценке неизвестных параметров по простой выбор-

ке); принцип максимума апостериорной вероятности; наименьшее отклонение в смысле

расстояния Кульбака–Лейблера (энтропийное расстояние); принцип наименьшей неоп-

ределенности (энтропия – мера неопределенности) в теории информации (рассуждения

опираются в ряде случаев на теорему Шеннона–МакМиллана–Бреймана). Важно также

отметить, что энтропийно подобный функционал часто является функцией Ляпунова

для динамической системы (например, системы обыкновенных дифференциальных

уравнений, итерационного процесса, уравнения (-ий) в частных производных эволюци-

онного типа и т.п.), порождающей рассматриваемую макросистему [12; 17–20]. Пожа-

луй, наиболее ярким примером этого тезиса является кинетическая теория (Л. Больц-

ман [8]).

227

номерами

(

1 r l N  

) встретятся и попробуют разыграть

один рубль по следующему правилу: с вероятностью

житель с

большим номером отдаѐт 1 рубль (если, конечно, он не банкрот)

жителю с меньшим номером и с вероятностью

наоборот. Будем

считать, что

 

;km

p t N







(





). При этом «в среднем» в единицу

времени осуществляется



встреч. Т.е., скажем, при





единицу времени каждый житель с вероятностью, большей

, с

кем-то должен встретиться. Приблизительно такую постановку

задачи в конце XVIII века предложил известный итальянский

экономист Вильфредо Парето, чтобы объяснить социальное

неравенство.

Пусть

 

– доля жителей города, имеющих ровно

рублей

в момент времени

(заметим, что

 

– случайная величина).

Пусть

 







Тогда по эргодической теореме для конечных однородных

марковских цепей (см. [18, 19; 35–38] и упражнение ниже):

 

0,..., 0, :

q q q

q S T N t T



       

 

1 , 0,..., 0.999

P s q









   











где

определяется из условия нормировки:







, т.е.



Скорость сходимости оценивается сверху, исходя из оценок в доказа-

тельстве эргодической теоремы для однородных марковских цепей с

Эргодическая теорема используется для нахождения распределения случайных вели-

чин

 

на больших временах. Далее используются законы больших чисел или, дру-

гими словами, явление концентрации инвариантной (стационарной) меры, о котором

мы подробнее поговорим в следующем примере. Точнее не само это явление, а его

следствие о том, что «хорошие» (например, липшицевы) функции на «хороших» ком-

пактных пространствах с мерой большого числа измерений почти везде близки к ме-

диане [47].