数理解析研究所講究録
第 1560 巻 2007 年 145-154

145

The cain algebra, the semigraphoid and the separoid
汪 金芳 (Jinfang Wang)
Graduate School of Science, Chiba University

千葉大学・大学院理学研究科

1 Introduction
The cain algebra was proposed recently by Wang (2006) and Wang (2007) to enable study of$pro\propto rties$ of probability density functions, especially those relevant for probabilistic conditional
independence, in a purely universal algebraic fashion. In the cain algebra the familiar likelihood
functions are replaced by the corresponding algebraic objects called the coins. A cain is an Abeliangroup with the coins as its elements equipped with . dot product. In the cain algebra, properties
such as conditional independence relations are repoesented by equations using appropriate coins.
$a$

One major advantage of the universal algebraic approach is that properties conceming probability density functions in general and conditional independence in particular can be derived automatically by transforming one coin equation to another coin equation by appealing to the cain
axioms, which themselves are in equational from. Thus the cain algebra is in contrast with otherwell-known axiomatic systems for conditional independence, such as the graphoid of Pearl andPaz (1987) and the separoid of Dawid (2001). The latter systems are built on some principal Properties of conditional independence regarded useful for general probabilistic reasoning, none of theaxioms in these systems being expressed in equations. A possible limitation of these latter approaches is that not all properties on probabilistic conditional independence can be derived fromthese finite set of axioms (Studen , 1992).
The purpose of this paper is to briefly introduce the cain algebra (Wang 2006, 2007) and showthat this algebraic system is consistent with the graphoid and the separoid.
$y$

2 The Cain Algebra
2.1 The Cainoida Partial order in L. It is further
Let $(L, \leq)$ be a lattice, where is a nonemPty set and$(L, \leq)$ is bounded below, that is, there exists a bottom
for any $x\in L$ .
with
that
suPPosed, and a set of elements are said mutually exclusive if
An element $x\in L$ is said nontrivial if
their pairwise meets are trivial. The direct product $L\otimes L=\{(x, y)|x, y\in L\}$ plays an importantrole in the theory. Note that $(x, y)\neq(y, x)$ if $x\neq y$ . To emphasize this asymmetry, we replace$(x, y)$ by using a new symbol(reads as) and making the following conventions$L$$\leq is$$\emptyset$$\emptyset\leq x$$x>\emptyset$$T_{y}^{x}$$V^{a}=1r_{l},$$\text{丁_{}y}=1P_{y},$$\pi_{\emptyset}^{\phi}=1$$coin- x- over- \mathcal{Y}$.

the
We call $1P$ the raising coin with context
the lowering coin with context , andmixed coin with raising context and lowering context . All these coins are called atom coins.
$x,$

$x$

$y$

$fi_{y}^{-}$$y$$1\Gamma_{y}$146

A coin is a concatenationof atom coins, with some atom coins (adjacent ornot) being possibly identical. Now denote by$n$$T\Gamma=ff_{y_{1}}^{1}\cdots 1\Gamma_{y_{\mathfrak{n}}}^{x_{n}}$$\mathfrak{C}=\{1\Gamma_{y_{1}}^{1}\cdots 1\Gamma_{y_{n}}^{n}|\iota r_{y_{1}}^{x_{1}},$$\cdots,$$\iota\lceil_{y_{n}^{n}}^{x}\in L\otimes L,$(1)$n\in N\}$

the set of all coins. Since can be any natural number, is an infinite set even if is finite. Notethat $L\otimes L=\{\rceil r_{y}|x, y\in L\}$ is a proper subset of C. In the set of coins , we introduce a binary, so that for any 丁
andwe have
dot oprator, :
$L$

$C$

$n$

$C$

$\cdot$$Cx\mathfrak{C}arrow C$$1t^{i}=\pi_{v_{1}}^{u_{1}}\cdots\pi_{v_{n}^{n}}^{u}$$=1r_{V1}^{x_{1}}\cdots\rceil r_{y_{m}}^{x_{m}}$$\rceil r\cdot W=W_{y}^{1}$...

$\text{架_{}m}^{m}$. 架1 . . .

(2)$\Gamma_{v_{\mathfrak{n}}}^{n}$

DEFINITION 2.1 (CAINOID). Let $(L, \leq)$ be a lattice with bottom Let
be the set of coins,is called cainoid iffor any Tr, $W,$
and . be defined by (2). An algebraic structureand $x,$ $y\in L$, the following hold:$\emptyset.$$(C, \cdot)$

Cl:
C2:
C3;

C4:
C5:

$1\Gamma\cdot 1\Gamma=$(丁.

$T\ulcorner$

1.丁$\mathfrak{C}of(l)$$\rceil\ulcorner’\in C$

$a$

架. 丁

). 架’

丁.

$=$

$(1\lceil^{l}\cdot V’’)$$=1\Gamma$$1\lceil^{oe}\cdot 1\Gamma_{x}=1$$\iota r_{\nu}=\rceil r^{v_{V}}\cdot \mathfrak{n}_{y}^{-}$(where$x>\emptyset$)

From the definition it is not hard to see that a cainoid
forms an Abelian
. The
lr,
may be regarded as algebraic abstractions of the joint probability density
coins
and
function $f(x)$ , the reciprocal $1/f(x)$ , and the conditional density function $f(x|y)$ , respectively. A
may then be regarded as the abstraction of the product $f(x_{1}|y_{1})\cdots f(x_{n}|y_{n})$ of
coin
conditional probability density functions. Axiom C5 may be regarded as the abstraction of thedefinition of conditional density function, $f(x|y)=f(x, y)/f(y)$ . With these interpretations, theidentity rv $=W_{x}1P1\Gamma_{y}(x>\emptyset, y>\emptyset)$ may be regarded as an anologue of the familiar Bayes’
theorem.
$\Psi^{oup}$$(\mathfrak{C}, \cdot)$$Tr_{x}$$T\rho_{y}$$\rceil r_{y_{1}^{1}}\cdots 1\Gamma_{y_{n}^{n}}^{x}$$n$

As a direct consequence of the axioms, we have the following $im\mu rtant$ result. In a cainoid
the embedding panial order $\leq can$ be represented by the identity: $x\leq y\Leftrightarrow W_{y}=1(x>\emptyset)$ . In
the cain algebra most of the problems will be reduced to the problem of solving or transformingsome coin equations to other coin equations. For this Purpose two following Properties are of basic
importance.
PROPOSITION 2.1 (RAISING-uP LAw). For any$x>\emptyset,$ $y,$ $z$$\rceil r_{l}^{\vee y}=P_{y\vee z}1\rho\Leftrightarrow\rceil r^{\nu\vee z}=\pi^{v}$

丁1of we have
$L$

(3)

$(x>\emptyset)$

The coinon the l.h. . of (3) is obtained by detaching the context from $y\vee z$ ofand raising using $W$ . To ensure the validity of the detachment, we need the $inde\mu ndence$$W_{l}^{\vee y}$

$s$

$y$

condition’, $1\nu^{p}=W1\Gamma^{l}$$y$$\rceil r_{y\vee\approx}$.

PROPOSITION 2.2 ( $LOWERINGrightarrow DOWN$ LAw). For any$x>\emptyset,$ $y,$ $z$$1\rho_{\nu\vee z}=\iota r_{z}^{v\nu_{1\ulcorner_{y}}}\Leftrightarrow W^{\vee z}=V^{v}1\Gamma^{z}$of we have$L$$(x>\emptyset)$

(4)

147
The coinon the l.h. . of (4) is obtained by lowering inusing , and joining
with . To ensure the validity ofjoining with , again we need the ‘independence condition’,. The following fact is also helpful for transforming coin equations.
$s$$T\nabla_{y\vee z}$

$y$

$z$

$y$

$\rceil\rho_{\chi}\vee\nu$$y$$1\ulcorner_{y}$$z$$W^{\vee z}=1T^{y}1\Gamma^{z}$

PROPOSITION 2.3. Let $x\vee z,$ $x\vee w,$ $y\vee z,$ $y\vee w$ be nontrivial. Then
$1T_{x}^{v\vee\approx}=Tr_{x}^{\vee w}T\Gamma$

where$\rceil\ulcorner\in C$$\cong$

架\vee z $=$ 架\vee w\rceil \Gamma(5)

is an arbitrary coin.

2.2 Canonical expraesions
To introduce filrther structues in a cainoid we now study canonical $\exp oessions$ of coins. Let丁be an arbitrary coin. A coin identity of the form 丁
is called an expressionof with length , where
are atom coins other than unity. There are infinitely many
expressions which are equivalent to one another. Two raising coins lr and $W$ , withand, are said mutually prime, if $x\neq y$ .
$\neq 1$$=F_{\nu 1}^{1}\cdots 1P_{\nu r}^{r}$$1\Gamma$$r$$\rceil r_{y1}1\ldots 1P_{y_{f}}^{r}$$x>\emptyset$$y>\emptyset$, there exists nonzero integers
THEOREM 2.1. For any arbitrary coin Tr, so that lr can be exp’essed ascoins $W^{1},i=1,$$\neq 1$$\cdots$$n_{i}$and mutually prime

$r$

(6)

丁 $=(\rceil r1)^{n_{1}}\cdots(P)$DEFINITION 2.2 (PRIME COIN). A raising coin lr is called

an expression$a$prime coin if there does not exist$\rceil r=(1r1)^{nl}\cdots(T^{r})^{n_{r}}$so that each $x_{i}<x$ for each $i=1,$
If

2.1.

$L$

$\cdots r$.

satisfies the descending chain condition (DCC) then we have a stronger result than $th\infty rem$

THEOREM 2.2. Suppose that satisfies the $DCC$. Then there exist nonzero integers
that every coinhas a unique expression$L$$n_{1},$ $\cdots$,$n_{r}$

so$1\Gamma\in \mathfrak{C}$\rceil 「 =where (i)$1r^{1},$$\cdots$$1r$ ‘

are prime; and (ii)

$($

(7)

架 $1)^{n_{1}}\cdots(1\Gamma’)^{n_{r}}$$1\Gamma^{x_{1}},$$\cdots$$\rceil r^{r}$

are mutually prime.

The unique expression given by (7) is called the canonical exPoession of T. is called theorder of rr, written as $|1\Gamma|=r$ ; and $x=_{1=1}^{r}x_{i}$ is called the context of , wrimen as 3(1r) $=x$ .
The context ? defines a function from the set of coins I to the lat\^uce with the propenies: (i)$?(t\Gamma)=?(1\Gamma^{-1})$ ,and (ii) sub-additivity:.
Now we make a further assumption that each nontrivial element has a canonicaljoin rePoesentation
$r$

$T$

$L$

$9(1\Gamma 1\Gamma’)\leq X(1\Gamma)\vee?(1f’)$$x$$x=x_{1}\vee x_{2}\vee\cdots\vee x_{n}$

(8)

148

, and
cannot be the join of a proper subset of$x_{i}\lla$is,,for somethat for all we have(ii) if
impliesthen$a\in A$ . This is possible for any finite join-semidistributive lattice ($J6nsson$ and Kiefer, 1962).

That is, (i) (8) is irredundant so that$x=\vee A$$A\subset L$$\{x_{1}, \cdots , x_{n}\}$$x$$\{x_{1}, \cdots x_{n}\}\ll A$$x_{i}$

by including all possible joins. Expanding
For (8) we shall write
we get a sublattice of L. We call the sublattice of generated
and meets of subsets ofby . The sub-lattice also induces a cainoid, which will be denoted by . Note that an elementof is necessarily contained in C.
$\mathfrak{U}(x)=\{x_{1}, \cdots x_{n}\}$$\mathfrak{U}(x)$$L$$L_{x}$$L_{x}$$\mathfrak{U}(x)$$L_{x}$$x$$\mathfrak{C}_{x}$$C_{x}$

induced by the ub-lattice
DEFINITION 2.3 (MARGINAL cAINOID). The cainoid
the marginal cainoid of . An element of is called marginal coin of .
$(C_{x}, \cdot)$$L_{x}$

is called

$x$

$a$

$C_{x}$$x$$s$

to denote an arbitrary marginal coin of . The set of all coins equivaWe use the notation
lent to rr with respect to is called, using standard group terminology, the coset of rr with respect. The coset is also referred to as theto . This coset is given byorbit of lr caused by the subgroup .
$x$$1\Gamma[x]$$x$$1\Gamma C_{x}$$1\Gamma C_{x}\equiv\{l\Gamma[x]1\ulcorner|\rceil\ulcorner[x]\in \mathfrak{C}_{x}\}$$x$$C_{x}$

2.3 The Cain
Now we shall introduce further $s\alpha uctures$ into a cainoid. This is done by considering an operation
analogous to the integration of ordinary functions.
an arbitrary. Now denote by
We have already introduced the symbols Tr and$x(\rceilr)=X(1\Gamma\{x\})=x$,$2(1\Gamma\{x\})=x$
we
have
while
that
.
Note
coin in with context$1\Gamma\{x\}$$1\Gamma[x]\in \mathfrak{C}_{x}$$X(1\Gamma[x])\leq$$\mathfrak{C}$$x$.

DEFINITION 2.4 (x-lNTEGRABILITY). Let $x\in L.$ A coin ] is said x-integrable if has context
with $y\geq x$ .
no less than , that is,$1\ulcorner$$\lceil$$1\Gamma=t\Gamma\{y\}$$x$is x-integrable
Note that when both rr and 11“ are x-integrable, it does not follow that
$x=x_{1}\veex_{2}$
instance,
irredundantly,
where
are
let
since some terms can cancell out. For
is not x-integrable because
then lrll“
join irreducible. Let$D(\eta^{-}1T^{t})=x_{2}<x$ . It follows then the set of x-integrable coins is not closed under dot product.To
define the coin integration we assume that is a complemented distributive lattice.
$1I^{-}1\ulcorner$$x_{1},$ $x_{2}$$1T^{\cdot}=1\Gamma^{x_{1}}1r2W=\text{丁_{}x_{1}}1P^{2}$$=(1\Gamma^{x_{2}})^{2}$$L$

DEFINITION 2.5 (COIN INTEGRATION). FOr an arbitrary $X\in$ L. let 3)(X) be the Set of all x:
into
integrable coins. The x-integration is afunction, denoted by , fromsuch that, there is a unique coin
, so that for any$\int_{x}$$\mathfrak{C}$$1\Gamma\{y\}\in \mathfrak{D}(x)$$\mathfrak{D}(x)$$\mathfrak{C}$.

$\int_{x}$$\mathfrak{D}(x)arrow$$1\Gamma\{y\wedge\overline{x}\}\in \mathfrak{C}$(9)$\int_{x}(1\Gamma\{y\})=.1\Gamma\{y\wedge\overline{x}\}$Further, the function$\int_{x}$satisfies the following properties (writing$\int 1\ulcorner dx$

instead$of \int_{x}($

丁 ):
$)$

(i) If $W$ is x-integrable then$\int 1\Gamma^{y}dx=W^{\wedge\overline{x}}$

(10)

149

(ii) Let $x=x_{1}\vee x_{2}$ with
$1\Gamma=]\ulcorner\{y_{1}\}1\Gamma\{y_{2}\}$(that is,$x_{1}\wedge x_{2}=\emptyset$

be x-integrable, where

Funher assume thatare relative complements $wrt$. ). Let
is -integrable.
-integrable and. Then it holds$x_{1}$andis$1[\{y_{1}\}$$x_{1}\wedge y_{2}=x_{2}\wedge y_{1}=\emptyset$$x$$x_{2}$$1\Gamma\{y_{2}\}$$x_{1}$$x_{2}$(11)$\int(1\ulcorner\{y_{1}\}1\Gamma\{y_{2}\})d(x_{1}\vee x_{2})=\int 1\ulcorner\{y_{1}\}dx_{1}\int 1\Gamma\{y_{2}\}dx_{2}$(iii) For any$\eta^{-}\in C$

it holds(12)$\int\rceil\ulcorner d\emptyset=\eta^{-}$丁 is defined for any. Axiom (10) is analogous to the definition ofNote that, so. Thus (10)thenmarginal probability density functions. Note that if, a special case of (12). Axiom (11) is an analogue of the following proprty
impliesof the conventional integration $\int f(x, z)g(y, z)$ $dxdy= \int f(x, z)dx\int g(y, z)dy$ .
$\int_{x}($$x\leq?(\rceil\ulcorner)$$)$$x=\emptyset$$\overline{x}=T$$y\wedge\overline{x}=y$$\int 1\Gamma^{y}d\emptyset=\nu$

DEFINITION 2.6 (CAIN). A cainoid$\mathfrak{C}$is called cain if Cfu rther satisfies the axioms (10)$a$$arrow(12)$.

Now we list some of the properties of the cain.

THEOREM 2.3. If is x-integrable and$1\Gamma$

THBORBM 2.4. For any $x,$ $y,$ $z\in L,$

THEOREM 2.5. If $x\geq z,$$y\wedge z=\emptyset$$x\wedge y=\emptyset$, then $\int 1\Gamma[y]I\Gamma dx=$ 丁 $[y] \int\eta^{-}dx$$1\Gamma_{y}^{x}=1\Gamma_{z}^{x}\Rightarrow T\rho_{y}=1P_{y\wedge z}$

then

.

$\int 1P_{y}dz=1\Gamma_{y}^{x\wedge\overline{z}}$Theorem 2.5 tells us how to compute a ‘conditionally marginal’ coin from a ‘conditional joint’
coin. The next theorem is an analogy of the fact that (conditional) probability density functions
integrate to unity.
THBOREM 2.6. For any $x,$ $y\in L$ with$x>\emptyset$

we have$\int V_{\nu}d(x\wedge\overline{y})=1$$(x>\emptyset)$

See Wang (2007) for more properties useful for transforming coin equations.

The following two theorems give two imponrt rules concerning certian $typs$ of coin equations. These rules will play important roles in transforming coin identitie .
$s$

THEOREM 2.7 (LAW OF NORMALIzATION). Let
Then$\rceil r_{y\vee z}=1\Gamma[\overline{z}]$$\rceil r^{\vee y\vee z}=1\Gamma[\overline{y}]^{\eta^{-}}[\overline{x}]$$\Rightarrow$$\Rightarrow$$\overline{x},\overline{y}$be the complements ofx andy respectively.

$\rceil r_{\nu\vee z}=1r_{y\wedge^{\overline{\frac{z}{z}}}}^{\wedge}$(13)$(x>\emptyset)$(14)$\rceil r^{\vee y\vee z}=\text{丁^{}(x\vee z)\wedge\overline{\nu}_{1\Gamma^{(y\vee x)\wedge\overline{x}}1\Gamma_{z\wedge 5\wedge\overline{y}}}}$

The following results are immediate consequences of Theorem 2.7. Thesebe more frequently met in aPplications than general forms (13)-(14).

$spe\dot{\alpha}al$cases will

150

COROLLARY 2.1. If $x,$ $y,$ are nontrivial and mutually exclusive then$z$$\Rightarrow$$1P_{y\vee z}=\rceil\ulcorner[\overline{z}]$架\ve \mbox{\boldmath $\nu$}\ve z

COROLLARY 2.2. For any
悟\vee y$=l\Gamma[\overline{y}]\rceil\ulcorner[\overline{x}]$$x,$ $y$(15)$(x>\emptyset)$$\mathfrak{s}r_{y\vee z}^{x}=\iota r_{y}$(16)$1\Gamma^{x\vee\nu\vee z}=1\Gamma^{x\vee z}P^{\vee z}1\Gamma_{l}$$\Rightarrow$

we have$1\Gamma_{y}=1\Gamma[\overline{y}]$$\Rightarrow$$=1\Gamma[\overline{y}]1\Gamma[\overline{x}]$$\Rightarrow$$1\Gamma_{y}=$架\wedge 9(17)$(x>\emptyset)$

加 r\wedge ae(18)$1r^{\vee y}=V^{A}$

When $x,$ are nontrivial and mutually exclusive then (17) and (18) reduce to, $res\mu cuvely$$y$$\rceil r_{y}=$$\rceil r^{\vee y}=1\ulcorner[\overline{y}]$丁$[\overline{y}]$丁$[\overline{x}]\Rightarrow$(19)$\rceil r_{y}=1r$$\Rightarrow$(20)$1\Gamma^{\vee\nu}=W1\Gamma^{y}$

We shall refer to the law of Nonrgalization as the N-Law for short. The N-Law is a powerfulprinciple that enables one to write an ‘ambiguous’ coin equation in an ‘exact’ form. This is useful, for instance, in situation when many atom coins enter into a coin equation but we are onlyinterested in relations conceming a small portion of them. Those ’nuisance’ coins can be treatedas ‘proportionality’ constant.
$s$

A large’ coin identity can give rise to many ‘small’ identities using the following Law ofMarginalization, or the M-Law.

THEOREM 2.8 (LAW OF MARGINALIZATION). If, then for any $a,$ $b\in L$,$x\wedge y=\emptyset$(21)$\rceil r_{z}^{\vee y}=\iota r_{l}W_{l}\Rightarrow 11_{z}^{\prec x\wedge a)\vee(y\wedge b)}=1r_{z}^{\wedge a}\rceil r_{z}^{y\wedge b}$

In particular,$lfz=\emptyset$then$\iota r^{v\nu}=$

評刷$\Rightarrow 1\Gamma^{\{x\wedge a)v(y\wedge b)}=\pi^{\alpha\wedge a}W^{\wedge b}$.

The following rule is also useful in marginalizing a ‘fat’ coin equation.
THEOREM 2.9. If $x,$ $y,$ are mumally exclusive then
$z$

(22)

$1\Gamma^{\vee\nu\vee z}=1\ulcorner[\overline{z}]W^{\vee z}\Rightarrow 1\Gamma^{\vee y}=]\ulcorner[\overline{z}]\Uparrow v$

3 The $Grapho\ddagger d$ and the Separoid
3.1 Conditional $Inde\mu ndence$
Now we shall assume thatwith bottom and top
DEFINITION 3.1.

$L$

is a Boolean algebra. That is, is a complemented distributive lattice. Let be the cain defined on L.

$T>\emptyset$$\emptyset$

$x$

$L$

$\mathfrak{C}$is said independent of conditional on , written
$y$

$z$

, iff

$x\Lambda y|z$$1\Gamma_{y\vee z}^{x}=T_{z}^{x}$

.

151

, and say in this case that is $inde\mu ndent$ of . So independenceif
We shall write
is a special case of conditional independence. Applying the R- and L-Laws, we immediately see
that, if
. If
oris equivalent to either
then, then. Note thatgive equivalent conditions forandis symmetric for and , i.e., $x\perp y|z\Rightarrow yJLx|z$ , unless $\emptyset=y<x\not\leq z$ .
$x\perp y$$x,$ $y,$$x,$ $y>\emptyset$$z>\emptyset$$x$$x\perp y|\emptyset$$x$$1\Gamma^{x\vee y\vee z}=V^{y\vee z}1r_{z}$$\iota r_{z}^{\vee y}=T_{z}^{x}P_{z}$$1\nabla_{y\vee z}=\iota r_{z}^{x}$$T\Gamma_{y}=\iota r$$y$$\iota r^{\vee y}=\iota r\iota r$$x\perp y$$x\perp- y|z$$y$

It can be shown that the embedding lattice order $x\leq y$ is equivalent to $x\perp x|y$ . It can also be$x\perp y|T,$ $x\perp y|y$ for any $x,$
shown that $y\leq z\Rightarrow x\perp y|z$ for any . For instance,. Ifthen for any we have $x\leq z\Rightarrow x\perp y|z$ .
$x\perp\emptyset|y,$$x$$\emptyset<x$

$y$

$y$

As an immediate consequence of the N-Law (16), we have the following seemingly weakerbut equivalent condition for conditional independence. For the usual probabilistic conditional$inde\infty ndence$ , this condition is commonly known as the Factorization Theorem.
THEOREM 3.1 (FACTORIZATION). If nontrivial elements$x\perp y|z\Leftrightarrow\pi^{a\vee\nu\vee z}=$where$\rceil\ulcorner[\overline{x}]$and 丁$[\overline{y}]$$x,$ $y,$ $z$

丁 [x-]

are also mutually exclusive, then(23)

$1\Gamma[\overline{y}]$are appropriate coins of the marginal cains$\mathfrak{C}_{\overline{x}}$and$C_{\overline{y}}$respectively.

As an illustration, if $D=\{1,2,3\}$ then any one of the following equations,gives a necessary and sufficient condition for $1\perp 2|3$ .
$1\Gamma_{3}^{12}=T_{3}^{1}1\Gamma_{3}^{2},$$1\Gamma^{13}1\Gamma_{3}^{2},1\Gamma^{123}=1\Gamma^{23}1\Gamma_{3}^{1},$$\text{丁_{}23}^{1}=I\Gamma_{3}^{1},$$\rceil\ulcorner^{123}=$$\rceil\ulcorner_{13}^{2}=I\ulcorner_{3}^{2}$

3.2 The Graphoid
The following properties of conditional $i\mathfrak{n}dependence$ can be derived from the axioms of the cain.
These $prop\iota ties$ play an $im\mu rtant$ role in statistical graphical models (Lauritzen, 1996).
THEOREM 3.2 (DECOMPOSITION).
$a\rfloor Lb|z$$Ifx\wedge y=\emptyset$.

THEOREM 3.3 (wEAK UNION). If $x,$ $y,$$w)$.

$z,$ $w$, then for any $a\leq x,$ $b\leq y$ it holds thatx ML$y|z\Rightarrow$are mutually exclusive, then $x1L(y\vee z)|w\Rightarrow x\perp y|(z\vee$

The following theorem gives a seemingly weaker sufficient and necessary condition for thejoint conditional $inde\mu ndencex\perp(y\vee z)|w$ . This condition is sometimes referred to as the contraction Property (Pear, 2000, P.ll).

THEOREM 3.4 (cONTRACTION). If $x,y,$ $z,w$ are nontrivial and mutually exclusive, then we have$x\perp y|(z\vee w)x\perp z|w$$\Leftrightarrow x\perp(y\vee z)|w$

THEOREM 3.5 (INTBRsBcTION). If $x,$ $y,$ $z,w$ are nontrivial and mutually exclusive, then$x\perp y|(z\vee w)$$\Leftrightarrow x\perp(y\vee z)|w$$x\perp z|(y\vee w)$

(24)

152

. defined on a Boolean algebra
Recall that a temary relation
all nontrivial and mutually exclusive elements we have$\cdot\coprod\cdot|$

Gl :
G2 :

:
$G4$ :
G5 :$G3$$x\coprod y|z\Rightarrow y$is called a graphoid, if for(Symmetry)

垣 $x|z$(Decomposition)$x\coprod(y\vee w)|z\Rightarrow xIJy|z$
$x$

$L$

垣 $(y\vee z)|w\Rightarrow x\coprod y|(z\vee w)$$x\coprod y|(z\vee w),$ $x\coprod z|w\Rightarrow x$ 垣 $(y\vee z)|w$$x\coprod y|(z\vee w),$ $x\coprod z|(y\vee w)$$\Rightarrow x$

IJ $(y\vee z)|w$(Weak union)(Contraction)(Intersection)

In the finitary case, $P^{ro}N^{rties}$ GI-G5 were discussed by Dawid (1979) and Spohn (1980). The
name graphoid was due to Pearl and Paz (1987), who used GI-G5 as axioms to characterize the re-lation between graphs and informational relevance; see also Pear1(200). The results of this section. is a graphoid. Properties of the classical probashow that if is a Boolean algebra, thenbilistic conditional independence are not limited to those discussed in the previous subsection. In
fact Studen (1992) showed that it is not $\mu ssible$ to give a finite characterization of conditional
independence relations. See Wang (2007) for discussions on more useful properties conceming
conditional independence.
$L$$\cdot JL\cdot|$$y$

3.3 The Separoid
The cain algebra is consistent with a stronger system than the graphoid. In this section we showthat the cain algebra satisfies the defining axioms of a strong separoid of Dawid $(2W1)$ . The
separoid includes several axiomatic systems, such as the orthogonoid and the graphoid, relevant
for formal reasoning using the concept of irrelevance of information.

The concept of a separoi was invented by Dawid $(2W1)$ . In the very last paragraph of his
paper, Professor Dawid concluded that New concepts of irrelevance’ in a wide variety of settings,
have been proliferating rapidly, and this can be expected to continue. It should be regarded as amatter of course, when any such new definition is Proposed, that a check be made to see whether
it satisfies the separoid axioms PI-P5. If not, departures from the axioms should be carefully
identified andjustified”. Dawid showed that both the orthgoid and the graphoid can be regarded asa special case of the separoid. In this section we show that the universal algebraic definition of thecain conditional independence does satisfy the defining axioms of the strong separiod.
$d$

DEFINITION 3.2 (SEPAROID). Let $(S, \leq)$ be ajoin-semilattice. Let

on S. Then$(S, \leq, \perp)$

is a

PL

$separo\ddagger d$$\cdot\perp-\cdot|$. be a ternary relation

if the following $h_{0}u$$x\perp y|x$$P2:x\perp y|z$$\Rightarrow y\perp x|z$$\Rightarrow x\perp w|z$
P3:$\Rightarrow x\perp y|(z\vee w)$
P4: $x1y|z\ w\leq y$$x\perpy|z\x\perpw|(y\veez)\Rightarrowx\perp(y\vee w)|z$P5:$x\perp y|z\ w\leq y$

REMARK 3.1. None of the axioms PI-P5 is equational in fom thus the descripnon ofa sepamid
as given in Definition 3.2 does not constitute a universal algebra.
$(S, \leq, \rfloor L)$

153

DEFINITION 3.3 (STRONG SEPAROID). A Sepamid
and the following additional properzy holds
P6: If z\leq y&w$x\perp y|$$\leq y$$(S, \leq, \perp)$

is Said StrOng if $(S, \leq)$ iS a lattiCe

thenz&x\perp ylw$\Rightarrow x\perp y|(z\wedge w)$

Now we show that PI-P6 are satisfied by a cain conditional independence,$\cdot\perp\cdot|\cdot$.

THEOREM 3.6. Let be a cain generated by a complemented distributive laOice $(L, \leq)$ . We
say that a temary relation $xJLy|z$ holds for nontrivial elements $x,y,$ inthe coin idenitity
holds in C Then $(L, \leq, \perp)$ is a strong separoid.
$\mathfrak{C}$$z$$L_{l}f$$1\Gamma_{z}^{x\vee\nu}=\iota r_{l}1\Gamma_{z}^{y}$

See Wang (2007) for details of the proof.

4 Discussions
In this paper we introduced a new universal algebraic system called the cain. This framework is
built $u\mu n$ some essential algebraic properties of the probability density functions. In the cain algebra conditional independence is defined through a coin equation, which can be easily transformed
into other equivalent equations using the rules of the algebra. In particular we have showed theconsistency with the well-known axiomatic systems of graphoid and the separoid. This universal algebraic approach provides possibilities for making statistical causal inference using the new
algebraic tools combing with modem techniques such as the Grobner basis theories.

References[1] Dawid, A. P. (1979). Conditional independence in statistical theory (with discussion). J. Ray.

Statist. Soc. Ser. $B411-31$ .

[2] Dawid, A. P. (2001). Separoids: a mathematical framework for conditional independence andirrelevance. Ann. Math. An. Intell. 32335-372.

[31 $J6nsson$ , B. an Kiefer, J. (1962). Finite sublattices of a free lattice. Canad. J. Math. 14487$d$497.

[4] Lauritzen, S. L. (1996). Graphical Models. Clarendon, Oxford.

[5] Pearl, J. (2000). Causalimodels, reasoning and inference. Cambridge University Press, New

York.

[6] $p_{ear1,J.andPaz,A.(1987)ra}re1ations.InAd_{\mathcal{V}}ancesinAm\dot ficiac_{f_{Intelligence}^{hoids:agra}b_{HoggandL.Soee1s,eds.)357-363,Nonh-}^{h- based1ogicforreasoningaboutre1ev\bm{t}ce}}$Holland, Amsterdam.

.

[71 $S\mu hn$ , W. (1980). Stochastic independence, causal independence, and shieldability. J. Phil.

Logic 9$73-\mathfrak{B}$

.

154

[8] Studenj, M. (1992). Conditional independence relations have no finite complete character-ization. In Transactions of the 1lth Prague Conference on Information Theory, Statistical
Decision Functions and Random Processes 377-396. Academia, Prague.

[9] Wang, .(2006). The coin algebra for conditional independence. 数理簿析研究所講究録 1506,$J$

Statistical Conditional Inference

and Its Related Topics, $2006\not\in 7H,$ $177- 196$ .

.

$[10]Wang,J.(2\alpha_{\xi_{toTheAnnal_{S}ofStatistics}^{ebra:auniversa1algebraic}}tionalindependence.SubmitteI7).Thecaina]$

approach for probabilistic condi-