Edge probability of random graph with prescribed degree sequence Let G be a graph which is randomly generated from degree sequence D = (d1, d2, .., dn) and x, y are vertices in G. How to compute the probability that (x, y) is an edge of G? 
 A: I want to show, that your problem can be solved by solving $O(n)$ times more common problem:

Problem 2: What is the number of graphs with degrees $(d_1,\dots,d_n)$?

Let's denote this number by $f(d_1,\dots,d_n)$. It's generating function is equal to
$$F=F(z_1,\dots,z_n)=\prod_{i< j}(1+z_iz_j)\tag{1}$$
(assuming that multiple edges and cycle-edges are not allowed). For simplicity I'll assume, that $x$ is a first vertex (with degree $d_1$) and $y$ is the second and $d_1\leq d_2$. Probability, you are interested in, is equal to
$$p=1-g(d_1,\dots,d_n)/f(d_1,\dots,d_n)\tag{2},$$
where $g(d_1,\dots,d_n)$ is equal to number of graphs with degrees $(d_1,\dots,d_n)$ which does not contain edge $\{1,2\}$. It's generating function is equal to $$G=G(z_1,\dots,z_n)=\prod_{i< j;\{i,j\}\neq\{1,2\}}(1+z_iz_j),\tag{3}$$
so we have
$$F=(1+z_1z_2)G.\tag{4}$$
Therefore
$$f(d_1,d_2,d_3,\dots,d_n)=g(d_1,d_2,d_3,\dots,d_n)+g(d_1-1,d_2-1,d_3,\dots,d_n)\tag{5}$$ and
$$g(d_1,\dots,d_n)=\sum_{k=0}^{d_1} (-1)^k f(d_1-k,d_2-k,d_3,\dots,d_n).\tag{6}$$
From (2) and (6) we see, that solving problem 2 ($d_1+1$ times) is enough for calculating desired probability.
Of course problem 2 can be solved in time $c(n(n-1)/2)(d_1+1)(d_2+1)\dots (d_n+1)$, but I think you can try to find a better solution. Problem 2 might be a known graph enumeration problem. Probably you already know about this book, but if you don't, take a look.
