图论：着色最大值相关期望——随机二着色异色边数期望推导问询

咱们先明确问题背景：假设图$G$有$n$个顶点和$e$条边，每个顶点都独立地以$\frac{1}{2}$的概率被染成黑色或白色。随机变量$X$代表连接白色顶点与黑色顶点的边的数量，现在要推导$E[X]$的表达式。

我的推导思路是这样的：

• 定义指示随机变量$X_{i,j}$：当顶点$i$和$j$之间存在边，且二者颜色不同时，$X_{i,j}=1$；反之$X_{i,j}=0$。
• 总随机变量$X$可以表示为图中所有边对应的指示变量之和：
  $$X = \sum_{(i,j) \in E} X_{i,j}$$
  这里的$(i,j) \in E$表示遍历图$G$的所有边，避免把不存在的边也纳入计算。
• 利用期望的线性性（这个性质不管变量是否独立都成立，非常好用），我们可以把总期望拆成各个指示变量期望的和：
  $$E[X] = \sum_{(i,j) \in E} E[X_{i,j}]$$
• 对于指示变量来说，$E[X_{i,j}]$就等于事件“$X_{i,j}=1$”发生的概率，也就是$P(X_{i,j}=1)$。咱们来算这个概率：
  顶点$i$和$j$独立着色，颜色不同的情况有两种：$i$白$j$黑，或者$i$黑$j$白。每种情况的概率是$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$，所以总概率是$\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$。
• 因为图$G$一共有$e$条边，每条边对应的$E[X_{i,j}]$都是$\frac{1}{2}$，所以直接求和就能得到：
  $$E[X] = \sum_{(i,j) \in E} \frac{1}{2} = \frac{e}{2}$$

内容的提问来源于stack exchange，提问作者Addem