Стохастический клеточный автомат - Stochastic cellular automaton

Стохастические клеточные автоматы или вероятностные клеточные автоматы (PCA), или случайные клеточные автоматы, или локально взаимодействующие цепи Маркова являются важным расширением клеточного автомата . Клеточные автоматы - это динамическая система с дискретным временем взаимодействующих сущностей, состояние которой дискретно.

Состояние коллекции сущностей обновляется в каждый дискретный момент времени в соответствии с некоторым простым однородным правилом. Состояния всех сущностей обновляются параллельно или синхронно. Стохастические клеточные автоматы - это СА, правило обновления которых является стохастическим , что означает, что состояния новых объектов выбираются в соответствии с некоторыми распределениями вероятностей. Это случайная динамическая система с дискретным временем . Из пространственного взаимодействия между объектами, несмотря на простоту правил обновления, может возникнуть сложное поведение, подобное самоорганизации . Как математический объект его можно рассматривать в рамках случайных процессов как систему взаимодействующих частиц в дискретном времени. См. Более подробное введение.

PCA как марковские случайные процессы

Как марковский процесс с дискретным временем, PCA определяются в пространстве произведений (декартово произведение), где - конечный или бесконечный граф, например, а где - конечное пространство, например, или . Вероятность перехода имеет вид произведения, где и - распределение вероятностей на . В целом некоторые местности требуются где с конечными окрестностями к. См. Более подробное введение с точки зрения теории вероятностей. ${\ displaystyle E = \ prod _ {k \ in G} S_ {k}}$${\ displaystyle G}$${\ Displaystyle \ mathbb {Z}}$${\ displaystyle S_ {k}}$${\ Displaystyle S_ {к} = \ {- 1, + 1 \}}$${\ Displaystyle S_ {к} = \ {0,1 \}}$${\ Displaystyle P (d \ sigma | \ eta) = \ otimes _ {k \ in G} p_ {k} (d \ sigma _ {k} | \ eta)}$${\ displaystyle \ eta \ in E}$${\ displaystyle p_ {k} (d \ sigma _ {k} | \ eta)}$${\ displaystyle S_ {k}}$${\ displaystyle p_ {k} (d \ sigma _ {k} | \ eta) = p_ {k} (d \ sigma _ {k} | \ eta _ {V_ {k}})}$${\ displaystyle \ eta _ {V_ {k}} = (\ eta _ {j}) _ {j \ in V_ {k}}}$${\ displaystyle {V_ {k}}}$

Примеры стохастического клеточного автомата

Мажоритарный клеточный автомат

Есть версия мажоритарного клеточного автомата с вероятностными правилами обновления. См . Правило Тоома .

Связь с решеточными случайными полями

PCA может быть использован для имитации модели Изинга в ферромагнетизме в статистической механике . Некоторые категории моделей изучались с точки зрения статистической механики.

Сотовая модель Поттса

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

Немарковское обобщение

Модель Гальвеса-Лехербаха является примером обобщенного PCA с немарковским аспектом.

Рекомендации

дальнейшее чтение

• Алмейда, РМ; Макао, EEN (2010), "Стохастическая клеточная модель автомата для динамики лесных пожаров в распространенной", девятая Бразильской конференция по динамике, управлению и их приложениям, 7-11 июня 2010 , DOI : 10,1088 / 1742-6596 / 285/1/ 012038.
• Кларк, KC; Хоппен, С. (1997), «Самомодифицирующаяся модель клеточного автомата исторической урбанизации в районе залива Сан-Франциско» (PDF) , Environment and Planning B: Planning and Design , 24 (2): 247–261, doi : 10.1068 / b240247 , S2CID  40847078.
• Махаджан, Мина Бхаскар (1992), Исследования в языковых классах, определяемых различными типами изменяющихся во времени клеточных автоматов , доктор философии. диссертация, Индийский технологический институт Мадрас.
• Нисио, Хидэносукэ; Kobuchi, Youichi (1975), "толерантные Fault клеточные пространства", журнал компьютерных и системных наук , 11 (2): 150-170, DOI : 10.1016 / s0022-0000 (75) 80065-1 , MR  0389442.
• Смит, Элви Рэй, III (1972), "определение языка распознавания в реальном времени одномерным клеточных автоматов", журнал компьютерных и системных наук , 6 (3): 233-253, DOI : 10.1016 / S0022-0000 (72) 80004-7 , MR  0309383.
• Agapie, A .; Андрейка, А .; Джуклеа, М. (2018). Louis, P.-Y .; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Журнал вычислительной биологии . Возникновение, сложность и вычисление. 27 . Springer. С. 699–708. DOI : 10.1007 / 978-3-319-65558-1 . ISBN 9783319655581. PMC  4148062 . PMID  24999557 .