Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
3. Iterated Proportional Fitting Procedure and Infinite Products of Stochastic Matrices
verfasst von : J. Brossard, C. Leuridan
Erschienen in: Séminaire de Probabilités XLIX
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The iterative proportional fitting procedure (IPFP), introduced in 1937 by Kruithof, aims to adjust the elements of an array to satisfy specified row and column sums. Thus, given a rectangular non-negative matrix X
0 and two positive marginals a and b, the algorithm generates a sequence of matrices (X
n)n≥0 starting at X
0, supposed to converge to a biproportional fitting, that is, to a matrix Y whose marginals are a and b and of the form Y = D
1X
0D
2, for some diagonal matrices D
1 and D
2 with positive diagonal entries.
When a biproportional fitting does exist, it is unique and the sequence (X
n)n≥0 converges to it at an at least geometric rate. More generally, when there exists some matrix with marginal a and b and with support included in the support of X
0, the sequence (X
n)n≥0 converges to the unique matrix whose marginals are a and b and which can be written as a limit of matrices of the form D
1X
0D
2.
In the opposite case (when there exists no matrix with marginals a and b whose support is included in the support of X
0), the sequence (X
n)n≥0 diverges but both subsequences (X
2n)n≥0 and (X
2n+1)n≥0 converge.
In the present paper, we use a new method to prove again these results and determine the two limit-points in the case of divergence. Our proof relies on a new convergence theorem for backward infinite products ⋯M
2M
1 of stochastic matrices M
n, with diagonal entries M
n(i, i) bounded away from 0 and with bounded ratios M
n(j, i)∕M
n(i, j). This theorem generalizes Lorenz’ stabilization theorem. We also provide an alternative proof of Touric and Nedić’s theorem on backward infinite products of doubly-stochastic matrices, with diagonal entries bounded away from 0. In both situations, we improve slightly the conclusion, since we establish not only the convergence of the sequence (M
n⋯M
1)n≥0, but also its finite variation.