Consider an infinite random geometric graph in which the node locations follow a Poisson point process with density $\rho$ and edges are placed between the nodes that are closer than $d$. Therefore, the length of the edges follow the following PDF:

$$ f(l)= \begin{cases} \frac{2 l}{d^2} \;\quad l \le d \\ 0 \qquad\; l > d \end{cases} $$

In the above graph, consider the nodes inside the circle of radius $r$ centered at the origin. Assume, at time $t=0$, we place a tiny robot inside each of the mentioned nodes. That is, the density of the robots on the plane is given by:

$$ g(l)= \begin{cases} \rho \quad l \le r \\ 0 \quad\; l > d \end{cases} $$ where $l$ is the distance from the origin. The following figure shows an example of the initial placement of the robots.


At each time step, the robots go to one of the neighbours randomly.

Now, my question is that: what is the density function of the robots at $t>0$? Is that possible to compute the density function when $t \rightarrow \infty$?

Sorry guys, I am by no means a mathematician. Please let me know if anything is unclear.

  • 1
    $\begingroup$ Look up books by Wolfgang Woess as editor or author. A recent collection: Random walks, boundaries and spectra. Birkhauser, 2011. From 2000 (Cambridge Univ.Press): Random walks on infinite graphs and groups. $\endgroup$ – Deer Hunter Jan 18 '13 at 21:08
  • 1
    $\begingroup$ Thank you Hunter. I had a quick look at his 2011 book but I couldn't find anything related. I don't have access to the 2000 one right now but I will look it up once I found it. Please let me know if you remember anything more specific from the books. $\endgroup$ – Helium Jan 18 '13 at 21:44

Here's a start.

Let $r = d/2$ be the radius of the ball you're considering.

First, read up on random walks: http://en.wikipedia.org/wiki/Random_walk. Assume you have only one robot, and assume your random walk is on a two dimensional lattice. For small $t$, this is easy to compute with matrix multiplication. You know there are only $n = 1 + 4t + 2t(t-1)$ possible points in the lattice on which you can step on or land on after $t$ steps. Let $A_t$ be the $n \times n$ adjacency matrix of these $n$ vertices. Let $e_{i,t} \in \{0,1\}^n$ be the vector of all $0$s except for a $1$ in the $i$th spot. Assume that the first row (and column) of $A_t$ corresponds to the origin. Then, the probability that you are at vertex $i$ after $t$ steps is $e_{1,t}' A_t^t e_{i,t}$ (where the prime means transpose, and $A^t = A \times A \cdots \times A$ is $A$ raised to the $t$th power). I'm pretty sure you should be able to solve this explicitly. You can use the fact that everything the same distance from the origin in the $\cal L_1$ norm should have the same density.

After that warm up, let's move on to your original question. After $t$ steps, you only need to consider the finite graph that is within the radius $r(t+1)$ ball around the origin (everywhere else has probability $0$ of being reachable after only $t$ steps). Try to make the adjacency matrix of that graph and work with it in the same way as the lattice case -- I don't know how to do this, but I would guess there's some Markov theory out there to help you out. One thing you can take advantage of us the fact that you know this distribution must be symmetric around the origin, in particular the density is only a function of the distance from the origin. This should make things easier, so all you need to consider is the probability that you are distance $q$ from the origin after $t$ steps. Once you solve this problem, call your density at the location $(x,y)$ after $t$ steps $f_t(x,y)$. Note that $f_t$ will be a function of $r$. Let $X$ be a random variable sampled from this distribution.

Now you also need to consider starting with multiple robots. Supposing that multiple robots are allowed to be at the same vertex, this doesn't make it much harder than the one robot case. The robots can start uniformly on the circle, call the random variable that is sampled uniformly on this circle $U$. There will be a Poisson number of robots that you start with, let $M$ be a random variable sampled from this Poisson distribution. So the density you get from multiple robots is just $MU + X$.

I think this is a reasonable start to the solution except that I didn't fully define the distribution of $X$. Good luck, and neat question.

  • 1
    $\begingroup$ Could you clarify how you obtained the total number of possible locations occupied after $t$ steps on a regular lattice? For example, plugging in $t = 0$, $t = 1$ and $t = 2$ do not give reasonable answers. Should your answer not be $t^2$? $\endgroup$ – cardinal Mar 17 '13 at 16:20
  • 1
    $\begingroup$ oh, good catch. it's not supposed to be $n = 1 + 4t + 2(t-1)^2$, it's supposed to be $n= 1 + 4t + 2t(t-1) = 1 + 2t + 2t^2$. $1$ is the origin, $+4t$ is the axes, $+2t(t-1)$ is the 4 triangular arrays. e.g., for $t=2$, $(0,0)$ and $(1,0), (2, 0)$ and the other 3 directions, and $(1,1)$ and the other four quadrants. $\endgroup$ – user1448319 Mar 18 '13 at 21:04
  • $\begingroup$ How are you going to be at $(1,0)$ after two steps? (Maybe I'm not understanding the walk you're describing. If I think of the "usual" random walk on $\mathbb Z^2$, i.e., uniform in the four cardinal directions, then, unless I'm mistaken, the answer in my first comment should be correct.) $\endgroup$ – cardinal Mar 18 '13 at 22:13
  • $\begingroup$ You can't end on $(1,0)$ after two steps starting from $(0,0)$. But you CAN walk through $(1,0)$ after taking two steps. You MUST consider all points that are reachable within 2 steps in order to construct $A_t$ as described above. $\endgroup$ – user1448319 Mar 18 '13 at 22:17
  • $\begingroup$ That's true, but I took the sentence to mean what it said: You know there are only $n=1+4t+2(t−1)^2$ possible places you can land on the lattice after $t$ steps. :-) Perhaps an edit would help clarify. Cheers. $\endgroup$ – cardinal Mar 18 '13 at 22:32

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.