Случайное блуждание на графе

[Hasek]

Пусть частица случайно блуждает по данному графу.



В каждый момент времени переход на любую из соседних вершин равновероятен. Старт случайного блуждания в точке $A$. Найти среднее значение

• времени возвращения в $A$
• количество посещений $D$ до возвращения в $A$
• количество посещений $C$ до возвращения в $A$

Я решал так:

Пусть $a$ -- среднее время возвращения в $A$ при старте из $A$, $b$ -- среднее время возвращения в $A$ при старте из $B$, аналогично определим $c$, $d$ и $e$. Они связаны следующими соотношениями:

$$\begin{cases} a = \frac{1}{2}(c+1) + \frac{1}{2}(b+1)\\ b = \frac{1}{2} + \frac{1}{2}(c+1)\\ c = \frac{1}{2} + \frac{1}{2}(b+1)\\ d = \frac{1}{2}(c+1) + \frac{1}{2}(e+2)\\ e = \frac{1}{2}(c+1) + \frac{1}{2}(d+2) \end{cases}$$

Решение этой системы $a=3, b=2, c=2, d=5, e=5$, значит, ответ на первый вопрос будет $3$.

Но, насколько мне известно, для связного неориентированного графа с $n$ рёбрами среднее время возвращения в начальную точку определяется как $\frac{2n}{d}$, где $d$ -- валентность вершины, из которой стартовали. Для этого графа формула даёт $a = \frac{2\cdot6}{2} = 6$.

Получается, я неправильно составил систему уравнений? И как найти среднее количество посещений какой-либо из вершин до возвращения в начальную?

[DeBill]

Hasek
Судя по третьему уравнению системы, валентность "с" равна 2, да?

[Hasek]

DeBill в сообщении #1195562 писал(а):

Судя по третьему уравнению системы, валентность "с" равна 2, да?

И точно, нет.
Правильно будет $c = \frac{1}{4} + \frac{1}{4}(b+1) + \frac{1}{4}(d+2) + \frac{1}{4}(e+2)$, но при таком исправлении ответ получится $a=8$.

[DeBill]

Hasek
Почему $d+2$, а не $d+1$?

-- 26.02.2017, 18:08 --

Hasek в сообщении #1195553 писал(а):

И как найти среднее количество посещений какой-либо из вершин до возвращения в начальную?

Да ровно так же: " пусть $b_1$ - среднее кол-во посещений $D$ до первого возвращения в $A$ при старте из $B$, и т.п.....

[Hasek]

DeBill в сообщении #1195565 писал(а):

Почему $d+2$, а не $d+1$?

Потому что вершина $D$, как и $E$, отстоит от $A$ на расстоянии как минимум $2$ шагов (считаем, что нам потребовалось $2$ шага, чтобы достичь её, перед тем, как мы отсчитываем время возвращения в $A$ из неё, во всяком случае я записал именно из таких соображений).

UPDATE: Хотя, при записи связующих соотношений выглядит более разумным считать шаги не от $A$, а от вершины, определяемой левой частью уравнения, тогда везде будет $(d+1)$ и $(e+1)$, что даст ответ $a=6$. Это правильное понимание?

[Hasek]

DeBill в сообщении #1195565 писал(а):

Да ровно так же: " пусть $b_1$ - среднее кол-во посещений $D$ до первого возвращения в $A$ при старте из $B$, и т.п.....

Проверьте, пожалуйста, правильно ли я понял соотношения на них...

Итак, пусть $E(T_{AA}), E(T_{BA}), E(T_{CA}), E(T_{DA}), E(T_{EA})$ -- среднее число посещений $D$ до возвращения в $A$ при старте из $A, B, C, D, E$ соответственно. Тогда

$$ \begin{cases} E(T_{AA}) = \frac{1}{2}E(T_{BA}) + \frac{1}{2}E(T_{CA})\\ E(T_{BA}) = \frac{1}{2}\cdot0 + \frac{1}{2}E(T_{CA})\\ E(T_{CA}) = \frac{1}{4}\cdot0 + \frac{1}{4}E(T_{BA}) + \frac{1}{4}(E(T_{DA})+1) + \frac{1}{4}E(T_{EA})\\ E(T_{DA}) = \frac{1}{2}E(T_{CA}) + \frac{1}{2}E(T_{EA})\\ E(T_{EA}) = \frac{1}{2}E(T_{CA}) + \frac{1}{2}(E(T_{DA})+1) \end{cases}$$

Значение $E(T_{DA})$, выраженное из этой системы, будет средним числом посещений $D$ до возращения в $A$. Чтобы найти среднее число посещений $C$, надо вместо $(E(T_{DA})+1)$ подставить просто $E(T_{DA})$, а вместо $E(T_{CA})$ наоборот $(E(T_{CA})+1)$ и выразить $E(T_{CA})$. Правильно?

[DeBill]

Hasek в сообщении #1195568 писал(а):

Это правильное понимание?

Да. Только надо говорить не "выглядит более разумным", а "очевидно, надо делать именно так и только так, потому что смысл этого равенства такой: длина пути из Д в А такова: сделали ОДИН шаг из Д, а потом - оставшиеся шаги - из той соседней вершины, в которую попали"

-- 26.02.2017, 20:34 --

Hasek в сообщении #1195595 писал(а):

Правильно?

Да.

-- 26.02.2017, 20:42 --

Ой: невнимательно прочел....Правильный ответ: нет.

Hasek в сообщении #1195595 писал(а):

Значение $E(T_{DA})$, выраженное из этой системы, будет средним числом посещений $D$ до возращения в $A$

Нет. Это будет ..... - при условии, что мы стартовали из Д.

Hasek в сообщении #1195595 писал(а):

Чтобы найти среднее число посещений $C$, надо вместо $(E(T_{DA})+1)$ подставить просто $E(T_{DA})$, а вместо $E(T_{CA})$ наоборот $(E(T_{CA})+1)$

Да (имеется в виду - в правой части)

Hasek в сообщении #1195595 писал(а):

и выразить $E(T_{CA})$.

Нет.

(Оффтоп)

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

[Hasek]

DeBill

Да, выражать в обоих случаях надо $E(T_{AA})$, так как старт по условию из $A$ (сам же запутался в своих обозначениях).

Большое спасибо за внимательную проверку и комментарии!