Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(v_1,v_2,v_3,v_4)$, and edges $E=(e_1,e_2,e_3)$ where $e_1=(v_1,v_2)$,$e_2=(v_2,v_3)$ and $e_3=(v_3,v_4)$.
In other words a graph with the structure
o-o-o-o
Am I correct in assuming that $q_{j,k}$ can be calculated with the formula
$q_{j,k} = \mu(j,k)\frac{n(j,k)}{2|E|}$
where $n(j,k)$ is the number of edges connecting nodes with remaining degrees $j$ and $k$, and $\mu(j,k) = \begin{cases} 2 \text{ if } j = k \\ 1 \text{ else} \end{cases}$. In which case an estimation of $q_{j,k}$ based on graph $G$ would be the following:
$q_{0,1} = q_{1,0} = 1\frac{2}{6} \\ q_{1,1} = 2\frac{1}{6}$
As you can see, all probabilities sum to 1. However online there is a slide show (page 9) that shows that the joint degree distribution, which is closely related to the remaining degree distribution, is apparently supposed to be calculated with a similar formula except $j$ and $k$ are now degrees rather than remaining degrees (subtract 1), and $\mu(j,k) = \begin{cases} 1 \text{ if } j = k \\ 2 \text{ else} \end{cases}$.
With the formula suggested in the slide show the calculation of $q_{j,k}$ wouldn't work even if $j$ and $k$ were degrees rather than remaining degrees because the probabilities wouldn't add up to 1. So am I missing something or has a mistake been made in those slides?
Best Answer
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j \ne k$, then the edge has a $\frac12$ chance of contributing to $q_{j,k}$ and a $\frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $\frac{m(j,k)}{\nu(j,k) \cdot m}$ where $m$ is the number of edges and $\nu(j,k) = \begin{cases}1 & j=k \\ 2 & \text{else}\end{cases}$, and it's possible that here is where the mistake comes from.