我有一个连通的有向加权图。边权重表示移动顶点之间的概率；从顶点 emanating 的所有边的权重之和为一。该图包含两个 sink：A 和 B。对于图中每个顶点，我想知道起始点的行走到达 A 的概率以及到达 B 的概率。这是什么样的问题？如何解决？
1个回答
5
这个问题属于代数问题。对于从一个顶点开始的路径，到达A的概率是从每个相邻顶点到达A的概率的加权平均值。让我们更具体地说明一下。
设P是图的邻接矩阵。也就是说，Pi,j是从顶点i移动到顶点j的概率。设置PA,A=1。如果我们将分配给每个顶点的概率向量与P相乘，则得到的向量包含每个顶点邻居的加权平均值。我们要找的是一个向量v，使得P v = v且vA = 1。
这个向量v是P对应于特征值为1的特征向量。是否P总有这样的特征值？幸运的是，Perron-Frobenius定理告诉我们它确实存在，并且这是P的最大特征值。解决方法是形成邻接矩阵P并找到对应于其最大特征值的特征向量。
还有一种近似解。如果我们取一个顶点概率向量x，其中xA=1，其他元素设置为0，则Pk x将在k趋于无穷时收敛于v。Pk可能比特征向量更容易计算，当k较小时。
如果按字母顺序排序顶点，则与图对应的矩阵P如下：
该矩阵具有等于1的特征值，相应的特征向量是：[1 0 70/79 49/79]。也就是说，从C到达A的确切概率为70/79，从D到达A的概率为49/79。如果你计算出B的答案，它将得到9/79和30/79，这正是我们所期望的。
< p > P16 [1 0 0 0] 的值约为[1 0 0.886 0.62]，并且精确到小数点后6位。
设P是图的邻接矩阵。也就是说，Pi,j是从顶点i移动到顶点j的概率。设置PA,A=1。如果我们将分配给每个顶点的概率向量与P相乘，则得到的向量包含每个顶点邻居的加权平均值。我们要找的是一个向量v，使得P v = v且vA = 1。
这个向量v是P对应于特征值为1的特征向量。是否P总有这样的特征值？幸运的是，Perron-Frobenius定理告诉我们它确实存在，并且这是P的最大特征值。解决方法是形成邻接矩阵P并找到对应于其最大特征值的特征向量。
还有一种近似解。如果我们取一个顶点概率向量x，其中xA=1，其他元素设置为0，则Pk x将在k趋于无穷时收敛于v。Pk可能比特征向量更容易计算，当k较小时。
例子
让我们看一下以下简单图：
如果按字母顺序排序顶点，则与图对应的矩阵P如下：
该矩阵具有等于1的特征值，相应的特征向量是：[1 0 70/79 49/79]。也就是说，从C到达A的确切概率为70/79，从D到达A的概率为49/79。如果你计算出B的答案，它将得到9/79和30/79，这正是我们所期望的。
< p > P16 [1 0 0 0] 的值约为[1 0 0.886 0.62]，并且精确到小数点后6位。
- Don Reba
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接