Densité de robots faisant une marche aléatoire dans un graphique géométrique aléatoire infini

Considérons un graphique géométrique aléatoire infini dans lequel les emplacements des nœuds suivent un processus de point de Poisson avec une densité et des arêtes sont placées entre les nœuds plus proches que . Par conséquent, la longueur des bords suit le PDF suivant: $\rho$ $d$

F (l) = {\begin{cases} \frac{2 l}{{ré}^{2}} l \leq ré \\ 0 l > ré \end{cases}

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

Dans le graphique ci-dessus, considérons les nœuds à l'intérieur du cercle de rayon centré à l'origine. Supposons qu'au temps , nous plaçons un petit robot à l'intérieur de chacun des nœuds mentionnés. C'est-à-dire que la densité des robots dans l'avion est donnée par: $r$ $t=0$

g (l) = {\begin{cases} ρ l \leq r \\ 0 l > ré \end{cases}

$g(l)= \begin{cases} \rho \quad l \le r \\ 0 \quad\; l > d \end{cases}$ où est la distance de l'origine. La figure suivante montre un exemple de placement initial des robots.

l

$l$

exemple

À chaque pas de temps, les robots se rendent au hasard chez l'un des voisins.

Maintenant, ma question est la suivante: quelle est la fonction de densité des robots à $t>0$ ? Est-il possible de calculer la fonction de densité lorsque $t \rightarrow \infty$ ?

Désolé les gars, je ne suis en aucun cas un mathématicien. Veuillez me faire savoir si quelque chose n'est pas clair.

probability stochastic-processes pdf asymptotics graph-theory Hélium
la source

Recherchez des livres de Wolfgang Woess en tant qu'éditeur ou auteur. Une collection récente: promenades aléatoires, frontières et spectres. Birkhauser, 2011. À partir de 2000 (Cambridge Univ.Press): promenades aléatoires sur des graphiques et des groupes infinis.

Deer Hunter

Merci Hunter. J'ai jeté un coup d'œil à son livre de 2011 mais je n'ai rien trouvé de similaire. Je n'ai pas accès à celui de 2000 pour le moment mais je le rechercherai une fois que je l'aurai trouvé. Veuillez me faire savoir si vous vous souvenez de quelque chose de plus spécifique dans les livres.

Helium

Voici un début.

Soit le rayon de la balle que vous envisagez. $r = d/2$

Tout d'abord, lisez les promenades aléatoires: http://en.wikipedia.org/wiki/Random_walk . Supposons que vous n'ayez qu'un seul robot et que votre marche aléatoire se fasse sur un réseau bidimensionnel. Pour les petits , c'est facile à calculer avec la multiplication matricielle. Vous savez qu'il n'y a que points possibles dans le réseau sur lesquels vous pouvez marcher ou atterrir après pas. Soit la matrice d'adjacence de ces sommets. Soit $t$ $n = 1 + 4t + 2t(t-1)$ $t$ $A_t$ $n \times n$ $n$ soit le vecteur de tous less à l'exception d'unauème point. Supposons que la première ligne (et colonne) de correspond à l'origine. Alors, la probabilité que vous soyez au sommetaprèsétapes est (où les moyens premiers se transposent, et $e_{i,t} \in \{0,1\}^n$ $0$ $1$ $i$ $A_t$ $i$ $t$ $e_{1,t}' A_t^t e_{i,t}$ $A^t = A \times A \cdots \times A$ est portée à la - ième puissance). Je suis sûr que vous devriez être en mesure de résoudre ce problème de manière explicite. Vous pouvez utiliser le fait que tout à la même distance de l'origine dans la norme doit avoir la même densité. $A$ $t$ $\cal L_1$

Après cet échauffement, passons à votre question d'origine. Après étapes, il suffit de considérer le graphe fini qui se trouve dans le rayon balle autour de l'origine (partout ailleurs a la probabilité d'être accessible après seulement $t$ $r(t+1)$ $0$ $t$ pas). Essayez de faire la matrice d'adjacence de ce graphique et de travailler avec elle de la même manière que le cas du réseau - je ne sais pas comment faire, mais je suppose qu'il existe une théorie de Markov pour vous aider. Une chose que vous pouvez profiter de nous, c'est que vous savez que cette distribution doit être symétrique autour de l'origine, en particulier la densité n'est fonction que de la distance de l'origine. Cela devrait faciliter les choses, donc tout ce que vous devez considérer est la probabilité que vous vous trouviez à la distance de l'origine après étapes. Une fois que vous avez résolu ce problème, appelez votre densité à l'emplacement après étapes $q$ $t$ $(x,y)$ $t$ . Notez que sera fonction de . Soit une variable aléatoire échantillonnée à partir de cette distribution. $f_t(x,y)$ $f_t$ $r$ $X$

Maintenant, vous devez également envisager de commencer avec plusieurs robots. En supposant que plusieurs robots soient autorisés à se trouver au même sommet, cela ne rend pas beaucoup plus difficile que le cas d'un seul robot. Les robots peuvent commencer de manière uniforme sur le cercle, appelez la variable aléatoire qui est échantillonné uniformément sur ce cercle . Il y aura un nombre de Poisson de robots avec lesquels vous commencez, soit une variable aléatoire échantillonnée à partir de cette distribution de Poisson. Ainsi , la densité que vous obtenez de multiples robots est juste . $U$ $M$ $MU + X$

Je pense que cela est un début raisonnable à la solution , sauf que je ne définissaient pas complètement la distribution de . Bonne chance et bonne question. $X$

user1448319
la source

Pourriez-vous préciser comment vous avez obtenu le nombre total d'emplacements possibles occupés après

étapes sur un réseau régulier? Par exemple, brancher

ne donne pas de réponses raisonnables. Votre réponse ne devrait-elle pas être

t

$t$

t = 0

$t = 0$

t = 1

$t = 1$

t = 2

$t = 2$

t^{2}

$t^2$

cardinal

oh, bonne prise. ce n'est pas censé être

, c'est censé être

est l'origine,

les axes,

n = 1 + 4 t + 2 (t - 1)^{2}

$n = 1 + 4t + 2(t-1)^2$

n = 1 + 4 t + 2 t (t - 1) = 1 + 2 t + 2 t^{2}

$n= 1 + 4t + 2t(t-1) = 1 + 2t + 2t^2$

1

$1$

+ 4 t

$+4t$

+ 2 t (t - 1)

$+2t(t-1)$ est les 4 tableaux triangulaires. par exemple, pour

et les 3 autres directions, et

et les quatre autres quadrants.

t = 2

$t=2$

(0, 0)

$(0,0)$

(1, 0), (2, 0)

$(1,0), (2, 0)$

(1, 1)

$(1,1)$

user1448319

Comment allez-vous être à

après deux étapes? (Peut-être que je ne comprends pas la marche que vous décrivez. Si je pense à la marche aléatoire "habituelle" sur

, c'est-à-dire uniforme dans les quatre directions cardinales, alors, à moins que je ne me trompe, la réponse dans ma première le commentaire devrait être correct.)

(1, 0)

$(1,0)$

Z^{2}

$\mathbb Z^2$

Cardinal

Vous ne pouvez pas terminer sur

après deux étapes à partir de

. Mais vous POUVEZ parcourir

après avoir fait deux étapes. Vous DEVEZ considérer tous les points qui sont accessibles en 2 étapes afin de construire

comme décrit ci-dessus.

(1, 0)

$(1,0)$

(0, 0)

$(0,0)$

(1, 0)

$(1,0)$

A_{t}

$A_t$

user1448319

C'est vrai, mais j'ai pris la phrase pour signifier ce qu'elle disait: vous savez qu'il n'y a que endroits possibles où vous pouvez atterrir sur le réseau après étapes. $n=1+4t+2(t−1)^2$ $t$ :-) Peut-être qu'une modification aiderait à clarifier. À votre santé.

Cardinal

Densité de robots faisant une marche aléatoire dans un graphique géométrique aléatoire infini

Réponses: