the variable scope of a PC unit n does not contain X1, it must has probability 1 while computing
p(X1 = x1). Finally, following all ancestors of the two blue units (i.e., “ancestor units” in Fig. 5(b)),
we can compute the probability of the root unit, which is the target quantity p(X1 = x1). At a ﬁrst
glance, this seems to suggest that we need to evaluate these ancestor units explicitly. Fortunately,
as we will proceed to show, the root unit’s probability can be equivalently computed using the blue
units’ probabilities weighted by a set of cached top-down probabilities.
For ease of presentation, denote the two blue input units as n1 and n2, respectively. A key observation
is that the probability of every ancestor unit of {n1, n2} (including the root unit) can be represented
as a weighted mixture over pn1 (x) and pn2(x), the probabilities assigned to n1 and n2, respectively.
The reason is that for each decomposable product node m, only distributions deﬁned on disjoint
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS