Density of robots doing random walk in an infinite random geometric graph 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.
 A: 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.
