1
$\begingroup$

Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ...$. My question:

Is there any necessary and sufficient condition that can be simply checked to make sure that there is a measure on the set $\Omega$ that can produce the given numbers.

I came across this problem after solving this counting question, where I realized the numbers given in the source textbook cannot be correct, and showed it by checking two sufficient conditions.

I am wondering if there is any efficient algorithm for this purpose. I guess the above problem should be NP-hard since I can formulate it as a linear programming model for the case of real-valued measures (such as probability measures), which includes exponential number $O(2^n)$ of linear constraints involving $|\Omega|$ variables. I think the problem is more difficult for integer-valued measures.

$\endgroup$
7
  • 1
    $\begingroup$ As stated, you have $2^n-1$ values whose consistency you want to check so you are not going to be more efficient than that. $\endgroup$
    – Henry
    Commented May 12 at 21:10
  • $\begingroup$ Hope a more efficient method is presented with better average performance. $\endgroup$
    – Amir
    Commented May 12 at 21:25
  • 1
    $\begingroup$ You might be able to spot an inconsistency faster than that if you are lucky: for example being told $\mu(A_1)=0.3$ and $\mu(A_1 \cap A_2)=0.7$ $($and $\mu(A_2)=0.9)$ only requires a comparison of two values, but showing consistency requires looking at all the values so cannot be any faster. $\endgroup$
    – Henry
    Commented May 12 at 22:53
  • $\begingroup$ Yes exactly! It is why I told better average performance in my comment. Some type of polyhedral analysis may be useful; see e.g., the method used in this answer. $\endgroup$
    – Amir
    Commented May 12 at 23:04
  • 1
    $\begingroup$ @paperskilltrees as stated in the OP, the only method I currently know is to find a feasible solution to a system involving $O(2^n)$ linear equations and $|\Omega|$ variables. $\endgroup$
    – Amir
    Commented May 17 at 14:05

0

Reset to default

You must log in to answer this question.