SOURCE-LINKED INTELLIGENCE

On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

arXiv · AI, language, vision and robotics · article · Aug 31, 2026 · UTC

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computa

Read original source ↗ Open in workspace

recordType

paper

region

Global