https://blog.csdn.net/weixin_45697774/article/details/104274160
知识
需要注意的是，\(P(A|B)P(B)=P(AB)\)，这个东西并没有要求 \(A,B\) 独立。感性理解一下，两件事情同时发生即在发生事件 \(B\) 的情况下，发生 \(A\)，若没发生 \(A\)，则显然 A,B 不可能同时发生。显然这个式子等价于 \(P(B|A)P(A)\)，即在发生 \(A\) 的情况下，发生 \(B\)，同样也是 \(A,B\) 同时发生。
期望的线性性证明。
其中一步挺重要的。
\[\sum_x x\sum_y P(X=x,Y=y)=\sum_x x\sum_yP(X=x)P(Y=y|X=x)=\sum_x xP(X=x)\sum_y P(Y=y|X=x)=\sum_x xP(X=x) \]最后一步是因为 \(\sum\limits_{y}P(Y=y|X=x)=1\)，即在事件 \(X\) 发生 \(x\) 下 \(Y\) 事件无论发生啥，所有概率和一定为 \(1\)。
同理，另一部也可证明。
注意到，我们并没有利用到两个事件的独立性，因此 \(X,Y\) 之间可以不独立。
期望 dp
首先，往往是设 \(f(x)\) 为从 \(x\) 出发的期望。
然后转移利用全期望公式。
即枚举下一步的事件，然后其期望已经求好了，乘上其概率即可。
但在 [PKUWC2018]随机游走 中，存在 
这个 \(+1\) 是为什么呢？
感谢 wxy 老师的教导。
考虑我们求得是 \(E(X|Y=y)\)，即下一步走到某个点，当前节点的期望。
考虑 \(E(Y=y)\) 那么一定是 \(\sum\limits_i p_i v_i\) 的形式，现在多走了一步，那么一定是 \(\sum_i p_i(v_i+1)=\sum\limits_i p_iv_i+\sum\limits_i p_i=E(Y=y)+1\)。
同理，你也可以用期望的线性性来解决。
原先的东西你可以看成是 \(x\to n\)，那么你钦定 \(y\)，变成了求 \(E(x\to y\to n)=E(x\to y)+E(y\to n)=1+E(y\to n)\)。
标签：概率,期望,limits,一步,sum,发生,事件 From： https://www.cnblogs.com/xugangfan/p/17239551.html