Случайные блуждания по ориентированному графу в R

Question

Я новичок в программировании на R.У меня есть ориентированный граф, который имеет 6 узлов, а также предоставил матрицу вероятности из 6 строк и 6 столбцов.Если случайный бродяга, пройдя 100 000 шагов по графику, должен получить выходной вектор, подобный следующему: 0,1854753, 0,1301621,0,0556688, 0,1134808, 0,15344649, 0,3617481, что соответствует вероятностям посещения 6 узлов в этом эксперименте случайного блуждания (число делится наобщее количество шагов, в данном случае 100 000).

Мне нужно создать функцию для этой задачи и продемонстрировать, как ее использовать.Функция принимает график и количество шагов в качестве входных данных.

Предоставленная матрица выглядит следующим образом:

     [,1] [,2] [,3] [,4] [,5] [,6]

[1,]  0.0  0.5  0.3  0.0  0.0  0.2

[2,]  0.1  0.2  0.0  0.4  0.1  0.2

[3,]  0.5  0.0  0.0  0.0  0.0  0.5

[4,]  0.0  0.1  0.0  0.0  0.6  0.3

[5,]  0.0  0.0  0.0  0.4  0.0  0.6

[6,]  0.4  0.0  0.0  0.0  0.2  0.4

Может кто-нибудь помочь мне решить проблему?

Answer 1

Вот пошаговая реализация с использованием цепочки Маркова (через библиотеку R markovchain).

1. Мы начинаем с загрузки библиотеки.

   library(markovchain);
   

2. Мы определяем матрицу перехода и состояния (здесь просто 1 ... 6 для узлов графа) * ​​1011 *

   mat <- matrix(c(
       0.0,  0.5,  0.3,  0.0,  0.0,  0.2,
       0.1,  0.2,  0.0,  0.4,  0.1,  0.2,
       0.5,  0.0,  0.0,  0.0,  0.0,  0.5,
       0.0,  0.1,  0.0,  0.0,  0.6,  0.3,
       0.0,  0.0,  0.0,  0.4,  0.0,  0.6,
       0.4,  0.0,  0.0,  0.0,  0.2,  0.4), ncol = 6, byrow = T)
   states <- as.character(1:6);
   

3. Мы определяем объект цепи Маркова.

   mc <- new(
       "markovchain",
       states = states,
       byrow = TRUE,
       transitionMatrix = mat,
       name = "random_walk");
   

4. Теперь мы смоделируем случайное блуждание, состоящее из nSteps (здесь 1e6) и получим асимптотические вероятности для каждого состояния (узла) с prop.table(table(...))

   nSteps <- 1e6;
   random_walk <- markovchainSequence(nSteps, mc, t0 = "1");
   prop.table(table(random_walk));
   #random_walk
   #       1        2        3        4        5        6
   #0.185452 0.129310 0.055692 0.113410 0.153787 0.362349
   

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

Обернуть это в одну функцию просто, и я оставлю это на ваше усмотрение.

Answer 2

Предполагается, что вы даете матрицу вероятности (prob_mat) для ориентированного графа, а не количество шагов (no_of_steps) в качестве входных данных.Это должно сделать:

set.seed(150)

find_pos_prob <- function(prob_mat, no_of_steps){

                 x <- c(1:nrow(prob_mat))               # index for nodes
                 position <- 1                          # initiating from 1st Node
                 occured <- rep(0,nrow(prob_mat))       # initiating occured count

                 for (i in 1:no_of_steps)   {
                 # update position at each step and increment occurence
                 position  <-  sample(x, 1, prob = prob_mat[position,])      
                 occured[position] <- occured[position] + 1
                                            }
                 return (occured/no_of_steps)
                     }

find_pos_prob(prob_mat, 100000) 

#[1] 0.18506 0.13034 0.05570 0.11488 0.15510 0.35892

Данные:

prob_mat <- matrix( c(0.0,  0.5,  0.3,  0.0,  0.0,  0.2,
                      0.1,  0.2,  0.0,  0.4,  0.1,  0.2,
                      0.5,  0.0,  0.0,  0.0,  0.0,  0.5,
                      0.0,  0.1,  0.0,  0.0,  0.6,  0.3,
                      0.0,  0.0,  0.0,  0.4,  0.0,  0.6,
                      0.4,  0.0,  0.0,  0.0,  0.2,  0.4), byrow = TRUE, ncol = 6) 

Примечание: результаты моделирования будут отличаться от аналитических решений.В идеале вы должны удалить начальное число, выполнить функцию 15-20 раз и взять среднее значение вероятностей за периоды