Square Hellinger Subadditivity for Bayesian Networks and its
  Applications to Identity Testing
  We show that the square Hellinger distance between two Bayesian networks on
the same directed graph, $G$, is subadditive with respect to the neighborhoods
of $G$. Namely, if $P$ and $Q$ are the probability distributions defined by two
Bayesian networks on the same DAG, our inequality states that the square
Hellinger distance, $H^2(P,Q)$, between $P$ and $Q$ is upper bounded by the
sum, $\sum_v H^2(P_{\{v\} \cup \Pi_v}, Q_{\{v\} \cup \Pi_v})$, of the square
Hellinger distances between the marginals of $P$ and $Q$ on every node $v$ and
its parents $\Pi_v$ in the DAG. Importantly, our bound does not involve the
conditionals but the marginals of $P$ and $Q$. We derive a similar inequality
for more general Markov Random Fields.
  As an application of our inequality, we show that distinguishing whether two
Bayesian networks $P$ and $Q$ on the same (but potentially unknown) DAG satisfy
$P=Q$ vs $d_{\rm TV}(P,Q)>\epsilon$ can be performed from
$\tilde{O}(|\Sigma|^{3/4(d+1)} \cdot n/\epsilon^2)$ samples, where $d$ is the
maximum in-degree of the DAG and $\Sigma$ the domain of each variable of the
Bayesian networks. If $P$ and $Q$ are defined on potentially different and
potentially unknown trees, the sample complexity becomes
$\tilde{O}(|\Sigma|^{4.5} n/\epsilon^2)$, whose dependence on $n, \epsilon$ is
optimal up to logarithmic factors. Lastly, if $P$ and $Q$ are product
distributions over $\{0,1\}^n$ and $Q$ is known, the sample complexity becomes
$O(\sqrt{n}/\epsilon^2)$, which is optimal up to constant factors.
