Titre du document / Document title

A limit theorem for sets of stochastic matrices

Auteur(s) / Author(s)

CONDON Anne ⁽¹⁾ ; SAKS Michael ⁽²⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Department of Computer Science, University of British Columbia, 2366 Main Mall, Vancouver, BC, V6T1Z4, CANADA
⁽²⁾ Department of Mathematics-Hill Center, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, ETATS-UNIS

Résumé / Abstract

The following fact about (row) stochastic matrices is an easy consequence of well known results: for each positive integer n ≥ 1 there is a positive integer q = q(n) with the property that if A is any n x n stochastic matrix then the sequence of matrices A^q, A^2q, A^3q,..., converges. We prove a generalization of this for sets of stochastic matrices under the Hausdorff metric. Let d be any metric inducing the standard topology on the set of n x n real matrices. For a matrix A and set of matrices B define d(A, B) to be the infimum of d(A, B) over all B ∈ B. For two sets of matrices A and B, define d⁺(A, B) to be the supremum of d(A, B) over all A e A, and define d(A, B) to be the maximum of d⁺(A, B) and d⁺(B, A). This is the Hausdorff metric on the set of subsets of n x n stochastic matrices. If A is a set of stochastic matrices and k is a positive integer, define A^(k) to be the set of all matrices expressible as a product of a sequence of k matrices from A. We prove: For each positive integer n there is a positive integer p = p(n) such that if A is any subset of n x n stochastic matrices then the sequence of subsets A^(p), A^(2p), A^(3p),... converges with respect to the Hausdorff metric.

Revue / Journal Title

Linear algebra and its applications   ISSN 0024-3795   CODEN LAAPAW 

Source / Source

2004, vol. 381, pp. 61-76 [16 page(s) (article)] (5 ref.)

Langue / Language

Anglais
Revue : Anglais

Editeur / Publisher

Elsevier, New York, NY, ETATS-UNIS  (1968) (Revue)

Mots-clés anglais / English Keywords

Topology ; Standards ; Metric ; Hausdorff dimension ; Integer ; Stochastic matrix ; Limit theorem ;

Mots-clés français / French Keywords

Topologie ; Norme ; Métrique ; Dimension Hausdorff ; Nombre entier ; Matrice stochastique ; Théorème limite ;

Mots-clés espagnols / Spanish Keywords

Topología ; Norma ; Métrico ; Dimensión Hausdorff ; Entero ; Matriz estocástica ; Teorema límite ;

Localisation / Location

INIST-CNRS, Cote INIST : 14246, 35400011935989.0050