INSTRUCTIONS
• Discussions with other students are not discouraged. However, all write-ups must be done individually with your own solutions.
• Be clear and precise in your writing.
Problem 1. Consider a 4×4 matrix in which all the entries are equal to 1. Note that this has an equivalent representation in the form of a complete bipartite graph and the permutation σ = (1 2 3 4) (i.e., σ(i) = i, for all i ∈ [1 : 4]) corresponds to a perfect matching of that graph. For an arbitrary permutation τ, define k = τ−1(1) and N1(σ,τ) = |{1,2,3,4} {σ(τ(1)),σ(τ(2)),...,σ(τ(k − 1))}|. For j ∈ [1 : 4], argue that for all permutations τ such that τ(j) = 1, we have N1(σ,τ) = 5 − j. Finally, conclude that the number of permutations τ for which N1(σ,τ) = j is equal to 6, for all j ∈ [1 : 4].
with equality if and only if X is a Gaussian random variable.
Problem 3. For any two probability distributions PX and QX, suppose holds, for a constant k. Show that k ≤ 2.
[Hint. Consider and , for
Problem 4. Let PX and QX be two probability distributions on X and f : X → [0,B], where B is a constant. Prove that |EX∼PX[f(X)] − EX∼QX[f(X)]| ≤ B.TV (PX,QX).
