19 3.Linearity of Expectation of certain events with known probabilities.Then E[X]P[A]+P[A]+...+P[An]. Example.Let us calculate the expected number of fixed points of a random permutation o on (1.n.If X(a)={()=l, we can express this as a sum of indicator variables: xo)=∑xXo) where Xi(a)=1 if a(i)=i and 0 otherwise.Then E即周=Pe0==月 and =+片+…+=1 So a random permutation has 1 fixed point (or "loop")on the average. 3.2 Hamiltonian Paths We expectation of X to estimate the minimum or ma there alwaysx mum value 2 for which X(u)≥ is an orientation of a complete graph (for any two vertices u,v,exactly one of the directed edges (u,) )and (v,u)is present A Hamilt path in a tournament is a directed d path passing through all vertices.The following result of Szele(1943)shows the existence of a tournament with very many Hamiltonian paths. 3.2.1 Theorem.There is a tournament on n vertices that has at least Hamiltonian paths Proof.Let us calculate the e cted number of Hamiltonian enautati0oorieutatio with bability ). sider t an X th t that an ith th +1 of diff erent edges is ch EXl=P[o(0,ai+)∈Tfor i=1,2n-1刂=2 The total number of Hamiltonian paths X equals the sum of these indicator variables over all potential Hamiltonian paths,i.e.permutations,and so EX]=∑EX=- So there is a tournament with at leastHamiltonian paths. 19 3. Linearity of Expectation of certain events with known probabilities. Then E [X] = P[A1] + P[A2] + · · · + P[An] . Example. Let us calculate the expected number of fixed points of a random permutation σ on {1, . . . , n}. If X(σ) = |{i: σ(i) = i}|, we can express this as a sum of indicator variables: X(σ) = Xn i=1 Xi(σ) where Xi(σ) = 1 if σ(i) = i and 0 otherwise. Then E [Xi ] = P[σ(i) = i] = 1 n and E [X] = 1 n + 1 n + · · · + 1 n = 1. So a random permutation has 1 fixed point (or “loop”) on the average. 3.2 Hamiltonian Paths We can use the expectation of X to estimate the minimum or maximum value of X, because there always exists an elementary event ω ∈ Ω for which X(ω) ≥ E [X] and similarly, we have X(ω) ≤ E [X] for some ω ∈ Ω. We recall that a tournament is an orientation of a complete graph (for any two vertices u, v, exactly one of the directed edges (u, v) and (v, u) is present). A Hamiltonian path in a tournament is a directed path passing through all vertices. The following result of Szele (1943) shows the existence of a tournament with very many Hamiltonian paths. 3.2.1 Theorem. There is a tournament on n vertices that has at least n! 2n−1 Hamiltonian paths. Proof. Let us calculate the expected number of Hamiltonian paths in a random tournament T (every edge has a random orientation, chosen independently with probability 1 2 ). For a given permutation σ on {1, . . . , n}, consider the sequence {σ(1), σ(2), . . . , σ(n)} and denote by Xσ the indicator of the event that all the edges (σ(i), σ(i+ 1)) appear in T with this orientation. Because the orientation of different edges is chosen independently, E [Xσ] = P[(σ(i), σ(i + 1)) ∈ T for i = 1, 2, . . . , n − 1] = 1 2 n−1 . The total number of Hamiltonian paths X equals the sum of these indicator variables over all potential Hamiltonian paths, i.e. permutations, and so E [X] = X σ E [Xσ] = n! 2 n−1 . So there is a tournament with at least n! 2n−1 Hamiltonian paths. ✷