Random Variables · Theory Problems

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Advanced Problems.

  1. (20 points) Let \(F\) be a \(k\)-CNF in which every clause has \(k\) literals and the number of clauses \(m\) is less than \(2^{k}\). Prove that \(F\) is satisfiable.
  2. (20 points) Consider a random graph \(G(n, p)\) where every pair of vertices is connected by an edge with probability \(p\), independent of others. A triangle is a set of 3 distinct vertices \(\{u, v, w\}\) where edges \((u,v), (v,w), (w,u)\) all exist.
    • What is the expected number of triangles?

    • If \(n \to \infty\) and \(p = c/n\) for some constant \(c \in (0, 1)\), then what is the limit of the expected number of triangles?

    Hint:
    Define an indicator random variable \(I_{S}\) for every subset \(S\) of 3 distinct vertices, where \(I_{S} = 1\) if the vertices in \(S\) form a triangle and \(0\) otherwise. The total number of triangles is the sum of these indicators over all \(\binom{n}{3}\) possible subsets. For the second part, substitute \(p = c/n\) into the formula you derived and evaluate the limit as \(n \to \infty\).
  3. (20 points) Consider \(a_{0}, a_{1}, …, a_{n} \in \{0,1\}^{n}\) where \(a_{0} = (0,…,0)\) and each \(a_{i+1}\) is obtained from \(a_{i}\) by flipping one uniformly random coordinate. Let \(X\) be the number of ones in \(a_{n}\). Find \(\lim_{n\to\infty}E[X]/n\).
    Hint:
    Focus on the state of a single coordinate after \(n\) steps. A bit will be \(1\) if and only if it has been flipped an odd number of times throughout the process.
  4. (20 points) Let \(A\) be an \(n \times n\) matrix where each entry is chosen independently and uniformly from the finite field \(\mathbb{F}_{2}\). Calculate the limit of the probability that \(A\) is invertible as \(n \to \infty\). \[\lim_{n \to \infty}\Pr[\det(A) \neq 0].\]
    Hint:
    Consider the rows of the matrix sequentially. For the matrix to be invertible, the rows must form a linearly independent set. Determine the number of valid choices for the \(k\)-th row, given that it cannot lie in the subspace spanned by the previous \(k-1\) rows.
  5. (30 points) Consider a subcritical Galton-Watson branching process \(\{Z_{n}\}_{n \ge 0}\) starting with one ancestor \(Z_{0} = 1\). In this process, each individual in generation \(n\) produces offspring independently according to the same distribution to form generation \(n+1\). In this case, the offspring distribution is Poisson with parameter \(\lambda < 1\).

    Let \(T = \sum_{n=0}^{\infty} Z_{n}\) be the total progeny, representing the total number of individuals that ever exist in the family tree. Prove that the total progeny \(T\) follows the Borel distribution: \[\Pr[T = k] = \frac{(k\lambda)^{k-1}}{k!}e^{-k\lambda}.\]