On The Maximum-Entropy Extensions Of Probability Measures Over Undirected Graphs

Two problems: 1. whether a given family of discrete probability measures indexed by the maximal cliques of an undirected graph can be extended, and 2. how to compute explicitly the extension having maximal Shannon entropy, are examined from the point of view of graph decompositions. Close product formula for the extensions is presented and its algorithmical complexity is evaluated. Two conjectures on optimality of our decompositions in both problems are put forward. 1. INTRODUCTION Let N and X i , i 2 N , be finite nonempty sets. For I ae N we denote by X I the Cartesian product \Pi i2I X i ; X ; = f;g. Having a probability measure P on XN , in symbols P 2 P(XN ), its image under the coordinate projection of XN onto X I (often called marginal of P ) is denoted by P I 2 P(X I ). Let A be a nonempty family of subsets of the basic set N . A system of probability measures Q = (Q I 2 P(X I ); I 2 A) is said to be consistent if Q is equal to the system P A = (P I ; I 2 A) for some P 2..