Marche aléatoire et temps de frappe moyen dans un graphique simple non orienté

Soit un simple graphe non orienté sur sommets et m arêtes.n $G=(V,E)$$n$$m$

Je suis en train de déterminer la durée prévue de l'algorithme de Wilson pour générer un arbre couvrant aléatoire de $G$ . Là, il apparaît $O(\tau)$ , où $\tau$ est le temps moyen de frappe :

• $\pi$ est la distribution stationnaire $\pi(v)=\frac{d(v)}{2m}$ ,
• $u$ est un sommet arbitraire, et
• $H(u,v)$ est le temps de frappe ( temps d' accès AKA ), c'est-à-dire le nombre prévu d'étapes avant que le sommet $v$ soit visité, à partir du sommet $u$ .

Quelle est la limite supérieure générale du temps de frappe moyen? Et quel est le pire cas $G$ qui maximise le temps de frappe moyen?

Pour clarifier ma question, je n'ai pas besoin de calculs ou d'une preuve détaillée (bien qu'ils puissent être utiles à d'autres personnes rencontrant cette question à l'avenir). Pour moi personnellement, une citation serait suffisante.

L'article mentionne un autre algorithme de Broder qui fonctionne dans le temps de couverture prévu (première fois lorsque tous les sommets ont été visités). Ensuite, il est dit que le temps moyen de frappe est toujours inférieur au temps de couverture. Cependant, il ne donne qu'une limite asymptotique de $\Theta(n)$ pour la plupart des graphiques (c'est -à -dire des graphiques expanseurs ) pour le comparer avec $\Theta(n \log n)$ par Broder pour la plupart des graphiques (avec une définition un peu plus inclusive de la plupart ).

Il donne un exemple de graphique où le temps de frappe moyen est et le temps de couverture est . Bien que l'on sache que c'est le pire des cas pour ce dernier, il ne dit rien du tout sur le pire des cas. Cela signifierait que le pire des cas pour l'algorithme de Wilson pourrait se situer n'importe où entre et .Θ ( n 3 ) O ( n 2 ) O ( n 3$\Theta(n^2)$$\Theta(n^3)$$O(n^2)$$O(n^3)$

Il y a deux implémentations publiquement disponibles de l'algorithme de Wilson que je connais. L'un est dans la bibliothèque de graphiques Boost , tandis que le second est dans l' outil graphique . La documentation du premier ne mentionne pas le temps de fonctionnement, tandis que le second déclare:

Le temps d'exécution typique pour les graphiques aléatoires est .$O(n \log n)$

Ce qui ne répond pas à la question et semble en fait incompatible avec l'article de Wilson. Mais je signale cela au cas où, pour gagner du temps à quiconque ayant la même idée de consulter la documentation de mise en œuvre.

J'avais initialement espéré que le pire des cas pourrait être atteint par un graphique construit en attachant un chemin à une clique, en raison de Lovász , où le temps de frappe peut être aussi élevé que . Cependant, la probabilité de cet événement est d'environ lors de la sélection des sommets de la distribution stationnaire. Par conséquent, ce qui donne un lié pour le temps de frappe moyen dans ce graphique.$\Omega(n^3)$ O(n2$\frac{1}{n}$$O(n^2)$

Un article de Brightwell et Winkler montre qu'un sous-ensemble de graphiques de sucettes maximise le temps de frappe prévu, atteignant . Le graphique de Lovász est également un graphique de sucette, mais dans ce cas, la taille de la clique est , plutôt que la moitié. Cependant, il faut veiller à ne pas confondre le temps de frappe prévu avec le temps de frappe moyen. Ce résultat, comme le précédent, fait référence au temps de frappe attendu pour deux sommets spécifiques choisis au préalable.$4n^3/27$$\frac{2}{3} n$

J'ai décidé de demander à David Wilson lui-même, peu de temps après, obtenu une réponse:

Pour les graphes non orientés sur sommets, le pire temps moyen de frappe est . L'exemple est le graphique à barres , qui se compose de deux cliques de taille reliées par un chemin de longueur . Je ne sais pas quelle est la pire constante. Le document [Brightwell-Winkler] examine les temps de frappe (attendus) commençant à et se terminant à . Le temps de frappe moyen est la moyenne de pour fixes et les choix aléatoires de partir de la distribution stationnaire d'une marche aléatoire. C'est un fait agréable que cela ne dépend pas de$n$$\Theta(n^3)$$n/3$$n/3$$H(x,y)$$x$$y$$H(x,y)$$x$$y$$x$. J'ai appris les temps de frappe grâce au livre Aldous-Fill , qui est inachevé mais sur le Web.

Il y a même une preuve de ce fait dans le livre susmentionné, qui se présente comme suit:

Pour construire un graphe sur sommets, commencez par deux graphes complets sur sommets. Distinguer les sommets dans un graphique ("la cloche gauche") et les sommets dans l'autre graphique ("la cloche droite"). Connectez ensuite les graphiques via un chemin .$n=2n_1+n_2$$n_1$$v_l \neq v_L$$v_R \neq v_r$$v_L - w_1 - \cdots w_{n_2} - v_R$

Ensuite, il est officieusement soutenu qu'il faut du temps moyen sur pour atteindre et à partir de là, il y a une chance de frapper , il faut donc environ pour frapper . A partir de il est possible que frappe la cloche droite avant de retourner dans la cloche gauche, il faut donc environ pour entrer dans la cloche droite.$n_1$$v_L$$\frac{1}{n_1}$$w_1$$n_1^2$$w_1$$w_1$$\frac{1}{n_2}$$n_1^2 n_2$

Le réglage nous donne le temps moyen .$n_1 = n_2 = n/3$$O(n^3)$

Certes, je suis perdu au moment où ils déclarent:

À partir de il est possible que frappe la cloche droite avant de revenir dans la cloche gauche.$w_1$$\frac{1}{n_2}$

Mais pour apaiser mon esprit, j'ai exécuté une simulation de marches aléatoires sur des graphiques à barres construits de cette façon, entre des sommets choisis dans la distribution stationnaire. En effet, le temps moyen de frappe s’adaptait très bien à une courbe .$\frac{(n+1)^3}{54}$

Cependant, les commentaires sur la preuve informelle sont toujours les bienvenus.

Dans un article récent , nous avons trouvé une borne supérieure mn (pas de grand O) sur le nombre attendu de "cycles sautés" par l'algorithme de Wilson et il est serré aux constantes. Cela ne répond pas directement à la question du temps de fonctionnement des algorithmes de Wilson car la taille moyenne des cycles sautés ne semble pas évidente. Par contre, je n'ai pas assez de "réputation" pour laisser un commentaire ...