On Determining the Convergence Rate of an Infinite Product of Stochastic Matrices

Résumé Technique : Sur la détermination du taux de convergence d'un produit infini de matrices stochastiques

Énoncé du problème
L'article traite de l'analyse des produits infinis de matrices stochastiques, un composant fondamental des protocoles de consensus pour le contrôle distribué, l'estimation et l'optimisation. Bien que la convergence de tels produits vers une matrice de rang un soit bien établie pour des « ensembles convergents » spécifiques (par exemple, les matrices de type scrambling, les matrices de Sarymsakov), déterminer le taux de convergence reste un défi. Plus précisément, les auteurs étudient si des semi-normes de consensus submultiplicatifs peuvent être utilisés pour borner uniformément le taux de convergence pour toutes les matrices d'un ensemble convergent donné. Une question clé est de savoir s'il existe une semi-norme unique dans laquelle chaque matrice d'un ensemble convergent agit comme une contraction (c'est-à-dire possède une valeur de semi-norme strictement inférieure à 1), garantissant ainsi une convergence exponentielle.

Méthodologie
Les auteurs emploient le cadre des semi-normes de consensus, définis sur le sous-espace $M_{n \times n}$ des matrices ayant des sommes de lignes égales. Une semi-norme de consensus $|\cdot|$ satisfait $|M|=0$ si et seulement si $M = \mathbf{1}c$ (une matrice de rang un). L'analyse repose sur :

1. La submultiplicativité : La propriété $|M_1 M_2| \leq |M_1||M_2|$, qui lie la valeur de la semi-norme au taux de convergence.
2. Le rayon spectral conjoint semi-radial : Une adaptation novatrice du rayon spectral conjoint, définie en utilisant une semi-norme de consensus plutôt qu'une norme matricielle standard, pour caractériser le comportement asymptotique des produits infinis.
3. Des arguments topologiques : L'utilisation de la densité de certains ensembles de matrices (tels que les matrices stochastiques positives) au sein de l'espace de toutes les matrices stochastiques pour dériver des contradictions concernant l'existence de semi-normes de contraction uniformes.
4. La propriété de Hajnal : L'exploitation d'un résultat connu selon lequel le produit d'une matrice non-scrambling avec une matrice stochastique spécifique peut être non convergent.

Contributions clés et résultats

1. Non-existence de semi-normes de contraction uniformes pour les ensembles convergents généraux
L'article affine des résultats antérieurs pour prouver que tous les ensembles convergents n'admettent pas une semi-norme de consensus submultiplicative unique dans laquelle toutes les matrices sont des contractions.

• Théorème 1 : Pour $n > 2$, il n'existe pas de semi-norme de consensus submultiplicative $|\cdot|$ telle que $|S| < 1$ pour tout $S$ dans l'ensemble $R$ (matrices stochastiques avec diagonales positives et un graphe enraciné) ou l'ensemble $K$ (matrices de Sarymsakov).
• Théorème 3 : Si un ensemble convergent $C$ est dense dans l'ensemble de toutes les matrices stochastiques $S_{n \times n}$, et s'il existe une semi-norme où tous les $S \in C$ sont des contractions, alors $C$ doit être un sous-ensemble des matrices de type scrambling.
• Implication : Puisque $R$ et $K$ sont denses dans $S_{n \times n}$ mais contiennent des matrices non-scrambling, aucune semi-norme unique ne peut borner le taux de convergence pour toutes les matrices de ces ensembles. Cela contraste avec l'ensemble des matrices scrambling ($S$) et les matrices doubles stochastiques avec des graphes faiblement connexes ($D$), où de telles semi-normes (par exemple, le coefficient d'ergodicité ou la deuxième plus grande valeur singulière) existent.

2. Propriété de contraction par produit fini
L'article établit que, bien que les matrices individuelles d'un ensemble convergent compact puissent ne pas être des contractions dans une semi-norme donnée, les produits finis de celles-ci deviennent éventuellement des contractions.

• Corollaire 2 : Pour tout ensemble convergent compact $C$ et toute semi-norme de consensus submultiplicative, il existe un entier fini $k$ tel que le produit de n'importe quelles $k$ matrices de $C$ est une contraction (c'est-à-dire $|S_k \cdots S_1| < 1$).
• Ce résultat généralise la propriété connue pour les matrices scrambling (où une longueur de produit fini garantit la propriété scrambling) aux semi-normes de consensus généraux.

3. Rayon spectral conjoint semi-radial et taux de convergence
Les auteurs introduisent le rayon spectral conjoint semi-radial $\sigma(C)$, défini comme la limite de la suprême de la racine $t$-ième de la semi-norme des produits de longueur $t$.

• Théorème 4 : Un ensemble compact $C$ est convergent si et seulement si $\sigma(C) < 1$. De plus, si $\sigma(C) < 1$, la convergence est exponentielle, bornée par $\delta^t$ pour tout $\delta > \sigma(C)$.
• Cela fournit un mécanisme théorique pour borner les taux de convergence même lorsque les matrices individuelles ne sont pas des contractions, à condition que le rayon spectral conjoint semi-radial soit inférieur à un.

Signification et affirmations
L'article affirme clarifier les limites de l'utilisation des semi-normes submultiplicatives pour borner les taux de convergence dans le consensus distribué.

• Il démontre que la « belle » propriété de posséder une semi-norme de contraction unique n'est pas universelle ; elle échoue pour des classes importantes comme $R$ et $K$ lorsque $n > 2$.
• Il souligne que la capacité de déterminer les taux de convergence via une seule semi-norme est étroitement liée à la densité topologique de l'ensemble de matrices et à la propriété scrambling.
• L'article postule que, bien que les matrices individuelles puissent ne pas être des contractions, le comportement « conjoint » (capturé par le rayon spectral conjoint semi-radial) assure que les produits finis finissent par se contracter, offrant ainsi une voie vers des bornes de taux pour les ensembles convergents généraux.
• Les auteurs concluent en notant des questions ouvertes : spécifiquement, si la propriété de contraction par produit fini (Corollaire 2) est vérifiée avec un $k$ borné par une fonction de la dimension $n$ pour toutes les semi-normes, ou s'il existe des semi-normes pour lesquelles une telle borne n'existe pas.