Timeline for Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 17 at 14:07 | history | edited | Amir | CC BY-SA 4.0 |
added 40 characters in body
|
| May 17 at 14:05 | comment | added | Amir | @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. | |
| May 17 at 13:46 | history | edited | Amir | CC BY-SA 4.0 |
added 7 characters in body
|
| May 16 at 21:15 | comment | added | paperskilltrees | @Amir, can you describe any algorithm to check the consistency and its asymptotic complexity? | |
| May 16 at 21:14 | comment | added | paperskilltrees | @Henry Let $N = 2^n - 1$ be the size of the input. The desired algorithm cannot be faster than $O(N)$, agreed. But can it actually be achieved? | |
| May 12 at 23:04 | comment | added | Amir | 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. | |
| May 12 at 22:53 | comment | added | Henry | 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. | |
| May 12 at 21:25 | comment | added | Amir | Hope a more efficient method is presented with better average performance. | |
| May 12 at 21:10 | comment | added | Henry | 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. | |
| May 12 at 20:46 | history | edited | Amir | CC BY-SA 4.0 |
edited title
|
| May 12 at 20:41 | history | asked | Amir | CC BY-SA 4.0 |