Finite Factored Sets: Polynomials and Probability

post by Scott Garrabrant · 2021-08-17T21:53:03.269Z · LW · GW · 2 comments

Contents

  5.1. Characteristic Polynomials
  5.2. Factoring Characteristic Polynomials
  5.3. Characteristic Polynomials and Orthogonality
  5.4. Probability Distributions on Finite Factored Sets
  5.5. The Fundamental Theorem of Finite Factored Sets
None
2 comments

In this post, given a finite factored set [? · GW] $F=(S,B)$, we will show how to associate each $E\subseteq S$ with a characteristic polynomial, $Q_E^F$. We will discuss how to factor these characteristic polynomials, and use these characteristic polynomials to build up to the fundamental theorem of finite factored sets, which associates conditional orthogonality with conditional independence in probability distributions.

 

5.1. Characteristic Polynomials

Definition 28. Given a finite factored set $F=(S,B)$, let ${\text{Poly}}^F$ denote the ring of polynomials with coefficients in $R$ and variables in $P\left(S\right)$. 

Definition 29. Given a finite factored set $F=(S,B)$, a $p\in {\text{Poly}}^F$, and an $f:P\left(S\right)\to R$, we write $p\left(f\right)\in R$ for the evaluation of $p$ at $f$, computed by replacing each $E\subseteq S$ with $f\left(E\right)$.

Definition 30. Given a finite factored set $F=(S,B)$, and a polynomial $p\in {\text{Poly}}^F$, $\text{supp}\left(p\right)\subseteq P\left(S\right)$ denotes the set of all variables $v\in P\left(S\right)$ that appear in $p$. $\text{supp}\left(p\right)$ is called the support of $p$.

Definition 31. Given a finite factored set $F=(S,B)$ and an $E\subseteq S$, let $Q_E^F\in {\text{Poly}}^F$ be given by $Q_E^F={\sum }_{s\in E}{\prod }_{b\in B}[s{]}_b$.  $Q_E^F$ is called the characteristic polynomial of $E$ (in $F$).

We will be building up to an understanding of how to factor $Q_E^F$ into irreducibles. For that, we will first need to give some basic notation for manipulating polynomials in ${\text{Poly}}^F$.

Definition 32. Given a finite factored set $F=(S,B)$, an $s\in S$, and a $C\subseteq B$, let ${\text{mono}}_C^F\left(s\right)\in {\text{Poly}}^F$ be given by ${\text{mono}}_C^F\left(s\right)={\prod }_{b\in C}[s{]}_b$. 

Definition 33. Given a finite factored set $F=(S,B)$, an $E\subseteq S$, and a $C\subseteq B$, let ${\text{monos}}_C^F\left(E\right)\in P\left({\text{Poly}}^F\right)$ be given by ${\text{monos}}_C^F\left(E\right)=\left\{{\text{mono}}_C^F\right(s)\mid s\in E\}$. 

Definition 34. Given a finite factored set $F=(S,B)$, an $E\subseteq S$, and a $C\subseteq B$, let ${\text{poly}}_C^F\left(E\right)\in {\text{Poly}}^F$ be given by ${\text{poly}}_C^F\left(E\right)={\sum }_{m\in {\text{monos}}_C^F\left(E\right)}m$. 

Proposition 26. Let $F=(S,B)$ be a finite factored set, and let $E\subseteq S$. Then $Q_E^F={\text{poly}}_B^F\left(E\right)$.

Proof. We start by showing that for all $s\ne t\in S$, ${\text{mono}}_B^F\left(s\right)\ne {\text{mono}}_B^F\left(t\right)$. 

Let $s\ne t\in S$ be arbitrary. By Proposition 3 [? · GW], if $s\ne t$, there must be some $b\in B$ such that $[s{]}_b\ne [t{]}_b$. Then, note that $[s{]}_b\in \text{supp}({\text{mono}}_B^F\left(s\right))$. If $[s{]}_b$ were also in $\text{supp}\left({\text{mono}}_B^F\right(t\left)\right)$, then $t$ would be in both $[s{]}_b$ and $[t{]}_b$, contradicting the fact that these two sets are disjoint. Therefore ${\text{mono}}_B^F\left(s\right)\ne {\text{mono}}_B^F\left(t\right)$.

Thus ${\text{monos}}_B^F\left(E\right)$ has exactly one element for each element of $E$, so we have that ${\sum }_{m\in {\text{monos}}_B^F\left(E\right)}m={\sum }_{s\in E}{\text{mono}}_B^F\left(s\right)=Q_E^F$. $\square$

Proposition 27. Let $F=(S,B)$ be a finite factored set, and let $E_0,E_1\subseteq S$ be subsets of $S$. Let $C_0,C_1\subseteq B$ be disjoint subsets of $B$. Let $E_2={\chi }_{C_0}^F(E_0,E_1)$, and let $C_2=C_0\cup C_1$. Then ${\text{poly}}_{C_2}^F\left(E_2\right)={\text{poly}}_{C_0}^F\left(E_0\right)\cdot {\text{poly}}_{C_1}^F\left(E_1\right)$.

Proof. For $i\in \{0,1,2\}$, let $M_i={\text{monos}}_{C_i}^F\left(E_i\right)$. We will start by showing that $f:M_0\times M_1\to M_2$, given by $f(m_0,m_1)=m_0{m}_1$, is a well-defined function and a bijection.

First, observe that it follows immediately from the definition that for all $s_0,s_1\in S$, if $s_2={\chi }_{C_0}^F(s_0,s_1)$ we have that ${\text{mono}}_{C_0}^F\left(s_0\right)={\text{mono}}_{C_0}^F\left(s_2\right)$, ${\text{mono}}_{C_1}^F\left(s_1\right)={\text{mono}}_{C_1}^F\left(s_2\right)$, and ${\text{mono}}_{C_0}^F\left(s_2\right)\cdot {\text{mono}}_{C_1}^F\left(s_2\right)={\text{mono}}_{C_2}^F\left(s_2\right)$. Combining these, we get that ${\text{mono}}_{C_0}^F\left(s_0\right)\cdot {\text{mono}}_{C_1}^F\left(s_1\right)={\text{mono}}_{C_2}^F\left({\chi }_{C_0}^F\right(s_0,s_1\left)\right)$.

For all $(m_0,m_1)\in M_0\times M_1$, there exists some $s_0\in E_0$ such that $m_0={\text{mono}}_{C_0}^F\left(s_0\right)$, and some $s_1\in E_1$ such that $m_1={\text{mono}}_{C_1}^F\left(s_1\right)$, and this gives us that $m_0{m}_1={\text{mono}}_{C_0}^F\left(s_0\right){\text{mono}}_{C_1}^F\left(s_1\right)={\text{mono}}_{C_2}^F\left({\chi }_C^F\right(s_0,s_1\left)\right)\in M_2$. Thus, $f$ is well-defined.

To see that $f$ is surjective, observe that for all $m_2\in M_2$, there exists an $s_2\in E_2$ such that $m_2={\text{mono}}_{C_2}^F\left(s_2\right)$, and there exist $s_0\in E_0$ and $s_1\in E_1$ such that $s_2={\chi }_C^F(s_0,s_1)$, and we have $f\left({\text{mono}}_{C_0}^F\right(s_0),{\text{mono}}_{C_1}^F(s_1\left)\right)=m_2$.

To see that $f$ is injective, observe that for $i\in \{0,1\}$, for all $m_i\in M_i$, $\text{supp}\left(m_i\right)\subseteq {\bigcup }_{b\in C_i}b$. Further, ${\bigcup }_{b\in C_0}b$ and ${\bigcup }_{b\in C_1}b$ are disjoint. Thus, for all $m_0\in M_0$ and $m_1\in M_1$, $\text{supp}\left(m_i\right)=\text{supp}\left(m_0{m}_1\right)\cap {\bigcup }_{b\in C_i}b$.

This means that for all $m_0,m_0^{\prime }\in M_0$ and $m_1,m_1^{\prime }\in M_1$, if $m_0{m}_1=m_0^{\prime }{m}_1^{\prime }$, then $\text{supp}\left(m_0\right)=\text{supp}\left(m_0^{\prime }\right)$ and $\text{supp}\left(m_1\right)=\text{supp}\left(m_1^{\prime }\right)$. However, every monomial in $M_0$ or $M_1$ is just equal to the product of all variables in its support. Thus $m_0={\prod }_{v\in \text{supp}\left(m_0\right)}v=m_0^{\prime }$ and $m_1={\prod }_{v\in \text{supp}\left(m_1\right)}v=m_1^{\prime }$. Thus $f$ is injective, and thus a bijection between $M_0\times M_1$ and $M_2$.

Now, we have that

$$\begin{array}{cc}{\text{poly}}_{C_0}^F\left(E_0\right)\cdot {\text{poly}}_{C_1}^F\left(E_1\right)& =\left(\sum _{m_0\in M_0}{m}_0\right)\left(\sum _{m_1\in M_1}{m}_1\right)\\ & =\sum _{m_0\in M_0}\sum _{m_1\in M_1}{m}_0{m}_1\\ & =\sum _{(m_0,m_1)\in M_0\times M_1}{m}_0{m}_1\\ & =\sum _{(m_0,m_1)\in M_0\times M_1}f(m_0,m_1)\\ & =\sum _{m_2\in M_2}{m}_2\\ & ={\text{poly}}_{C_2}^F\left(E_2\right).\end{array}$$

$\square$

Proposition 28. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. If $p$ divides $Q_E^F$, then $p=r\cdot {\text{poly}}_C^F\left(E\right)$, for some $r\in R$ and $C\subseteq B$.

Proof. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. Let $p,q\in {\text{Poly}}^F$ satisfy $pq=Q_E^F$. We thus must have $\text{supp}\left(p\right)\cup \text{supp}\left(q\right)=\text{supp}\left(Q_E^F\right)$. 

If there were some $T\in \text{supp}\left(p\right)\cap \text{supp}\left(q\right)$, then the degree of $T$ in $Q_E^F$ would be at least 2, contradicting the definition of $Q_E^F$ and Corollary 1 [? · GW]. Thus, $\text{supp}\left(p\right)\cap \text{supp}\left(q\right)=\left\{\right\}$.

There can be no combining like terms, then, in the product $pq$. The monomial terms in $Q_E^F$ are in bijective correspondence to the pairs of monomial terms in $p$ and monomial terms in $q$.

In particular, this means that since all the coefficients in $pq$ are equal to $1$, all the coefficients in $p$ must be equal to some $r\in R$, and all of the coefficients in $q$ must be equal to $1/r$.

Further, for all $b\in B$, if $b\cap \text{supp}\left(p\right)$ is nonempty, $b\cap \text{supp}\left(q\right)$ must be empty, since otherwise $Q_E^F$ would contain a term with two factors in $b$, which clearly never happens according to the definition of $Q_E^F$. 

Since $E$ is nonempty, for each $b\in B$ there must be some $T\in b\cap \text{supp}\left(Q_E^F\right)$. Thus at least one of $b\cap \text{supp}\left(p\right)$ and $b\cap \text{supp}\left(q\right)$ must be nonempty, so exactly one of $b\cap \text{supp}\left(p\right)$ and $b\cap \text{supp}\left(q\right)$ must be nonempty.

Let $C$ be the set of all $b\in B$ such that $b\cap \text{supp}\left(p\right)$ is nonempty. 

For every $b\in C$, every term of $Q_E^F$ has exactly one factor in $b$. Thus, every term in $p$ has exactly one factor in $b$. These cover all variables in the support of $p$, so each term in $p$ must have total degree $|C|$.

For each $m\in {\text{monos}}_C^F\left(E\right)$, $m$ divides a term in $Q_E^F$. Since $m$ has no common support with $q$, $m$ must also divide a term in $p$. Thus $r\cdot m$ must be a term in $p$. Conversely, every term in $p$ divides a term in $Q_E^F$, and thus must be in ${\text{monos}}_C^F\left(E\right)$. Thus every term in $p$ is of the form $r\cdot m$ for some $m\in {\text{monos}}_C^F\left(E\right)$. Thus $p={\sum }_{m\in {\text{monos}}_C^F\left(E\right)}r\cdot m=r\cdot {\text{poly}}_C^F\left(E\right)$. $\square$

 

5.2. Factoring Characteristic Polynomials

We will now show how to factor characteristic polynomials into irreducibles. 

Definition 35. Given a finite factored set $F=(S,B)$, and a nonempty subset $E\subseteq S$, let ${\text{Irr}}^F\left(E\right)\subseteq P\left(B\right)$ denote the set of all $C\subseteq B$ such that:

1. $C$ is nonempty,
2. ${\chi }_C^F(E,E)=E$, and
3. there is no nonempty strict subset $D\subset C$ such that ${\chi }_D^F(E,E)=E$.

Proposition 29. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. Then ${\text{Irr}}^F\left(E\right)\in \text{Part}\left(B\right)$.

Proof. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. It suffices to show that the sets in ${\text{Irr}}^F\left(E\right)$ are pairwise disjoint and cover $B$. 

We start by showing that the set of all $C\subseteq B$ satisfying ${\chi }_C^F(E,E)=E$ is closed under intersection. Indeed, if ${\chi }_{C_0}^F(E,E)=E$ and ${\chi }_{C_1}^F(E,E)=E$, then ${\chi }_{C_0\cap C_1}^F(E,E)={\chi }_{C_0}^F(E,{\chi }_{C_1}^F(E,E\left)\right)={\chi }_{C_0}^F(E,E)=E$.

Next, observe that ${\chi }_B^F(E,E)=E$. Thus, for all $b\in B$, we can consider $C_b={\bigcap }_{C\subseteq B,b\in C,{\chi }_C^F(E,E)=E}C$. Since $C_b$ is an intersection of a finite nonempty collection of sets $C$ satisfying ${\chi }_C^F(E,E)=E$, we have that ${\chi }_{C_b}^F(E,E)=E$. Further, $b\in C_b$, so $C_b$ is nonempty.

Assume for the purpose of contradiction that there is some nonempty strict subset $D\subset C_b$ such that ${\chi }_D^F(E,E)=E$. If $b\in D$, then we have a contradiction by the definition of $C_b$. If $b\notin D$, then note that ${\chi }_{B\setminus D}^F(E,E)=E$, so ${\chi }_{C_b\setminus D}^F(E,E)=E$, and $C_b\setminus D$ is a nonempty strict subset of $C_b$ that contains $b$, contradicting the definition of $C_b$.

Thus $C_b\in {\text{Irr}}^F\left(E\right)$ for all $b\in B$, and since $b\in C_b$, this means that the sets in ${\text{Irr}}^F\left(E\right)$ cover $B$.

Next, we need to show that the sets in ${\text{Irr}}^F\left(E\right)$ are pairwise disjoint. Let $C_0,C_1\in {\text{Irr}}^F\left(E\right)$ be arbitrary distinct elements. We have that ${\chi }_{C_0\cap C_1}^F(E,E)=E$, and $C_0\cap C_1$ is a subset of $C_0$ and $C_1$, and thus a strict subset of at least one of them. Thus $C_0\cap C_1$ is empty.

Thus ${\text{Irr}}^F\left(E\right)\in \text{Part}\left(B\right)$. $\square$

The following two propositions constitute a factorization of $Q_E^F$ into irreducibles.

Proposition 30. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. Then $Q_E^F={\prod }_{C\in {\text{Irr}}^F\left(E\right)}{\text{poly}}_C^F\left(E\right)$.

Proof. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. Let $n=|{\text{Irr}}^F\left(E\right)|$, and let ${\text{Irr}}^F\left(E\right)=\{C_0,\dots ,C_{n-1}\}$. For $0\le k<n$, let $C_{\le k}={\bigcup }_{i=0}^k{C}_i$.

We will show by induction on $k$ that ${\prod }_{i=0}^k{\text{poly}}_{C_i}^F\left(E\right)={\text{poly}}_{C_{\le k}}^F\left(E\right)$ for all $0\le k<n$.

If $k=0$, the result is trivial, as ${\prod }_{i=0}^0{\text{poly}}_{C_i}^F\left(E\right)={\text{poly}}_{C_0}^F\left(E\right)={\text{poly}}_{C_{\le 0}}^F\left(E\right)$.

For $k>0$, observe that $C_k$ and $C_{\le k-1}$ are disjoint, and that $E={\chi }_{C_k}^F(E,E)$, thus by Proposition 27, we have ${\text{poly}}_{C_k}^F\left(E\right)\cdot {\text{poly}}_{C_{\le k-1}}^F\left(E\right)={\text{poly}}_{C_{\le k}}^F\left(E\right)$. Thus, by induction, we get ${\prod }_{i=0}^k{\text{poly}}_{C_i}^F\left(E\right)={\text{poly}}_{C_{\le k}}^F\left(E\right)$.

In the case where $k=n-1$, this gives that ${\prod }_{C\in {\text{Irr}}^F\left(E\right)}{\text{poly}}_C^F\left(E\right)={\text{poly}}_B^F\left(E\right)=Q_E^F$. $\square$

Proposition 31. Let $F=(S,B)$ be a finite factored set, and let $E$ be a nonempty subset of $S$. Then ${\text{poly}}_C^F\left(E\right)$ is irreducible for all $C\in {\text{Irr}}^F\left(E\right)$.

Proof. Let $F=(S,B)$ be a finite factored set, let $E$ be a nonempty subset of $S$, and let $C\in {\text{Irr}}^F\left(E\right)$.

Assume for the purpose of contradiction that $p_0\cdot p_1={\text{poly}}_C^F\left(E\right)$, and that both $p_0$ and $p_1$ have nonempty support. By Proposition 28, we have that $p_i=r_i\cdot {\text{poly}}_{C_i}^F\left(E\right)$, for some $r_0,r_1\in R$, and $C_0,C_1\subseteq B$. 

We will first need to show that $C_0$ and $C_1$ are nonempty and disjoint. They must be nonempty, because $p_0$ and $p_1$ have nonempty support. Assume for the purpose of contradiction that $b\in C_0\cap C_1$. Let $s$ be an element of $E$, and note that for $i\in \{0,1\}$, we have $[s{]}_b\in \text{supp}{\text{poly}}_{C_i}^F(E)$. Thus $[s{]}_b$ must be degree at least 2 in ${\text{poly}}_C^F\left(E\right)$, which contradicts the fact that every variable clearly has degree at most 1 in ${\text{poly}}_C^F\left(E\right)$.

Next, we need to show that $C_0\cup C_1=C$. We already know that

$$\begin{array}{cc}\text{supp}\left({\text{poly}}_C^F\right(E\left)\right)& =\text{supp}\left(r_0{r}_1{\text{poly}}_{C_0}^F\right(E\left){\text{poly}}_{C_1}^F\right(E\left)\right)\\ & =\text{supp}\left({\text{poly}}_{C_0}^F\right(E\left)\right)\cup \text{supp}\left({\text{poly}}_{C_1}^F\right(E\left)\right).\end{array}$$

Let $s$ be an element of $E$. Given an arbitrary $b\in B$, we have that $b\in C$ if and only if $[s{]}_b\in \text{supp}({\text{poly}}_C^F\left(E\right))$ if and only if $[s{]}_b\in \text{supp}({\text{poly}}_{C_i}^F\left(E\right))$ for some $i\in \{0,1\}$ if and only if $b\in C_0\cup C_1$. 

We now have that $C_0$ and $C_1$ are disjoint and that $C=C_0\cup C_1$. Thus, by Proposition 27, we have that ${\text{poly}}_{C_0}^F\left(E\right)\cdot {\text{poly}}_{C_1}^F\left(E\right)={\text{poly}}_C^F\left({\chi }_{C_0}^F\right(E,E\left)\right)$. Thus ${\text{poly}}_C^F\left(E\right)=r_0{r}_1{\text{poly}}_C^F\left({\chi }_{C_0}^F\right(E,E\left)\right)$, so ${\text{monos}}_C^F\left(E\right)={\text{monos}}_C^F\left({\chi }_{C_0}^F\right(E,E\left)\right)$.

Let $s_0,s_1\in E$ be arbitrary, and let $s_2={\chi }_{C_0}^F(s_0,s_1)$. Note that ${\text{mono}}_C^F\left(s_2\right)\in {\text{monos}}_C^F\left({\chi }_{C_0}^F\right(E,E\left)\right)={\text{monos}}_C^F\left(E\right)$, so there is some $s_3\in E$ such that ${\text{mono}}_C^F\left(s_2\right)={\text{mono}}_C^F\left(s_3\right)$. Thus $s_2{\sim }_b{s}_3$ for all $b\in C$. However, we also have that $s_2{\sim }_b{s}_1$ for all $b\in B\setminus C$, so $s_2={\chi }_C^F(s_3,s_1)$. Since $C\in {\text{Irr}}^F\left(E\right)$, ${\chi }_C^F(E,E)=E$, so $s_2={\chi }_{C_0}^F(s_0,s_1)\in E$. Since $s_0$ and $s_1$ were arbitrary elements of $E$, we have that ${\chi }_{C_0}^F(E,E)=E$. Since $C_0$ is a nonempty strict subset of $C$, this contradicts the fact that $C\in {\text{Irr}}^F\left(E\right)$.

Thus, ${\text{poly}}_C^F\left(E\right)$ is irreducible for all $C\in {\text{Irr}}^F\left(E\right)$. $\square$

 

5.3. Characteristic Polynomials and Orthogonality

We can now give an alternate characterization of conditional orthogonality in terms of divisibility of characteristic polynomials.

Lemma 3. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z\in \text{Part}\left(S\right)$ be partitions of $S$. The following are equivalent.

1.  $X{\perp }^{F}Y|Z$.
2. $Q_z^F$ divides $Q_{x\cap z}^F\cdot Q_{y\cap z}^F$ for all $x\in X$, $y\in Y$, and $z\in Z$.
3.  $Q_z^F\cdot Q_{x\cap y\cap z}^F=Q_{x\cap z}^F\cdot Q_{y\cap z}^F$ for all $x\in X$, $y\in Y$, and $z\in Z$.

Proof. Clearly condition 3 implies condition 2. We will first show that condition 1 implies condition 3, and then show that condition 2 implies condition 1.

Let $F=(S,B)$, and let $X,Y,Z\in \text{Part}\left(S\right)$ satisfy $X{\perp }^{F}Y|Z$. Consider an arbitrary $x\in X$, $y\in Y$, and $z\in Z$. We want to show that $Q_z^F\cdot Q_{x\cap y\cap z}^F=Q_{x\cap z}^F\cdot Q_{y\cap z}^F$. 

Let $C=h^F\left(X|z\right)$. Clearly $C{⊢}^{F}X|z$. We thus have that ${\chi }_C^F(z,z)=z$, so ${\chi }_{B\setminus C}^F(z,z)=z$. We also have that $h^F\left(Y|z\right)\subseteq B\setminus C$, so $Y|z{\le }_z\left({\bigvee }_S\right(B\setminus C\left)\right)|z$. These two together give that $B\setminus C{⊢}^{F}Y|z$.

Since $C{⊢}^{F}X|z$, we have that ${\chi }_C^F(x\cap z,z)=x\cap z$. Thus, by Proposition 27, we have that ${\text{poly}}_C^F(x\cap z)\cdot {\text{poly}}_{B\setminus C}^F\left(z\right)=Q_{x\cap z}^F$. Similarly, since $B\setminus C{⊢}^{F}Y|z$, we have that ${\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F(y\cap z)=Q_{y\cap z}^F$.

Since ${\chi }_C^F(x\cap z,y\cap z)\subseteq {\chi }_C^F(x\cap z,z)=x\cap z$, and ${\chi }_C^F(x\cap z,y\cap z)\subseteq {\chi }_C^F(z,y\cap z)=y\cap z$, we have ${\chi }_C^F(x\cap z,y\cap z)\subseteq x\cap y\cap z$. We also have that

$$\begin{array}{cc}{\chi }_C^F(x\cap z,y\cap z)& \supseteq {\chi }_C^F(x\cap y\cap z,x\cap y\cap z)\\ & \supseteq x\cap y\cap z.\end{array}$$

Thus ${\chi }_C^F(x\cap z,y\cap z)=x\cap y\cap z$.

By Proposition 27, this gives that ${\text{poly}}_C^F(x\cap z)\cdot {\text{poly}}_{B\setminus C}^F(y\cap z)=Q_{x\cap y\cap z}^F$.

Finally, since ${\chi }_C^F(z,z)=z$, we have that ${\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F\left(z\right)=Q_z^F$.

Thus, $Q_z^F\cdot Q_{x\cap y\cap z}^F$ and $Q_{x\cap z}^F\cdot Q_{y\cap z}^F$ are both equal to ${\text{poly}}_C^F(x\cap z)\cdot {\text{poly}}_{B\setminus C}^F(y\cap z)\cdot {\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F\left(z\right)$.

Thus, condition 1 implies condition 3. It remains to show that condition 2 implies condition 1.

Fix $F=(S,B)$, and $X,Y,Z\in \text{Part}\left(S\right)$, and let $Q_z^F$ divide $Q_{x\cap z}^F\cdot Q_{y\cap z}^F$ for all $x\in X$, $y\in Y$, and $z\in Z$. Assume for the purpose of contradiction that it is not the case that $X{\perp }^{F}Y|Z$. Thus, there exists some $z\in Z$ such that $h^F\left(X|z\right)\cap h^F\left(Y|z\right)\ne \left\{\right\}$. Let $z\in Z$ and $b\in B$ satisfy $b\in h^F\left(X|z\right)\cap h^F\left(Y|z\right)\ne \left\{\right\}$.

Let $C\subseteq B$ be such that $b\in C$ and $C\in {\text{Irr}}^F\left(z\right)$, and let $p={\text{poly}}_C^F\left(z\right)$. Thus, $p$ is an irreducible factor of $Q_z^F$.

Either $p$ divides $Q_{x\cap z}^F$ for all $x\in X$ or $p$ divides $Q_{y\cap z}^F$ for all $y\in Y$, since otherwise there would exist an $x\in X$ and a $y\in Y$ such that $p$ divides neither $Q_{x\cap z}^F$ nor $Q_{x\cap z}^F$, but does divide their product, contradicting the fact that $p$ is irreducible, and thus prime.

Assume without loss of generality that $p$ divides $Q_{x\cap z}^F$ for all $x\in X$. Fix an $x\in X$. Let us first restrict attention to the case where $x\cap z$ is nonempty. 

Let $Q_{x\cap z}^F=p\cdot q$. By Proposition 28, $p=r_0\cdot {\text{poly}}_{C_0}^F(x\cap z)$ and $q=r_1\cdot {\text{poly}}_{C_1}^F(x\cap z)$ for some $r_0,r_1\in R$ and $C_0,C_1\subseteq B$. We will show that $C_0=C,C_1=B\setminus C$, and $r_0=r_1=1$.

Let $s$ be an element of $x\cap z$. Then for all $b\in B$, $b\in C$ if and only if $[s{]}_b\in \text{supp}(p)$ if and only if $[s{]}_b\in \text{supp}({\text{poly}}_{C_0}^F(x\cap z))$ if and only if $b\in C_0$. Thus $C_0=C$. 

For all $b\in B\setminus C$, we have $[s{]}_b\in \text{supp}(Q_{x\cap z}^F)$ and $[s{]}_b\notin \text{supp}(p)$, so $[s{]}_b\in \text{supp}(q)$, so $b\in C_1$. Similarly, for all $b\in C_1$, $[s{]}_b\in \text{supp}(q)$, so $[s{]}_b\notin \text{supp}(p)$, so $b\in B\setminus C$. Thus $C_1=B\setminus C$.

Since $p$ and ${\text{poly}}_{C_0}^F(x\cap z)$ both have all coefficients equal to $1$, we have $r_0=1$. Thus, $p={\text{poly}}_C^F(x\cap z).$

Similarly, since all the coefficients of $p$ are $1$ and all the coefficients of $Q_{x\cap z}^F$ are $1$, all the coefficients of $q$ are $1$, so $r_1=1$. Thus, $q={\text{poly}}_{B\setminus C}^F(x\cap z)$.

We thus have that $Q_{x\cap z}^F={\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F(x\cap z)$.

In the case where $x\cap z$ is empty, we also have $Q_{x\cap z}^F={\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F(x\cap z)$, since both sides are $0$.

By Proposition 27, $Q_{x\cap z}^F={\text{poly}}_B^F\left({\chi }_C^F\right(z,x\cap z\left)\right)$. Thus, ${\text{monos}}_B^F(x\cap z)={\text{monos}}_B^F\left({\chi }_C^F\right(z,x\cap z\left)\right)$, so $x\cap z={\chi }_C^F(z,x\cap z)={\chi }_{B\setminus C}^F(x\cap z,z)$.

Since $x\cap z={\chi }_{B\setminus C}^F(x\cap z,z)$ for all $x\in X$, we have that $B\setminus C{⊢}^{F}X|z$. However, this contradicts the fact that $b\notin B\setminus C$, and $b\in h^F\left(X|z\right)$.

Thus, condition 2 implies condition 1. $\square$

 

5.4. Probability Distributions on Finite Factored Sets

The primary purpose of all this discussion of characteristic polynomials has been to build up to thinking about the relationship between orthogonality and probabilistic independence. We will now discuss probability distributions on finite factored sets.

Recall the definition of a probability distribution.

Definition 36. Given a finite set $S$, a probability distribution on $S$ is a function $P:P\left(S\right)\to R$ such that 

1.  $P\left(E\right)\ge 0$ for all $E\subseteq S$,
2.  $P\left(\right\{\left\}\right)=0$,
3.  $P\left(S\right)=1$, and
4. $P(E_0\cup E_1)=P\left(E_0\right)+P\left(E_1\right)$ whenever $E_0,E_1\subseteq S$ satisfy $E_0\cap E_1=\left\{\right\}$.

A probability distribution on a finite factored set $F$ is a probability distribution on its underlying set that also satisfies another condition, which represents the probability distribution coming from a product of distributions on the underlying factors.

Definition 37. Given a finite factored set $F=(S,B)$, a probability distribution on $F$ is a probability distribution $P$ on $S$ such that for all $s\in S$, we have $P\left(\right\{s\left\}\right)={\prod }_{b\in B}P\left(\right[s{]}_b)$.

Proposition 32. Given a finite factored set $F=(S,B)$, a probability distribution on $S$ is a probability distribution $P$ on $F$ if and only if $P\left(E\right)=Q_E^F\left(P\right)$ for all $E\subseteq S$.

Proof. If $P\left(E\right)=Q_E^F\left(P\right)$ for all $E\subseteq S$, in particular this means that $P\left(\right\{s\left\}\right)=Q_{\left\{s\right\}}^F\left(P\right)=\left({\prod }_{b\in B}\right[s{]}_b\left)\right(P)={\prod }_{b\in B}P(\left[s{]}_b\right)$ for all $s\in S$.

Conversely, if $P\left(\right\{s\left\}\right)={\prod }_{b\in B}P\left(\right[s{]}_b)$ for all $s\in S$, then for all $E\subseteq S,P\left(E\right)={\sum }_{s\in E}{\prod }_{b\in B}P\left(\right[s{]}_b)=({\sum }_{s\in E}{\prod }_{b\in B}\left[s{]}_b\right)\left(P\right)=Q_E^F\left(P\right)$. $\square$

 

5.5. The Fundamental Theorem of Finite Factored Sets

We are now ready to state and prove the fundatmental theorem of finite factored sets.

Theorem 3. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z\in \text{Part}\left(S\right)$ be partitions of $S$. Then $X{\perp }^{F}Y|Z$ if and only if for all probability distributions $P$ on $F$ and all $x\in X$, $y\in Y$, and $z\in Z$, we have $P(x\cap z)\cdot P(y\cap z)=P(x\cap y\cap z)\cdot P\left(z\right)$.

Proof. We already have by Lemma 3 that if $X{\perp }^{F}Y|Z$, then for all $x\in X$, $y\in Y$, and $z\in Z$, $Q_z^F\cdot Q_{x\cap y\cap z}^F=Q_{x\cap z}^F\cdot Q_{y\cap z}^F$. Thus for any probability distribution $P$ on $F$, we have

$$\begin{array}{cc}P\left(z\right)\cdot P(x\cap y\cap z)& =Q_z^F\left(P\right)\cdot Q_{x\cap y\cap z}^F\left(P\right)\\ & =Q_{x\cap z}^F\left(P\right)\cdot Q_{y\cap z}^F\left(P\right)\\ & =P(x\cap z)\cdot P(y\cap z).\end{array}$$

Conversely, assume that for all probability distributions $P$ on $F$, and all $x\in X$, $y\in Y$, and $z\in Z$, we have $P(x\cap z)\cdot P(y\cap z)=P(x\cap y\cap z)\cdot P\left(z\right)$.

If $S$ is empty, then $\left\{\right\}$ is the unique partition of $S$, and we have $\left\{\right\}{\perp }^F\left\{\right\}|\left\{\right\}$. Thus, we can restrict our attention to the case where $S$ is nonempty. 

Fix an arbitrary $x\in X$, $y\in Y$, and $z\in Z$. Let $q=Q_{x\cap z}^F\cdot Q_{y\cap z}^F-Q_{x\cap y\cap z}^F\cdot Q_z^F$. We will first show that $q\left(f\right)=0$ for all $f:P\left(S\right)\to R^{>0}$.

Given an arbitrary $f:P\left(S\right)\to R^{>0}$, we can define $P_f:P\left(S\right)\to R$ by $P_f\left(E\right)=Q_E^F\left(f\right)/Q_S^F\left(f\right)$, and we will show that $P_f$ is a distribution on $F$.

$P_f$ is well-defined because $Q_S^F\left(f\right)$ is a nonempty sum of products of positive real numbers, and thus positive. Further, since $Q_E^F\left(f\right)$ is a sum of products of positive real numbers, $P_f\left(E\right)\ge 0$ for all $E\subseteq S$. Since $Q_{\left\{\right\}}^F=0$, we also have $P_f\left(\right\{\left\}\right)=0$. Clearly $P_f\left(S\right)=1$. Finally, for all $E_0,E_1\subseteq S$ with $E_0\cap E_1=\left\{\right\}$, we have

$$\begin{array}{cc}{P}_f(E_0\cup E_1)& =Q_{E_0\cup E_1}^F\left(f\right)/Q_S^F\left(f\right)\\ & =\left(Q_{E_0}^F\right(f)+Q_{E_1}^F(f\left)\right)/Q_S^F\left(f\right)\\ & =P_f\left(E_0\right)+P_f\left(E_1\right).\end{array}$$

Therefore $P_f$ is a distribution on $S$. We still need to show that $P_f$ is a distribution on $F$.

Observe that for all $s\in S$ and $b\in B$, since ${\chi }_{\left\{b\right\}}^F\left(\right[s{]}_b,S)=[s{]}_b$, we have that $Q_{[s{]}_b}^F\left(f\right)={\text{poly}}_{\left\{b\right\}}^F\left(\right[s{]}_b)\cdot {\text{poly}}_{B\setminus \left\{b\right\}}^F(S)$, and since ${\chi }_{\left\{b\right\}}^F(S,S)=S$, we have that $Q_S^F\left(f\right)={\text{poly}}_{\left\{b\right\}}^F\left(S\right)\cdot {\text{poly}}_{B\setminus \left\{b\right\}}^F\left(S\right)$. Thus, we have that

$$\begin{array}{cc}{P}_f\left(\right[s{]}_b)& ={\text{poly}}_{\left\{b\right\}}^F\left(\right[s{]}_b\left)\right(f\left)/{\text{poly}}_{\left\{b\right\}}^F\right(S\left)\right(f)\\ & =f\left(\right[s{]}_b\left)/{\text{poly}}_{\left\{b\right\}}^F\right(S\left)\right(f).\end{array}$$

Thus, for all $s\in S$, 

$$\begin{array}{cc}\prod _{b\in B}{P}_f\left(\right[s{]}_b)& =\left(\prod _{b\in B}f\right(\left[s{]}_b\right)\left)/\right(\prod _{b\in B}{\text{poly}}_{\left\{b\right\}}^F\left(S\right)\left(f\right))\\ & =Q_{\left\{s\right\}}^F\left(f\right)/Q_S^F\left(f\right)\\ & =P_f\left(\right\{s\left\}\right).\end{array}$$

Thus $P_f$ is a distribution on $F$.

It follows that P${}_f(x\cap z)\cdot P_f(y\cap z)=P_f(x\cap y\cap z)\cdot P_f\left(z\right)$. We therefore have that

$$\begin{array}{cc}q\left(f\right)& =Q_{x\cap z}^F\left(f\right)\cdot Q_{y\cap z}^F\left(f\right)-Q_{x\cap y\cap z}^F\left(f\right)\cdot Q_z^F\left(f\right)\\ & =\left(P_f\right(x\cap z)\cdot P_f(y\cap z)-P_f(x\cap y\cap z)\cdot P_f(z\left)\right)\cdot Q_S^F(f{)}^2\\ & =0\cdot Q_S^F(f{)}^2\\ & =0.\end{array}$$

Thus, $q$ is a polynomial that is zero on an open subset of inputs, so $q$ is the zero polynomial. Thus $Q_{x\cap z}^F\cdot Q_{y\cap z}^F-Q_z^F\cdot Q_{x\cap y\cap z}^F=0$, so $Q_z^F\cdot Q_{x\cap y\cap z}^F=Q_{x\cap z}^F\cdot Q_{y\cap z}^F$. Since $x\in X$, $y\in Y$, and $z\in Z$ were arbitrary, by Lemma 3, we have $X{\perp }^{F}Y|Z$. $\square$

 

In the next two posts, we will introduce temporal inference using finite factored sets, and discuss future potential research directions.

2 comments

Comments sorted by top scores.