Computing the maximum-entropy extension of given discrete probability distributions. (English) Zbl 0726.62012

Malvestuto, F. M.

Comput. Stat. Data Anal. 8, No. 3, 299-311 (1989).

Summary: The maximum-entropy extension of given discrete probability distributions over a “fully reducible” set class admits a closed-form expression, which makes its computation direct. In the remaining cases the computation of the maximum-entropy extension is carried out using the standard procedure of iterative proportional fitting, whose costs can often be reduced by applying the graph-theoretical techniques of reduction and decomposition. By making joint use of these techniques, we present a computation policy which limits the application of the iterative proportional fitting procedure to computing the marginals of a maximum-entropy distribution corresponding to the nonseparable components (in the graph-theoretical sense) of the underlying set class.

MSC:

62B10	Statistical aspects of information-theoretic topics
62E17	Approximations to statistical distributions (nonasymptotic)

Keywords:

maximum-entropy principle; IPFP; intersection graph; reduction; decomposition

References:

[1]	Beeri, C.: On the desirability of acyclic database schemes. ACM journal 30, 479-513 (1983) · Zbl 0624.68087
[2]	Berge, C.: Graphs and hypergraphs. (1973) · Zbl 0254.05101
[3]	Bishop, Y. M. M.: Discrete multivariate analysis: theory and practice. (1976)
[4]	Darroch, J. N.: Markov fields and loglinear interaction models for contingency tables. The annals of statistics 8, 522-539 (1980) · Zbl 0444.62064
[5]	Darroch, J. N.: Interaction models. Encyclopedia of statistical sciences 4, 182-187 (1983)
[6]	Deming, W. E.: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Annals of mathematical statistics 11, 427-444 (1940) · Zbl 0024.05502
[7]	Denteneer, D.: A fast algorithm for iterative proportional Fitting in log-linear models. Computational statistics & data analysis 3, 251-264 (1986) · Zbl 0591.65098
[8]	Feller, W.: An introduction to probability theory and its applications. (1968) · Zbl 0155.23101
[9]	Fienberg, S. E.: Iterative proportional Fitting. Encyclopedia of statistical sciences 4, 275-279 (1983)
[10]	Goodman, L. A.: The analysis of multidimensional contingency tables: stepwise procedure and direct estimation methods for building model for multiple classification. Technometrics 13, 33-61 (1971) · Zbl 0218.62066
[11]	Guiasu, S.: Maximum entropy condition in queueing theory. Journal of operational research society 37, 293-301 (1986) · Zbl 0582.60090
[12]	Haberman, S. J.: The analysis of frequency data. (1974) · Zbl 0325.62017
[13]	Haberman, S. J.: Log-linear fit for contingency tables. Algorithm AS51. Applied statistics 21, 218-225 (1972)
[14]	Harary, F.: Graph theory. (1969) · Zbl 0182.57702
[15]	Huber, P. J.: Projection pursuit. The annals of statistics 13, 435-475 (1985) · Zbl 0595.62059
[16]	Jaynes, E. T.: Information theory and statistical mechanics I. Physical review 106, 620-630 (1957) · Zbl 0084.43701
[17]	Jaynes, E. T.: On the rationale of maximum-entropy methods. IEEE-information theory 70, 939-952 (1982)
[18]	Kullback, S.: Categorical data problems using an information-theoretic approach. Handbook of statistics 4, 831-871 (1984) · Zbl 0597.62055
[19]	Lauritzen, S. L.: Decomposable graphs and hypergraphs. Journal of australian mathematical society 36, No. Series A, 12-29 (1984) · Zbl 0533.05046
[20]	Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions. Discrete mathematics 69, 61-77 (1988) · Zbl 0637.60021
[21]	Shore, J. E.: Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE-information theory 26, 26-37 (1980) · Zbl 0429.94011
[22]	Tarjan, R. E.: Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM journal of computing 13, 566-579 (1984) · Zbl 0545.68062