Fix some positive integers $N$ and $d\_k$, $k=1,2,\dots$ with $N=\sum\_{k=1}^\infty d\_k$.


Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ vertices, $d\_k$ of which have degree $k$ (i.e., they are connected by an edge to $k$ other vertices).


Now suppose that you (uniformly) randomly pick $M$ vertices of $G$ to form a new graph $U$, $M < N$. Join two vertices of $U$ by an edge if there is an edge in $G$ between these two vertices. Hence $U$ is a random subgraph of $G$.


Now let $p\_k$ be the number of vertices in $U$ that have degree $k$.


If $M$, $N$, and $d\_k$ are fixed, what is the expectation of $p\_k$?



The degrees in a random subgraph
It doesn't matter that $G$ was chosen randomly. The choice of $G$ might matter if you asked for something more complicated about the distribution than the expected value.


The probability that a vertex $v$ is included is $M/N$.


Let the degree of $v$ be $h \ge k$ in $G$. The chance that precisely $k$ of its neighbors are included in $U$, conditioned on the inclusion of $v$, is 


$$\frac{{h \choose k}{N-h-1 \choose M-k-1}}{N-1 \choose M-1}. $$ 


So, the expected number of vertices of degree $k$ in $U$ is


$$ \sum\_{h \ge k} d\_h \frac{M}{N}\frac{{h \choose k}{N-h-1 \choose M-k-1}}{N-1 \choose M-1}.$$


