## 3 Common Distributional Assumptions for Bayesian Networks
### Discrete BNs  
_Discrete BNs_[25] assume that both \(\mathbf{X}\) and the \(X_{i}\) are multinomial random variables (The literature sometimes denotes discrete BNs as \"dBNs\" or \"DBNs\"; we do not do that in this paper to avoid confusion with dynamic BNs, which are also commonly denoted as \"dBNs\"). Local distributions take the form  
\[X_{i}\mid\Pi_{X_{i}}\sim Mul(\pi_{ik|j}), \pi_{ik|j}=\mathrm{P}\big{(}X_{i}=k\mid\Pi_{X_{i}}=j\big{)};\]  
their parameters are the conditional probabilities of \(X_{i}\) given each configuration of the values of its parents, usually represented as a conditional probability table (CPT) for each \(X_{i}\). The \(\pi_{ik|j}\) can be estimated from data via the sufficient statistic \(\{n_{ijk},i=1,\ldots N;j=1,\ldots,q_{i};\)\(k=1,\ldots,r_{i}\}\), the corresponding counts tallied from \(\{X_{i},\Pi_{X_{i}}\}\) using maximum likelihood, Bayesian or shrinkage estimators as described in [PERSON] and Friedman [5] and Hausser and Strimmer [33].  
The global distribution takes the form of an \(N\)-dimensional probability table with one dimension for each variable. Assuming that each \(X_{i}\) takes at most \(l\) values, the table will contain \(|Val(\mathbf{X})|=O\big{(}l^{N}\big{)}\) cells, where \(Val(\cdot)\) denotes the possible (configurations of the) values of its argument. As a result, it is impractical to use for medium and large BNs. Following standard practices from categorical data analysis [34], we can produce the CPT for each \(X_{i}\) from the global distribution by marginalising (that is, summing over) all the variables other than \(\{X_{i},\Pi_{X_{i}}\}\) and then normalising over each configuration of \(\Pi_{X_{i}}\). Conversely, we can compose the global distribution from the local distributions of the \(X_{i}\) by multiplying the appropriate set of conditional probabilities. The computational complexity of the composition is \(O\big{(}l^{N}\big{)}\) because applying (1) for each of the \(l^{N}\) cells yields  
\[\mathrm{P}(\mathbf{X}=\mathbf{x})=\prod_{i=1}^{N}\mathrm{P}\Big{(}X_{i}=x_{i} \mid\Pi_{X_{i}}=\mathbf{x}_{\Pi_{X_{i}}}\Big{)},\]  
which involves \(N\) multiplications. As for the decomposition, for each node, we:  
1. Sum over \(N-|\Pi_{X_{i}}|-1\) variables to produce the joint probability table for \(\{X_{i},\Pi_{X_{i}}\}\), which contains \(O\Big{(}l^{|\Pi_{X_{i}}|+1}\Big{)}\) cells. The value of each cell is the sum of \(O\Big{(}l^{N-|\Pi_{X_{i}}|-1}\Big{)}\) probabilities.
2. Normalise the columns of the joint probability table for \(\{X_{i},\Pi_{X_{i}}\}\) over each of the \(O\Big{(}l^{|\Pi_{X_{i}}|}\Big{)}\) configurations of values of \(\Pi_{X_{i}}\), which involves summing \(O(l)\) probabilities and dividing them by their total. The resulting computational complexity is \[\underbrace{O\Big{(}l^{|\Pi_{X_{i}}|+1}\cdot l^{N-|\Pi_{X_{i}}|-1}\Big{)}}_{ \text{marginalisation}}+\underbrace{O\Big{(}l\cdot l^{|\Pi_{X_{i}}|}\Big{)}}_{ \text{normalisation}}=O\Big{(}l^{N}+l^{|\Pi_{X_{i}}|+1}\Big{)}\] (2) for each node and \(O\Big{(}Nl^{N}+l\sum_{i=1}^{N}l^{|\Pi_{X_{i}}|}\Big{)}\) for the whole BN.  
**Example 1** (Composing and decomposing a discrete BN).: _For reasons of space, this example is presented as Example A1 in Appendix B._