How did the following approximation arise in Bayati's paper on random graph generation

32 Views Asked by At

so I have been doing a bit of research on Bayati's paper. It can be found on https://arxiv.org/pdf/cs/0702124.pdf. The exact details of my problem can be found at page $5$ of the paper.

With that said I will try my best to set up my problem here.

$\bar d = (d_1,....,d_n)$, a degree sequence for $n$-vertices.

For a fixed Graph $G$, Let $m$ be the number of edges of $G$.

Now define $q_r = \frac{m-r}{m}, \lambda(\bar d) = \frac{\sum_{i\in[n]}\binom{d_i}{2}}{\sum_{i\in n} d_i}, \gamma_G = \sum_{i\sim_G j \frac{d_id_j}{4m}}$

Lastly let's believe for now that $\binom{2m-2r}{2}\approx 2m^2q_r^2$.

How did Bayati came up with the approximation for

$\begin{equation}\Pi_{r\in[m]}\frac{1}{2m^2q_r^2 - 2mq_r^2\lambda(\bar d) - 4m(1-q_r)q_r^2\gamma_G} \end{equation} \approx e^{\lambda(d) + \gamma_G}\ \Pi_{r\in[m]}\frac{1}{\binom{2m-2r}{2}}$

I worked on this for quite some time and I cant see why Bayati managed to drop so many terms on the exponential ? Any help with this is deeply appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

From the denominator of $2m^2q_r^2 - 2mq_r^2\lambda(\bar d) - 4m(1-q_r)q_r^2\gamma_G$, factor out a $2m^2 q_r^2$, which will form part of the approximation: $$\prod_{r \in [m]} \frac1{2m^2 q_r^2} \approx \prod_{r \in [m]} \frac1{\binom{2m-2r}{2}}.$$ What's left in the denominator is $1 - \frac1{m}\lambda(\bar d) - \frac{2(1-q_r)}{m}\gamma_G = 1 - \frac1{m}\lambda(\bar d) - \frac{2r}{m^2}\gamma_G$.

The second part of the approximation is, in general terms, $$ \prod_{r \in [m]} \frac1{1 - a_r} \approx \prod_{r \in [m]}\frac1{e^{-a_r}} = \exp\left(\sum_{r \in [m]} a_r\right) $$ where $a_r = \frac1m \lambda(\bar d) + \frac{2r}{m^2}\gamma_G$. This approximation is valid provided $a_r$ is small: $1 - a_r \sim e^{-a_r}$ as $a_r \to 0$.

Finally, $\sum_{r \in [m]} a_r$ simplifies exactly to $\lambda(\bar d) + \frac{m+1}{m} \gamma_G$, which it is reasonable to approximate as $\lambda(\bar d) + \gamma_G$.