TThe probabilistic Method Pick random ball from a box, Pr[the ball is blue]>0 889 →There is a blue ball.. Define a probability space Q,and a property P: Pr[P(x)]>0 >3xE with the property P
The Probabilistic Method • Pick random ball from a box, Pr[the ball is blue]>0. ⇒ There is a blue ball. • Define a probability space Ω, and a property P: Pr x [P(x)] > 0 = ⇤x ⇥ with the property P
Averaging Principle .Average height of the students in class is l. →There is a student of height≥l(sI) .max avg min 江市 For a random variable X, .xs E[X],such that X=x is possible; ·x≥EX],such that X=x is possible
• Average height of the students in class is l. ⇒ There is a student of height ≥ l ( ≤ l ) Averaging Principle min max avg • For a random variable X, • ∃ x ≤ E[X], such that X = x is possible; • ∃ x ≥ E[X], such that X = x is possible
Hamiltonian paths in tournament Hamiltonian path: a path visiting every vertex exactly once. Theorem(Szele 1943) There is a tournament on n players with at least n!2-(-1)Hamiltonian paths
Hamiltonian paths in tournament There is a tournament on n players with at least n!2(n1) Hamiltonian paths. Theorem (Szele 1943) Hamiltonian path: a path visiting every vertex exactly once
Theorem(Szele 1943) There is a tournament on n players with at least n!2-(1)Hamiltonian paths. Pick a random tournament T on n players [n]. For every permutation x of [n], x-6anm #Hamiltonian paths:=X E[X]=Pr[Xz=1]=2m-)
There is a tournament on n players with at least n!2(n1) Hamiltonian paths. Theorem (Szele 1943) For every permutation π of [n], π is a Hamiltonian path π is not a Hamiltonian path X = 1 0 Pick a random tournament T on n players [n]. X = # Hamiltonian paths: X E[X] = Pr[X = 1] = 2(n1)
Theorem(Szele 1943) There is a tournament on n players with at least n!2-(1)Hamiltonian paths. Pick a random tournament T on n players [n]. Hamiltonian paths:=X 2 EX]=Pr[X元=1]=2-n-) E[X]=∑E[Xxl=n2(n-)
There is a tournament on n players with at least n!2(n1) Hamiltonian paths. Theorem (Szele 1943) Pick a random tournament T on n players [n]. X = # Hamiltonian paths: X E[X] = Pr[X = 1] = 2(n1) E[X] = E[X] = n!2(n1)