The probabilistic Method Pick random ball from a box, o0 Pr[the ball is bluel>0 000 →There is a blue ball. Define a probability space O,and a property P: Pr[P(x)]>0 X xE 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 / →There is a student of height≥l(sl) max avg min For a random variable X, ·3x≤EX☑，such that X=x is possible; ●3x≥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-(n-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-(n-1)Hamiltonian paths. Pick a random tournament T on n players [n]. For every permutation x of [n], 1 πis a Hamiltonian path x is not a Hamiltonian path Hamiltonian paths:= π E[X]=Pr[XI =1]=2-(n-1)
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-(n-1)Hamiltonian paths. Pick a random tournament T on n players [n]. Hamiltonian paths:=X EXπ]=Pr[Xz=1=2-n-) EX]=∑E[XJ=n2n-) 兀
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)