Как найти вероятности в графе возможностей с циклами?

Question

Допустим, у меня был такой график, где вес на каждом ребре был вероятностью прохождения вдоль этого ребра, выбранной случайным образом. Если бы я хотел выяснить вероятность попадания в данную вершину, начиная с 0, это было бы относительно просто. По сути, я бы просто нашел все возможные пути к каждой из вершин без каких-либо исходящих ребер, а затем умножил вероятности на каждом ребре в этом пути. В этом случае я получаю вероятность 1/2 для вершины 2 и 1/2 для вершины 3.

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

Answer 1

Для каждого пути между двумя узлами A -> B сделайте следующее: Для каждой пары узлов (Z,X) на пути A -> B рассчитайте вероятность пути как бесконечную геометрическую сумму для пары.

Пример: (Предположим, Z -> X -> C -> Z)

A
|
Z - +
|   C
X - +
|
B

P(A->B) = P(A->Z) . { P(Z ->X) + P(Z->X).P(X->C).P(C->Z).P(Z->X) + P(Z->X).P(X->C).P(C->Z).P(Z->X).P(X->C).P(C->Z).P(Z->X) + ... } . P(X -> B)
        = P(A->Z) . P(Z->X).{ 1 + m + m^2 + m^3 + ... } . P(X->B)
           (m = P(X->C).P(C->Z).P(Z->X) )
        = P(A->Z) . { P(Z->X)/(1-m) } . P(X->B)
        = P(A->Z) . { P(Z->X)/[1 - P(X->C).P(C->Z).P(Z->X) ] } . P(X->B)

И расширите это для каждого (Z,X) на пути A -> B. Это будет очень вычислительно для больших графов, но вы должны делать то, что должны.

Теперь обращаясь к вашему актуальному вопросу,

1. List all possible paths from A -> B assuming all edges have weight as 1.
2. for each path:
      for each edge pair {Z,X} (Z->X for which X->Z path exists and Z-X is not a bidirectional edge):
         do the above.
3. Compute the arithmetic mean over all the path probabilities, that is your answer.

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