= Solution
The <Kullback-Leibler divergence> of a <product measure> is the sum of the individual divergences, by expanding the logarithm of the <likelihood ratio> and taking its <expected value>. Put $q=1/2-t/\sqrt n$ and define $W(S)$ to be the unordered pairs lying within one group, while $C(S)$ is the set of unordered pairs crossing between groups. Then
$$
D_{\mathrm{KL}}(P_S\Vert P_{S'})=\sum_{e\in W(S)\setminus W(S')}D_{\mathrm{KL}}(\operatorname{Ber}(1/2)\Vert\operatorname{Ber}(q))+\sum_{e\in W(S')\setminus W(S)}D_{\mathrm{KL}}(\operatorname{Ber}(q)\Vert\operatorname{Ber}(1/2)).
$$
Thus choosing the printed $\partial S$ to mean $W(S)$ gives its order of the summands. If $\partial S$ denotes the usual <graph cut> $C(S)$, their two orders must be interchanged. Each unordered <edge> is counted once.
The inequality $\log x\leq x-1$ gives
$$
\boxed{D_{\mathrm{KL}}(\operatorname{Ber}(p)\Vert\operatorname{Ber}(q))\leq p\left(\frac pq-1\right)+(1-p)\left(\frac{1-p}{1-q}-1\right)=\frac{(p-q)^2}{q(1-q)}.}
$$
Since $1/3<q<1/2$, each changed-edge divergence is at most $9t^2/(2n)$. Summing over at most $n(n-1)/2$ pairs gives $D_{\mathrm{KL}}(P_S\Vert P_{S'})\leq9nt^2/4$. This is the information scale needed for <Fano's inequality>.
Back to article page
