前言

突然發現自己沒有系統學過期望。
做一本通的時候是從二分圖開始聽的課，dp這一章只是四處搜題解而已。
做期望題基本都是靠玄學和《感性理解》
都是很簡單的東西，但系統很重要，該補的還是要補的。

期望的基本性質

$E(c)=c$

$E(cx)=cE(x)$

$E(x+y)=E(x)+E(y)$

$E(xy)=E(x)E(y)$ （條件：x,y相互獨立）

比較容易錯的是第四條。其實這個性質附帶的條件是很自然的，把兩邊的期望式子都拆開：
$$\sum _{i,j}{x}_i{y}_{j}P(x=x_i,y=y_j)=(\sum _i{x}_{i}P(x=x_i))\times (\sum _j{y}_{j}P(y=y_j))$$
這個東西成立的條件是 $P(x=x_i,y=y_j)=P(x=x_i)\times P(y=y_j)$，也就是 $x,y$ 相互獨立。

第三條看著特顯然但是也不是那么顯然。
$$\begin{gathered} E(x+y)=\sum _{i,j}(x_i+y_j)P(x=x_i,y=y_j) \\ =\sum _i{x}_i\sum _{j}P(x=x_i,y=y_j)+\sum _j{y}_j\sum _{i}P(x=x_i,y=y_j) \\ =\sum _i{x}_{i}P(x=x_i)+\sum _j{y}_{j}P(y=y_j) \\ =E(x)+E(y) \end{gathered}$$
其中 ${\sum }_{j}P(x=x_i,y=y_j)$ 自然語言就是只要 $x=x_i$，$y$ 取什么值都行，那么也就是 $P(x=x_i)$，才有了第二行到第三行的變換。
其中第三條極其常用，當總問題較為復雜時，常常將其拆分為幾個小問題分別進行期望的求解。

較復雜的期望模型

給出初始狀態 $S$，終止狀態 $T$。
每個狀態 $A$ 有若干轉移狀態 $B_i$ 和對應的概率以及轉移代價，$\sum P(A\to B_i)=1$。
定義 $E(x)$ 表示從 $x$ 到結束的期望代價，則有轉移：
$$E(A)=\sum _i(E(B_i)+cost(A\to B_i))?P(A\to B_i)$$
轉移正確性來自期望本身的定義。
當轉移為 DAG 時，直接拓撲即可。（綠豆蛙的歸宿）
當轉移有環時，高斯消元。（隨機游走）

利用概率求解期望

先求出每個事件的概率，最終乘上其對應的價值，也可以求出期望。

總結

以上是生活随笔為你收集整理的期望学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。