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 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, and here is another one, 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.

  • $\begingroup$ Opening the bounty after at least one answer has been given means that the answer you got wasn't satisfactory. I just wonder what was wrong with it from your perspective. If you have questions, feel free to ask :). $\endgroup$ – fedja May 19 '11 at 2:48
  • $\begingroup$ The answer may be useful (in fact, I voted it), but I cannot explain why the approximation is so tight, not necessarily when $r=\log{N}/N$. I ran a lot of simulations and it always seems to be the case, at least when the transmission radius is small and N is large, as I expected. In the specific case of $d_{\rm min}=1$ it has been shown by Penrose that the approximation holds true asymptotically. But when $k>1$ I can't come up with a simple argument to justify its use $\endgroup$ – Bob May 19 '11 at 4:47
  • $\begingroup$ The range $\log N/N$ (for $k=1$) is the only interesting one because if we have the approximation correct when the estimate runs from almost $0$ to almost $1$, it is correct on the additive scale everywhere by monotonicity (but it may be (and actually is) bad on the multiplicative scale). You say $k>1$ is different? I'll check it then (when I ran it over in my head, it seemed the same to me but you never know until you write things down). I'll try to get a more decent estimate for the error too (just not today :) ). $\endgroup$ – fedja May 20 '11 at 21:27
  • $\begingroup$ I'm not saying $k>1$ is different. I'm saying that, from simulations, the approximation appears to be tight, at least, for interesting application scenarios, where the radius is small enough. $\endgroup$ – Bob May 20 '11 at 22:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.