×

Iterated proportional fitting procedure and infinite products of stochastic matrices. (English) Zbl 1453.15014

Donati-Martin, Catherine (ed.) et al., Séminaire de probabilités XLIX. Cham: Springer. Lect. Notes Math. 2215, 75-117 (2018).
Summary: The iterative proportional fitting procedure (IPFP), introduced in 1937 by J. Kruithof [Telefoonverkeers rekening (Calculation of telephone traffic), De Ingenieur No. 52, E15–E25 (1937)], 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 \geq 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 \geq 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 \geq 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 \geq 0}\) diverges but both subsequences \((X_{2n})_{n \geq 0}\) and \((X_{2n+1})_{n \geq 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 \(\cdots 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 B. Touri and A. Nedić’s theorem [Automatica 48, No. 8, 1477–1488 (2012; Zbl 1275.15021)] 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 \cdots M_1)_{n \geq 0}\), but also its finite variation.
For the entire collection see [Zbl 1402.60004].

MSC:

15B51 Stochastic matrices
60B20 Random matrices (probabilistic aspects)
15B48 Positive matrices and their generalizations; cones of matrices
62H17 Contingency tables

Citations:

Zbl 1275.15021
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Aas, Limit points of the iterative scaling procedure. Ann. Oper. Res. 215(1), 15-23 (2014) · Zbl 1302.65112
[2] M. Bacharach, Estimating nonnegative matrices from marginal data. Int. Econ. Rev. 6(3), 294-310 (1965) · Zbl 0136.14301
[3] L.M. Bregman, Proof of the convergence of Sheleikhovskii’s method for a problem with transportation constraints. USSR Comput. Math. Math. Phys. 7(1), 191-204 (1967)
[4] J.B. Brown, P.J. Chase, A.O. Pittenger, Order independence and factor convergence in iterative scaling. Linear Algebra Appl. 190, 1-39 (1993) · Zbl 0776.60087
[5] I. Csiszár, I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3(1), 146-158 (1975) · Zbl 0318.60013
[6] S. Fienberg, An iterative procedure for estimation in contingency tables. Ann. Math. Stat. 41(3), 907-917 (1970) · Zbl 0198.23401
[7] C. Gietl, F. Reffel, Accumulation points of the iterative scaling procedure. Metrika 73(1), 783-798 (2013) · Zbl 1281.68243
[8] C.T. Ireland, S. Kullback, Contingency tables with given marginals. Biometrika 55(1), 179-188 (1968) · Zbl 0155.26701
[9] J. Kruithof, Telefoonverkeers rekening (Calculation of telephone traffic). De Ingenieur 52, pp. E15-E25 (1937). Partial English translation: Krupp, R.S. http://wwwhome.ewi.utwente.nl/ ptdeboer/misc/kruithof-1937-translation.html
[10] J. Lorenz, A stabilization theorem for dynamics of continuous opinions. Phys. A Stat. Mech. Appl. 355(1), 217-223 (2005)
[11] O. Pretzel, Convergence of the iterative scaling procedure for non-negative matrices. J. Lond. Math. Soc. 21, 379-384 (1980) · Zbl 0423.65020
[12] F. Pukelsheim, Biproportional matrix scaling and the iterative proportional fitting procedure. Ann. Oper. Res. 215, 269-283 (2014) · Zbl 1302.65114
[13] R. Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Mon. 74(4), 402-405 (1967) · Zbl 0166.03702
[14] B. Touri, Product of random stochastic matrices and distributed averaging. Springer Thesis (2012) · Zbl 1244.15023
[15] B. Touri, A. Nedic, Alternative characterization of ergodicity for doubly stochastic chains, in Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), Orlando, FL (2011), pp. 5371-5376
[16] B. Touri, A. Nedić, On ergodicity, infinite flow and consensus in random models. IEEE Trans. Autom. Control 56(7), 1593-1605 (2011) · Zbl 1368.37010 · doi:10.1109/TAC.2010.2091174
[17] B. Touri, A. Nedić, On backward product of stochastic matrices. Automatica 48(8), 1477-1488 (2012) · Zbl 1275.15021 · doi:10.1016/j.automatica.2012.05.025
[18] R.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.