随机图论的概率基础

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

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

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

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

改写一下就成为Markov‘s inequality

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

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

改写一下就成为Chebyshev‘s inequality

the total variation distance

r-th factorial moment有什么用

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

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.

期望\(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

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

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

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

一个非负实随机变量\(L\)被认为具有参数\(\lambda> 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)\)

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

泊松分布

期望\(\lambda>0\)

更新点Erd?s–Rényi graph的东西

这里扔几个链接
https://en.wikipedia.org/wiki/Erd?s–Rényi_model
Exact probability of random graph being connected
Probability of not having a path between two certain nodes, in a random graph
Prove that: Probability of connectivity of a random graph is increasing with the size of the graph