Chapter 4: Derandomisation

(a) To generate a uniformly random integer in \(\{1, \ldots, n\}\), we need \(\lceil \log_2 n \rceil\) random bits. These bits encode a binary number in \(\{0, \ldots, 2^{\lceil \log_2 n \rceil} - 1\}\). If \(n\) is not a power of 2, we may need to reject and resample (but the number of bits per attempt is \(\lceil \log_2 n \rceil\)).

(b) A uniformly random subset of \(\{1, \ldots, n\}\) is determined by \(n\) independent fair coin flips (one per element: include if heads). So we need exactly \(n\) random bits. \(\square\)

(a) \(\Pr[Z = 0] = \Pr[X = Y] = \Pr[X=0]\Pr[Y=0] + \Pr[X=1]\Pr[Y=1] = 1/4 + 1/4 = 1/2\). Similarly \(\Pr[Z = 1] = 1/2\). So \(Z\) is uniform.

(b) We check all pairs:

• \(X, Y\): independent by assumption.
• \(X, Z\): For any \(a, c \in \{0,1\}\), \(\Pr[X=a, Z=c] = \Pr[X=a, Y=a \oplus c] = \Pr[X=a]\Pr[Y=a \oplus c] = 1/4\). So \(X\) and \(Z\) are independent.
• \(Y, Z\): Symmetrically, \(\Pr[Y=b, Z=c] = 1/4\). So \(Y\) and \(Z\) are independent.

(c) No! They are not mutually independent. Knowing any two determines the third: \(Z = X \oplus Y\). For instance:

This is a canonical example: pairwise independence does not imply mutual independence. \(\square\)

Let \(\mathcal{H}\) be a strongly universal family of functions from \(U\) to \(\{0,1\}\). For distinct \(x, y \in U\):

Since the range has size 2, we get \(\Pr[h(x) = h(y)] = 1/2 = 1/|\text{range}|\), which is exactly the universal hashing condition.

More generally, for a strongly universal family into a range of size \(q\), summing over all \(q\) values of \(a\): \(\Pr[h(x) = h(y)] = \sum_{a} \Pr[h(x) = a, h(y) = a] = q \cdot \frac{1}{q^2} = \frac{1}{q}\). \(\square\)

(a) Run Algorithm 6 multiple times and keep the best cut. Since \(\mathbb{E}[c(A,B)] = m/2\), by Fact 22.3, each run has positive probability of achieving \(c(A,B) \geq m/2\). Let \(p = \Pr[c(A,B) \geq m/2]\). After \(t\) independent runs, the probability of never achieving \(\geq m/2\) is \((1-p)^t\). Setting \((1-p)^t \leq 0.01\) gives \(t \geq \lceil \ln(100)/\ln(1/(1-p)) \rceil\).

Since \(p \geq 1/(m+1)\) (at least one of the \(m+1\) possible cut values \(\{0, 1, \ldots, m\}\) is \(\geq m/2\), so the random partition hits it with some positive probability), repeating \(O(m)\) times suffices.

(b) By a more careful counting argument, the probability is at least \(\frac{1}{m+2}\). For each edge, the indicator \(Y_e\) contributes to the sum \(c(A,B) = \sum Y_e\). Since the bits are fully independent, we can show via a second-moment argument or direct counting that the probability mass at or above the mean is at least \(1/(m+2)\). (In many cases the probability is much larger, close to \(1/2\).) \(\square\)

(a) Fix distinct \(x, y \in \{0,1\}^k\) and target values \(\alpha, \beta \in \{0,1\}\). We need:

The conditions are \(\langle a, x \rangle \oplus b = \alpha\) and \(\langle a, y \rangle \oplus b = \beta\). Subtracting (over \(\mathbb{F}_2\)):

Since \(x \neq y\), the vector \(x \oplus y\) is nonzero. So exactly half of all \(a \in \{0,1\}^k\) satisfy this equation (the solutions form a coset of a codimension-1 subspace). Given any such \(a\), exactly one value of \(b\) satisfies \(\langle a, x \rangle \oplus b = \alpha\). So the number of valid \((a, b)\) pairs is \(2^{k-1} \cdot 1 = 2^{k-1}\) out of \(2^{k+1}\) total, giving probability \(1/4\). \(\checkmark\)

(b) \(|\mathcal{H}| = 2^{k+1}\) (choices for \(a\) and \(b\)). We need \(k + 1\) random bits.

(c) Evaluating \(h_{a,b}(x)\) requires computing the inner product \(\langle a, x \rangle\) over \(\mathbb{F}_2\), which is a bitwise AND followed by XOR (popcount mod 2). This takes \(O(k)\) time. \(\square\)

(a) Assign each vertex to group \(A\) or \(B\) independently with probability \(1/2\). For a directed triangle \(u \to v \to w \to u\), the probability that all three edges cross the partition (i.e., exactly the right pattern of \(A\) and \(B\) assignments) requires specific alternation. There are \(2^3 = 8\) equally likely assignments of 3 vertices. Exactly 2 out of 8 give a proper crossing pattern for the directed triangle. So each triangle is properly oriented with probability \(1/4\).

By linearity of expectation, the expected number of properly oriented triangles is \(T/4\) where \(T\) is the total number of directed triangles.

(b) Using conditional expectations: Process vertices \(v_1, \ldots, v_n\). For vertex \(v_i\), compute the conditional expected number of properly oriented triangles if \(v_i\) is placed in \(A\) vs \(B\), considering the vertices already placed and averaging over the remaining unplaced vertices. Choose whichever gives a higher conditional expectation.

Alternatively, using 3-wise independence: The proof uses 3 vertex bits per triangle, so we only need 3-wise independence. Construct a 3-wise independent family using \(O(\log n)\) bits, then enumerate all seeds. \(\square\)

Probabilistic method: Consider the complete graph \(K_n\). Colour each vertex red or blue with probability \(1/2\) independently. For any triangle \(\{u,v,w\}\), the probability that all three vertices get the same colour is:

The total number of triangles in \(K_n\) is \(\binom{n}{3}\). By linearity of expectation, the expected number of monochromatic triangles is:

Since the expectation is at most \(n^3/24\), there exists a colouring achieving at most this many monochromatic triangles.

Derandomisation: Use the method of conditional expectations. Process vertices one by one. For each vertex, choose the colour (red or blue) that minimises the conditional expected number of monochromatic triangles among already-coloured triples. Each step can be computed in \(O(n^2)\) time (checking all pairs involving the current vertex), giving a total time of \(O(n^3)\). \(\square\)

(a) For distinct \(x, y \in \mathbb{F}_p^k\), we need \(\Pr_a[h_a(x) = h_a(y)] = 1/p\). We have:

Since \(x \neq y\), the vector \(x - y\) is nonzero in \(\mathbb{F}_p^k\). For a uniformly random \(a \in \mathbb{F}_p^k\), the inner product \(\langle a, x-y \rangle\) is uniformly distributed over \(\mathbb{F}_p\) (since at least one coordinate of \(x-y\) is nonzero, say coordinate \(j\), and \(a_j\) ranges over all of \(\mathbb{F}_p\)). So:

(b) For strong universality, we need: for all distinct \(x, y\) and all \(\alpha, \beta \in \mathbb{F}_p\): \(\Pr_a[h_a(x) = \alpha, h_a(y) = \beta] = 1/p^2\).

Consider \(k = 1\), \(x = 1\), \(y = 2\). Then \(h_a(1) = a\) and \(h_a(2) = 2a\). The condition \(h_a(1) = \alpha\) forces \(a = \alpha\), which then forces \(h_a(2) = 2\alpha\). So \(\Pr[h_a(1) = \alpha, h_a(2) = \beta] = 0\) whenever \(\beta \neq 2\alpha\). This is not \(1/p^2\) for all \(\alpha, \beta\).

The issue is that this family has only \(k\) degrees of freedom (the entries of \(a\)), but strong universality for pairs requires \(k+1\) degrees of freedom (adding a constant term \(b\), as in \(h_{a,b}(x) = \langle a, x \rangle + b \mod p\)). \(\square\)