朋友的朋友大概率比我的朋友多

标签：概率 frac 朋友 sum 期望 sigma align

\(G=(V,E)\)
度数之和：

\[2|E| \]

那么每个人的朋友期望数量：

\[E(d)=\frac{2|E|}{|V|} \]

然后随机选择某一对关系（某一条边）与某个点有关的概率，然后再从这条边选其中一个端点，
假设自己是 \(u\)，然后看一下点 \(u\) 的朋友的期望朋友数量：
对于每一个点 \(v~(v\ne u)\)，点 \(v\) 是 \(u\) 的朋友的概率：

\[\frac{d_v}{2|E|-d_u} \]

对于一个点 \(v\) 对于期望的贡献就是：

\[\frac{d_v^2}{2|E|-d_u} \]

这里假设自己算自己的朋友，因为自己的朋友数量等于自己的朋友数量，不影响大小比较，所以对于某个点 \(u\)，好友的期望好友数量就是：

\[\sum_{v\in V}{}\frac{d_v^2}{2|E|} \]

然后拿这个值和 \(u\) 点的朋友数量作差：

\[\begin{align} \Delta_u&=\sum_{v\in V}\frac{d_v^2}{2|E|}-d_u\\ &=\sum_{v\in V}\frac{d_v^2-\frac{2|E|d_u}{|V|}}{2|E|}\\ &=\sum_{v\in V}\frac{d_v^2-E(d)d_u}{2|E|} \end{align} \]

然后 \(u\) 是随机取的，我们要求出的是 \(E(\Delta)\)，所以可以将 \(d_u\) 替换成 \(E(d)\)。
那么就有：

\[\begin{align} E(\Delta)&=\sum_{v\in V}\frac{d_v^2-E(d)^2}{2|E|}\\ &=\sum_{v\in V}\frac{d_v^2+E(d)^2-2E(d)^2-2d_vE(d)+2d_vE(d)}{2|E|}\\ &=\sum_{v\in V}\frac{(d_v-E(d))^2-2E(d)(E_d-d_v)}{2|E|}\\ \end{align} \]

然后观察分子上减号之前，发现 \(E(d)\) 就是期望（平均）度数，所以前半部分就是 \(\sigma\) （方差），那么那么原式：

\[\begin{align} E(\Delta)&=\sigma-\frac{\sum_{v\in V}2 E(d)(E_d-d_v)}{2|E|}\\ &=\sigma-\frac{E(d)\times|V|-\sum_{v\in V} d_v}{|E|}\\ &=\sigma-\frac{2|E|-2|E|}{|E|}\\ &=\sigma \end{align} \]

这里 \(\sigma\) 方差显然大于等于 \(0\)：
做差发现大于等于 \(0\)，所以朋友的朋友的期望个数大于等于自己的朋友的期望个数。
也就是：朋友的朋友大概率比我的朋友多。

---

省流：朋友多的人大概率是我的朋友。

标签：概率,frac,朋友,sum,期望,sigma,align
From： https://www.cnblogs.com/weirdoX/p/18343972