Binomial approximation for vertex degree counts

Let $\mu (j)$ be the probability mass at $j$ of the prescribed $\mathrm{Bin}(n,f_k)$ law, for $j\in \{0,\dots ,n\}$. These masses are nonnegative and sum to one because this law is supported on $\{0,\dots ,n\}$. Hence they define a finite probability space with outcome set ${\mathrm{\Omega }}_Y=\{0,\dots ,n\}$ and weight $\mu (j)$ at $j$. The function $j\mapsto j$ on this space has the required law by [F6]. Each event probability in the comparison distance depends only on that law, so we may use this finite realization as $Y$ in the rest of the proof; the resulting distance applies to any realization of the prescribed law. No common probability space or coupling of $X_k$ and $Y$ is required.

To establish the dependence implication locally, suppose $U,V$ are independent real variables on a common finite probability space. Put $S=U(\mathrm{\Omega })$ and $T=V(\mathrm{\Omega })$. By [F5] and [F7], grouping the expectation in [F9] according to the joint values and then using [F8] gives $\mathrm{Cov}(U,V)={\sum }_{a\in S}{\sum }_{b\in T}(a-\mathbb{E}U)(b-\mathbb{E}V)\mathbb{P}(U=a)\mathbb{P}(V=b)$. Distributivity factors this into $({\sum }_{a\in S}(a-\mathbb{E}U)\mathbb{P}(U=a))({\sum }_{b\in T}(b-\mathbb{E}V)\mathbb{P}(V=b))=0$, since the marginal probabilities sum to one and the marginal weighted sums are $\mathbb{E}U$ and $\mathbb{E}V$. Thus independent finite-space variables have zero covariance. The degrees are such variables by [F1] and [F6]. When $n\ge 2$ and $0<p<1$, [F2] gives $\mathrm{Cov}(d(u),d(v))=p(1-p)>0$ for distinct vertices, so these degrees cannot be independent.

By the single-vertex degree law and the first-moment identity, $\mathbb{E}{X}_k=n{f}_k$. Grouping a finite expectation sum according to the values of its variable gives $\mathbb{E}Z={\sum }_{j=0}^{n}j\mathbb{P}(Z=j)$ for any finite-space variable $Z$ taking values in $\{0,\dots ,n\}$. Thus expectation depends only on this finite law, and [F4] gives $\mathbb{E}Y=n{f}_k$ for the realization in step 1.1. Both $X_k$ and $Y$ take values in $\{0,\dots ,n\}$. By [F7], the constant variable $n$ on either space has expectation $n{\sum }_{\omega }w(\omega )=n$, and linearity gives $\mathbb{E}(n-Z)=n-\mathbb{E}Z$ for $Z=X_k$ and separately for $Z=Y$. Applying [F5] at threshold one to the nonnegative integer-valued variables $X_k$, $Y$, $n-X_k$, and $n-Y$ therefore gives $\mathbb{P}(X_k\mathrm{\ne }0)\le n{f}_k$, $\mathbb{P}(Y\mathrm{\ne }0)\le n{f}_k$, $\mathbb{P}(X_k\mathrm{\ne }n)\le n(1-f_k)$, and $\mathbb{P}(Y\mathrm{\ne }n)\le n(1-f_k)$.

For any $A\subseteq \{0,\dots ,n\}$, if $0\mathrm{\notin }A$, both probabilities of $A$ are bounded by the corresponding probabilities of being nonzero; if $0\in A$, apply the same observation to the complement of $A$. In either case their absolute difference is at most $\mathbb{P}(X_k\mathrm{\ne }0)+\mathbb{P}(Y\mathrm{\ne }0)\le 2n{f}_k$. The same argument with $n$ in place of $0$ bounds the difference by $2n(1-f_k)$. It is also at most one. Taking the supremum proves the displayed bound, and the stated convergence follows immediately.

For $n=2$, let $A_{12}$ be one if the sole possible edge occurs and zero otherwise. Both degrees equal $A_{12}$, so for $k=1$ the definition in [F1] gives $X_1=2A_{12}$. Hence for $0<p<1$, $\mathbb{P}(X_1=0)=1-p$, $\mathbb{P}(X_1=2)=p$, and $\mathbb{P}(X_1=1)=0$. To rule out any binomial law, consider $\mathrm{Bin}(m,q)$ with an integer $m\ge 0$ and $q\in [0,1]$. If $m=0$ or $q\in \{0,1\}$, [F10] makes this law constant, unlike $X_1$. Otherwise $m\ge 1$ and $0<q<1$. The event that exactly one of its Bernoulli summands is one is the disjoint union of $m$ events, each having probability $q(1-q{)}^{m-1}$ by [F8]. Thus [F5] gives probability $mq(1-q{)}^{m-1}>0$ to the value one, whereas $X_1$ has probability zero there. This proves that $X_1$ is not binomial and completes the remaining assertions.