马尔可夫过程##通用的马尔可夫概率转移过程期望值求解方法

好像搞定了任意连通图的任意转移概率的马尔可夫过程的路径期望值计算，包含多结束点以及每条边带加权路径期望值计算。这电路图里面引入“升压器”的概念就行。

如果每个顶点的边数bn，每条边转移概率都相同就是1/bn，那就是很简单的电路图，很好计算，其实只要每条边的两个端点的pkbn相等，这条边换成pkbn条边连接就行，或者理解化成这条边的电阻为1/(pk*bn)。

少量边两端的pk*bn不相等，这条边中间引入升压器概念连接起来，其它相等的边正常按正常电阻连接，然后按电路图计算就行。复杂点的桥式电路，可以用星形和Y行的电路转换。如果不相等的太多，就不适合这么去计算了，这种就老老实实的解方程组。

这样很多时候就可以不用解方程组直接计算了。

连通图的n个顶点，每个顶点的边bn，每条边的转移概率pk，对bn条边求和有∑pk=1。边的路径加权wk。从O点出发，到m个点Em结束，问加权转移路径期望值x=?

1、列方程组的办法：

m个点：
xm=0
其它的点：
xn= ∑pk(xk+wk)= ∑pkwk+ ∑pkxk (1)

求解方程组（1）就得到每个点的路径加权期望值。不过方程组多了求解的人工手算还是有点难度的。

2、另外的平衡状态解法：

如果有平衡状态：
Em个点Bm=0只蚂蚁
其它的n-m个顶点，每个点有Bn只电子蚂蚁?，下一步每条边爬出Bn*pk只蚂蚁，如果除了O点少了I只电子蚂蚁?，其它的n-m-1个顶点都保持Bn只电子蚂蚁?不变。

平衡状态方程组 （2）
Bm=0
Bn=∑ Bk*pk，bn条边另外端求和
Bo=-I+∑ Bk*pk
这个方程组比方程组（1）应该好求。

那么:
xo=1/I ∑ Bn ∑pk*wk 。（3）

3、下面我们来用电路图找出平衡状态，以及求出（2）、（3）的Bn和I。

连通图每个顶点的bn条边，每条边为bnpk个电阻1欧姆的电阻，如果一条边两边线数目bnpk相等，那么可以直接连接起来，或者连接这条边电阻为1/(bn*pk)欧姆。如果两边线数目不等，用2个“升压器”接入1欧姆电阻的两端，升压器作用就是得到新的电压是输入端每跟线电压之和。

O点接入电源正极电流I安培，m个点接入电源负极，电压0伏。n-m个点电压为Vn，这样连通图每条边的端点输出电压V=Vnbnpk=（Vnbn)pk=Bnpk，Bn=Vnbn。因为两端电阻为1，电流就为两端电压差。我们可以直接想象成电流为两端的电压各自流出到另外一端，这就和一条边两端的输出的电子蚂蚁各自爬到另外一端效果等同。

除了电源正负级，节点电流和为0， 所以 ∑ Bnpk保持不变，电源正极电流减少了I。这个电路图就和（2）完全对应起来了，其中Bn=Vnbn。

xo=1/I ∑ Bn ∑pk*wk 。

=1/I* ∑ Vn*bn* ∑pk*wk 。（4）

现在就是转换成等效的转换电路图的电压电流计算了。升压器没有或者比较少的时候，还是比较方便直接计算的。

4、常见的特殊情况，转移概率是每边相同，pk=1/bn，这样没有任何边有升压器。就是最简单普通的电路图。

xo=1/I ∑ Vn ∑wk (5）

这时候O点进O点出的平衡状态异常简单，Bn=bn，I=bo
xoo=1/bo* ∑ （∑ wk)) (6)
如果加权都相等wk=w
xoo=1/bo ∑ （∑ wk)) =2E/bow (7)
再如果bn都相等
xoo=2E/bow=nw (8)

E连通图的边数，n连通图的顶点数。

如果加权都为w:

xo=w/I ∑ Vn bn （9）