P2973 Driving Out the Piggies G

· · 题解

题目链接

P2973 Driving Out the Piggies G

 

题意

给定一张无向图，保证 1 号结点一定连接了至少 1 个结点。现在在 1 号结点放一个炸弹，每个单位时间内，它有 \frac pq 的概率在当前结点爆炸，有 1 - \frac pq 的概率等概率随机选择一条出去的边转移到其它结点。问炸弹最终在每个结点上爆炸的概率。

 

解

其它题解提到，在一个点爆炸的概率 = 这个点的期望经过次数 \times 每次炸弹爆炸的概率（即 \frac pq）。

这样感性理解一下可能能觉得是对的。这里写一下一个简单的，不那么偏感性的解释：

显然炸弹爆炸的次数的取值只有 \{0,1\}。这样我们发现，炸弹的期望爆炸次数与爆炸概率 在数值上相等。从而

在一个点爆炸的概率 = 期望在这个点爆炸的次数 = 期望经过这个点且在这个点爆炸的次数

当随机变量 X 和 Y 互相独立时，E(XY) = EX \cdot EY。定义 X 为经过这个点的次数，Y 为每次爆炸次数（显然同样取值 \{0,1\}），则所求即

E(XY) = EX \cdot EY

同样，由 Y 取值 \{0,1\} 知，EY 数值上等于每次爆炸概率，即 \frac pq。

所以，在一个点爆炸的概率，数值上等于在这个点的期望爆炸次数 E(XY)，数值上等于这个点的期望经过次数 EX 乘每次爆炸概率 \frac pq。

 

如有错误恳请指正，如有其它见解敬请提出。