随机图论的概率基础

目录

• 概率论中的马尔科夫不等式
• 概率论中的切比雪夫不等式
• the total variation distance
• r-th factorial moment有什么用
• 各种分布之间的联系
• geometric distribution 几何分布
• 负二项分布
• 几何分布的连续版本是指数分布(或负指数分布)
• 超几何分布 从$N$个红蓝双色球中抽取$n$个球的颜色统计
• 泊松分布

几乎可以作为任何需要基础概率论知识的学科的前导资料

Random Graphs by Béla Bollobás 书里给出的就是快问快答的形式，这里摘几个较新鲜的。不定期更新

概率论中的马尔科夫不等式

if (X) is a non-negative r.v. with mean (mu) and (tgeq0),then

[mugeq P(Xgeq tmu)tmu ]

改写一下就成为Markov's inequality

[P(Xgeq tmu)leq1/t ]

概率论中的切比雪夫不等式

Now let (X) be a real-valued r.v. with mean (mu) and variance (sigma^2) .if (dgeq 0)

[E{(X-mu)^2}>P(|X-mu|geq d)cdot d^2 ]

改写一下就成为Chebyshev's inequality

[P(|X-mu|^2geq d)leq sigma^2/d^2 ]

the total variation distance

r-th factorial moment有什么用

[E_r(X)=sumlimits_{k=r}^{infty}p_kcdot(k)_r ]

其中((k)_r)是下降乘，共(r)项

[(k)_r = k(k-1). ... (k-r+ 1). ]

Note that if (X) denotes the number of objects in a certain class then (E_r(X)) is the expected number of ordered r-tuples of elements of that class.

各种分布之间的联系

给个链接

http://www.math.wm.edu/~leemis/chart/UDR/UDR.html

geometric distribution 几何分布

The binomial distribution describes the number of successes among n trials, with the probability of a success being p. Now consider the number of failures encountered prior to the first success, and denote this by Y.

[P(Y=k)=q^kp ,k=0,1,... ]

期望(q/p),方差(q/p^2),r-th factorial moment (r!(q/p)^r)

负二项分布

The number of failures prior to the rth success, say (Zr), is said to have a negative binomial distribution

[P(Z_r=k)= binom{r+k-1}{k}p^rq^k ,k=0,1,... ]

Since Zr is the sum of r independent geometric r.vs,

期望(rp/q),方差(rq/p^2)

几何分布的连续版本是指数分布(或负指数分布)

一个非负实随机变量(L)被认为具有参数(lambda> 0)的指数分布如果

[P(L<t)=1-e^{-lambda t} for t>0 ]

PDF是(lambda e^{-lambda t}) 期望(1/lambda) 方差(1/lambda^2)

超几何分布 从(N)个红蓝双色球中抽取(n)个球的颜色统计

The hypergeometric distribution with parameters (N,R)and (n)((0<n<N,0<R<N))

[egin{aligned} q_{k} &=P(X=k)=left(egin{array}{l} R \ k end{array} ight)left(egin{array}{c} N-R \ n-k end{array} ight) /left(egin{array}{l} N \ n end{array} ight) \ &=left(egin{array}{l} n \ k end{array} ight)left(egin{array}{c} N-n \ R-k end{array} ight) /left(egin{array}{c} N \ R end{array} ight), quad k=0, ldots, s end{aligned} ]

其中(s=min{n,R})

泊松分布

[P(Y=k)=p(k ; lambda)=mathrm{e}^{-lambda} lambda^{k} / k !, k=0,1, ldots ]

期望(lambda>0)