Граф со cлучайными переключениями активных вершин

[LynxGAV]

Имеется бесконечное дерево с распределением степеней вершин $p_k$ ($p_k$ - вероятность того, что случайно выбранная вершина имеет степень $k$, степень вершины $k$ - число ребер, входящих/выходящих из вершины). Каждая вершина может быть в трех состояниях: "активном", "неактивном" и "бесполезном". В начальный момент времени вершинам присваиваются состояния, причем таким образом, что доля активных вершин составляет $\rho_0$, доля неактивныx $s_0$ и доля бесполезных, соответственно, $1-\rho_0-s_0$. В таких пропорциях состояния распределены на дереве случайным образом независимо от степени вершин (доля ... - вероятность того, что случайно выбранная вершина в ... состоянии). Доля бесполезных вершин со временем не меняется и с ними вообще ничего не происходит.

Шаг заключается в том, что все имеющиеся в данный момент активные вершины смотрят сколько у них неактивных соседних вершин и меняют одну из них, выбранную случайно, на активную (если такая имеется) (смотрят и меняют по очереди, сначала первая, потом вторая). [Пояснение. Каждая активная вершина выбирает одного неактивного соседа из имеющихся в наличии случайным образом и меняет его состояние на активное. Активные вершины делают это по очереди (порядок не важен, вершины не нумерованные). Потому, например, может произойти, что одна активная вершина А выберет именно того неактивного соседа В, статус которого может поменяться из-за совсем другой активной вершины С. После того, как вершина В станет активной и надо потом апдейтить неактивного соседа активной вершины С, может оказаться, что такого не имеется и что вершина С ничье состояние не изменит. Ну, что же поделать, значит ей не повезло.] Когда произойдет перебор всех имеющихся активных вершин и состояния неактивных соседей будут изменены, истекает время $\triangle t$ и начинается второй шаг по той же самой схеме и такой же длительностью.

Найти долю активных вершин после шага $n=1,2,\ldots$, а также асимптотическое значение при $n\to\infty$.

Есть идеи, как это сделать?

В принципе, если возможно составить приближенное диф. уравнение, то такой вариант тоже интересен.

[GeorgeI]

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

[Xaositect]

Понятно, что наше дерево можно разбить на участки(возможно, бесконечные), состоящие из активных и неактивных вершин, которые "изолированы" друг от друга вершинами бесполезными.
Понятно, что если в таком участке есть хотя бы одна активная вершина, то при $t\rightarrow \infty$ этот участок будет становиться целиком активным, причем количество новых активных вершин на каждом шаге равно min(количество активных вершин, количество неактивных вершин, смежных с активными). Кажется, что с течением времени именно второй фактор становится определяющим.
Участки же, которые состоят из неактивных вершин, так и останутся неактивными, то есть для определения предельной доли активных вершин хорошо бы долю вершин, лежащих в таких участках. (Не уверен, но вроде бы почти все они должны быть конечными, так как в бесконечном участке с вероятностью 1 есть активная вершина. Также не уверен, но если $s_0<(Ek)^-1$ ($Ek$ - матожидание степени вершины), то доля будет нулем (исходя из того, что у каждой неактивной вершины матожидание числа неактивных соседей <1)

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

[LynxGAV]

GeorgeI писал(а):

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

Покороче и полегче не получилось. Меня интересовали аналитические результаты, потому тема была размещена именно в этом разделе. Если бы формулирование на языке программирования давало ответ, это было бы чудно, но - увы.

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

Xaositect писал(а):

Понятно, что наше дерево можно разбить на участки(возможно, бесконечные), состоящие из активных и неактивных вершин, которые "изолированы" друг от друга вершинами бесполезными. Понятно, что если в таком участке есть хотя бы одна активная вершина, то при $t\rightarrow \infty$ этот участок будет становиться целиком активным, причем количество новых активных вершин на каждом шаге равно min(количество активных вершин, количество неактивных вершин, смежных с активными). Кажется, что с течением времени именно второй фактор становится определяющим.
Участки же, которые состоят из неактивных вершин, так и останутся неактивными, то есть для определения предельной доли активных вершин хорошо бы долю вершин, лежащих в таких участках. (Не уверен, но вроде бы почти все они должны быть конечными, так как в бесконечном участке с вероятностью 1 есть активная вершина. Также не уверен, но если $s_0<(Ek)^-1$ ($Ek$ - матожидание степени вершины), то доля будет нулем (исходя из того, что у каждой неактивной вершины матожидание числа неактивных соседей <1)

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

В этой задаче можно показать, что выше некоторого критического значения вероятности найти активную или неактивную вершину, дерево будет состоять из бесконечного подграфа и из конечных подграфов активных и неактивных вершин, разделенных подграфами бесполезных (бесконечный - значит размер такого подграфа растет линейно, когда общее число вершин в дереве стремится к бесконечности, в отличие от конечного - который таким и остается). Ниже критического значения будут присутствовать только конечные подграфы.

Спасибо за участие, я уже продвинулась в решении, потому вопрос не так актуален. Если кому-то понадобится, то есть несколько релевантных статей на эту тему, например, вот эта.

[Xaositect]

LynxGAV в сообщении #196213 писал(а):

Если кому-то понадобится, то есть несколько релевантных статей на эту тему, например, вот эта.

А, я вспомнил, где я видел что-то похожее!
В прошлом году мне на глаза попадались несколько статей по исследованию Percolation и Aggregation в некоторых клеточных автоматах.