1
$\begingroup$

I am new to Random geometric graphs. I have a graph with vertices being generated uniformly over $[0,1]^2$. There is an edge between two vertices if the Euclidean distance between the two vertices is $\le r$. I am trying to find the probability of this. For that I am starting as below: $$P(\mbox{two random nodes have an edge between them})=P((x_i-x_j)^2+(y_i-y_j)^2\le r^2)$$ I am taking the nodes to be uniformly and independently generated over $[0,1]^2$, hence $p(x_i)=p(x_j)=p(y_i)=p(y_j)=1$ and they are all independent. Using these and after some calculations I found that the probability is $r^4$. But I could not get any reference where I can verify this result and I have a feeling that I am wrong. So, can anyone kindly comment on this result and please help correct it if it is wrong? Thanks in advance.

EDIT: The following is my calculations that led to the result $r^4$. Please suggest corrections if something is wrong.

$$P((x_i-x_j)^2+(y_i-y_j)^2\le r^2)\\ =\int\int\int P((x_i-x_j)^2+(y_i-y_j)^2\le r^2|x_i,y_i,x_j)p_{x_i,y_i,x_j}(x_i,y_i,x_j)dx_idy_idx_j\\ =\int_{|x_i-x_j|\le r}\int_{|y_i-y_j|\le \sqrt{r^2-(x_i-x_j)^2}}dx_i dx_j dy_i dy_j$$ Now using the transformations $X=x_i-x_j,\ Y=y_i-y_j$, I rewrote the integral as $$\frac{}{}\int_{-r}^{r}\int_{\sqrt{r^2-X^2}}^{\sqrt{r^2-X^2}}XY dY dX=r^4$$

Note: I do not want the probability that a particular node has an edge with some other node which is easily seen to be $\pi r^2$.

$\endgroup$
7
  • 1
    $\begingroup$ "Using these and after some calculations I found that the probability is $r^4$." Very curious to see these calculations I am, hmmm? To begin with, the result depends on the number of points. $\endgroup$
    – Did
    Mar 23 '14 at 17:23
  • $\begingroup$ Some (major) problems with the computation in your Edit: it does not take into account the boundaries of the square; it considers two points, not whatever number of points are thrown into the square; dimension arguments show that $r^4$ is absurd, for two points the thing should scale as $r^2$ when $r\to0$. $\endgroup$
    – Did
    Mar 23 '14 at 18:16
  • $\begingroup$ Okay, so should I better say that I am calculating the probability that there is an edge between two randomly selected nodes? $\endgroup$ Mar 23 '14 at 18:25
  • $\begingroup$ Depends on what you want to do. The post does not suggest that you are asking for what the Edit tries to do. (By the way, the "Note" at the very end is wrong as well.) $\endgroup$
    – Did
    Mar 23 '14 at 18:26
  • $\begingroup$ I edited my question. $\endgroup$ Mar 23 '14 at 18:31
2
$\begingroup$

After some hesitations, it seems that one is actually throwing two points uniformly and independently in $[0,1]^2$ and that one asks for the probability $p(r)$ that their distance is at most $r$. Thus, $$ p(r)=\iint_{[0,1]^2}A(x,r)\,\mathrm dx, $$ where $A(x,r)$ is the area of the set $$ [0,1]^2\cap D(x,r), $$ where $D(x,r)$ is the full disk $$ D(x,r)=\{y\in\mathbb R^2\mid\|y-x\|\leqslant r\}. $$ The computation of the exact value of $p(r)$ is tedious (except when $r\geqslant\sqrt2$ since then $p(r)=1$) but one can note that, for every $r\leqslant1$, the set $[0,1]^2\cap D(x,r)$ is at most $D(x,r)$, whose area is $\pi r^2$, and at least a quarter of $D(x,r)$. Thus, $$ \tfrac14\pi r^2\leqslant p(r)\leqslant\pi r^2. $$ Recall that this holds only for $$ 0\lt r\leqslant1. $$

$\endgroup$

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.