Exercise 14.4

The arc reversal operation of in a Bayesian network allows us to change the direction of an arc $X\rightarrow Y$ while preserving the joint probability distribution that the network represents @Shachter:1986. Arc reversal may require introducing new arcs: all the parents of $X$ also become parents of $Y$, and all parents of $Y$ also become parents of $X$.

1. Assume that $X$ and $Y$ start with $m$ and $n$ parents, respectively, and that all variables have $k$ values. By calculating the change in size for the CPTs of $X$ and $Y$, show that the total number of parameters in the network cannot decrease during arc reversal. (Hint: the parents of $X$ and $Y$ need not be disjoint.)

2. Under what circumstances can the total number remain constant?

3. Let the parents of $X$ be $\textbf{U} \cup \textbf{V}$ and the parents of $Y$ be $\textbf{V} \cup \textbf{W}$, where $\textbf{U}$ and $\textbf{W}$ are disjoint. The formulas for the new CPTs after arc reversal are as follows: % Prove that the new network expresses the same joint distribution over all variables as the original network.