Chebyshev's Inequality Chebyshev's Inequality: For any t >0, ar[X] Pr[X-E[X]川≥t]≤ t2
Chebyshev’s Inequality Chebyshev’s Inequality: Pr[|X ⇥E[X]| ⌅ t] ⇤ Var[X] t 2 . For any t > 0
Variance Definition(variance); The variance of a random variable X is VAr[X]=E[(X-E[X)2]=E[x2]-(EX])2 The standard deviation of random variable X is 6[X]=VVar[X]
Variance Definition (variance): The variance of a random variable X is Var[X] = E (X E[X])2⇥ = E X2⇥ (E[X])2 . The standard deviation of random variable X is [X] = Var[X]
Covariance Theorem: Var[X+Y]=Var[X]+Var[Y]+2Cov(X,Y); n n Var Var[Xl+∑Cov(Xi,Xi). i=1 i计i Definition (covariance): The covariance of X and Y is Cov(X,Y)=E[(X-E[X])(Y-E[Y])]
Covariance Definition (covariance): The covariance of X and Y is Cov(X,Y ) = E[(X E[X])(Y E[Y ])]. Theorem: Var[X +Y ] = Var[X]+Var[Y ]+2Cov(X,Y ); Var ⇤ n i=1 Xi ⇥ = ⇤ n i=1 Var[Xi]+ ⇤ i=j Cov(Xi ,Xj)
Random Graphs Paul Erdos Alfred Renyi (1913-1996) (1921-1970)
Random Graphs Alfréd Rényi (1921 - 1970) Paul Erdős (1913 - 1996)
Erdos-Renyi 1960 paper: ON THE EVOLUTION OF RANDOM GRAPHS by P.ERDOs and A.RENYI Institute of Mathematics Hungarian Academy of Sciences,Hungary 1.Definition of a random graph Let En,w denote the set of all graphs having n given labelled vertices Vi,Va,, Vn and N edges.The graphs considered are supposed to be not oriented,without parallel edges and without slings (such graphs are sometimes called linear graphs). Thus a graph belonging to the set En,N is obtained by choosing N out of the possible(2)edges between the points Vi,V2,..,Vn,and therefore the number of elements of E is quat.A random graphcan be defined as an element of En,w chosen at random,so that each of the elements of En,x have the same probability to be chosen,namely1 There is however an other slightly different point of view,which has some advantages.We may consider the forma. tion of a random graph as a stochastic process defined as follows:At time t=1 we choose one out of the (possible edges connecting the points Vi,V2,.,V
ON THE EVOLUTION OF RANDOM GRAPHS P. ERD& and A. RBNYI Institute of h4fathematics Hmgarian Academy of Sciences, Hungary 1. Definition of a random graph Let E,, .V denote the set of all graphs having n given labelled vertices VI, L’s;,., Vn and N edges. The graphs considered are supposed to be not oriented, without parallel edges and without slings (such graphs are sometimes called linear graphs). Thus a graph belonging to the set En, N is obtained by choosing N out of the possible (5) edges between the points VI, VZ, ..., Vn, and therefore the number of n elements of En, ?V is equal to 2 (’ ‘> . AT A random graph r,, N can be defined as an element of En, N chosen at random, so that each of the elements of E,, N have the same probability to be chosen, namely 1 /( > ‘I;l . There is however an other slightly different point of view, which has some advantages. We may conszder the formation of u random graph as a stochastic process defined as follows : At time t=l we choose one out of the (;) p ossible edges connecting the points VI, VZ,..., V,, each of these edges having the same probability to be chosen ; let this edge be denoted by el. At time t=2 we choose one of the possible (z) -1 edges, different from er, all these being equiprobable. Continuing this process at time t=k+l we choose one of the (a) 4 p ossible edges different from the edges er, ez, ..., ek already chosen, each of the remaining edges being equiprobable, i.e. having the probability 1 /I(;)-k). We d enote by r,, .V the graph consisting of the vertices VI, Vt, .. ., LTfi and the edges el, e2, ‘.., eN. 11 Other not equivalent but closely connected notions of random graphs are as follows: 1) \Ve may define a random graph i’z, G by dropping the restriction that there should be no parallel edges; thus we may suppose that e,+t may be equal with probability 1 /(z) with each of the [z) edg es, independently of whether they are contained in the sequence of edges e,, e?, .‘., e,t or not. These randum graphs are considered in the paper 131. 2) T%‘e may decide with respect to each of the (?J) edges, whether they should form part of the random graph considered or not, the probability of including a given edge being p= lV/:( i) for each edge and the decisions concerning different edges being independent. We denote the random graph thus obtained by rzf,%,. These random graphs have been considered in the paper [4J Erdős-Rényi 1960 paper:
G(n,p） ® V=n Vu,v∈V independently Pr[{u,v}EE]=p uniform random graph:G(n
|V | = n ⇥u, v V G(n, p) independently Pr [ {u, v} E ] = p uniform random graph: G(n, 1 2 )
G(n,P) Probability space: 2(g) Pr[G]=plGl(1-p)(3)-IGI
G(n, p) Probability space: 2( [n] 2 ) Pr[ G ] = p|G| (1 p)( n 2)|G|
Threshold Pr[G(n,p)has property P] 1 p 0 1
Threshold p Pr[G(n, p) has property P] 0 1 1
Threshold Property P p(n)is a threshold for property P: p=o(p(n)) Pr[G(n,p)has P]=o(1) p=w(p(n)) Pr[G(n,p)has P]=1-o(1)
Pr[G(n, p) has P ] = 1-o(1) Pr[G(n, p) has P ] = o(1) Threshold Property P p(n) is a threshold for property P: 㱺 㱺 p = o(p(n)) p = (p(n))
Property k-clique:contain a k-clique as a subgraph. Theorem The threshold for k-clique is f(n)=n-2/(k1) p=o(f(n)) Pr[G(n,p)contains a k-clique]=o(1) p=w(f(n)) >Pr[G(n,p)contains a k-clique]=1-o(1)
k k 2/(k1) k k k Property -clique: contain a -clique as a subgraph. Theorem The threshold for -clique is p = o(f(n)) p = !(f(n)) f(n) = n Pr[G(n, p) contains a -clique] = o(1) Pr[G(n, p) contains a -clique] = 1 o(1)