Spencer Gordon<EMAIL_ADDRESS>
California Institute of Technology and Bijan Mazaheri<EMAIL_ADDRESS>
California Institute of Technology and Yuval Rabani<EMAIL_ADDRESS>
Hebrew University in Jerusalem and Leonard Schulman<EMAIL_ADDRESS>
California Institute of Technology

# Causal Inference Despite Limited Global Confounding via Mixture Models

###### Abstract

A Bayesian Network is a directed acyclic graph (DAG) on a set of $n$ random
variables (the vertices); a Bayesian Network Distribution (BND) is a
probability distribution on the random variables that is Markovian on the
graph. A finite $k$-mixture of such models is graphically represented by a
larger graph which has an additional “hidden” (or “latent”) random variable
$U$, ranging in $\\{1,\ldots,k\\}$, and a directed edge from $U$ to every
other vertex. Models of this type are fundamental to causal inference, where
$U$ models an unobserved confounding effect of multiple populations, obscuring
the causal relationships in the observable DAG. By solving the mixture problem
and recovering the joint probability distribution with $U$, traditionally
unidentifiable causal relationships become identifiable. Using a reduction to
the more well-studied “product” case on empty graphs, we give the first
algorithm to learn mixtures of non-empty DAGs.

###### keywords:

mixture models, Bayesian networks, causal DAGs, hidden confounder, population
confounder, clobal confounding, causal identifiability

##  1 Introduction

The distinction between causation and correlation is paramount to the
development of scientific knowledge. While learning spurious correlations is
sufficient for _predicting_ outcomes, causal inference seeks the effect of
intervening on a system. This fortification is an essential step towards using
data to _recommend_ courses of action, whether they are medical treatments or
a changes in economic policy.

Interventional effects are often explored in experimental settings via
“Randomized Controlled Trials” (RCTs), which decouple intervened variables
from potential confounding. Unfortunately, experiments are impossible or
prohibitively expensive in a wide range of complex natural and artificial
systems. In such settings researchers often have to resort to collecting
samples of an assortment of measurements from a joint distribution governed by
causal relations. Such relations define a structural causal model (SCM),
described by a Bayesian network (Pearl, 1985).

The assumption of causal sufficiency describes the often unrealistic case in
which all relevant variables in the causal system are observed. Under causal
sufficiency, the consequences of all interventions on the system are
identifiable by adjusting for the confounders described by the SCM. If causal
sufficiency is relaxed, unobserved confounders cannot be adjusted for using
observed statistics, limiting the identifiability of some interventional
distributions. The _graphical_ conditions under which causal relationships are
identifiable are well studied (Shpitser and Pearl, 2006; Huang and Valtorta,
2008; Pearl, 2009; Spirtes et al., 2000a; Peters et al., 2017; Koller and
Friedman, 2009). There has been little exploration into the identifiability of
causal relationships using _numerical_ conditions.

This paper will address a setting in which an unobserved multiplicity of
populations that confounds an entire system - often called a _mixture model_.
The setting emerges when combining data from many setting or laboratories,
whose environments may exert a confounding influence. Adjusting for the
observed confounder in such settings would involve considering each data
source separately. To make full use of the merged dataset, we may want to
instead assume that some simpler unobserved $U$ (taking on fewer states than
the number of datasets) is sufficient to control for the confounding induced
by the merging. Examples of such a $U$ could include private attributes like
health status or artificially constructed classes such as individual price
sensitivity.

Such a setting satisfies neither observability of the “backdoor adjustment
set” nor the sparsity requirements on the connection of $U$ for the “frontdoor
criterion” (Pearl, 2009). As a result, the causal relationships within the SCM
are considered unidentifiable in the traditional framework. This worst case
analysis ignores the fact that limited cardinality of $U$ would also limit
$U$’s ability to completely hide the causal dynamics. We will show that mild
additional assumptions in conjunction with a known DAG structure allow
identification of the joint probability distribution with the previously
unobservable $U$, a sufficient condition for applying the backdoor adjustment.

###  1.1 Problem Statement

A Bayesian network is a directed acyclic graph
$\mathcal{G}=(\vec{V},\vec{E})$, on a set of
$\mathopen{|}\vec{V}\mathclose{|}=n$ random variables. A corresponding
Bayesian network distribution (BND) is a probability distribution on the
random variables that is Markovian on the graph. That is to say, the joint
distribution on the variables can be factored as
$\prod_{i=1}^{n}\mathcal{P}[V_{i}=v_{i}\mid\operatorname{\operatorname{\textbf{pa}}}(V_{i})]$
where $\operatorname{\operatorname{\textbf{pa}}}(V_{i})$ is the assignment to
the parents of $V_{i}$. A $k$-MixBND on $\mathcal{G}$ is a convex combination,
or “mixture”, of $k$ BNDs. We represent this situation graphically by a single
unobservable random variable $U$ with edges to each of the variable $V\in G$.
Here, $U$ is referred to as a “source” variable with range ${1,\ldots,k}$ and
the variables in $\mathcal{G}$ are referred to as the “observables.” The main
complexity parameter of the problem is $k$, representing the number of mixture
constituents or “sources.”

The extremely special case where $\mathcal{G}$ is empty has been of
longstanding interest in the theory literature. Such a distribution is a
mixture of $k$ product distributions or $k$-MixProd. See Fig. 1.

(a) $V_{1}$$V_{2}$$V_{3}$$V_{4}$$U$ (b) $V_{1}$$V_{2}$$V_{3}$$V_{4}$$U$

Figure 1: (a) A small Bayesian Network, with latent variable $U$. (b) In the
empty graph, a $k$-MixBND is a $k$-MixProd (mixture of product distributions).

In this paper we study the _identification_ problem for $k$-MixBNDs.
Specifically, given the graph $\mathcal{G}$, and given a joint distribution
$\mathcal{P}$ on the variables (vertices), recover up to small statistical
error (a) the mixture weights (probability of each source), up to a
permutation of the constituents, and (b) for every mixture source and for
every vertex $V$, its conditional distribution given each possible setting to
the parents of $V$. This task identifies the joint probability distribution
$\mathcal{P}(U,\vec{V})$ up to the $k!$ permutations in the label $U$.
Identification will be shown by giving an algorithm that reduces the
$k$-MixBND problem into a series of calls to a $k$-MixProd oracle. $k$-MixBND
models are not always identifiable, as further discussed in _Assumptions_
below. Thus, another contribution of our paper is to establish a sufficient
setting to guarantee identifiability.

##### Assumptions

The following assumptions are used throughout this paper.

  1. 1.

_We have access to a $k$-MixProd oracle requiring $\mathcal{O}(k)$ variables
that are independent within each source. _ As different algorithms have
different requirements for the number of independent variables, we will keep
our results agnostic to these requirements. The most efficient published
algorithm is given in Gordon et al. (2021), which requires
$N_{\text{mp}}=3k-3$ variables and time complexity $\exp(k^{2})$. Recent
unpublished work improves the complexity bound to $\exp(k\log k)$.

  2. 2.

_The observable variables in our BND are binary and discrete._ While a number
of papers have focused on continuous or large-alphabet settings, we restrict
our focus to the simplest setting of binary, discrete variables. Appendix C.2
gives a reduction from alphabets of any size $d$ to the binary case, incurring
a mild cost in complexity.

  3. 3.

_The mixture is supported on $\leq k$ sources._ If the hidden variable $U$ has
unrestricted range (Specifically, range $k=2^{n}$ would be enough), the model
is rich enough to describe _any_ probability distribution on $\vec{V}$, making
identification impossible. The question is therefore one of trading $k$
against the sample and computational complexity of an algorithm (and the
degree of the network).

  4. 4.

_The underlying Bayesian DAG is sufficiently sparse._ In order to reduce
$k$-MixBND to $k$-MixProd we need sufficiently many variables that can be
separated from each other by conditioning on disjoint _Markov boundaries_
(example in Fig. 2, definition in Sec. 1.4). As a result, the complexity of
the algorithm is exponential in the size of a Markov boundary. Both for
complexity and in order to keep $n$ small, a bound on the maximum degree
$\Delta$ is required. We require $n\geq(\Delta+1)^{4}N_{\text{mp}}$.111If the
skeleton of $\mathcal{G}$ happens to be a path, then we only need a milder
condition that $n\geq 2N_{\text{mp}}$. For details see Appendix C.1.

$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$V_{6}$$V_{7}$$V_{8}$$V_{9}$$V_{10}$$V_{11}$$V_{12}$$V_{13}$$U$

$U\mid\operatorname{\operatorname{\textbf{COND}}}$$V_{1}\mid
V_{2},V_{3}$$V_{6}\mid V_{4},V_{8}$$V_{9}\mid V_{7},V_{10},V_{11}$$V_{13}\mid
V_{12}$

$\operatorname{\operatorname{\textbf{COND}}}:=\left\\{\begin{aligned}
&\scalebox{0.4}{ \leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{3}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{4}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{7}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\\\ &\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{8}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.77943pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{10}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.77943pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{11}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to24.36pt{\vbox
to24.36pt{\pgfpicture\makeatletter\hbox{\hskip 12.1811pt\lower-12.1811pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{11.3811pt}{0.0pt}\pgfsys@curveto{11.3811pt}{6.28569pt}{6.28569pt}{11.3811pt}{0.0pt}{11.3811pt}\pgfsys@curveto{-6.28569pt}{11.3811pt}{-11.3811pt}{6.28569pt}{-11.3811pt}{0.0pt}\pgfsys@curveto{-11.3811pt}{-6.28569pt}{-6.28569pt}{-11.3811pt}{0.0pt}{-11.3811pt}\pgfsys@curveto{6.28569pt}{-11.3811pt}{11.3811pt}{-6.28569pt}{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.77943pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor[named]{.}{rgb}{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}\hbox{\scriptsize{\definecolor[named]{.}{rgb}{1,1,1}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}$V_{12}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\end{aligned}\right\\}$$\vec{I}:=\left\\{\scalebox{0.4}{
\leavevmode\hbox to20.72pt{\vbox
to20.72pt{\pgfpicture\makeatletter\hbox{\hskip
10.35957pt\lower-10.35957pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.5,0.5,1}\pgfsys@color@rgb@fill{0.5}{0.5}{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.5,0.5,1}\pgfsys@color@rgb@fill{0.5}{0.5}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{9.55957pt}{0.0pt}\pgfsys@curveto{9.55957pt}{5.27966pt}{5.27966pt}{9.55957pt}{0.0pt}{9.55957pt}\pgfsys@curveto{-5.27966pt}{9.55957pt}{-9.55957pt}{5.27966pt}{-9.55957pt}{0.0pt}\pgfsys@curveto{-9.55957pt}{-5.27966pt}{-5.27966pt}{-9.55957pt}{0.0pt}{-9.55957pt}\pgfsys@curveto{5.27966pt}{-9.55957pt}{9.55957pt}{-5.27966pt}{9.55957pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\scriptsize{$V_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to20.72pt{\vbox
to20.72pt{\pgfpicture\makeatletter\hbox{\hskip
10.35957pt\lower-10.35957pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{1,0.5,0.5}\pgfsys@color@rgb@fill{1}{0.5}{0.5}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{1,0.5,0.5}\pgfsys@color@rgb@fill{1}{0.5}{0.5}\pgfsys@invoke{
}{}\pgfsys@moveto{9.55957pt}{0.0pt}\pgfsys@curveto{9.55957pt}{5.27966pt}{5.27966pt}{9.55957pt}{0.0pt}{9.55957pt}\pgfsys@curveto{-5.27966pt}{9.55957pt}{-9.55957pt}{5.27966pt}{-9.55957pt}{0.0pt}\pgfsys@curveto{-9.55957pt}{-5.27966pt}{-5.27966pt}{-9.55957pt}{0.0pt}{-9.55957pt}\pgfsys@curveto{5.27966pt}{-9.55957pt}{9.55957pt}{-5.27966pt}{9.55957pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\scriptsize{$V_{6}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to20.72pt{\vbox
to20.72pt{\pgfpicture\makeatletter\hbox{\hskip
10.35957pt\lower-10.35957pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.5,1,0.5}\pgfsys@color@rgb@fill{0.5}{1}{0.5}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.5,1,0.5}\pgfsys@color@rgb@fill{0.5}{1}{0.5}\pgfsys@invoke{
}{}\pgfsys@moveto{9.55957pt}{0.0pt}\pgfsys@curveto{9.55957pt}{5.27966pt}{5.27966pt}{9.55957pt}{0.0pt}{9.55957pt}\pgfsys@curveto{-5.27966pt}{9.55957pt}{-9.55957pt}{5.27966pt}{-9.55957pt}{0.0pt}\pgfsys@curveto{-9.55957pt}{-5.27966pt}{-5.27966pt}{-9.55957pt}{0.0pt}{-9.55957pt}\pgfsys@curveto{5.27966pt}{-9.55957pt}{9.55957pt}{-5.27966pt}{9.55957pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.79944pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\scriptsize{$V_{9}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\scalebox{0.4}{
\leavevmode\hbox to22.16pt{\vbox
to22.16pt{\pgfpicture\makeatletter\hbox{\hskip
11.08101pt\lower-11.08101pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{1,0.75,0.5}\pgfsys@color@rgb@fill{1}{0.75}{0.5}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.6pt}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{1,0.75,0.5}\pgfsys@color@rgb@fill{1}{0.75}{0.5}\pgfsys@invoke{
}{}\pgfsys@moveto{10.281pt}{0.0pt}\pgfsys@curveto{10.281pt}{5.67812pt}{5.67812pt}{10.281pt}{0.0pt}{10.281pt}\pgfsys@curveto{-5.67812pt}{10.281pt}{-10.281pt}{5.67812pt}{-10.281pt}{0.0pt}\pgfsys@curveto{-10.281pt}{-5.67812pt}{-5.67812pt}{-10.281pt}{0.0pt}{-10.281pt}\pgfsys@curveto{5.67812pt}{-10.281pt}{10.281pt}{-5.67812pt}{10.281pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.77943pt}{-1.76012pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\scriptsize{$V_{13}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\right\\}$”Conditioning
set””Independent set” Figure 2: The reduction process of conditioning on
$\operatorname{\operatorname{\textbf{COND}}}$ to create an instance of
$k$-MixProd. A Bayesian network with four vertices $V_{1},V_{6},V_{9},V_{13}$
and their corresponding disjoint Markov boundaries are indicated.

  5. 5.

_The resulting product mixtures are non-degenerate._ Even in mixtures of
graphs with sparse structure (in particular the empty graph—the $k$-MixProd
problem), the $k$-MixBND can be unidentifiable if the mixture components are
insufficiently distinct. (E.g., trivially, a mixture of identical sources
generates the same statistics as a single source.) Past work has used
conditions such as $\zeta$-separation in Gordon et al. (2021) to ensure that
matrices representing the parameters for each source are well-conditioned.
These are not always necessary conditions; characterizing necessary conditions
is a difficult question tackled in part in Gordon and Schulman (2022).

  6. 6.

_The DAG structure representing conditional independence properties within
each source, or a common supergraph of these structures, is known._ It is
often the case that domain knowledge provides an understanding of the causal
DAG. If the causal DAG is unknown, we are faced with a different problem
commonly known as “Causal Discovery”(see Glymour et al. (2019a) for a recent
survey.) A method for causal discovery in the presence of a universal
confounder has been suggested in Anandkumar et al. (2012a) by substituting
independence tests with rank tests. In our motivating example of dataset
merging, it is likely that the structure can be learned from an individual
dataset. Like in Anandkumar et al. (2012a), the presented algorithm will
actually only require a supergraph of the true structure. Hence, some
uncertainty in knowledge of the graph can be tolerated. In fact, the algorithm
also works even if the different components of the $k$-MixBND use slightly
different causal graphs.

###  1.2 Summary of contributions

######  Theorem 1.1.

Our algorithm identifies a $k$-MixBND distribution with on a graph of maximum
degree $\Delta$ and of size $n\geq\Omega(N_{\text{MP}}\Delta^{4})$, using
$O(n2^{\Delta^{2}})$ calls to an oracle for the $k$-MixProd problem. For an
exact statement see Theorem 4.4.

The algorithm will be built on the insight that conditioning on a set of
Markov boundaries $\operatorname{\operatorname{\textbf{COND}}}\subset\vec{V}$
of $\vec{I}\subset V$ induces _within-source_ independence (that is,
$V_{i}\perp\\!\\!\\!\perp V_{j}\mid
U,\operatorname{\operatorname{\textbf{COND}}}$ for all
$V_{i},V_{j}\in\vec{I}$). This describes an instance of $k$-MixProd for which
we can identify the joint probability distribution
$\mathcal{P}(\vec{I},U\mid\operatorname{\operatorname{\textbf{COND}}})$. See
Figure 2 for an illustration.

Recovering
$\mathcal{P}(\vec{I},U\mid\operatorname{\operatorname{\textbf{COND}}})$ for
some $\vec{I}\subset\vec{V}$ is insufficient to recover the full joint
probability distribution $\mathcal{P}(\vec{V},U)$. Hence, we execute a set of
$O(n2^{\Delta^{2}})$ “runs” of a $k$-MixProd oracle on differing
$\vec{I},\operatorname{\operatorname{\textbf{COND}}}$ and assignments to their
Markov boundaries and synthesize information gained from these runes into the
joint probability distribution.

The first challenge is to handle symmetries in permutation of the output
labels of $U$ by “aligning” the outcomes of these runs. The second challenge
is to remove the conditioning of $\vec{C}$ from each run. We do this by
synthesizing the results of many runs with a procedure we call “Bayesian
unzipping.” Our key contributions can be summarized by these “alignment” and
“unzipping” procedures, as well as the notion of a “good collection of runs”
that allows for the successful application of these sub-processes

##### Organization

The rest of the paper is organized as follows. In Section 1.3 we outline the
literature background of the problem. In Section 1.4 we give some Bayesian
network notation. In Section 2 we formally develop the notion of a “run,”
which calls a $k$-MixProd oracle. In Section 3 we explain how the output of
the “runs” is combined to get the desired mixture parameters. This section
details the processes of alignment and Bayesian unzipping. Section 4 explains
what is necessary in a group of runs in order for the algorithm to succeed,
which provides a framework for defining algorithms in terms of sets of runs.

In Appendix A we define the $k$-MixBND algorithm in pseudo-code. In Appendix C
we analyze the $k$-MixBND algorithm. In Appendix B we prove the existence of a
good collection of runs. In Appendix C.2 we generalize our algorithms to
handle non-binary observations.

###  1.3 Background

There are two problems within mixture models: (1) _Learning_ the model,
namely, producing any model consistent with (or close to) the observations;
(2) _Identifying_ the model, namely, producing the true model (or one close to
it) up to permutations in the source label. The feasibility of the
identification problem hinges on a one-to-one mapping between the observed
statistics and the model’s parameters. When using the resulting model to
deconfound causal relationships, it is imperative that that the joint
probability distribution with the confounder be identified.

The idea of using mixture models to identify parameters in latent variables
dates back to E. S. Allman (2009), who use algebraic methods from Kruskal
(1976, 1977) to exploit within-source independence. Anandkumar et al. (2012b)
follows a similar strategy using tensor decomposition. Both of these works
rely on within-source independence between three variables with support on
large alphabets (i.e. large cardinality) to achieve _generic_ 222Here,
“generic” identifiability means that the set of unidentifiable models makes up
a Lebesgue measure $0$ subset in the parameter space. identifiablility.
Specifically, the alphabet size of the independent variables must scale
linearly with $k$. Such a requirement can be achieved by combining variables
of smaller variables, i.e. two binary variables can be combined to make up an
alphabet size of $4$. E. S. Allman (2009) showed that identifiability holds
_generically_ for smaller alphabets with $\mathcal{O}(\log(k))$ independent
variables via these combinations.

A different line of work in the theory community seeks _full_ identifiability,
requiring $\mathcal{O}(k)$ independent variables in conjunction with
separation conditions to ensure that the visible variables behave differently
in different mixture components 333Separation conditions can be thought of as
a form of faithfulness of edges from $U$ to $\vec{V}$. This problem, referred
to as $k$-MixProd, and has been studied for nearly 30 years (Kearns et al.,
1994; Cryan et al., 2001; Freund and Mansour, 1999; Feldman et al., 2008;
Chaudhuri and Rao, 2008; Tahmasebi et al., 2018; Chen and Moitra, 2019; Gordon
et al., 2021).444We do not even try to list the extensive analogous literature
for parametrized distributions over $\mathbb{R}$. In Feldman et al. (2008) a
seminal algorithm for $k$-MixProd was given with running time $n^{O(k^{3})}$
for mixtures on $n$ binary variables ($n$ sufficiently large). This was
improved in Chen and Moitra (2019) to $k^{O(k^{3})}n^{O(k^{2})}$. The most
recent algorithm, Gordon et al. (2021) identifies a mixture of $k$ product
distributions on at least $3k-3$ variables in time $2^{O(k^{2})}n^{O(k)}$,
under a mild “separation” condition that excludes unidentifiable instances.
Under somewhat stricter separation, the time complexity improves to
$2^{O(k^{2})}n$. One can choose between the generic identifiability and full
identifiability approaches when reducing Bayesian network mixtures to mixtures
of products. The same complexity bottlenecks appear in both strategies, but
the number of independent variables that must be instantiated differs.

To our knowledge, the only other attempt at detailing a multiple-run reduction
to $k$-MixProd is Anandkumar et al. (2012a), which gives an algorithm for
mixtures of Markov random fields–i.e., undirected graphical models. As both
papers make use of boundary conditioning to induce independence and a form of
“alignment,” our paper can be thought of as both an improvement and an
extension to the directed graph case. While Anandkumar et al. (2012a) require
a single variable that is independent from the rest of the structure for
allignment, our algorithm develops the notion of “good collections of runs” to
eliminate this restriction – a contribution which may have implications in the
Markov random field setting as well. Additional complications arise for
directed graphs because the outputs of the $k$-MixProd subroutine are
conditioned on their Markov boundaries while the desired parameters are only
conditioned on their _parents_. Finally, we note that Anandkumar et al.
(2012a) only guarantees identification of second order marginal probabilities,
which is insufficient for causal identification. 555We also mention that
Anandkumar et al. (2010) and Anandkumar et al. (2012a) introduce the idea of a
sparse local separator; if this can be adapted to the directed-graph case one
might be able to somewhat relax assumption 4. We do not attempt this in this
paper.

##### Other related work

Kivva et al. (2021) contains as a special case a reduction to the $k$-MixProd
problem. Their goal is to learn a causal graphical model with latent
variables, but with a very different structure on the visible and latent
variables. They allow for a DAG of latent variables with visible children
(which is learned as part of their algorithm); on the other hand, they require
that there be no causal relations between visible variables. In our work, the
structure on the latent variables is trivial (since there is a single latent
variable), but the structure on the visible variables is arbitrary.
Characterizing identifiability in the generalization of both these settings in
which we allow structure on both the visible and latent portion of the graph
is a nice problem beyond the scope of this paper.

Another paper with kindred motivation to ours is Kumar and Sinha (2021), which
studies inference of a certain kind of MixBND, in which the structure of the
Bayesian network is known, but the data collected is a mixture over some $m$
unknown interventional distributions. The authors give sufficient conditions
for identifiability of the network and of the intervention distributions. At a
technical level, the papers are not closely related. $k$ is not a parameter in
their work, and instead what is essential is an “exclusion” assumption which
says that each variable has some value to which it is not assigned by any of
the interventions.

Some other loosely related work includes learning hidden Markov models (Hsu et
al., 2012; Anandkumar et al., 2012b; Sharan et al., 2017), an incomparable
line of work to our question, but with somewhat similar motivation. In the
same vein, some papers study learning mixtures of Markov chains from
observations of random paths through the state space Batu et al. (2004); Gupta
et al. (2016). These models, too, differ substantially from the models
addressed in this paper, and pose very different challenges. Literature on
causal structure learning (Spirtes et al., 2000b; Glymour et al., 2019b)
answers the question of identifying the _presence_ of hidden confounders. Fast
Causal Inference (FCI) harnesses observed conditional independence to learn
causal structure, which can detect the presence of unobserved variables when
the known variables are insufficient to explain the observed behavior. This
literature includes the MDAG problem in which the DAG structure may depend
upon the hidden variable; see Thiesson et al. (1998) for heuristic approaches
to this problem. Other related works study causal inference in the presence of
visible “proxy” variables which are influenced by a latent confounder (Miao et
al., 2018; Kuroki and Pearl, 2014; Mazaheri et al., 2023). This has more
recently given rise to attempts at deconfounding using multiple causes
(Heckerman, 2018; Ranganath and Perotte, 2018; Wang and Blei, 2019). The
initial assumptions of Wang and Blei (2019) were shown to be insufficient for
deconfounding in Ogburn et al. (2019). This illustrates the necessity of
identifying of the joint probability distribution with the confounder.
666Thanks to Betsy Ogburn for her thoughts on this topic.

Finite mixture models have been the focus of intense research for well over a
century, since pioneering work in the late 1800s (Newcomb, 1886; Pearson,
1894), and doing justice to the vast literature that emanated from this
endeavor is impossible within the scope of this paper. See, e.g., the surveys
Everitt and Hand (1981); Titterington et al. (1985); Lindsay (1995); McLachlan
et al. (2019).

###  1.4 Notation

A Bayesian network consists of a directed acyclic graph (DAG)
$\mathcal{G}=(\vec{V},\vec{E})$ and a probability distribution $\mathcal{P}$
over $\vec{V}=\left\\{V_{1},\dotsc,V_{n}\right\\}$ factoring according to
$\mathcal{G}$, i.e.,

$\mathcal{P}(V_{1},V_{2},\dotsc,V_{n})=\prod_{i=1}^{n}\mathcal{P}(V_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(V_{i})),$

where $\operatorname{\operatorname{\textbf{PA}}}(V)$ is the set of parents of
$V\in\vec{V}$. (Similarly, let $\operatorname{\operatorname{\textbf{CH}}}(V)$
denote the children of $V$.) Equivalently, $\mathcal{P}$ must satisfy that for
any $V\in\vec{V}$, $V$ is independent of its non-descendants, given its
parents.

Generally, we will use bold letters to denote sets of variables. For a matrix
$M$, we will use $M_{ij}$ to identify entries. We use $M_{i,-}$ to denote the
vector $(M_{i,1},M_{i,2},\ldots M_{i,k})$.

Conditioning on the “Markov boundary” of a vertex
$\operatorname{\operatorname{\textbf{MB}}}(V)$ makes $V$ conditionally
independent from everything else in the graph (Pearl, 2014).

######  Definition 1.2 (Markov Boundary).

For a vertex $Y$ in a DAG $\mathcal{G}=(\vec{V},\vec{E})$, the Markov boundary
of $Y$, denoted $\operatorname{\operatorname{\textbf{MB}}}(Y)$, is defined by

$\operatorname{\operatorname{\textbf{MB}}}(Y)\coloneqq\operatorname{\operatorname{\textbf{PA}}}(Y)\cup\operatorname{\operatorname{\textbf{CH}}}(Y)\cup\operatorname{\operatorname{\textbf{PA}}}(\operatorname{\operatorname{\textbf{CH}}}(Y))\setminus\\{Y\\}.$

######  Lemma 1.3 (See Pearl (2014)).

For any vertex $V\in\vec{V}$ and subset $S\subseteq
V\setminus(\operatorname{\operatorname{\textbf{MB}}}(V)\cup\left\\{V\right\\})$,
$\mathcal{P}(V\mid\operatorname{\operatorname{\textbf{MB}}}(V),S)=\mathcal{P}(V\mid\operatorname{\operatorname{\textbf{MB}}}(V))$.

###### Observation 1.4

For any $X,Y\in\vec{V}$, $X\in\operatorname{\operatorname{\textbf{MB}}}(Y)\iff
Y\in\operatorname{\operatorname{\textbf{MB}}}(X)$

##### Uppercase/lowercase conventions

Following notation in causal inference literature, we will use lowercase
letters to denote assignments. For example $\mathcal{P}(v\mid
u)=\mathcal{P}(V=v\mid U=u)$. Following this convention, we will write
$\operatorname{\operatorname{\textbf{pa}}}(V)$,
$\operatorname{\operatorname{\textbf{ch}}}(V)$, and
$\operatorname{\operatorname{\textbf{mb}}}(X)$ to denote assignment to the
parents $\operatorname{\operatorname{\textbf{PA}}}(V)$, children
$\operatorname{\operatorname{\textbf{CH}}}(V)$, and Markov boundary
$\operatorname{\operatorname{\textbf{MB}}}(V)$.

##### Within-source probabilities

It will be easier to write $\mathcal{P}_{u}(v)=\mathcal{P}(v\mid u)$ to give
the probability distribution within a source.

Finally, here are a few more definitions that will make the upcoming sections
simpler.

######  Definition 1.5 (Top).

We will use $\operatorname{\textbf{TOP}}(V)$ to denote
$\operatorname{\operatorname{\textbf{MB}}}(V)\setminus\operatorname{\operatorname{\textbf{CH}}}(V)$.

######  Definition 1.6 (Depth of a vertex).

Given a DAG $\mathcal{G}=(\vec{V},\vec{E})$ and any vertex $V\in\vec{V}$, let
$d_{\mathcal{G}}(V)$ be the depth of $V$ in $\mathcal{G}$, i.e. the length of
the shortest path from a degree-$0$ vertex in $\mathcal{G}$. When
$\mathcal{G}$ is clear from context, we’ll omit the subscript.

######  Definition 1.7.

We’ll introduce a parameter $\gamma(G)$ which will appear in the complexity of
the identification procedure, which is defined by
$\gamma(G)\coloneqq\max_{V\in\vec{V}}\left|\operatorname{\operatorname{\textbf{MB}}}(V)\right|$.

##  2 Applying a $k$-MixProd run

Our algorithm will induce instances of $k$-MixProd through post-selected
conditioning. A significant portion of this paper will be accounting for
multiple calls (or “runs”) of a $k$-MixProd oracle and explaining how their
results can be combined.

###  2.1 Describing runs

We will need to keep track of two crucial elements of each “run” of a
$k$-MixProd oracle.

  1. 1.

Which variables $\in\vec{V}$ are passed to our $k$-MixProd oracle as
independent variables (the independent set).

  2. 2.

Which variables $\in\vec{V}$ we have conditioned on (the conditioning set) and
what values we have post-selected these variables to take.

A sufficient conditioning set to induce within-source independence among the
independent set is the union of their Markov boundaries. This will be further
refined in Subsection 4.2.

######  Definition 2.1 (Run).

A run over a graph $\mathcal{G}=(\vec{V},\vec{E})$ is a tuple
$a=(\vec{I}^{a},f^{a})$ where $\vec{I}^{a}\subseteq\vec{V}$ are variables that
we will $d$-separate (within each source) by conditioning on assignments to
the set

$\operatorname{\operatorname{\textbf{COND}}}^{a}\coloneqq\bigcup_{I\in\vec{I}^{a}}\operatorname{\operatorname{\textbf{MB}}}(I)$

The value of the assignment is given by
$f^{a}:\operatorname{\operatorname{\textbf{COND}}}^{a}\to\left\\{0,1\right\\}$.
We’ll call $\vec{I}^{a}$ the independent set for $a$, and
$\operatorname{\operatorname{\textbf{COND}}}^{a}$ the conditioning set.

We will restrict our attention to _well-formed runs_ , i.e. runs for which
$\vec{I}^{a}\cap\operatorname{\operatorname{\textbf{COND}}}^{a}=\emptyset$.

######  Definition 2.2.

An individual run $a=(\vec{I}^{a},f^{a})$ is $N$-independent if
$\left|\vec{I}^{a}\right|\geq N$.

##### Superscript notation

We’ll write $\operatorname{\operatorname{\textbf{mb}}}^{a}(V)$,
$\operatorname{\operatorname{\textbf{pa}}}^{a}(V)$,
$\operatorname{\operatorname{\textbf{ch}}}^{a}(V)$ to refer to the assignment
to the Markov boundary of $V$, parents of $V$, and children of $V$ as set by
run $a$.777Any quantities parameterized by a run will take the parameter as a
superscript. In a similar spirit, we’ll occasionally write $v^{0}$ to denote
the assignment $V=0$.

######  Definition 2.3 (Distribution induced by a run).

For any well-formed run $a$, the induced distribution on the variables in
$\vec{I}^{a}$ is denoted by

$\mathcal{P}^{a}(\cdot)=\mathcal{P}(\cdot\mid\operatorname{\operatorname{\textbf{cond}}}^{a}),$

where $\operatorname{\operatorname{\textbf{cond}}}^{a}$ is the assignment to
$\operatorname{\operatorname{\textbf{COND}}}^{a}$ in keeping with our
conventions.

The outputs of applying a $k$-MixProd oracle to $\mathcal{P}^{a}(\vec{I}^{a})$
are a matrix $\vec{M}^{a}\in[0,1]^{\left|\vec{I}^{a}\right|\times k}$ and a
vector of mixture weights, $\pi^{a}\in[0,1]^{k}$ (satisfying
$\sum_{u}\pi^{a}_{u}=1$) given by

$\displaystyle M^{a}_{i,u}$
$\displaystyle\coloneqq\mathcal{P}^{a}(X^{a}_{i}=1\mid
U_{a}=u)=\mathcal{P}(X_{i}=1\mid
U^{a}=u,\operatorname{\operatorname{\textbf{COND}}}^{a}),$
$\displaystyle\quad\forall X_{i}\in\vec{I}^{a},u\in[k]$ (1)
$\displaystyle\pi^{a}_{u}$
$\displaystyle\coloneqq\mathcal{P}^{a}(U^{a}=u)=\mathcal{P}(U_{a}=u\mid\operatorname{\operatorname{\textbf{COND}}}^{a}),$
$\displaystyle\quad\forall j\in[k]$ (2)

where $U^{a}$ is the mixture source distributed over $[k]$ according to
$\mathcal{P}(U\mid\operatorname{\operatorname{\textbf{COND}}}^{a})$. Note that
because mixtures are invariant to permutations of mixture component labels, we
cannot guarantee correspondence between the labels for the source variables
from different runs. Hence the labels of $U^{a}$ to an unknown permutation of
the labels in $U$. Alignment of these labels is handled in Section 3.1.

##  3 Combining Runs

A single run of the $k$-MixProd oracle will not contain sufficient information
to learn the parameters of the $k$-MixBND problem. Instead we must synthesize
information across _multiple_ runs.

###  3.1 Aligning source labels across different runs

Each run of the $k$-MixProd oracle will return $\mathcal{P}^{a}(V\mid
U_{a}=u)$ for some arbitrary permutation $U_{a}$ of the variable. We need to
align all of the outputs to the same permutation of the source, $U$. If the
runs overlap on at least one variable with the same mixture probabilities, we
can use that “alignment variable” to identify which source corresponds to
which set of parameters. In our setup, we will guarantee these alignment
variables exist by ensuring that runs have shared vertices in their
independent sets whose Markov boundaries have identical assignments.

######  Definition 3.1.

$X\in\vec{V}$ is separated if for all $u_{i}\neq u_{j}\in[k]$,
$\mathcal{P}_{u_{i}}(x)\neq\mathcal{P}_{u_{j}}(x)$.

######  Definition 3.2 (Aligned runs).

A pair of runs $a,b$ over independent sets $\vec{I}^{a},\vec{I}^{b}$ is
alignable if there exists a separated $X\in\vec{I}^{(a)}\cap\vec{I}^{(b)}$
such that $\mathcal{P}^{a}_{u}(V^{(ab)})=\mathcal{P}^{b}_{u}(V^{(ab)})$ for
all $u\in[k]$. We’ll call any such random variable $X$ an alignment variable,
and use $\operatorname{\operatorname{\textbf{AV}}}(a,b)$ to denote the set of
all alignment variables for $\mathcal{P}^{a}$ and $\mathcal{P}^{b}$. We
sometimes say $a$ and $b$ are “aligned at” $X$.

######  Definition 3.3 (Alignment spanning tree).

We say a set of $\ell$ runs is alignable if there exists an undirected
spanning tree over the graph with vertices $a_{1},\ldots a_{\ell}$ and an edge
$\\{a_{i},a_{j}\\}$ whenever
$\operatorname{\operatorname{\textbf{AV}}}(a_{i},a_{j})\neq\emptyset$. We call
this the alignment spanning tree.

The alignment step will take the output from alignable runs and permute the
mixture labels until the parameters match along each alignment variable.
Pseudocode for this procedure is given in Algorithm 1.

###  3.2 Bayesian unzipping: recovering parameters per source

Recall that our algorithm conditions on Markov boundaries to induce
independent variables. Hence, after aligning the sources in runs of the
$k$-MixProd oracle we will have access to
$\mathcal{P}_{u}(Y\mid\operatorname{\operatorname{\textbf{MB}}}(Y))$ for each
$Y\in V$. Our goal is to obtain $\mathcal{P}_{u}(\vec{V})$, which is described
by the parameters
$\mathcal{P}_{u}(Y\mid\operatorname{\operatorname{\textbf{PA}}}(Y))$ for each
$Y\in\vec{V}$. Note that

$\mathcal{P}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{mb}}}(Y))=\frac{\mathcal{P}_{u}(y^{1},\operatorname{\operatorname{\textbf{mb}}}(Y))}{\mathcal{P}_{u}(y^{1},\operatorname{\operatorname{\textbf{mb}}}(Y))+\mathcal{P}_{u}(y^{0},\operatorname{\operatorname{\textbf{mb}}}(Y))}.$
(3)

The terms in this fraction are all of the same form and can be factored
according to the DAG into

$\mathcal{P}_{u}(y,\operatorname{\operatorname{\textbf{mb}}}^{a}(Y))=\mathcal{P}_{u}(\operatorname{\textbf{top}}(Y))\mathcal{P}_{u}(y\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))\underbrace{\prod_{V\in\operatorname{\operatorname{\textbf{CH}}}(Y)}\mathcal{P}_{u}(v^{a}\mid
f^{a}(\operatorname{\operatorname{\textbf{PA}}}(V)\setminus\\{Y\\}),y)}_{\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(Y)\mid\operatorname{\textbf{top}}^{a}(Y),y)}.$

See Figure 3 for a concrete example of this decomposition. After substituting
this factorization into Equation (3) we see that
$\mathcal{P}_{u}(\operatorname{\textbf{top}}(Y))$ appears in both the
numerator and denominator because it is independent of the assignment to $Y$.
Simplification leaves only the following terms:

  1. 1.

$\mathcal{P}_{u}(y^{0}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
and
$\mathcal{P}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$,
which must sum to 1.

  2. 2.

$\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(Y)\mid\operatorname{\textbf{top}}^{a}(Y),y^{0})$
and
$\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(Y)\mid\operatorname{\textbf{top}}^{a}(Y),y^{1})$
which are both the product of the desired parameters of variables later in the
topological ordering. We can ensure we have access to these terms by solving
for the parameters of $V\in\vec{V}$ in a reverse-topological ordering.888We
will want to ensure that we only need to unzip parameters from vertices of a
bounded depth, which bounds the iterations of this step. Details on how this
is done appear in Section 4.2.

We can substitute
$1-\mathcal{P}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
for
$\mathcal{P}_{u}(y^{0}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
in the expanded version of Equation (3) to obtain a single equation with only
$\mathcal{P}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
as an unknown, which we can then solve. The pseudocode for this process is
given in Algorithm 2.

$Y$$V_{1}$$V_{2}$$V_{5}$$V_{4}$$V_{3}$

$Y$$V_{1}$$V_{2}$$V_{5}$$V_{4}$$V_{3}$

$Y$$V_{1}$$V_{2}$$V_{5}$$V_{4}$$V_{3}$

$Y$$V_{1}$$V_{2}$$V_{5}$$V_{4}$$V_{3}$

Figure 3: We can decompose
$\mathcal{P}_{u}(v_{1},v_{2},v_{3},y,v_{4},v_{5})=\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathcal{P}_{u}(v_{1},v_{2},v_{3})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\mathcal{P}_{u}(y\mid
v_{1},v_{2})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{P}_{u}(v_{4}\mid
y,v_{3})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{0.7,0.35,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.7,0.35,0}\mathcal{P}_{u}(v_{5}\mid
y,v_{4})\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$.
$U$ and any other variables in the graph are omitted for clarity.

####  3.2.1 Recovering the distribution on sources

Now consider some arbitrary run $a$ with conditioning
$\operatorname{\operatorname{\textbf{cond}}}^{a}$. Since
$\mathcal{P}_{u}(\vec{V})=\prod_{V\in\vec{V}}\mathcal{P}_{u}(V\mid\operatorname{\operatorname{\textbf{PA}}}(V))$,
knowing $\mathcal{P}_{u}(V\mid\operatorname{\operatorname{\textbf{PA}}}(V))$
grants us full access to the within-source probability distribution
$\mathcal{P}_{u}(\vec{V})$ after Bayesian unzipping. From this we can we
obtain
$\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{cond}}}^{a})=\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u)$. The $k$-MixProd oracle will also return
$\mathcal{P}^{a}(U)=\mathcal{P}(U\mid\operatorname{\operatorname{\textbf{cond}}}^{a})$
when run on $a$ (after source alignment). Finally,
$\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a})$ is directly
observable. Combining these terms in Bayes’ rule lets us compute the
distribution on $U$ (under the assumption of positivity),

$\mathcal{P}(u)=\frac{\mathcal{P}(u\mid\operatorname{\operatorname{\textbf{cond}}}^{a})\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a})}{\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u)}.$

###  3.3 Outline of the combination process

Combining a set of runs $\mathcal{A}$ has four steps.

  1. 1.

Use a $k$-MixProd oracle on
$\mathcal{P}(\vec{I}^{a}\mid\operatorname{\operatorname{\textbf{COND}}}^{a})$
for each run $a\in\mathcal{A}$ to compute
$P(V\mid\operatorname{\operatorname{\textbf{MB}}}(V),U_{a}=u)$ for all
variables $V\in\vec{V}$.

  2. 2.

Align the parameters obtained from the previous step to ensure that $U$ means
the same thing across different runs, giving
$\mathcal{P}_{u}(V\mid\operatorname{\operatorname{\textbf{MB}}}(Y))$.

  3. 3.

Recover $\mathcal{P}_{u}(V\mid\operatorname{\operatorname{\textbf{PA}}}(V))$
for each vertex $V\in\vec{V}$ via Bayesian unzipping.

  4. 4.

Compute $\mathcal{P}(U)$ by applying Bayes’ law.

The full procedure appears as Algorithm 3.

##  4 Collections of runs

With the main concepts of source alignment and Bayesian unzipping now defined,
our algorithm will primarily consist of finding a good collection of these
runs so that these subroutines can be successfully applied to recover the
$k$-MixBND mixture.

###### Observation 4.1

Two runs $a,b$ are aligned at $X\in\vec{V}$ if and only if

  1. 1.

$X\in\vec{I}^{a}\cap\vec{I}^{b}$,

  2. 2.

$\operatorname{\operatorname{\textbf{mb}}}^{a}(X)=\operatorname{\operatorname{\textbf{mb}}}^{b}(X)$,
i.e,
$f^{a}(\operatorname{\operatorname{\textbf{MB}}}(X))=f^{b}(\operatorname{\operatorname{\textbf{MB}}}(X))$,
and

  3. 3.

$X$ is separated given $\operatorname{\operatorname{\textbf{mb}}}^{a}(X)$
(equivalently, given $\operatorname{\operatorname{\textbf{mb}}}^{b}(X)$).

######  Definition 4.2.

A collection of runs $\mathcal{A}$ covers $X\in\vec{V}$ if for every
assignment $\operatorname{\operatorname{\textbf{pa}}}(X)$ to
$\operatorname{\operatorname{\textbf{PA}}}(X)$ there exists a run
$a\in\mathcal{A}$ with $X\in\vec{I}^{a}$ and
$\operatorname{\operatorname{\textbf{pa}}}(X)=\operatorname{\operatorname{\textbf{pa}}}^{a}(X)$.

######  Definition 4.3 (A good collection of runs).

A collection of well-formed runs $\mathcal{A}$ is _good_ if it is (i)
alignable via an alignment spanning tree, (ii) every run is
$N_{\text{mp}}$-independent, and (iii) the collection covers every vertex in
$\vec{V}$.

The following is our main result on good collections of runs:

######  Theorem 4.4.

Given a graph with max degree $\Delta$ satisfying $n\geq N_{\text{mp}}\times
O(\Delta^{4})$, we can find a set of centers
$\vec{X}=\left\\{X_{1},\dotsc,X_{N_{\text{mp}}}\right\\}\subseteq\vec{V}$ of
size $N_{\text{mp}}$ and depth at most $3N_{\text{mp}}$, such that Algorithm 4
succeeds in finding a good collection of runs $\mathcal{A}$ of size
$O(2^{\Delta^{2}}n)$.

While any good collection of runs will suffice for our algorithm, Theorem 4.4
represents conditions under which we can provably obtain such a collection of
runs. In Appendix C.1, we give a good collection of runs for mixture of paths
which is more efficient than the one found by Algorithm 4.

###  4.1 A generic good collection of runs

To prove Theorem 4.4, we will sketch the collection of good runs, leaving some
details to Appendix B. To ensure alignment is possible, we will construct a
set of _central runs_ , $\mathcal{A}_{C}$ which we can align to each other and
which all other runs will be alignable to.

######  Definition 4.5 (Centers, Central Runs).

A set of vertices
$\vec{X}=\left\\{X_{1},\dotsc,X_{N_{\text{mp}}}\right\\}\subseteq\vec{V}$ will
be called centers if the Markov boundaries of the vertices in $\vec{X}$ are
disjoint. Given a set of centers $\vec{X}$, a run $a$ is called a central run
if $\vec{I}^{a}=\vec{X}$.

To build these central runs, we will start with a set of $N_{\text{mp}}$
vertices $\vec{X}=\left\\{X_{1},X_{2},\dotsc X_{N_{\text{mp}}}\right\\}$ with
_disjoint_ Markov boundaries and a maximum depzth of $3N_{\text{mb}}$, whose
existence is implied by our degree bounds (see Appendix B). An example of four
such vertices is given in Figure 2.

First, we fix a run $a_{0}$ with $\vec{I}^{a_{0}}=\vec{X}$ and
$\operatorname{\operatorname{\textbf{mb}}}^{a_{0}}(\vec{X})$ being chosen
arbitrarily where
$\operatorname{\operatorname{\textbf{MB}}}(\vec{X})\coloneqq\cup_{X_{i}\in\vec{X}}\operatorname{\operatorname{\textbf{MB}}}(X_{i})$.
We will refer to this assignment
$\operatorname{\operatorname{\textbf{mb}}}^{a_{0}}(\vec{X})$ as the _default_
assignment. Each run in $a\in\mathcal{A}_{C}$ will have the same independent
set $\vec{I}^{a}=\vec{X}$ and will agree with $a_{0}$ on the assignment to all
of the conditioning set other than the Markov boundary of some
$X_{i}\in\vec{X}$, i.e.

$f^{a}(V)=f^{a_{0}}(V)\;\;\forall
V\in\operatorname{\operatorname{\textbf{MB}}}(\vec{X})\setminus\operatorname{\operatorname{\textbf{MB}}}(X_{i}).$
(4)

The central runs will span over all assignments
$\operatorname{\operatorname{\textbf{mb}}}(X_{i})$ to
$\operatorname{\operatorname{\textbf{MB}}}(X_{i})$ for each $X_{i}\in\vec{X}$.
We’ll write each such run as
$a_{0}[\operatorname{\operatorname{\textbf{mb}}}(X_{i})]$.

######  Definition 4.6.

$\mathcal{A}_{C}\coloneqq\left\\{a_{0}\right\\}\cup\left\\{a_{0}[\operatorname{\operatorname{\textbf{mb}}}(X_{i})]:i\in[3k-3],\operatorname{\operatorname{\textbf{mb}}}(X_{i})\in\left\\{0,1\right\\}^{\operatorname{\operatorname{\textbf{MB}}}(X_{i})}\right\\}$.

See Figure 4 for an example of a set of central runs and a visualization of
how they are alignable.

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$0$X_{1}$00$X_{2}$0

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$1$X_{1}$00$X_{2}$0

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$1$X_{1}$10$X_{2}$0

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$0$X_{1}$10$X_{2}$0

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$0$X_{1}$01$X_{2}$0

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$0$X_{1}$01$X_{2}$1

$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$$\operatorname{\operatorname{\textbf{MB}}}(X_{2})$0$X_{1}$00$X_{2}$1

Aligned at $X_{2}$Aligned at $X_{2}$Aligned at $X_{2}$Aligned at
$X_{1}$Aligned at $X_{1}$Aligned at $X_{1}$Default Assignment Run $a_{0}$

Figure 4: An alignment spanning tree of the default assignment $a_{0}$
($\operatorname{\operatorname{\textbf{COND}}}^{a_{0}}$ arbitrarily assigns all
Markov boundaries to $0$) and six other central runs. The runs on the left
cover all possible assignments to
$\operatorname{\operatorname{\textbf{MB}}}(X_{2})\in\left\\{(0,0),(0,1),(1,0)\right\\}$,
while maintaining the default assignment to
$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$ to allow alignment with
$a_{0}$. The right runs similarly cover all possible assignments to
$\operatorname{\operatorname{\textbf{MB}}}(X_{1})$, aligned at $X_{2}$.

The central runs provide a backbone for easily guaranteeing alignment. The
runs in $\mathcal{A}_{Y}$ made up of the following two types of perturbations
to the independent set (with $\operatorname{\operatorname{\textbf{COND}}}^{a}$
always defined as the union of the Markov boundaries of the independent set,
as in Definition 2.1):

  1. 1.

For each $Y\in\operatorname{\operatorname{\textbf{MB}}}(X_{i})$ for some
$X_{i}\in\vec{X}$, we exclude $X_{i}$ from the independent set to form
$\vec{I}^{a_{Y}}=\vec{X}\cup\\{Y\\}\setminus\\{X_{i}\\}$.999This is a well-
formed run since $Y\in\operatorname{\operatorname{\textbf{MB}}}(X_{i})\implies
X_{j}\notin\operatorname{\operatorname{\textbf{MB}}}(Y)$ for any $j\neq i$ by
Observation 1.4.

  2. 2.

For each
$Y\notin\operatorname{\operatorname{\textbf{MB}}}(\vec{X})\cap\vec{X}$,
$\vec{I}^{a}=\vec{X}\cup\\{Y\\}$.

For either independence set we will form
$2^{\mathopen{|}\operatorname{\operatorname{\textbf{PA}}}(Y)\mathclose{|}}$
runs each associated with a single assignment to
$\operatorname{\operatorname{\textbf{pa}}}^{a}(Y)$, with the remaining
variables in
$\operatorname{\operatorname{\textbf{COND}}}^{a}\cap\operatorname{\operatorname{\textbf{COND}}}^{a_{0}}$
conditioned on their defaults given by $f^{a_{0}}$. Any other assignments to
variables in $\operatorname{\operatorname{\textbf{COND}}}^{a}$ can be chosen
arbitrarily. The pseudocode for this construction is in Appendix B, as well as
justification for why our degree bounds imply that $N_{\text{mp}}$ disjoint
Markov boundaries can be found.

###  4.2 Limiting the depth of unzipping

As currently given, our algorithm may require Bayesian unzipping parameters up
to the depth of the graph. We can bound accumulated errors from this process
by limiting the depth of the vertices that need to be unzipped.

Recall that the goal of the conditioning set of each run is to $d$-separate
each of the vertices in the independent set. For a topological ordering on the
independence set, notice that we need not condition on the descendants of the
deepest vertices in order to $d$-separate them from the others. Conveniently,
avoiding conditioning on these vertices descendants leaves the output of the
$k$-MixProd oracle in the desired form. We call these deepest vertices
“bottom” vertices.

######  Definition 4.7 (Bottom vertices in a run).

Given vertices $\vec{I}$, we’ll define the set of bottom vertices of the run
to be the subset
$\operatorname{\operatorname{\textbf{BOT}}}(\vec{I})\subseteq\vec{I}$ of
vertices with maximal depth among the vertices in $\vec{I}$. That is
$d(B)=\max_{I\in\vec{I}}d(I)$ for all
$B\in\operatorname{\operatorname{\textbf{BOT}}}(\vec{I})$.

We can now update the conditioning sets for our definition of runs:

$\operatorname{\operatorname{\textbf{COND}}}^{a}\coloneqq\bigcup_{I\in\vec{I}^{a}\setminus\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})}\operatorname{\operatorname{\textbf{MB}}}(I)\bigcup_{B\in\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})}\operatorname{\operatorname{\textbf{PA}}}(B)$
(5)

We append two additional requirements for a good collection of runs
(Definition 4.3).

  * •

no vertex appears both as a bottom vertex and a non-bottom vertex, and

  * •

every non-bottom vertex has depth at most $3N_{\text{mp}}$.

Note that because we only need independent sets of size $N_{\text{mp}}$, it is
trivial to limit the depth of our non-bottom vertices to $3N_{\text{mp}}$.

##  5 Conclusion

We have developed the first algorithm for identifying the parameters of
$k$-MixBND mixtures. This algorithm allows us to access the probability
distributions within each source - equivalent to the probability distribution
conditioned on a universal and unobserved confounder. With access to this
conditional distribution, the confounding of $U$ can be adjusted for, opening
up the opportunity for causal inference despite universal confounding.

The algorithm presented here is intended as an identifiability result.
Instead, we hope this algorithm and framework can serve as a springboard for
understanding how solutions to the $k$-MixProd and $k$-MixBND problems are
intimately related.

The alignment process is highly nontrivial and a likely reason why papers such
as Anandkumar et al. (2012a) made crude assumptions (such as a conveniently
independent variable) to simplify this process. The formal development of a
notion of a run, while tedious, will allow for further improvements to give
better “good sets of runs.” Graph-specific sets of runs can be optimized
further, as demonstrated in Appendix C.1.

## References

  * Anandkumar et al. (2010) A. Anandkumar, V. Tan, and A. Willsky.  High dimensional structure learning of ising models on sparse random graphs.  2010\.
  * Anandkumar et al. (2012a) A. Anandkumar, D. Hsu, F. Huang, and S. M. Kakade.  Learning high-dimensional mixtures of graphical models.  _arXiv preprint arXiv:1203.0697_ , 2012a.
  * Anandkumar et al. (2012b) A. Anandkumar, D. J. Hsu, and S. M. Kakade.  A method of moments for mixture models and hidden Markov models.  In _Proc. 25th Ann. Conf. on Learning Theory - COLT_ , volume 23 of _JMLR Proceedings_ , pages 33.1–33.34, 2012b.  URL http://proceedings.mlr.press/v23/anandkumar12/anandkumar12.pdf.
  * Batu et al. (2004) T. Batu, S. Guha, and S. Kannan.  Inferring mixtures of Markov chains.  In _Proc. 17th Conf. on Learning Theory_ , pages 186–199, 2004.  10.1007/978-3-540-27819-1_13.
  * Chaudhuri and Rao (2008) K. Chaudhuri and S. Rao.  Learning mixtures of product distributions using correlations and independence.  In _Proc. 21st Ann. Conf. on Learning Theory - COLT_ , pages 9–20. Omnipress, 2008.  URL http://colt2008.cs.helsinki.fi/papers/7-Chaudhuri.pdf.
  * Chen and Moitra (2019) S. Chen and A. Moitra.  Beyond the low-degree algorithm: mixtures of subcubes and their applications.  In _Proc. 51st Ann. ACM Symp. on Theory of Computing_ , pages 869–880, 2019.  10.1145/3313276.3316375.
  * Cryan et al. (2001) M. Cryan, L. Goldberg, and P. Goldberg.  Evolutionary trees can be learned in polynomial time in the two state general Markov model.  _SIAM J. Comput._ , 31(2):375–397, 2001.  10.1137/S0097539798342496.
  * E. S. Allman (2009) J. A. Rhodes E. S. Allman, C. Matias.  Identifiability of parameters in latent structure models with many observed variables.  _Ann. Statist._ , 37(6A):3099–3132, 2009.  10.1214/09-AOS689.
  * Everitt and Hand (1981) B. S. Everitt and D. J. Hand.  Mixtures of discrete distributions.  In _Finite Mixture Distributions_ , pages 89–105. Springer Netherlands, Dordrecht, 1981.
  * Feldman et al. (2008) J. Feldman, R. O’Donnell, and R. A. Servedio.  Learning mixtures of product distributions over discrete domains.  _SIAM J. Comput._ , 37(5):1536–1564, 2008.  10.1137/060670705.
  * Freund and Mansour (1999) Y. Freund and Y. Mansour.  Estimating a mixture of two product distributions.  In _Proc. 12th Ann. Conf. on Computational Learning Theory_ , pages 53–62, July 1999.  10.1145/307400.307412.
  * Glymour et al. (2019a) C. Glymour, K. Zhang, and P. Spirtes.  Review of causal discovery methods based on graphical models.  _Frontiers in Genetics_ , 10, 2019a.  ISSN 1664-8021.  10.3389/fgene.2019.00524.  URL https://www.frontiersin.org/article/10.3389/fgene.2019.00524.
  * Glymour et al. (2019b) C. Glymour, K. Zhang, and P. Spirtes.  Review of causal discovery methods based on graphical models.  _Frontiers in Genetics_ , 10:524, 2019b.  10.3389/fgene.2019.00524.
  * Gordon and Schulman (2022) S. L. Gordon and L. J. Schulman.  Hadamard extensions and the identification of mixtures of product distributions.  _IEEE Transactions on Information Theory_ , 2022.  to appear.
  * Gordon et al. (2021) S. L. Gordon, B. Mazaheri, Y. Rabani, and L. J. Schulman.  Source identification for mixtures of product distributions.  In _Proc. 34th Ann. Conf. on Learning Theory - COLT_ , volume 134 of _Proc. Machine Learning Research_ , pages 2193–2216. PMLR, 2021\.  URL http://proceedings.mlr.press/v134/gordon21a.html.
  * Gupta et al. (2016) R. Gupta, R. Kumar, and S. Vassilvitskii.  On mixtures of Markov chains.  In _Advances in Neural Information Processing Systems_ , volume 29, 2016.  URL https://proceedings.neurips.cc/paper/2016/file/8b5700012be65c9da25f49408d959ca0-Paper.pdf.
  * Heckerman (2018) D. Heckerman.  Accounting for hidden common causes when inferring cause and effect from observational data.  (NIPS 2017 causal inference workshop), 2018.  URL https://arxiv.org/abs/1801.00727.
  * Hsu et al. (2012) D. Hsu, S. M. Kakade, and T. Zhang.  A spectral algorithm for learning hidden Markov models.  _J. Comput. Syst. Sci._ , 78(5):1460–1480, September 2012.  10.1016/j.jcss.2011.12.025.
  * Huang and Valtorta (2008) Y. Huang and M. Valtorta.  On the completeness of an identifiability algorithm for semi-Markovian models.  _Ann. Math. Artif. Intell._ , 54(4):363–408, December 2008.  /10.1007/s10472-008-9101-x.
  * Kearns et al. (1994) M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie.  On the learnability of discrete distributions.  In _Proc. 26th Ann. ACM Symp. on Theory of Computing_ , pages 273–282, 1994.  10.1145/195058.195155.
  * Kivva et al. (2021) Bohdan Kivva, Goutham Rajendran, Pradeep Kumar Ravikumar, and Bryon Aragam.  Learning latent causal graphs via mixture oracles.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=f9mSLa07Ncc.
  * Koller and Friedman (2009) D. Koller and N. Friedman.  _Probabilistic Graphical Models: Principles and Techniques_.  MIT Press, 2009.
  * Kruskal (1976) Joseph B Kruskal.  More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling.  _Psychometrika_ , 41(3):281–293, 1976.
  * Kruskal (1977) Joseph B Kruskal.  Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics.  _Linear algebra and its applications_ , 18(2):95–138, 1977.
  * Kumar and Sinha (2021) A. Kumar and G. Sinha.  Disentangling mixtures of unknown causal interventions.  In C. de Campos and M. H. Maathuis, editors, _Proc. Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ , volume 161 of _Proc. Machine Learning Research_ , pages 2093–2102. PMLR, 27–30 Jul 2021.  URL https://proceedings.mlr.press/v161/kumar21a.html.
  * Kuroki and Pearl (2014) M. Kuroki and J. Pearl.  Measurement bias and effect restoration in causal inference.  _Biometrika_ , 101(2):423–437, 2014.  10.1093/biomet/ast066.
  * Lindsay (1995) B. G. Lindsay.  _Mixture models: theory, geometry and applications_.  1995\.
  * Mazaheri et al. (2023) Bijan Mazaheri, Atalanti Mastakouri, Dominik Janzing, and Mila Hardt.  Causal information splitting: Engineering proxy features for robustness to distribution shifts, 2023.
  * McLachlan et al. (2019) G. J. McLachlan, S. X. Lee, and S. I. Rathnayake.  Finite mixture models.  _Annual Review of Statistics and Its Application_ , 6(1):355–378, 2019.  10.1146/annurev-statistics-031017-100325.
  * Miao et al. (2018) W. Miao, Z. Geng, and E. T. Tchetgen.  Identifying causal effects with proxy variables of an unmeasured confounder.  _Biometrika_ , 105(4):987–993, 2018.  10.1093/biomet/asy038.
  * Newcomb (1886) S. Newcomb.  A generalized theory of the combination of observations so as to obtain the best result.  _American Journal of Mathematics_ , 8(4):343–366, 1886.
  * Ogburn et al. (2019) Elizabeth L Ogburn, Ilya Shpitser, and Eric J Tchetgen Tchetgen.  Comment on “blessings of multiple causes”.  _Journal of the American Statistical Association_ , 114(528):1611–1615, 2019.
  * Pearl (1985) J. Pearl.  Bayesian networks: A model of self-activated memory for evidential reasoning.  Technical Report CSD-850021, R-43, UCLA Computer Science Department, June 1985.
  * Pearl (2009) J. Pearl.  _Causality_.  Cambridge, 2nd edition, 2009.
  * Pearl (2014) J. Pearl.  _Probabilistic reasoning in intelligent systems: networks of plausible inference_.  Elsevier, 2014.
  * Pearson (1894) K. Pearson.  Contributions to the mathematical theory of evolution III.  _Philosophical Transactions of the Royal Society of London (A.)_ , 185:71–110, 1894.
  * Peters et al. (2017) J. Peters, D. Janzing, and B. Schölkopf.  _Elements of Causal Inference_.  MIT Press, 2017.
  * Ranganath and Perotte (2018) R. Ranganath and A. Perotte.  Multiple causal inference with latent confounding.  2018\.  URL https://arxiv.org/abs/1805.08273.
  * Sharan et al. (2017) V. Sharan, S. M. Kakade, P. Liang, and G. Valiant.  Learning overcomplete HMMs.  In _Advances in Neural Information Processing Systems_ , pages 940–949, 2017.  URL https://arxiv.org/abs/1711.02309.
  * Shpitser and Pearl (2006) I. Shpitser and J. Pearl.  Identification of joint interventional distributions in recursive semi-Markovian causal models.  In _Proc. 20th AAAI Conference on Artifical Intelligence_ , pages 1219–1226, 2006.  10.5555/1597348.1597382.
  * Spirtes et al. (2000a) P. Spirtes, C. Glymour, and R. Scheines.  _Causation, Prediction and Search_.  MIT Press, second edition, 2000a.
  * Spirtes et al. (2000b) P. Spirtes, C. Glymour, R. Scheines, S. Kauffman, V. Aimale, and F. Wimberly.  Constructing Bayesian network models of gene expression networks from microarray data.  2000b.
  * Tahmasebi et al. (2018) B. Tahmasebi, S. A. Motahari, and M. A. Maddah-Ali.  On the identifiability of finite mixtures of finite product measures.  (Also in “On the identifiability of parameters in the population stratification problem: A worst-case analysis,” Proc. ISIT’18 pp. 1051-1055), 2018.  URL https://arxiv.org/abs/1807.05444.
  * Thiesson et al. (1998) B. Thiesson, C. Meek, D. M. Chickering, and D. Heckerman.  Learning mixtures of DAG models.  In _Proc. 14th Conf. on Uncertainty in Artificial Intelligence_ , page 504–513, 1998.  10.5555/2074094.2074154.
  * Titterington et al. (1985) D. M. Titterington, A. F. M. Smith, and U. E. Makov.  _Statistical Analysis of Finite Mixture Distributions_.  John Wiley and Sons, Inc., 1985.
  * Wang and Blei (2019) Y. Wang and D. M. Blei.  The blessings of multiple causes.  _Journal of the American Statistical Association_ , 114(528):1574–1596, 2019.  10.1080/01621459.2019.1686987.

##  Appendix A $k$-MixBND algorithm pseudocode

Input: A set of runs $\mathcal{A}=\\{a_{0},\ldots,a_{\ell}\\}$ with outputs
$M^{a},\pi^{a}$ for each $a\in\mathcal{A}$. In addition, we have a spanning
tree $\mathcal{T}=(\mathcal{A},\vec{E})$ and alignment variables
$\operatorname{\operatorname{\textbf{AV}}}(a_{i},a_{j})\subseteq\vec{I}^{a^{(i)}}\cap\vec{I}^{a^{(j)}}$.

Output: $\mathcal{P}^{a}_{u}(\vec{I}^{a})$ and $\mathcal{P}^{a}(u)$ for each
$a\in\mathcal{A}$ and $u\in[k]$.

Let $\mathcal{P}^{a_{0}}(u)\leftarrow\pi^{a_{0}}_{u}$ and
$\mathcal{P}^{a_{0}}_{u}(\vec{I}^{a_{0}})\leftarrow M^{a_{0}}_{-,u}$ for an
arbitrary choice of $a_{0}$

for  _each edge $(a_{i},a_{j})$ along a breadth first traversal of
$\mathcal{T}$ from $a_{0}$_ do

Choose some
$X_{\operatorname{\operatorname{\textbf{AV}}}}\in\operatorname{\operatorname{\textbf{AV}}}(a_{i},a_{j})$.

Let $q,r$ give the indices for the alignment variable, i.e.
$X_{\operatorname{\operatorname{\textbf{AV}}}}=X^{a_{i}}_{q}$ and
$X_{\operatorname{\operatorname{\textbf{AV}}}}=X^{a_{j}}_{r}$.

Find $\sigma$, the permutation on the sources that minimizes
$\left\|M^{a_{i}}_{q,-}-\sigma M^{a_{j}}_{r,-}\right\|_{\infty}$.

Assign $\mathcal{P}^{a_{j}}(U)\leftarrow\sigma\pi^{a_{j}}$ and
$\mathcal{P}^{a_{j}}_{u}(\vec{I}^{a})\leftarrow\sigma M^{a_{j}}$.

end for

Algorithm 1 Alignment

Input: A collection of runs $\mathcal{A}$ of size at most $2^{O(\Delta^{2})}$
and their aligned output. For each $V_{i}$ and assignment to its parents
$\operatorname{\operatorname{\textbf{pa}}}(V_{i})$ there must be some run with
$V_{i}$ in its independent set with parents conditioned to
$\operatorname{\operatorname{\textbf{pa}}}(V_{i})$.

Output:
$\widetilde{\mathcal{P}}_{u}(Y\mid\operatorname{\operatorname{\textbf{PA}}}(Y))$

Fix a topological ordering on the vertices in $\vec{V}$, $\left\langle
X_{1},X_{2},\dotsc,X_{n}\right\rangle$; for  _$i=n,n-1,\dotsc,1$_ do

for  _each assignment $\operatorname{\operatorname{\textbf{pa}}}(X_{i})$ to
$\operatorname{\operatorname{\textbf{PA}}}(X_{i})$_ do

Let $a$ be a run in $\mathcal{A}$ with
$\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i})=\operatorname{\operatorname{\textbf{pa}}}(X_{i})$.

for  _$u=1,\dotsc,k$_ do

for  _$b=0,1$_ do

if  _$X_{i}$ is a bottom vertex_ then

Set
$\widetilde{\mathcal{P}}_{u}(x_{i}^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i}))\leftarrow\widetilde{\mathcal{P}}_{u}^{a}(x_{i}^{b})$.

else

Set
$\widetilde{\mathcal{P}}_{u}(x_{i}^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(X_{i}))\leftarrow\frac{\widetilde{\mathcal{P}}_{u}^{a}(x_{i}^{b})\widetilde{\mathcal{P}}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(X_{i})\mid\operatorname{\textbf{top}}^{a}(X_{i}),x_{i}^{1-b})}{\widetilde{\mathcal{P}}_{u}^{a}(x_{i}^{b})\widetilde{\mathcal{P}}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(X_{i})\mid\operatorname{\textbf{top}}^{a}(X_{i}),x_{i}^{1-b})+\widetilde{\mathcal{P}}_{u}^{a}(x_{i}^{1-b})\widetilde{\mathcal{P}}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(X_{i})\mid\operatorname{\textbf{top}}^{a}(X_{i}),x_{i}^{b})}$;

end if

end for

end for

end for

end for

Algorithm 2 Bayesian Unzipping

Input: A good collection of runs $\mathcal{A}$ of size at most
$2^{O(\Delta^{2})}$.

Output:
$\widetilde{\mathcal{P}}_{u}(Y\mid\operatorname{\operatorname{\textbf{PA}}}(Y))$
and $\widetilde{\mathcal{P}}(U)$.

Estimate $\widetilde{\mathcal{P}}^{a}(\vec{I}^{a})$ for all runs
$a\in\mathcal{A}$.

for  _each run $a\in\mathcal{A}$_ do

Set
$\left(M^{a},\pi^{a}\right)\leftarrow\textsc{LearnProductMixture}(\mathcal{P}^{a}(\vec{I}^{a}))$

end for

Run Algorithm 1 to align the sources in the output of all the runs in
$\mathcal{A}$.

Run Algorithm 2 to unzip the parameters.

Fix any run $a\in\mathcal{A}$.

for  _$u=1,\ldots,k$_ do

Set
$\widetilde{\mathcal{P}}(u)\leftarrow\frac{\widetilde{\mathcal{P}}(u\mid\operatorname{\operatorname{\textbf{cond}}}^{a})\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a})}{\widetilde{\mathcal{P}}_{u}(\operatorname{\operatorname{\textbf{cond}}}^{a})}$.

end for

Algorithm 3 The $k$-MixBND algorithm

##  Appendix B Finding good collections of runs

In this section we prove Theorem 4.4 and give a few different sufficient
conditions for the existence of a good collection of runs.

###  B.1 Constructing a good collection of runs from $N_{\text{mp}}$ centers

One sufficient condition for the existence of a good collection of runs is the
presence of $N_{\text{mp}}$ variables with disjoint Markov boundaries. We will
now present a good collection of runs for this case.

######  Lemma B.1.

Given a set
$\vec{X}=\left\\{X_{1},\dotsc,X_{N_{\text{mp}}}\right\\}\subseteq\vec{V}$ of
$N_{\text{mp}}$ variables with depth at most $3N_{\text{mp}}$ and disjoint
Markov boundaries, Algorithm 4 finds a good collection of runs $\mathcal{A}$,
satisfying $\left|\mathcal{A}\right|=O(2^{\gamma}n)$ where
$\gamma=\max_{V\in\vec{V}}\left|\operatorname{\operatorname{\textbf{MB}}}(V)\right|$,.

Input: Vertices
$\vec{X}=\left\\{X_{1},\dotsc,X_{3k-3}\right\\}\subseteq\vec{V}$ having
disjoint Markov boundaries with maximum depth $3N_{\text{mp}}$.

Output: A good collection of runs $\mathcal{A}$.

Let $a_{0}$ be a run with
$\vec{I}^{a_{0}}=\left\\{X_{1},\dotsc,X_{3k-3}\right\\}$ and
$\operatorname{\operatorname{\textbf{COND}}}^{a_{0}}$ chosen arbitrarily.

Set $\mathcal{A}\leftarrow\left\\{a_{0}\right\\}$.

for  _$i=1,\dotsc,3k-3$_ do

$\mathcal{A}\leftarrow\mathcal{A}\cup\left\\{a_{0}[\operatorname{\operatorname{\textbf{mb}}}(X_{i})]:\operatorname{\operatorname{\textbf{mb}}}(X_{i})\in\left\\{0,1\right\\}^{\operatorname{\operatorname{\textbf{MB}}}(X_{i})}\right\\}$.

for  _$Y\in\vec{V}\setminus\vec{X}$_ do

if  _$Y\in\operatorname{\operatorname{\textbf{MB}}}(X)$ for some
$X\in\mathcal{X}$_ then

$\vec{I}^{a}\leftarrow\vec{X}\cup\\{Y\\}\setminus\\{X_{i}\\}$

end if

else

$\vec{I}^{a}\leftarrow\vec{X}\cup\\{Y\\}$

end if

for
_$\operatorname{\operatorname{\textbf{pa}}}(Y)\in\\{0,1\\}^{\mathopen{|}\operatorname{\operatorname{\textbf{PA}}}(Y)\mathclose{|}}$_
do

if  _$Y\in\operatorname{\operatorname{\textbf{AN}}}(\vec{I}^{a}-Y)$_ then

$\operatorname{\operatorname{\textbf{COND}}}^{a}\leftarrow\operatorname{\operatorname{\textbf{MB}}}(\vec{I}^{a})$

end if

else

$\operatorname{\operatorname{\textbf{COND}}}^{a}\leftarrow\operatorname{\operatorname{\textbf{MB}}}(\vec{I}^{a}\setminus\\{Y\\})\cup\operatorname{\operatorname{\textbf{PA}}}(Y)$

end if

$\operatorname{\operatorname{\textbf{COND}}}^{a}\leftarrow\operatorname{\operatorname{\textbf{MB}}}(\vec{I}^{a})$

$f^{a}(\operatorname{\operatorname{\textbf{PA}}}(Y))\leftarrow\operatorname{\operatorname{\textbf{pa}}}(Y)$

$\mathsf{Defaults}\leftarrow\operatorname{\operatorname{\textbf{COND}}}^{a_{0}}\cap\operatorname{\operatorname{\textbf{COND}}}^{a}\setminus\operatorname{\operatorname{\textbf{PA}}}(Y)$

$f^{a}(\mathsf{Defaults})\leftarrow f^{a_{0}}(\mathsf{Defaults})$

$f^{a}(\operatorname{\operatorname{\textbf{COND}}}^{a}\setminus\operatorname{\operatorname{\textbf{COND}}}^{a_{0}}\setminus\operatorname{\operatorname{\textbf{PA}}}(Y))$
are chosen arbitrarily.

$\mathcal{A}\leftarrow\mathcal{A}\cup\\{a\\}$, where $a$ is given by
$a=(\vec{I}^{a},f^{a})$.

end for

end for

end for

Algorithm 4 Building a good collection of runs

######  Claim 1.

By construction, $\mathcal{A}_{C}$ covers $\vec{X}$ and is alignable.

######  Claim 2.

$A_{Y}$ covers $\vec{V}\setminus\vec{X}$ and each run in $\mathcal{A}_{Y}$ can
be aligned with some run in $\mathcal{A}_{C}$.

######  Proof B.2.

The fact that $\mathcal{A}_{Y}$ covers $\vec{V}\setminus\vec{X}$ follows
immediately from $\mathcal{A}_{Y}$ containing a run assigning for independent
variable $Y\in\vec{V}\setminus\vec{X}$ each possible assignment
$\operatorname{\operatorname{\textbf{pa}}}(Y)$. Fix any run
$a\in\mathcal{A}_{Y}$ with $\vec{I}^{a}=\vec{X}-X_{i}+Y$ or
$\vec{I}^{a}=\vec{X}+Y$ depending on whether $Y$ overlaps with
$\operatorname{\operatorname{\textbf{MB}}}(\mathcal{X})$. Now if
$\operatorname{\operatorname{\textbf{MB}}}(Y)\cap\operatorname{\operatorname{\textbf{MB}}}(X_{j})=\emptyset$
for any $j\neq i$, $a$ and $a_{0}$ are aligned at $X_{j}$. If instead
$\operatorname{\operatorname{\textbf{MB}}}(Y)\cap\operatorname{\operatorname{\textbf{MB}}}(X_{j})\neq\emptyset$
for all $j\neq i$, pick any $j$ and consider the central run
$a_{0}[\operatorname{\operatorname{\textbf{mb}}}^{a}(X_{j})]\in\mathcal{A}_{C}$.
Clearly, $a$ and $a_{0}[\operatorname{\operatorname{\textbf{mb}}}^{a}(X_{j})]$
are aligned at $X_{j}$. In either case, we’ve aligned $a$ to a run in
$\mathcal{A}_{C}$.

######  Claim 3.

Every run $a\in\mathcal{A}$ is at least $N_{\text{mp}}$-independent.

######  Proof B.3 (Proof of Lemma B.1).

This follows immediately from Claims 1, 2, and 3

###  B.2 Degree bounds

We can ensure that $N_{\text{mp}}$ centers can be found on certain degree-
bounded graphs, which in turn bound $\gamma$. Let $\Delta_{\text{in}}$ upper
bound on the in-degree of any vertex in $\mathcal{G}$ and let
$\Delta_{\text{out}}$ upper bound the out-degree. Then

$\gamma\leq\Delta_{\text{in}}+\Delta_{\text{out}}+\Delta_{\text{out}}(\Delta_{\text{in}}-1)=\Delta_{\text{in}}+\Delta_{\text{out}}\Delta_{\text{in}}.$

If we have a bound $\Delta$ on the degree of the undirected skeleton of
$\mathcal{G}$, we get that

$\gamma\leq\Delta(\Delta-1)=\Delta^{2}-\Delta.$

######  Corollary B.4.

If either of the following conditions hold, we can find $N_{\text{mp}}$
centers for $\mathcal{G}$ with depth at most $3N_{\text{mp}}$:

  1. 1.

$n\geq
N_{\text{mp}}(\Delta_{\text{in}}^{2}+2\Delta_{\text{out}}\Delta_{\text{in}}+\Delta_{\text{out}}^{2}\Delta_{\text{in}}^{2}-\Delta_{\text{in}}-\Delta_{\text{out}}+1)=N_{\text{mp}}\cdot
O(\Delta_{\text{out}}^{2}\Delta_{\text{in}}^{2})$.

  2. 2.

$n\geq N_{\text{mp}}(\Delta^{4}-2\Delta^{3}+\Delta+1)=N_{\text{mp}}\cdot
O(\Delta^{4})$.

######  Proof B.5 (Proof of Lemma 4.4).

This follows immediately from Corollary B.4 and Lemma B.1.

##  Appendix C Analyzing Bayesian Unzipping

In this section, we will analyze the numerical stability of the Bayesian
unzipping process.

######  Lemma C.1.

Let $a$ be a run with $Y\in\vec{I}^{a}$. Then we can compute
$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
for $b\in\left\\{0,1\right\\}$ as follows:

  1. 1.

If $Y\in\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})$, then

$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))=\mathcal{P}_{u}^{a}(y^{b}).$

  2. 2.

If $Y\notin\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})$, then

$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(y))=\frac{\mathcal{P}_{u}^{a}(y^{b})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(y)\mid\operatorname{\textbf{top}}^{a}(y),y^{1-b})}{\mathcal{P}_{u}^{a}(y^{b})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(y)\mid\operatorname{\textbf{top}}^{a}(y),y^{1-b})+\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}(y)\mid\operatorname{\textbf{top}}^{a}(y),y^{b})}$
(6)

######  Proof C.2.

In the following we’ll fix
$\operatorname{\operatorname{\textbf{ch}}}^{a}\coloneqq\operatorname{\operatorname{\textbf{ch}}}^{a}(Y)$,
$\operatorname{\operatorname{\textbf{mb}}}^{a}\coloneqq\operatorname{\operatorname{\textbf{mb}}}^{a}(Y)$,
$\operatorname{\operatorname{\textbf{pa}}}^{a}\coloneqq\operatorname{\operatorname{\textbf{pa}}}^{a}(Y)$,
and
$\operatorname{\textbf{top}}^{a}\coloneqq\operatorname{\textbf{top}}^{a}(Y)$.
If $Y\in\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})$, then
$\mathcal{P}_{u}^{a}(y^{b})=\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$,
so the claim is trivially true. If
$Y\notin\operatorname{\operatorname{\textbf{BOT}}}(\vec{I}^{a})$, then

$\displaystyle\mathcal{P}_{u}^{a}(y^{b})=\mathcal{P}_{u}^{a}(y^{b}\mid\operatorname{\operatorname{\textbf{mb}}}^{a})=\frac{\mathcal{P}_{u}(y^{b},\operatorname{\operatorname{\textbf{mb}}}^{a})}{\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{mb}}}^{a})}=\frac{\mathcal{P}_{u}(y^{b},\operatorname{\operatorname{\textbf{mb}}}^{a})}{\sum_{b^{\prime}=0,1}\widetilde{\mathcal{P}}_{u}(y^{b^{\prime}},\operatorname{\operatorname{\textbf{mb}}}^{a})}$

and we can expand
$\mathcal{P}_{u}(y^{b},\operatorname{\operatorname{\textbf{mb}}}^{a})$ as

$\mathcal{P}_{u}(y^{b},\operatorname{\operatorname{\textbf{mb}}}^{a})=\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})\mathcal{P}_{u}(\operatorname{\textbf{top}}^{a}).$

Substituting this back into the preceding equation, we obtain

$\displaystyle\mathcal{P}_{u}^{a}(y^{b})$
$\displaystyle=\frac{\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})\mathcal{P}_{u}(\operatorname{\textbf{top}}^{a})}{\sum_{b^{\prime}\in\left\\{0,1\right\\}}\mathcal{P}_{u}(y^{b^{\prime}}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b^{\prime}})\mathcal{P}_{u}(\operatorname{\textbf{top}}^{a})}$
$\displaystyle=\frac{\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})}{\sum_{b^{\prime}\in\left\\{0,1\right\\}}\mathcal{P}_{u}(y^{b^{\prime}}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a}y^{b^{\prime}})}.$

We now multiply both sides by the denominator (which is non-zero since all
terms are strictly positive by assumption) and then simplify to obtain

$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\left(\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})\right)+\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})\left(-\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{1-b})\right)=0.$

When augmented with the equation

$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})+\mathcal{P}_{u}(y^{1-b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})=1$

we have a system of two equations in
$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}),\mathcal{P}_{u}(y^{1-b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})$
which is non-singular whenever

$\left(\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})\right)\neq\left(-\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}_{u}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{1-b})\right).$

Since all probabilities occurring are strictly positive, this will always be
the case and we can solve the system for
$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})$. The
resulting equation is

$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a})=\frac{\mathcal{P}_{u}^{a}(y^{b})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{1-b})}{\mathcal{P}_{u}^{a}(y^{b})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{1-b})+\mathcal{P}_{u}^{a}(y^{1-b})\mathcal{P}(\operatorname{\operatorname{\textbf{ch}}}^{a}\mid\operatorname{\textbf{top}}^{a},y^{b})},$

proving the claim.

The following standard inequalities will be useful throughout the analysis:

###### Observation C.3

$\displaystyle\frac{1+x}{1-x}$ $\displaystyle\leq 1+3x\quad\text{and}$
$\displaystyle\quad 1-3x$ $\displaystyle\leq\frac{1-x}{1+x}\quad$ for
$x\in(0,1/4)$; $\displaystyle 1-2rx$
$\displaystyle\leq(1-x)^{r}\quad\text{and}$ $\displaystyle\quad(1+x)^{r}$
$\displaystyle\leq 1+2rx\quad$ for $x\in(0,1),r\geq 1,rx\leq 1$.

######  Lemma C.4.

Given access to
$\left\\{\widetilde{\mathcal{P}}_{u}^{a}(Y)\right\\}_{a\in\mathcal{A},j\in[k]}$
for a good collection of runs $\mathcal{A}$ from a distribution $\mathcal{P}$
satisfying
$\left|\widetilde{\mathcal{P}}_{u}^{a}(y^{b})-\mathcal{P}_{u}^{a}(y^{b})\right|/\mathcal{P}_{u}^{a}(y^{b})\leq\varepsilon$
for all $Y\in\vec{V}$, $b\in\left\\{0,1\right\\}$, $u\in[k]$ for $\varepsilon$
sufficiently small (and the estimated probabilities used as input to
$k$-MixProd oracles), the procedure in Algorithm 2 will output
$\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{PA}}}(Y))$
and $\widetilde{\mathcal{P}}(u)$ for all $Y\in\vec{V}$,
$b\in\left\\{0,1\right\\},u\in[k]$ satisfying

$\frac{\left|\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))-\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))\right|}{\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))}\leq(6(\Delta+1))^{\ell}\varepsilon$

where $\ell$ is the distance from $Y$ to the nearest bottom vertex if $Y$
doesn’t appear as a bottom vertex and is $0$ if $Y$ is a bottom vertex.

######  Proof C.5.

We fix a topological ordering on $\mathcal{V}$, let’s say
$X_{1},X_{2},\dotsc,X_{n}$. Now starting with the last vertex in topological
order, $X_{n}$, and proceeding in decreasing order, we’ll compute
$\widetilde{\mathcal{P}}_{u}(X_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(X_{i}))$.
For bottom vertices, we set
$\widetilde{\mathcal{P}}_{u}(x_{i}^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(X_{i}))=\widetilde{\mathcal{P}}_{u}^{a}(x_{i}^{b})$
for some run $a$ with
$\operatorname{\operatorname{\textbf{pa}}}(X_{i})=\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i})$.
It immediately follows that
$P_{u}(X_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(X_{i}))$ satisfies
the desired relative error bound. Inductively, assume we’ve already computed
$\widetilde{\mathcal{P}}_{u}(V_{m}\mid\operatorname{\operatorname{\textbf{PA}}}(V_{m}))$
for all $m>i$ satisfying the stated bounds, and that we also have access to
$\widetilde{\mathcal{P}}^{a}_{u}(V_{i})=\widetilde{\mathcal{P}}_{u}(V_{i}\mid\operatorname{\operatorname{\textbf{COND}}}^{a})$
for a subset of the runs $a\in\mathcal{A}$ that cover $V_{i}$. To streamline
notation, let $Y\coloneqq V_{i}$. Now fix a run $a\in\mathcal{A}$ with
$Y\in\vec{I}^{a}$.

Now we can bound each term above and below using the inductive hypothesis to
get the desired result. In particular, we know that

$(1-\varepsilon)\mathcal{P}_{u}^{a}(y^{b})\leq\widetilde{\mathcal{P}}_{u}^{a}(y^{b})\leq(1+\varepsilon)\mathcal{P}_{u}^{a}(y^{b})$

for $b\in\left\\{0,1\right\\}$ and

$(1-(6(\Delta+1))^{\ell-1}\varepsilon)\mathcal{P}_{u}(v^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(v^{b}))\leq\widetilde{\mathcal{P}}_{u}(v^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(v^{b}))\leq(1+(6(\Delta+1))^{\ell-1}\varepsilon)\mathcal{P}_{u}(v^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(v^{b}))$

for all $V\in\operatorname{\operatorname{\textbf{CH}}}(Y)$ and
$b\in\left\\{0,1\right\\}$ which implies that both the numerator and
denominator of (6) are within a factor of
$(1\pm\varepsilon)(1\pm(6(\Delta+1))^{\ell-1}\varepsilon)^{\Delta}$ of the
correct value for those terms. It immediately follows that
$\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
is bounded by

$\displaystyle\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))\frac{1-\varepsilon}{1+\varepsilon}\left(\frac{1-(6(\Delta+1))^{\ell-1}\varepsilon}{1+(6(\Delta+1))^{\ell-1}\varepsilon}\right)$
$\displaystyle\leq\widetilde{\mathcal{P}}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
$\displaystyle\leq\mathcal{P}_{u}(y^{1}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))\frac{1+\varepsilon}{1-\varepsilon}\left(\frac{1+(6(\Delta+1))^{\ell-1}\varepsilon}{1-(6(\Delta+1))^{\ell-1}\varepsilon}\right).$

We now use the inequalities from Observation C.3 to simplify the bounds as
follows:

$\displaystyle\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))$
$\displaystyle\leq\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))\frac{1+\varepsilon}{1-\varepsilon}\left(\frac{1+(6(\Delta+1))^{\ell-1}\varepsilon}{1-(6(\Delta+1))^{\ell-1}\varepsilon}\right)^{\Delta}$
$\displaystyle\leq\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))(1+3\varepsilon)(1+3(6(\Delta+1))^{\ell-1}\varepsilon)^{\Delta}$
$\displaystyle\leq\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))(1+3(6(\Delta+1))^{\ell-1}\varepsilon)^{\Delta+1}$
$\displaystyle\leq\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))(1+2\cdot
3(\Delta+1)(6(\Delta+1))^{\ell-1}\varepsilon)$
$\displaystyle\leq\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}^{a}(Y))(1+(6(\Delta+1))^{\ell}\varepsilon).$

The lower bound is analogous.

######  Lemma C.6.

Given access to
$\left\\{\widetilde{\mathcal{P}}_{u}^{a}(Y)\right\\}_{a\in\mathcal{A},j\in[k]}$
for a good collection of runs $\mathcal{A}$ from a distribution $\mathcal{P}$
satisfying
$\left|\widetilde{\mathcal{P}}_{u}^{a}(y^{b})-\mathcal{P}_{u}^{a}(y^{b})\right|/\mathcal{P}_{u}^{a}(y^{b})\leq\varepsilon$
for all $Y\in\vec{I}^{a}$, $b\in\left\\{0,1\right\\}$, $u\in[k]$ for
$\varepsilon$ sufficiently small, the procedure in Algorithm 2 will output
$\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{PA}}}(Y))$
and $\widetilde{\mathcal{P}}(u)$ for all $Y\in\vec{V}$,
$b\in\left\\{0,1\right\\},u\in[k]$ satisfying

$\frac{\left|\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))-\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))\right|}{\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))}\leq(6(\Delta+1))^{3N_{\text{mp}}}\varepsilon$

and

$\frac{\left|\widetilde{\mathcal{P}}(u^{j})-\mathcal{P}(u^{j})\right|}{\mathcal{P}(u^{j})}\leq
5\Delta^{2}\varepsilon.$

Since
$\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y)),\mathcal{P}(u^{j})\leq
1$, we also have that

$\left|\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))-\mathcal{P}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))\right|\leq(6(\Delta+1))^{9k}\varepsilon\quad\text{and}\quad\left|\widetilde{\mathcal{P}}(u^{j})-\mathcal{P}(u^{j})\right|\leq
5\Delta^{2}\varepsilon.$

######  Proof C.7.

The error bound on
$\widetilde{\mathcal{P}}_{u}(y^{b}\mid\operatorname{\operatorname{\textbf{pa}}}(Y))$
follows from Lemma C.4 above and the depth bound of $9k$ on non-bottom
vertices.

For the error bound on $\widetilde{\mathcal{P}}(u^{j})$ we write

$\displaystyle\widetilde{\mathcal{P}}(u^{j})=\frac{\widetilde{\mathcal{P}}(u^{j}\mid\operatorname{\operatorname{\textbf{cond}}}^{a})\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a})}{\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})}$

and analyze each term separately. First, define
$Z\coloneqq\operatorname{\operatorname{\textbf{AN}}}(\operatorname{\operatorname{\textbf{COND}}}^{a})\setminus\operatorname{\operatorname{\textbf{COND}}}^{a}$
to be all ancestors of vertices conditioned upon in $a$ minus
$\operatorname{\operatorname{\textbf{COND}}}^{a}$. Fix a topological order on
the vertices in $Z\cup\operatorname{\operatorname{\textbf{COND}}}^{a}$,
$\left\langle X_{1},\dotsc,X_{m}\right\rangle$. We can write

$\displaystyle\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})=$
$\displaystyle\sum_{z\in\left\\{0,1\right\\}^{Z}}\prod_{i=1}^{m}\widetilde{\mathcal{P}}(z(X_{i})\mid
z(X_{1},\dotsc,X_{i-1}),\operatorname{\operatorname{\textbf{cond}}}^{a})$
$\displaystyle=$
$\displaystyle\sum_{z\in\left\\{0,1\right\\}^{Z}}\prod_{X_{i}\in
Z\cup\operatorname{\operatorname{\textbf{COND}}}^{a}}\widetilde{\mathcal{P}}(z(X_{i})\mid
z(\operatorname{\operatorname{\textbf{PA}}}(X_{i})),\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i}))$
$\displaystyle=$
$\displaystyle\sum_{z\in\left\\{0,1\right\\}^{Z}}\left(\prod_{X_{i}\in
Z}\widetilde{\mathcal{P}}(z(X_{i})\mid
z(\operatorname{\operatorname{\textbf{PA}}}(X_{i})),\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i}))\right)$
$\displaystyle\left(\prod_{X_{i}\in\operatorname{\operatorname{\textbf{COND}}}^{a}}\widetilde{\mathcal{P}}(z(X_{i})\mid
z(\operatorname{\operatorname{\textbf{PA}}}(X_{i})),\operatorname{\operatorname{\textbf{pa}}}^{a}(X_{i}))\right).$

Now let $C_{z}$ denote the value in the first grouped product for a given
$z\in\left\\{0,1\right\\}^{Z}$. Since
$\sum_{z\in\left\\{0,1\right\\}^{Z}}C_{z}=1$, we can bound the error in the
result by the error in the second grouped product:

$(1-\varepsilon)^{\left|\operatorname{\operatorname{\textbf{COND}}}^{a}\right|}\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq(1+\varepsilon)^{\left|\operatorname{\operatorname{\textbf{COND}}}^{a}\right|}\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j}).$

Finally using the bound
$\left|\operatorname{\operatorname{\textbf{COND}}}^{a}\right|<2\Delta^{2}$ and
the inequalities from Observation C.3 we obtain

$(1-2\Delta^{2}\varepsilon)\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq(1+2\Delta^{2}\varepsilon)\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j}).$

By assumption
$\widetilde{\mathcal{P}}(u^{j}\mid\operatorname{\operatorname{\textbf{cond}}}^{a})\in(1\pm\varepsilon)\mathcal{P}(u^{j}\mid\operatorname{\operatorname{\textbf{cond}}}^{a})$;
$\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a})$ is
also known up to multiplicative accuracy $\varepsilon$ since the sampling
needed to estimate the distributions that are input to $k$-MixProd oracles far
exceed that needed to get an $\varepsilon$ estimate of this quantity. Thus,
the resulting bound on $\widetilde{\mathcal{P}}(u^{j})$ is

$(1-2\Delta^{2}\varepsilon)(1-3\varepsilon)\mathcal{P}(u^{j})\leq\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq(1+2\Delta^{2}\varepsilon)(1+3\varepsilon)\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})$

which can be simplified to

$(1-2\Delta^{2}\varepsilon-3\varepsilon)\mathcal{P}(u^{j})\leq\widetilde{\mathcal{P}}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})\leq(1+2\Delta^{2}\varepsilon+3\varepsilon)\mathcal{P}(\operatorname{\operatorname{\textbf{cond}}}^{a}\mid
u^{j})$

using $(1-x)(1-y)\geq(1-x-y)$ for $x,y\in[0,1)$ and
$2\Delta^{2}\varepsilon+3\varepsilon\leq 5\Delta^{2}\varepsilon$ for
$\Delta\geq 1$.

###  C.1 Mixtures of paths

Special cases do not require the condition of $N_{\text{mp}}$ disjoint Markov
boundaries. One of these special cases is a mixture of paths $v_{1}\rightarrow
v_{2}\rightarrow v_{3}\rightarrow\dotsb v_{n}$ over $k$. We will will give a
good set of runs for $n\geq 2N_{\text{mp}}$.

First, we will specify three default runs, which we will call ODD, EVEN, and
LINK.

######  Definition C.8 (ODD default run for Markov chains).

Run ODD is specified by an independence set of vertices with odd indices
$\vec{I}^{\textsf{ODD}}=\\{V_{1},V_{3},V_{5},\ldots,V_{2N_{\text{mp}}-1}\\}$.
The conditioning set is given by the evenly indexed vertices
$\operatorname{\operatorname{\textbf{COND}}}^{\textsf{ODD}}=\\{V_{2},V_{4},V_{6},\ldots,V_{2N_{\text{mp}}-2}\\}$.
$f^{\textsf{ODD}}$ may be chosen arbitrarily, but for simplicity we will give
$f^{\textsf{ODD}}(V_{i})=0$ for all
$V_{i}\in\operatorname{\operatorname{\textbf{COND}}}^{\textsf{ODD}}$.

######  Definition C.9 (EVEN default run for Markov chains).

Run EVEN is defined the same way for evenly indexed vertices. That is,
$\vec{I}^{\textsf{EVEN}}=\\{V_{2},V_{4},V_{6},\ldots,V_{2N_{\text{mp}}}\\}$,
$\operatorname{\operatorname{\textbf{COND}}}^{\textsf{EVEN}}=\\{V_{1},V_{3},V_{5},\ldots,V_{2N_{\text{mp}}-1}\\}$,
and $f^{\textsf{EVEN}}(v_{i})=0$ for all
$V_{i}\in\operatorname{\operatorname{\textbf{COND}}}^{\textsf{EVEN}}$.

######  Definition C.10 (LINK default run for Markov chains).

Run LINK is part evenly indexed vertices and part oddly indexed vertices.
$\vec{I}^{\textsf{LINK}}=\vec{I}^{\textsf{EVEN}}\cup\\{V_{1}\\}\setminus\\{V_{2}\\}$.
Similarly, we condition on the complement
$\operatorname{\operatorname{\textbf{COND}}}^{\textsf{LINK}}=\\{V_{2},V_{3},V_{5},\ldots,V_{2N_{\text{mp}}-1}\\}$
being $0$.

######  Claim 4.

If $n\geq 2N_{\text{mp}}$, then ODD, EVEN, and LINK are well-formed runs.

######  Claim 5.

ODD and LINK are aligned at $V_{1}$. EVEN and LINK are aligned at evenly
indexed vertices beyond $V_{2}$.

Now, we enumerate a set of runs that cover all possible entries to parents of
vertices.

######  Definition C.11.

Let $\textsf{ODD}[v_{i}]$ denote a run on
$\vec{I}^{\textsf{ODD}[V_{i}]}=\vec{I}^{\textsf{ODD}}$,
$\operatorname{\operatorname{\textbf{COND}}}^{\textsf{ODD}[V_{i}]}=\operatorname{\operatorname{\textbf{COND}}}^{\textsf{ODD}}$
with $f^{\textsf{ODD}[V_{i}]}(V_{j})=1$ if $i=j$ and $0$ if $i\neq j$.
Similarly define $\textsf{EVEN}[V_{i}]$ to be a run on
$\vec{I}^{\textsf{EVEN}[V_{i}]}=\vec{I}^{\textsf{EVEN}}$,
$\operatorname{\operatorname{\textbf{COND}}}^{\textsf{EVEN}[V_{i}]}=\operatorname{\operatorname{\textbf{COND}}}^{\textsf{EVEN}}$
with $f^{\textsf{EVEN}[V_{i}]}(v_{j})=1$ if $i=j$ and $0$ if $i\neq j$.

######  Claim 6.

Any run $\textsf{ODD}[V_{i}]$ is aligned with ODD at $V_{j}$ for $j<i-1$ or
$j>i+1$. Similarly, any run $\textsf{EVEN}[V_{i}]$ is aligned with EVEN at
$V_{j}$ for $j<i-1$ or $j>i+1$.

######  Definition C.12.

Let $\textsf{TAIL}^{b}[V_{i}]$ for $i>2N_{\text{mp}}$ give runs which have

$\displaystyle\vec{I}^{\textsf{TAIL}[V_{i}]}$
$\displaystyle=\\{V_{1},V_{3},V_{5},\ldots,V_{2N_{\text{mp}}-1},V_{i}\\}$
$\displaystyle\operatorname{\operatorname{\textbf{COND}}}^{\textsf{TAIL}[V_{i}]}$
$\displaystyle=\\{V_{2},V_{4},\ldots,V_{2N_{\text{mp}}-2},V_{i-1}\\}$

with

$f^{\textsf{TAIL}[V_{i}]}(V_{j})=\begin{cases}0&\text{ if }i-1\neq j\\\
b&\text{ if }i-1=j\end{cases}$

######  Claim 7.

Any run $\textsf{LINK}[V_{i}]$ is aligned with ODD at $V_{j}$ for
$j<2N_{\text{mp}}$ with even $j$.

######  Claim 8.

The set

$\left\\{\textsf{ODD}[V_{i}]\;:\;v_{i}\in\vec{I}^{\textsf{ODD}}\right\\}\cup\left\\{\textsf{EVEN}[V_{j}]\;:\;V_{j}\in\vec{I}^{\textsf{EVEN}}\right\\}\cup\left\\{\textsf{TAIL}^{0}[V_{j}],\textsf{TAIL}^{1}[V_{j}]\;:\;j>6k-6\right\\}$

covers $\vec{V}$.

######  Proof C.13.

For all $V_{i}$ with $i>6k-6$ we have $\textsf{LINK}^{0}[V_{i}]$ and
$\textsf{LINK}^{1}[V_{i}]$ to cover both possible assignments to $V_{i-1}$.

Consider $V_{i}$ with $i\leq 2N_{\text{mp}}$. If $i>1$ is odd, then
$f^{\textsf{EVEN}[V_{i}]}(V_{i-1})=0$ and $f^{\textsf{EVEN}}(V_{i-1})=1$, so
all possible assignments to the parent of $V_{i}$ are covered. Similarly, if
$i$ is even, then $f^{\textsf{ODD}[V_{i}]}(V_{i-1})=0$ and
$f^{\textsf{ODD}}(V_{i-1})=1$, so all possible assignments to the parent of
$V_{i}$ are covered. Finally, if $i=1$, then $V_{i}$ has no parents.

We give the following example to illustrate this construction. Consider $k=2$
and $n=8$. We will express a run $a$ as sequences of values 0, 1 or *. A * in
the $i$th location indicates $V_{i}\in\vec{I}^{a}$ and a 0 or 1 indicates
$f^{a}(V_{i})=0$ or $f^{a}(V_{i})=1$, respectively. Finally, - indicates that
the variable is not conditioned on and not in the independent set (not in
$\operatorname{\operatorname{\textbf{COND}}}$ and not in $\vec{I}$). The
default runs are:

EVEN $\displaystyle=\texttt{0*0*0*--}$ ODD $\displaystyle=\texttt{*0*0**--}$
LINK $\displaystyle=\texttt{*00*0*--}$

In addition to these runs, we have:

$\displaystyle\textsf{ODD}[V_{1}]$ $\displaystyle=\texttt{1*0*0*--}$
$\displaystyle\textsf{ODD}[V_{3}]$ $\displaystyle=\texttt{0*1*0*--}$
$\displaystyle\textsf{ODD}[V_{5}]$ $\displaystyle=\texttt{0*0*1*--}$
$\displaystyle\textsf{EVEN}[V_{2}]$ $\displaystyle=\texttt{*1*0*---}$
$\displaystyle\textsf{EVEN}[V_{4}]$ $\displaystyle=\texttt{*0*1*---}$
$\displaystyle\textsf{EVEN}[V_{6}]$ $\displaystyle=\texttt{*0*0*---}$
$\displaystyle\textsf{TAIL}^{0}[V_{7}]$ $\displaystyle=\texttt{*0*0-0*-}$
$\displaystyle\textsf{TAIL}^{1}[V_{7}]$ $\displaystyle=\texttt{*0*0-1*-}$
$\displaystyle\textsf{TAIL}^{0}[V_{8}]$ $\displaystyle=\texttt{*0*0--0*}$
$\displaystyle\textsf{TAIL}^{1}[V_{8}]$ $\displaystyle=\texttt{*0*0--1*}$

The construction of a good set of runs given does not use disjoint Markov
boundaries, yielding greater efficiency than our more general algorithm for
degree bounded graphs.

While similar in name and structure, this setting is different from that of
hidden Markov models. Hidden Markov models are Bayesian networks consisting of
a chain of unobserved variables, each affecting a unique observed variable,
with no causal relations among the observed variables. For instance, in Gupta
et al. (2016), all chains in the mixture have the same state space. The
sampling process selects a chain and a starting state from the mixture
distribution, then generates a short observable path through the chain. In
their model, under some conditions, a sufficiently large collection of paths
of length $3$ suffices to recover the parameters of the mixture, using
spectral methods. A different model is considered in Batu et al. (2004).
There, the constituents of the mixture have disjoint state spaces and the
observation is a long sequence of interleaved paths in the separate chains.
The primary challenge is to cluster the observable states into the $k$
constituents. This model can be viewed as a special case of the hidden Markov
model problem.

The natural extension of EVEN and ODD vertices is a two-coloring on a tree
which denotes sets that are of even or odd distance from the root. One can
construct a good set of runs for learning mixtures of trees of size $n\geq
2N_{\text{mp}}$ that is very similar to the one given for mixtures of paths.

###  C.2 Larger alphabets for mixtures of DAGs

The simplest reduction for larger alphabets is to replace each vertex with a
clique of $d$ binary vertices which represent the value of the nonbinary
vertex. The pseudocode for this process is given in Algorithm 5.

Input: A DAG $(\vec{V},\mathcal{E})$ on $n$ variables
$V_{1},\ldots,V_{n}\in[d]$.

Output: A DAG $(\mathcal{W},\mathcal{E}_{W})$ on $dn$ binary variables
$W_{1}^{1},\ldots W_{1}^{d},\ldots W_{n}^{1},\ldots W_{n}^{d}\in\\{0,1\\}$.

Start with $\mathcal{E}_{W}\leftarrow\emptyset$

for  _each vertex $i\in[n]$_ do

Form a clique among $W_{i}^{1},\ldots W_{i}^{d}$ by adding directed edges
$(W_{i}^{a},W_{i}^{b})$ to $\mathcal{E}_{W}$ for all pairs $a<b$ with
$a,b\in[d]$.

end for

for  _each directed edge $(V_{i},V_{j})\in\mathcal{E}$_ do

Add $\\{W_{i}^{1},\ldots,W_{i}^{d}\\}\times\\{W_{j}^{1},\ldots,W_{j}^{d}\\}$
to $\mathcal{E}_{W}$.

end for

Algorithm 5 Reduction for larger alphabets

###### Observation C.14

The maximum degree of $(\mathcal{W},\mathcal{E}_{W})$ outputted by Algorithm 5
is now at least $\Delta\geq d$.

###### Observation C.15

The number of vertices $|\mathcal{W}|=nd$.

We now give the function that translates data from the original graph to the
new graph.

######  Definition C.16 (One-hot encoding).

We define $\chi(v)=(\mathbb{1}_{0}(v),\ldots,\mathbb{1}_{d-1}(v))$ to give the
one-hot encoding of the value of a variable $V$.

This allows us to give the full algorithm.

Input: A DAG $(\vec{V},\mathcal{E})$ on $n$ variables
$V_{1},\ldots,V_{n}\in[d]$. And data with entries of the form
$(v_{1},v_{2},\ldots,v_{n})$.

Output: Parameters
$\mathcal{P}_{u}(v_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(V_{i}))$
for $i\in[n]$.

Use Algorithm 5 to create a larger DAG on binary variables, called
$\mathcal{G}^{\prime}$.

One-hot encode data on each $V_{i}$ into binary variables
$\xi(V)=(W^{1}_{i},\ldots,W^{d}_{i})$.

Run the Mixture of DAGs algorithm for $\mathcal{G}^{\prime}$ on the one-hot
encoded data.

for  _each parameter
$\mathcal{P}_{u}(v_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(V_{i}))$_
do

Let $Z$ indicate zero assignments to $W^{b}_{i}$ for $b\neq v_{i}$.

One-hot encode each parent
$V_{j}\in\operatorname{\operatorname{\textbf{PA}}}(V_{i})$ to obtain
assignments to
$\operatorname{\operatorname{\textbf{PA}}}(W^{v_{i}}_{i})\setminus\left\\{w^{b}\;:\;b\neq
v_{i}\right\\}$, denoted
$\operatorname{\operatorname{\textbf{pa}}}^{\operatorname{\operatorname{\textbf{OH}}}}(W^{v_{i}}_{i})$.

Assign
$\mathcal{P}_{u}(v_{i}\mid\operatorname{\operatorname{\textbf{PA}}}(V_{i}))=\mathcal{P}_{u}(W_{i}^{v_{i}}=1\mid
Z,\operatorname{\operatorname{\textbf{pa}}}^{\operatorname{\operatorname{\textbf{OH}}}}(W^{v_{i}}_{i}))$.

end for

Algorithm 6 DAG reduction for larger alphabets

######  Theorem C.17.

If $\mathcal{P}(\vec{V})=\sum_{u}\mathcal{P}_{u}(\vec{V})\mathcal{P}(u)$ is a
mixture of $k$ distributions over a DAG $\mathcal{G}=(\vec{V},\vec{E})$ with
$\vec{V}\in\\{0,\ldots,d-1\\}$ and there exists a set of $N_{\text{mp}}$
centers, then there is an algorithm to compute estimates of all parameters to
accuracy $\varepsilon$. If $D=\max(d,\Delta)$ then the algorithm uses
$O(nd2^{D^{2}})$ calls to the $k$-MixProd oracle.

######  Proof C.18.

The algorithm uses the reduction in Algorithm 6. This involves running the
algorithm on a larger graph with $nd$ vertices and $\Delta\geq d$, which
modifies the run-time and sample complexity as given.