Найдите самый длинный путь к первой вершине графа, определенной цепью Маркова

Question

Мне нужно определить цепь Маркова и построить ее график со следующими свойствами:

• Есть 4 вершины
• Каждая вершина имеет равную вероятность перехода к любой другой вершине (0,25)
• Вершина S ₁ является начальной вершиной

На рисунке ниже я думаю, что график должен выглядеть, но, пожалуйста, исправьте меня, если я ошибаюсь:

Марковская цепь выглядит так?

И если это так:

Какой кратчайший путь (с учетом ребер) до S ₁ ?

Это должно быть 1, так как есть ребро, которое возвращается к S ₁ .

Какой самый длинный путь (с учетом ребер) до S ₁ ?

Если предположить, что мы проходим каждую вершину только дважды (один раз из предыдущей вершины и один раз из цикла), то это должно быть 7.

Но как насчет вероятностей?

Answer 1

Если вопрос заключается в том, как найти вероятность того, что путешественник пройдет гамильтонов цикл (путь, который посещает каждый узел ровно один раз, а затем возвращается к начальному узлу):

Вызовите начальный узел S1,и путешественник T. Первый шаг T должен быть к некоторому другому узлу, а не к S1.Три таких узла доступны.Вероятность этого равна 3/4.

Достигнув этого узла, назовите его S2, затем T должен перейти к новому узлу, а не к S1 и не S2, а к одному из оставшихся двух.Вероятность этого равна 2/4.

Завершив этот шаг для узла, который мы назовем S3, у T осталось посетить только один узел, назовем его S4.Переход на S1, S2 или S3 означает сбой.Переход к S4 имеет вероятность 1/4.

Добравшись до S4, следующий ход Т должен вернуться к S1 и больше никуда.Вероятность этого составляет 1/4.

Общая вероятность: (3/4) (2/4) (1/4) (1/4) = 3 / 128.