Analytical forms for most likely matrices derived from incomplete information

Abstract

Consider a rectangular matrix describing some type of communication or transportation between a set of origins and a set of destinations, or a classification of objects by two attributes. The problem is to infer the entries of the matrix from limited information in the form of constraints, generally the sums of the elements over various subsets of the matrix, such as rows, columns, etc., or from bounds on these sums, down to individual elements. Such problems are routinely addressed by applying the maximum entropy method to compute the matrix numerically, but in this article we derive analytical, closed-form solutions. For the most complicated cases we consider the solution depends on the root of a non-linear equation, for which we provide an analytical approximation in the form of a power series. Some of our solutions extend to 3-dimensional matrices. Besides being valid for matrices of arbitrary size, the analytical solutions exhibit many of the appealing properties of maximum entropy, such as precise use of the available data, intuitive behaviour with respect to changes in the constraints, and logical consistency.

Keywords:

• maximum entropy
• communications networks
• convex optimisation
• optimal estimation
• most likely
• traffic matrix
• contingency table
• analytical form

Acknowledgments

I thank my colleagues Howard Karloff and N.J.A. Sloane for interesting and helpful discussions.

Notes

Notes

1. We assume that the balls are distinguishable. The boxes are distinguishable, being particular elements of a matrix.

2. The latter with the unfortunate adoption of Microsoft Word® for the typesetting of mathematical papers.

3. We say ‘estimation’ because the methods used do not have the same logical standing as MAXENT. Also, the problem of estimating traffic in a real IP network is significantly more complex than the problems considered in this article.

4. This usage goes back to Boltzmann's combinatorial formulation of statistical mechanics, see (Sommerfeld 1967).

5. if the matrix is a contingency table, simply rearrange the columns. If it refers to n nodes, re-label the nodes.

6. This is also true because the solution to our strictly concave maximisation problem is unique.

7. Note that ρ _i < 1 − 1/2 r _i ξ₀, so ρ₁ + ··· + ρ _n < n − ξ₀/2.