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. (a) Let Z1,Z2,...,Zn be a sequence of independent and identically distributed (i.i.d.) random variables with mean µ and variance σ2. Let be the sample mean. Show that Z¯n converges to µ in probability, i.e., for every ϵ > 0,
lim P(|Z¯n − µ| > ϵ) = 0.
n→∞
This is known as the weak law of large numbers (WLLN).
(b) For a sequence xn := (x1,x2,...,xn) with xi, for i ∈ [1 : n], taking values in a finite alphabet X, the empirical PMF is defined as . Let Xn = (X1,X2,...,Xn) be a sequence of i.i.d. random variables with Xi, for each i ∈ [1 : n], distributed according to PX over X. Using WLLN, show that πXn(x) converges to PX(x) in probability, i.e., limn→∞ P(|πXn(x) − PX(x)| > ϵ) = 0, for all x ∈ X.
Problem 2. A tripartite graph is a graph where the vertex set can be partitioned into three disjoint sets A, B, and C such that no two vertices within the same set have an edge between them. Let n1 be the number of edges between vertices in A and vertices in B, n2 be the number of edges between B and C, and n3 be the number of edges between A and C. Suppose n denotes the maximum number of triangles in such a graph. Prove that n2 ≤ n1n2n3.
[Hint. A triangle can be represented by three vertices, one each from A, B, and C. Pick a triangle uniformly at random from the set of all triangles in the graph.]
Problem 3. Let S be a random variable distributed according to PS over the set of all subsets of [1 : n] and µ be such that P(i ∈ S) ≥ µ, for all i ∈ [1 : n]. Then for jointly distributed random variables X1,X2,...,Xn,
µH(X1,X2,...,Xn) ≤ ES∼PS[H(XS)].
