Estimate the density function of a distribution based on binomial distributions. Let's consider a set of nodes $V$, and let some nodes be colored with one color choosen between two possible colors; denote the color $\alpha$ and $\beta$, with respectively $I>0$ and $K>0$ nodes colored with them. 
Note that we could have $K+I<n$, and possibly $I\neq K$. 
The above coloring is fixed, and we're conditioning upon it. 
We're going to generate the set of edges $E$ according to the Erdős–Rényi model (fixed a $p\in (0,1)$, each possible edge follows Bernoulli's law with parameter $p$); now, each uncolored node is going to take the most-viewed-by-him color: in other words, he counts how many nodes in his neighborhood have the first color, and how many have the second color, and eventually become colored with the most-frequent color he sees (if the two color have the same number of occurrences, the node keep uncolored).
Before observing $E$, the probability that a node $v$ take color $\alpha$ is $$\sum_{i=1}^{I} \Big\{ {{K}\choose{i}}p^i (1-p)^{K-i}\sum_{k=0}^{\min\{ i-1,K\}}  {{I}\choose{k}}p^k (1-p)^{I-k}\Big\}$$
where $i$ counts the number of $\alpha$-colored nodes in $N(v)$ while $k$ counts the number of $\beta$-colored nodes in $N(v)$.
This expression is not very handy, especially if we want to estimate the expected number of new $\alpha$-colored nodes.
I'm looking for useful inequality and estimation that can be used for nontrivial upper and lower bounds to the density above and to the expected value of the new $\alpha$-colored and $\beta$-colored nodes.
In particular, as a first step, I would investigate the case when $p=\frac{c}{n}$ for any $c>0$, $K+I<\frac{n}{\log n}$ and $I=\frac{K}{n^\epsilon}$ for any small $\epsilon>0$.
 A: The sum is $s=\mathbb P(U\lt V)$, where $U$ and $V$ are independent and binomial $(n-1,p)$. By symmetry, $s=\mathbb P(U\gt V)$ hence $2s=1-r$ with $r=\mathbb P(U=V)$. 
Note that $r=\mathbb P(W=0)$ where $W=X_1+\cdots+X_{n-1}$ is the sum of $n-1$ i.i.d. steps $X_k$ taking values $\pm1$ or $0$ with respective probabilities $p(1-p)$, $p(1-p)$ and $p^2+(1-p)^2$. 
Let $a=2p(1-p)$, then $\mathbb E(\mathrm e^{\mathrm itX_k})=a\cos(t)+1-a$ and $\mathbb E(\mathrm e^{\mathrm itW})=\mathbb E(\mathrm e^{\mathrm itX_k})^{n-1}$ by independence, hence
$$
2\pi r=\int_{-\pi}^{\pi}\mathbb E(\mathrm e^{\mathrm itW})\mathrm dt=\frac1{\sqrt{n}}\int_{-\pi\sqrt{n}}^{\pi\sqrt{n}}\left(a\cos(t/\sqrt{n})+1-a\right)^{n-1}\mathrm dt.
$$
Since $\left(a\cos(t/\sqrt{n})+1-a\right)^{n-1}=\left(1-\frac{at^2}{2n}\right)^{n-1}\to\mathrm e^{-at^2/2}$,
$$
2\pi r\sim\frac1{\sqrt{n}}\int_{-\infty}^{+\infty}\mathrm e^{-at^2/2}\mathrm dt=\frac1{\sqrt{n}}\sqrt{\frac{2\pi}a}.
$$
Finally,
$$
s=\frac{1-r}2=\frac12-\frac{1+o(1)}{c(p)\sqrt{n}},\qquad c(p)=4\sqrt{\pi p(1-p)}.
$$
A: Let us estimate the probability that we color a given vertex $u$ (which is not among $K+I$ colored vertices) with $\alpha$. Let us say that vertex $u$ has an $\alpha$-neighbor if at least one of its neighbors is colored with $\alpha$; similarly, we say vertex $u$ has a $\beta$-neighbor if at least one of its neighbors is colored with $\beta$. Below we will need the following estimate, for $T\in [1,1/p]$, 
$$(1-p)^T = e^{T\ln (1-p)} = e^{T(-p+O(p^2))}=1-Tp +O(p^2T^2).$$
First, we prove a lower bound.
\begin{align}
\Pr[u \text{ has color } \alpha] &\geq \Pr[u \text{ has an }\alpha\text{-neighbor and has no } \beta\text{-neighbor}]\\
& = (1-(1-p)^{I})\cdot (1-p)^K = (1+O(p^2(I+K)^2))\  p I \cdot (1-Kp)   .
\end{align}
On the other hand,
\begin{align}
\Pr[u \text{ has color } \alpha] &\leq \Pr[u \text{ has an }\alpha\text{-neighbor} ]\\
& = (1-(1-p)^{I}) = (1+O(p^2(I+K)^2))\ p I   .
\end{align}
Let $\theta = (n-K-I)/n$. Let $n_\alpha$ be the number of vertices that we color in $\alpha$ (not counting those that were already colored with $\alpha$); similarly, $n_\beta$ be the number of vertices we color in $\beta$.

Then 
  $$(1+O(p^2(I+K)^2))\ \theta\, n p I \cdot (1-Kp) \leq \mathbb{E}[n_\alpha] \leq (1+O(p^2(I+K)^2))\ \theta\, n p I.$$
Similarly, we get 
  $$(1+O(p^2(I+K)^2))\ \theta\, n p K \cdot (1-Ip) \leq \mathbb{E}[n_\beta] \leq (1+O(p^2(I+K)^2))\ \theta\, n p K.$$

In the given range of parameters, for $p=c/n$, we have 
$$\mathbb{E}[n_\alpha] = (1+o(1)) \,c I,$$
 and 
$$\mathbb{E}[n_\beta] = (1+o(1)) \,c K.$$
