задача на графы

[photon]

Задан регулярный случайный граф с числом вершин $N$. Каждая из вершин соединена 4 ребрами с другими вершинами (то есть degree distribution = 4). Каждая из вершин находится в одном из трех состояний -- $A,B,C$. В начальный момент времени задается определенная конфигурация графа. После этого случайным образом выбирается одна из вершин, если это буква $A$, то существует вероятность в единицу времени $a$, что она заменяется буквой $B$: $A \to B$. Аналогично для буквы $B$: она с вероятностью $b$ заменяется $C$: $B \to C$, но если выбранная буква -- буква $C$, то вероятность её замены зависит от ближайщих соседей, а именно: $C \to A$ c вероятностью $ck$, где $k=0,1,2,3,4$ -- число (ближайших) букв $A$ (соответственно, если таких букв не оказывается, то состояние вершины остается без изменения, если есть одна буква, то вероятность равна $c$). Как можно найти вероятности обнаружения пар ближайших соседей $AB,AC,BC,AA,BB,CC$ (считается, что $P(AB)=P(BA)$ и т.д.) и триплетов $CCA, ACA, ACB$ в таком графе (или на абстрактном языке плотности данных пар и триплетов)?

[незваный гость]

Я могу представить себе по крайней мере две базовых конфигурации такого графа:

1) систему несвязных тетраэдров с центрами (каждый с каждым)

2) Прямоугольная сетка, склееная краями (соответственно, тор, бутылка Клейна и проективная плоскость).

Готов также предположить, что результат может зависеть от топологии связей. Иначе достаточно изучить тетраэдр с центром, и дело в шляпе.

Тетраэдр с центром весьма удобный объект (для начала). Это марковская система с 243 состояниями, для которой легко написать матрицу переходов (между состояниями) и полностью обсчитать. Может помочь понять, с чем имеем дело.

И еще. Если Вы имеете дело, например, с плоской квадратной решеткой, то ее поведение может оказаться удобнее описывать не как граф, а как группу. Таким группам посвящено заметное количество исследований.

И еще. Мне кажется (хотя я и не могу обосновать сходу), что любая такая конечная система придет в состояние «все C» с вероятностью 1.

[LynxGAV]

незваный гость писал(а):

:evil:
Я могу представить себе по крайней мере две базовых конфигурации такого графа:

1) систему несвязных тетраэдров с центрами (каждый с каждым)

2) Прямоугольная сетка, склееная краями (соответственно, тор, бутылка Клейна и проективная плоскость).

Cогласна с пунктом 2) -- как приближение случайная прямоугольная сетка, склеенная краями. Но когда число вершин велико, то практически нет никакой разницы, склеенная она или нет.

Как приближение в сторону регулярности -- квадратная решетка на плоскости с периодическими гран. условиями.

Как приближение -- Bethe lattice (для этого случая $N=10^6$ уже пройдет) и в этом случае задача решается явно.

нг писал(а):

Иначе достаточно изучить тетраэдр с центром, и дело в шляпе.

Простите, а как тетраэдр соотносится с практической реализацией такого графа? И не противоречит ли понятию random graph?

[незваный гость]

LynxGAV писал(а):

Простите, а как тетраэдр соотносится с практической реализацией такого графа? И не противоречит ли понятию random graph?

Одна из возможных конфигураций.

В любом случае, какой бы мы конечный граф не взяли, «все C» — единственное поглощающее состояние, в которое система и придет с вероятностью 1.

[LynxGAV]

незваный гость писал(а):

И еще. Мне кажется (хотя я и не могу обосновать сходу), что любая такая конечная система придет в состояние «все C» с вероятностью 1.

Мне так не кажется (но может быть как один из вариантов). Зависит от вероятностей переходов.

Добавлено спустя 42 секунды:

незваный гость писал(а):

В любом случае, какой бы мы конечный граф не взяли, «все C» — единственное поглощающее состояние, в которое система и придет с вероятностью 1.

Кто это Вам сказал?

[незваный гость]

photon писал(а):

$C \to A$ c вероятностью $ck$, где $k=0,1,2,3,4$ -- число (ближайших) букв $A$ (соответственно, если таких букв не оказывается, то состояние вершины остается без изменения

Это делает «все С» поглощающим состоянием.

Добавлено спустя 8 минут 21 секунду:

LynxGAV писал(а):

Кто это Вам сказал?

Профессор Ибрагимов (Ильдар Абдулович) . То есть, это я так запомнил, что он сказал . Так что если чушь, то моя, а если правильно, то его

~~~

post scriptum ко всем вместе сообщениям о переходе в «все С» с вероятностью 1: это относится только к конечным системам с бесконечным временем. Для больших $N$ характерное время может быть очень, очень велико. И, я думаю, можно рассматривать вопрос о вероятности такого-то состояние при условии, что не «все С», т.е. исключив одно состояние из системы. Это делает систему, пожалуй, более интересной.

[maxal]

Преобразования вершин происходят одно за другим или одновременно для каждой вершины графа?
Правильно ли я понял, что нужно вычислить предельные вероятности (т.е. после прохожения бесконечного количества времени) присутствия указанных пар и триплетов?

[photon]

Я использую алгоритм (Мonte Carlo) на регулярном случайном графе с вершинами четвертого порядка и регулярную решетку на плоскости с периодическими граничными условиями. Чтобы получить стационарные состояния для данного процесса, выбирается случайная конфигурация графа и применяется та динамика, что я описал в первом посте, а именно: случайным образом выбирается вершина и также выбирается случайное число из $[0,1]$, если оно оказывается большим, чем вероятность перехода для данной вершины, которая равна $x \triangle t$, то состояние изменяется. Промежуток $\triangle t$ выбирается достаточно маленьким, чтобы вероятность перехода была не больше единицы для области изменений параметров $(a, b, c)$. В противном случае состояние вершины остается без изменения.

Поэтому, LynxGAV, незваный гость, вы оба по-своему правы. Для конечной системы стационарное состояние $P(C)=1$. Но этот тривиальный случай не интересен, да и размеры графа таковы, что я его приближаю к бесконечной системе. Активные (квазистационарные) состояния конечной системы определяются из среднего по выжившим буквам после $10^4$ независимых реализаций алгоритма для одних и тех же значений параметров со случайной начальной конфигурацией. Посчитанные средние сходятся к стационарным состояниям, когда $N \to \infty $.

[photon]

maxal писал(а):

Правильно ли я понял, что нужно вычислить предельные вероятности (т.е. после прохожения бесконечного количества времени) присутствия указанных пар и триплетов?

Да.

Eще важнее найти управляющее уравнение вида (для случайного графа с фиксированным числом вершин $N$):

$\frac{dP({\sigma},t)}{dt}=\sum \limits_{\sigma \neq {\sigma}'} T({\sigma}|{\sigma}')P({\sigma}',t)-\sum \limits_{\sigma \neq {\sigma}'} T({\sigma}'|{\sigma})P({\sigma},t)$,

где $\sigma$ представляет состояние системы $\sigma = (m_1, m_2, m_3, m_4, m_5)$.
Обозначения: $m_1$ - число вершин в состоянии $C$, $m_2$ - число вершин в состоянии $A$, $m_3$ - число пар в состоянии $CA$ (пары $CA$ и $AC$ считаются идентичными), $m_4$ - число пар в состоянии $CB$, $m_5$ - число пар в состоянии $BA$. Изменение состояния вершины влечет за собой неминуемое изменение состояний пар и триплетов. Точности пар мне достаточно, поэтому выбор состояния именно такой. Например, изменение числа вершин $B \to C$ меняет число пар $BB \to CB$, соответствующий переход я записываю так: $T(m_1+1, m_2, m_3, m_4+1, m5)$. Он будет пропорционален $b$ и числу пар $BB$, содержащихся в графе, но как я найду это число пар, если использую только пары $CA,CB,BA$ и правильно ли я рассуждаю (надо учесть, что рассматриваются пары вершин, соединенных ребром, с другой стороны, триплеты можно аппроксимировать некоррелированными парами, т. е. вероятность найти триплет, например, $CCA$ равна $P(CCA)=\frac{P(CC)P(CA)}{P(C)}$). Вопрос в том, как в явном виде записать переход $T(m_1+1, m_2, m_3, m_4+1, m5)$... Если какие-то моменты по-прежнему объяснены туманно, могу попытаться рассказать еще подробнее.