由此可见，从形式上看，对于每一个自然数以一共有 =—-—个单项式/ 丿 kl（rn-k）!m m（9）/=! /=1oo 8（10）p（U4）s工P（4）f=l /=1注意：（9）和（10）称为半可加性它们是估计概率大小的依据随机图定义一我们可以将〃个节点上的所有（带有标号）支撑子图的（K〃的所有支撑子图） 全体视为样本空间，记为G”,（实际上就是有限概率空间（G”，p）, 〃是一个概率函数从Gnp^挑选的一个元素G被称为一个随机图下面是关于随机图的几个例子:1. |最简单的概率空间區:对于任意G w G”，G的概率志P(G)是一个常数2", N =2.経过改进的概率空间—依然取G“如前所定义取介于0和1之间的任何一个数p为一 个待定的概率函数我们指定每一条边都具有相同的概率值°,同时约定：这样的约定是 相互独立的于是，1-卩就是特定一条边没有被选中的概率对于一个边数为m = e(G)的 随即图G而言，它的概率值为P(G) = /T(1_〃)S一个值得注意的现象是：P越小，G成为以个稀疏图的可能性(概率)就越大！而图论学家的正真兴趣在于：计算或估计一个随机图具有某个特性的概率有多大？下而就是一个关 于概率空间G切的例子：g2° °3(1-莎\2。
⑰ 必-莎1 1o2 3XI1/2“ °3| P(l-P)'1r oA1 A1△才(1—P)p'(l-p)2 3p'(l-p)2 £3结论1—Gjp中一个随机图连通的概率=3p2(l-p)+p3 = p2(3_2p)；结论2-G3/,中一个随机图是二部图的概率=1-/?3；结论3・£切小一个随机图是二部连通图的概率=3p2(l-p)；结论4-如果设X是Gg中元素中联通分支数目，则E(X) = 3(1 — /?)' +2x3 /?(! — p)・ + lx(3/?~(l — /?) + ) = 3 — 3/? + p'马尔科夫不等式b设X是一个非负随机变量而t是一个正实数则有pg"吗t这个不等式表明：随机变量变大的可能性为零特別地，壁：设X"是一个取值为非负整数的随机变量,它的概率空间为QyP〉如果E(X”)T 0 当nn 那么 Pg 二 0) T 0 当斤 T *这个性质经常被用來证明：对于数值p:0 t证明：根据马尔科夫不等式，P(| X - E(X) 2 心 P(| X - E(X)宀尸)V E((X - E(X) )2)=举2这个不等式经常被用于下面的形式：设Xn是一个取值为非负整数的随机变量,它的概率空间为(Q”,人)，如果E(X”)H0 近V(X〃)vv Ep〉那么P(X”=0)t0 (当 nig )。
证明：设 X = Xn 且 2|E(X”)|,注意到由于 XH =0=>\Xn- E(Xn) |=| E(Xn) |,P(X„ =0)| £(XJ|)数学期望:一个随机变量X的平均值就是它的数学期望，定义为:E(X)=》X(g)P(°dQ关于数学期望，我们关心它的一些基本性质：⑴ E(工XJ =》E(XJ(2) E(rX + ^y) = r£(X)4- sE(Y)(3) 如果X人是一个随机特征变量，那么E(XJ = P(X4 =1)(4) 如果E(xr)= E(x)E(y),则称X,Y是相互独立的随机变量随机变量的特征函数：一般地，在任何一个概率空间(Q,p)里面都有所谓的“随机特征变 量”：设4是概率空间(Q,/?)里面的一个事件，关于A的特征随机变量定义为:COW Ag A因此，对于每一个事件都有一个特征随机变量与之对应反过来，对于一个随机变量X和 一个实数/,我们都可以将它与下面事件{ewQ|X(e) = /}下面介绍在实际用应中数学期望的分解技术(即，将一个随机变量X分解成为若干个具 有特殊性质的集合Z特征随机变量Z和)市于我们的概率空间一般都是有限的，在计算数 学期望时往往要用到组合数学中的一个重要方法…“算两次方法(Double Counting)".例如： X是定义在概率空I'可G“上用来计算一个由一些支撑子图组成的集合H中元素的随机变 量。
根据定义，E(X)=工 X(G)P(G)是用来计算形如(G,H°)的数目的，这里，H. 6 H,且c G.其中伴随着权函数P(G)・ 我们首先根据定义，从外部循环开始，先对于空间G“中的每一个元素(随即图)G,执 行“程序”：在内部循环(H°w H)里面看每一个H中的元素H.,如果H. c G ,针对 对子(G,H°)计算概率P(G)；对称地，我们也可以将这个过程反转过來：先从每一个H中 的元素H()开始，扫描G®中的元素(随即图)，如果有支撑子图G e Gftf)使得H°uG, 则计算权P(G)这个计算的本质就是计算概率P(H0 c G) o如果使用特征函数技巧，则 有下列分解E(X)=工％)这里，X如是H的特征随机函数上式的本质来自于下面分解X= gH($H(°\/GwG”.“,X(G)=工心2)=工(Xh°(G) = 1HqwH 〃(&G= |{HoeH|HocG})下面我们将通过一个实际的应用说明数学期望的分解方法例1：设空间G“和自然数k > 3我们计算一个随机图Gw Gn f)中长为k的圈之数目的均 值解答：设X是G“中每一个随机图G中含有圈的数目的均值(期望)，显然，X是一个定义在G““上，取值于N中的随机变量。
容易看;lh 6“,,中£-圈的数目为1 / 1 n.p —八一 p • I 一 I 一 —儿"• _ —•八对于每一个圈C,我们可以定义它的特征随机变量为Xc：G“ t{0」}使得X/GwG_=>Xc(G) =CcG;根据定义，P(XC = 1)恰好追踪的是全体G“中这样的元素G,使得CuG,E(X» 工 P(G)Xc(G)=工 P(G) = P(CuG) = pJGeG“CqG由于X=》Xc，cE(X) = ZE(XC)= 〃(兀+ x pk注意：这里P(C c G)是事件CcG的概率，因此，G不是某个固定元素有点类似于下面关系P(X>a) = ^PMx>a粗略地讲，离散数学中的概率方法是沿着下面的想法发展的：为了证明具有某一种特性的对象存在，人们先定义一个足够大的概率空间，然后证明这个空间里面具有这种特性的元素的概率值为正值，下面我们将要证明著名数学家Erdos早年一个关于大围长和大色数图存在的定理Erdos的这个定理是说：“对于任意大的正整数k ,存在一个图G ,它的围长和色教胡尢幵首先我们有下面的准备工作:对于自然数％ k, n>k> 2,空间G“中的一个元素G含有一个阶数至少为k独立集的概率Z多为(、 ⑷, n ..P(^(G) >k)< (1 —/沪丿。
\k)同时还有、P(6y(G) >k)< p k它丿定理(Erdosl959)设有自然数k,I,那么有图G使得阴山@)> k.证明：固定变量e<\H且GwG“，P =严,即，G是〃个节点上的随即图，每一对节 点决定的一条潜在的边(potential edge)上的概率都独立地取值p设X是G做工长度至多 是/的圈的数目由于&/V1有17/ V \ — V1 (心 i \E(X) = 5~^—0 <2^— = o(n) oZ=3 2l 匸3 2l特别地(根据马尔科夫不等式)有P(X>n/2) = o(\)o设 x = P(3//?)ln n\ 使得P(a(G) >x)< n (1- * < [ne-p(x-l),2)' = o(l)乜丿我们可以选斤充分地大，使得上述两个不等式所涉及事件的概率都小于0.5.那么存在一个图 G ,其中长度不超过/的圈的数目少于«/2,同时独立数6Z(G)<3/2,-/lnno我们从每一个 长度不超过/的圈上拿掉一个节点，得到一个图Gb至少有〃/2个节点，同时G*的围长 大于/,且a(G*)Sa(G)•于是,g(G*) 3d 1 In n 61n/?只要我们将n。