Nombre de nœuds distincts dans une marche aléatoire

Le temps de trajet dans un graphique connecté est défini comme le nombre attendu d'étapes dans une marche aléatoire commençant à , avant que le nœud soit visité et que le nœud soit à nouveau atteint. Il s'agit essentiellement de la somme des deux temps de frappe et .$G=(V,E)$$i$$j$$i$$H(i,j)$$H(j,i)$

Existe-t-il quelque chose de similaire au temps de trajet (pas exactement le même) mais défini en termes de nœuds? En d'autres termes, quel est le nombre attendu de nœuds distincts par une marche aléatoire commençant à et revenant à visiterai?$i$$i$

Mise à jour (30 septembre 2012): Il existe un certain nombre de travaux connexes sur le nombre de sites distincts visités par un marcheur aléatoire sur un réseau (c'est-à-dire, ). Par exemple, voir: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no$\mathbb{Z}^n$

Quelqu'un a déjà lu quelque chose à ce sujet?

de Q & A avec vous dans les commentaires que vous semblez intéressés à étudier quelque chose défini comme la distance de la pile dans cet ensemble de diapositives, Sur la modélisation mathématique des caches

définir les distance de pile d'une référence comme étant le nombre d'adresses de bloc uniques entre la référence actuelle et la référence précédente au même numéro de bloc.

il a une analyse empirique via des repères. il indique en général qu'il n'y a "aucune mesure connue de la localité" des demandes de cache et propose ensuite la distance de pile comme une telle mesure. il ne le relie pas à la théorie des graphes aléatoires bien que vous ayez esquissé une telle connexion dans vos commentaires. (Il semble que la distance de la pile puisse être liée au mélange de chaînes Markov ?)

il semble que vous souhaitiez modéliser les performances de cache ou les algorithmes d'optimisation en considérant les requêtes de cache comme des nœuds d'un graphe et les bords comme des transitions entre des requêtes adjacentes. n'ont pas vu d'articles qui étudient la structure de ce graphique. il ne semble pas un graphique purement aléatoire dans des applications réelles en raison du succès des caches dans la pratique et de ce que l'on appelle la localité spatiale et temporelle dans les diapositives ci-dessus. c'est-à-dire une sorte de "clustering" comme Joe le dessine dans sa réponse.

(peut-être qu'il a une petite structure mondiale ?, ce qui est assez omniprésent dans les données du monde réel)

Un commentaire: J'ai récemment assisté à une conférence de Bruce Reed avec le titre Catching a Drunk Miscreant , qui était un travail conjoint avec Natasha Komorov et Peter Winkler. Si vous pouvez obtenir les résultats de ce travail, cela pourrait peut-être vous aider dans une certaine direction.

En général, ils prouvent une limite supérieure sur le nombre d'étapes dont un flic a besoin dans un graphique général pour pouvoir attraper un voleur, quand nous savons que le voleur se déplace au hasard le long des bords.

Ce n'est pas vraiment une bonne réponse à votre question, mais c'est un peu trop long pour un commentaire.

La quantité que vous recherchez variera d'un graphique à l'autre et dépendra de l'emplacement initial du déambulateur. Le nombre attendu de nœuds intermédiaires distincts dépendra fortement du clustering dans le graphique, et je m'attends à ce que le nombre attendu de nœuds intermédiaires distincts soit corrélé avec le coefficient de clustering .

Un cluster est fondamentalement un sous-ensemble de sommets qui partagent un grand nombre d'arêtes, de sorte que chaque sommet est connecté à une grande fraction des autres sommets du cluster. Lorsqu'un marcheur pénètre dans un cluster, il est susceptible de rester dans cette région pendant un grand nombre de sauts, revisitant éventuellement chaque nœud plusieurs fois. En effet, l'utilisation de marches aléatoires de cette manière est l'une des techniques de calcul utilisées pour identifier les grappes dans les grands graphiques. Ainsi, pour un marcheur commençant dans une grappe, le nombre attendu de sommets intermédiaires distincts évoluera probablement avec la taille de la grappe et la probabilité moyenne de quitter la grappe.

$N$$\frac{1}{N}$$N+1$ . Même si nous connectons certains sommets de ce graphique à un sommet dans un autre graphique (c'est-à-dire en dehors de cette clique), la probabilité que chaque saut quitte le cluster avant de revenir au site initial peut être très faible. Ainsi, nous nous attendons à ce que le clustering réduise le nombre de sommets intermédiaires distincts en confinant le marcheur dans le cluster.

Le degré moyen de sommets dans le graphique jouera également un rôle important, bien que cela soit lié au clustering. La raison en est que lorsque le marcheur saute sur un sommet de degré 1, il doit revenir au sommet précédent au saut suivant. Même lorsque le degré est 2, il n'y a qu'un seul chemin qui peut être suivi à travers le graphique, bien qu'il puisse être parcouru dans les deux sens à chaque saut. En revanche, pour les graphiques de degré supérieur à 2, le nombre de chemins peut exploser, ce qui rend extrêmement improbable le retour au site initial même si le chemin le plus court entre les deux est petit.

Ainsi, vous vous attendriez à ce que le nombre de sommets intermédiaires distincts soit élevé pour les graphiques qui ont tous deux un degré moyen sensiblement supérieur à 2 et qui n'ont pas non plus de regroupement significatif, comme les arbres.

Bien sûr, ces commentaires ne valent plus dans le cas des marches aléatoires quantiques, mais je suppose que vous ne vous souciez que du cas classique.