Densidad de robots haciendo caminatas al azar en un gráfico geométrico aleatorio infinito

Question

Considere un gráfico geométrico aleatorio infinito en el que las ubicaciones de los nodos siguen un proceso de punto de Poisson con densidad $ \rho $ y los bordes se colocan entre los nodos que están más cerca que $d$ . Por lo tanto, la longitud de los bordes sigue la siguiente PDF:

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

En el gráfico de arriba, considera los nodos dentro del círculo de radio $r$ centrado en el origen. Supongamos que, en el momento $t=0$ colocamos un pequeño robot dentro de cada uno de los nodos mencionados. Es decir, la densidad de los robots en el avión viene dada por:

$$ g(l)= \begin {cases} \rho \quad l \le r \\ 0 \quad\ ; l > d \end {cases} $$ donde $l$ es la distancia del origen. La siguiente figura muestra un ejemplo de la colocación inicial de los robots.

En cada paso de tiempo, los robots van a uno de los vecinos al azar.

Ahora, mi pregunta es: ¿cuál es la función de densidad de los robots en $t>0$ ? ¿Es posible calcular la función de densidad cuando $t \rightarrow \infty $ ?

Lo siento chicos, no soy de ninguna manera un matemático. Por favor, háganme saber si algo no está claro.

Answer 1

Aquí hay un comienzo.

Deje que $r = d/2$ sea el radio de la bola que estás considerando.

Primero, lee sobre los paseos al azar: http://en.wikipedia.org/wiki/Random_walk . Suponga que tiene un solo robot, y suponga que su paseo aleatorio es en un entramado bidimensional. Para los pequeños $t$ esto es fácil de calcular con la multiplicación de la matriz. Sabes que sólo hay $n = 1 + 4t + 2t(t-1)$ posibles puntos en la red en los que se puede pisar o aterrizar después de $t$ pasos. Deje que $A_t$ ser el $n \times n$ matriz de adyacencia de estos $n$ vértices. Que $e_{i,t} \in \{0,1\}^n$ ser el vector de todos $0$ s excepto por un $1$ en el $i$ el lugar. Supongamos que la primera fila (y columna) de $A_t$ corresponde al origen. Entonces, la probabilidad de que estés en el vértice $i$ después de $t$ pasos es $e_{1,t}' A_t^t e_{i,t}$ (donde los medios primarios se transponen, y $A^t = A \times A \cdots \times A$ es $A$ elevado a la $t$ el poder). Estoy bastante seguro de que deberías ser capaz de resolver esto explícitamente. Puedes usar el hecho de que todo lo que está a la misma distancia del origen en el $ \cal L_1$ La norma debería tener la misma densidad.

Después de ese calentamiento, pasemos a su pregunta original. Después de $t$ pasos, sólo hay que considerar el gráfico finito que está dentro del radio $r(t+1)$ bola alrededor del origen (en cualquier otro lugar tiene probabilidad $0$ de ser alcanzable sólo después de $t$ pasos). Intenta hacer la matriz de adyacencia de ese gráfico y trabaja con ella de la misma manera que el caso de la red No sé cómo hacerlo, pero supongo que hay alguna teoría de Markov que te puede ayudar. Una cosa que puedes aprovechar es el hecho de que sabes que esta distribución debe ser simétrica alrededor del origen, en particular la densidad es sólo una función de la distancia del origen. Esto debería hacer las cosas más fáciles, así que todo lo que necesitas considerar es la probabilidad de que la distancia $q$ desde el origen después de $t$ pasos. Una vez que resuelva este problema, llame a su densidad en el lugar $(x,y)$ después de $t$ pasos $f_t(x,y)$ . Tenga en cuenta que $f_t$ será una función de $r$ . Deje que $X$ ser una variable aleatoria muestreada de esta distribución.

Ahora también tienes que considerar empezar con múltiples robots. Suponiendo que se permita que varios robots estén en el mismo vértice, esto no lo hace mucho más difícil que el caso de un solo robot. Los robots pueden comenzar uniformemente en el círculo, llamar a la variable aleatoria que se muestrea uniformemente en este círculo $U$ . Habrá un número de robots de Poisson con los que empezarás, deja que $M$ ser una variable aleatoria muestreada de esta distribución de Poisson. Así que la densidad que obtienes de múltiples robots es sólo $MU + X$ .

Creo que es un comienzo razonable para la solución, excepto que no he definido completamente la distribución de $X$ . Buena suerte, y buena pregunta.