【摘要】：引理3.1契贝晓夫不等式对任意一个随机变量X，有其中，E和Var分别表示X的期望和方差。记EMST为基于生成集={X1，X2，…，χK，有详细证明请见文献[80]。另外，引入文献[81]中的一个结论。引理3.5生成树长度上界对任意一个分布在区域[0，a]2中的点的集合，记EST（）为用算法3.1生成的欧几里得生成树，则有
引理3.1 契贝晓夫不等式（Chebyshev's Inequatlity）
对任意一个随机变量X，有
其中，E（X）和Var（X）分别表示X的期望和方差。
引理3.2 契诺夫界（Tails of Chernoff Bound）
对任一个泊松随机变量X，E（X）=λ，有
其中，E（X）和Var（X）分别表示X的期望和方差。
引理3.3 最小生成树长度[79]
若点Xi，1≤i≤∞，均匀分布在区域[0，a]d。记EMST（χ（n））为基于生成集
={X1，X2，…，Xn}的最小生成树，则存在一个常数ν（d）＞0，使得(www.xing528.com)
注意上面这个引理中表明‖EMST（χ（n））‖～ν（d）·
·a是几乎一定（almost sure）成立的，而不是渐近几乎一定（asymptotically almost sure）成立，从而有以下引理成立。
引理3.4 最小生成树长度和
对于任意K（n）个以引理3.3中模型独立构造的点集合，记为χ1（n），χ2（n），…，χK（n）（n），有
详细证明请见文献[80]。
另外，引入文献[81]中的一个结论。
引理3.5 生成树长度上界
对任意一个分布在区域[0，a]2中的点的集合
（可看做组播会话
的生成集），记EST（
）为用算法3.1生成的欧几里得生成树，则有
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
