Wireless networks are typically modeled as random geometric graphs. The number of nodes $N$ in the network is drawn from a Poisson distribution with intensity $\lambda$ 


$$P(N = n) = \frac{\lambda^n e^{-n}}{n!}.$$ 


Once this number has been chosen, the $N$ nodes are placed uniformly at random over a circular (or squared) area of radius $R$. Two nodes are then connected by an edge if their euclidean distance is less than some predefined range, say $r\_0$, where $r\_0 << R$. 


As a result of [**Penrose's Theorem**](http://www.maths.bath.ac.uk/~masmdp/ab/kcon.html) to ensure that the graph is $k$-connected, it is sufficient to show that the minimum degree is at least $k$, i.e., $d\_{\rm min} \geq k$. This holds true asymptotically for a geometric random graph. 


I came across two papers dealing with connectivity in (wireless) networks (this is [**one**](http://www-lih.univ-lehavre.fr/~guinand/Enseignement/RIID/Bibliographie/2004_Bettstetter_On-the-connectivity-of-adhoc-networks.pdf), and here is [**another one**](http://cst.mi.fu-berlin.de/teaching/WS0607/19639-S/bettstetter02minimum.pdf), but there are others by different Authors in the literature). When posing the condition that the minimum degree is at least $k$, I often find this approximation:


$$ P(G{\rm ~is~k~conn}) \cong P (d\_{\rm min} \geq k) \cong P(d \geq k)^n$$ 


where $P(d \geq k)$ is the probability that the degree of a node (any node) is at least $k$. The first approximation is essentially true when the number of nodes is at least of a few hundreds. The second approximation is not true since the nodes degrees are correlated. What people say when using it, is that they assume *almost* statistical independence of the nodes degrees.  

In practice there is an excellent match between simulation results and the approximation above. Since I need to use the very same approximation, I was wondering if someone had a better argument to justify its use, rather than assuming its validity from the very beginning.



(almost) statistical independence of nodes degrees in a graph
This is a partial answer concerning the validity of the second approximation. I'll consider the case $k=1$ for simplicity: all the difficulties and tricks will be clear from it already.


First of all, when people claim that some probability estimate agrees well with simulations, they always mean the difference metric. There is no way to distinguish between the probability $10^{-20}$ and $10^{-100}$ in practice though, for most theoretical purposes, the difference here is much larger than between $0.9$ and $0.1$. Thus, we are interested just in showing that the estimate in question is good when it is neither too small, nor too close to $1$. Assuming that we are on the torus (to avoid rather boring discussion of the boundary effects), and that the number of points $N$ is fixed (for the difference metric conditioning on $N$ is not a big problem) we can say that the estimate in question is just $(1-(1-\pi r^2)^{N-1})^N$, which is neither $0$, nor $1$ if $\pi r^2=\frac{\log N+O(1) }{N}$. We shall carry out the computations under this assumption only because the monotonicity of both the true probability and the estimate in $r$ is obvious. Denote $Q=(1-\pi r^2)^{N-1}\asymp \frac 1N$


Enumerate the points $x\_i$ to throw on the torus and let $f\_i$ be the random variable that is $1$ if $x\_i$ is isolated and $0$ if not. We are interested in $E\prod\_i(1-f\_i)$. The most natural idea is to use the truncated PIE. The first term after $1$ is $-\sum\_i Ef\_i=-NQ$, which is just what we need. 


To use the truncated PIE, we need to estimate $Ef\_1\dots f\_m$. The estimate from below is straightforward: $x\_{k+1}$ has the area at least $1-\min(k,m)\pi r^2$ to choose from, so we get almost $Q^m$ on the multiplicative scale if $m$ is at most a small power of $N$. To make a (rather crude) estimate from above, consider the connected components of the set $x\_1,\dots,x\_m$ with respect to the connection at distance $2r$ or less. If each component is single point, we get the lower bound above, i.e., essentially $Q^m$. Suppose that there are $p<m$ components. There are at most $A(m)$ ways to place points to the components. For each way, we have the probability at most $B(m)(r^2)^{m-p}\le B'(m)\frac{(\log N)^{m-p}}{N^{m-p}}$ to have that type of clustering after which we have the chance at most $(1-(p+0.5)\pi r^2)^{N-m}\le Q^{p+0.5}$ that the remaining points are placed right (each non-trivial component has area at least $1.5\pi r^2$), so we lose some big constant $C(m)$ but gain almost $N^{1/2}$ in the denominator. Thus, for $m$ up to any constant, we have the expectation close to $Q^m=[O(\frac 1N)]^m$. Now, since ${N\choose m}\le \frac {N^m}{m!}$, we see that ${N\choose m}Q^m\le \frac{e^{O(m)}}{m!}$ whence we need just to go up to large constant $m$ in the truncated PIE to ensure any fixed given precision in our range. But this is just what we've shown to be possible above.


If one does everything less sloppily, he can (probably) obtain a power decay $N^{-\gamma}$ for the additive error in the second approximation. It is pretty clear that the multiplicative error can be huge but only if the probability in question is small. So, if you need to go outside the "physical" range in your investigations, you'd better be careful.


The first approximation step is also non-obvious but, since you were primarily concerned about the second one, I'll stop here for now. 


