Compactness of Bayes Network

A conditional probability table for Boolean $X_i$ with $k$ Boolean parents has $2^k$ rows for the combinations of parent values. Each row requires just one number for $p$ for $X_i=\text{true}$ (as we can find the false equivalent by taking $1-p$).

If each variable has no more than $k$ parents, the complete network requires $O(n\cdot 2^k)$ numbers. This grows linearly with $n$ compared to $O(2^n)$ for the full joint distribution.