一般数学方程

Question

我有一个由顶点和圆弧组成的网络（图），如下所示

我想要什么：

A希望从第1天到第m天在网络中进行一组随机游动，以便在随机游动集中至少一次随机游动中访问所有顶点

我在一个while循环中这样做

问题：

最小的实例（网络）由28天内的三种顶点（白天、晚上和晚上）组成

这将导致while循环永远运行。这是因为随机游动最有可能在夜间结束，并且由顶点（n-2）组成的随机游动的概率为（1/3^28=000000000000000 131%）

随机行走的起点是在可能的顶点/圆弧中均匀随机地选择下一个顶点/圆弧。在我的网络中，这将导致以下概率：

[(1/3, 1/3, 1/3), (0, 1/2, 1/2), (0, 0, 1)]
#Equivalent to
[(33, 33, 33), (0, 50, 50), (0, 0, 100)]
#[(day),(evening),(night)]

其中，每个元组表示当选择的最后一个顶点分别是白天、晚上和晚上时，下一个顶点最可能被选择的概率

解决方案：

我提出的解决方案是将概率[（33,33,33），（0,50,50），（0,0,100）]更改为fx[（80,15,5），（0,80,20），（0,0,100）]

我认为这是基于从每种顶点到每种顶点的弧的数量

#list1
[[27,27,27], [0,27,27], [0,0,27]]
#list2
[(80, 15, 5), (0, 80, 20), (0, 0, 100)]

总而言之：

矩阵中的第一个向量（在列表1中）表示从顶点类型1到顶点类型1、顶点类型2和顶点类型3的边数。类似地，向量2表示从顶点类型2到分别为向量类型1、类型2和类型3的边数，与向量3类似

列表2表示当最后选择的顶点分别为类型1、类型2和类型3时，随机游动中的下一个顶点将分别为顶点类型1、类型2和类型3选择的概率

需要帮助：

我想基于[[27,27,27]，[0,27,27]，[0,0,27]，[0,0,27]获得类似于[（80,15,5）、（0,80,20）、（0,0,100）]的东西

我如何从数学上做到这一点

（它不一定给出与列表2中完全相同的值，但大小比率相同（因为它们只是基于逻辑））

我认为它可以用一种通用的方式进行数学表达，因此它适用于不一定具有相同图形结构的更复杂的网络

奖金信息： 另一个例子，我想找到一组概率，它是第二个最不复杂的扩展[[27,27,27,27]，[0,27,27,0]，[0,0,27,0]，[27,27,27]]

更新： 有人告诉我，我也许可以模拟它，但我不知道如何在实践中做到这一点。然后我应该使用哪些概率？我如何使用这个模拟来获得最好的百分比

Answer 1

这个问题有点模糊。只有将100%分配给1，将0分配给其余部分，概率才能保持不变。根据您偏离100%的程度，结果将偏离更多

每天的概率可以用矩阵乘法计算。 对于示例情况，第一天的乘法如下所示：

  [1/3]   [ 0.80 0.15 0.05 ]
  [1/3] · [ 0    0.80 0.20 ]
  [1/3]   [ 0    0    1    ]

继续与同一矩阵相乘，得到第二天的概率

下面的代码描绘了概率的演变。为了将参数的数量简化一点，代码首先将80%的概率分配给一个，然后将其他20%的80%分配给第二个

from matplotlib import pyplot as plt
from matplotlib import ticker
import numpy as np

N = 29
x0 = np.array([1, 1, 1])
x0 = x0 / x0.sum() # starting probabilites, suppose all equal; make them sum to 1
a = 80 / 100
b = (1 - a) * a
c = a
m = np.array([(a, b, 1-a-b), (0, c, 1-c), (0, 0, 1)])
# m = m / m.sum(axis=1, keepdims=True)  # normalize such that rows sum to 1

x = np.zeros((N, len(x0)))
x[0,:] = x0
for i in range(N-1):
    x[i+1, :] = np.matmul(x[i], m)

labels = ['day', 'evening', 'night']
ind = np.arange(N)
for i, lab in enumerate(labels):
    plt.plot(ind, x[:,i], label=lab, marker='.', ls='-')
plt.xticks(ind)
plt.xlabel('day')
plt.gca().yaxis.set_major_formatter(ticker.PercentFormatter(1))
plt.title(f'Highest weight for going to next day: {a*100:.1f} %')
plt.legend()

最高概率为80%的绘图：

最高概率为99%的绘图：

只有在100%的情况下，概率才会保持不变，达到33.3%

下面是另一个示例在给定权重下的情况：

x0 = np.array([1, 1, 1, 1])
x0 = x0 / x0.sum()  # all values sum to 1
m = np.array([[27, 27, 27, 27], [0, 27, 27, 0], [0, 0, 27, 0], [27, 27, 27, 27]])
m = m / m.sum(axis=1, keepdims=True)  # normalize such that rows sum to 1
labels = ['A', 'B', 'C', 'D']

在这种情况下，A和D的概率总是相等的，因此曲线重合。

同样，最佳解决方案是为已经有太多传入箭头的节点赋予权重0：

[[50, 0, 0, 50], [0, 100, 0, 0], [0, 0, 100, 0], [50, 0, 0, 50]]