How do you define “independence” in combinatorics?

Question

I feel like most definitions of “independence” are circular. Consider how we count the number of cards in a standard deck of cards: $|S times R| = |S||R|$, where $S$ is the set of suits, and $R$ is the set of ranks. That is, $$S = {text{Hearts, Diamonds, Spades, Clubs}}$$ and $$R = { 2,3,dots,text{King},text{Ace} }.$$ We know that $|S| = 4$ and $|R| = 13$, so $|S times R| = |S||R| = 4 cdot 13 = 52.$ In such an example, we define that they are independent, because they are disjoint subsets. But do we know that? In this example, it is “obvious.” What about examples where it is not obvious?

Sudix · Accepted Answer

Let's say you have a structure $S$. This structure is a combination of a few Attributes, each from a certain set of possible values.
If we let $A_1,...,A_n$ be the sets of the possible values for the corresponding attributes, then we can, pretty general, define the structure $S$ as follows:
$$
S:= {pmatrix{x_1\vdots\x_n}in ⨉_{i=1}^n A_imid Ppmatrix{x_1\vdots\x_n}   }
$$
Where $P$ is a predicate, i.e. it models our constraints, on which combinations of attributes are allowed.
Our goal, as usual in combinatorics, is determining $|S|$.
We say that the structure $S$ is independent of an attribute $A_i$ is (in the combinatoric sense), if:
$$
forall x_1in A_1,...,x_nin A_n,y_iin A_i:qquad P(x_1,...,x_i,...,x_n) = P(x_1,...,y_i,...,x_n)  
$$
Simply put this means that we don't need to look at the value of attribute $A_i$ to find out whether a specific instance of the structure is valid.
We therefore can fix a specific $x_iin A_i$ (which exactly we choose doesn't matter), and define
$$P':  ⨉_{k=1\ineq i}^n A_kto {text{True},text{False}}$$
via
$$P'(x_1,...,x_{i-1},x_{i+1},...,x_{n}) = P(x_1,...,x_{i-1},x_i,x_{i+1},...,x_{n})$$
In terms of the cardinality, this then means the following:
$$
|S| =|A_i|cdot  |{pmatrix{x_1\...\x_{i-1}\x_{i+1}\...\x_{n}}in ⨉_{k=1\kneq i}^n A_kmid P'pmatrix{x_1\...\x_{i-1}\x_{i+1}\...\x_{n}}   }|
$$
As for every tuple $pmatrix{x_1\...\x_{i-1}\x_{i+1}\...\x_{n}}$, the structure instance $pmatrix{x_1\...\x_{i-1}\x_i\x_{i+1}\...\x_{n}}$ is either valid for all choises of $x_i$, or for none of it.
To finish this, let's look at your example.
Our structure is the set of valid cards, where each card has the two attributes suit and rank.
Therefore we have $n=2$, $A_1:= {text{Hearts, Diamonds, Spades, Clubs}}, A_2:={ 2,3,dots,text{King},text{Ace} }$. 
Since we have no restrictions on our set members of $S$ besides that we have to pick from every attribute, we have further $P(x_1,x_2)=text{True}$.
So, our structure $S$ is in this case independent of both $A_1$ and $A_2$, and therefore we have $|S| = |A_1|cdot |A_2|$

Mike Earnest · Answer

Here is another view point. Independence is a property of partitions, not of individual sets. Namely, let $S$ be a finite set, and let ${X_1,dots,X_m}$ and ${Y_1,dots,Y_n}$ be two partitions of $S$ (meaning the $X_i$ are nonempty, disjoint, and have a union of $S$, and same for the $Y_i$). We say that these two partitions are independent if
$$
|X_icap Y_j|text{ is the same for all }iin {1,dots,m},jin {1,dots,n}
$$
For example, let $S$ be a deck of cards, and let
$$
X_1={text{the set of spades}}={Aspadesuit,2spadesuit,dots,Kspadesuit},\X_2={text{the set of hearts}},\ X_3={text{the set of clubs}}\
X_4={text{the set of diamonds}}
$$
and
$$
Y_1={text{set of aces}},Y_2={text{set of twos}},dots,Y_{13}={text{set of kings}}
$$
Since it is true that $|X_icap Y_j|=1$ for all $i,j$, we conclude these two partitions are independent.
A consequence of the definition of independence is that
$$
|S|=mcdot ncdot |X_1cap Y_1|
$$

Will Orrick · Answer

To answer the question in the title: you don't. Independence is a concept in probability theory, not in combinatorics. In your card example, there is no concept of the sets $S$ and $R$ being independent. What you can say is that, if all $52$ cards are equally likely to be chosen in some experiment, then the probability of a particular rank, say ace, is independent of a particular suit, say clubs. But if one of the cards is sticky, and hence more likely to be chosen than the others, independence is lost.
You can look up the standard definitions of independence: for events $E$ and $F$, the events are independent if $Pr(Ecap F)=Pr(E)Pr(F)$, or equivalently, if $Pr(Evert F)=Pr(E)$.
Also, be careful to distinguish the concepts of disjointness and independence. They are not related.
Added: It looks like your question is really about sets that have the structure of a Cartesian product. If $S=Atimes B$ and all elements of $S$ are equally likely, then the events $X=$"first element of tuple is $x$" and $Y=$"second element of tuple is $y$" are independent in the usual probability sense. These events are the sets $X={(x,b)vert bin B}$ and $Y={(a,y)vert ain A}$. Now $Pr(Xcap Y)=Pr({(x,y)})=frac{1}{lvert Srvert}=frac{1}{lvert Arvertlvert Brvert}$, while $Pr(X)Pr(Y)=frac{lvert Brvert}{lvert Srvert}frac{lvert Arvert}{lvert Srvert}=frac{lvert Brvertlvert Arvert}{(lvert Arvertlvert Brvert)^2}=frac{1}{lvert Arvertlvert Brvert}$, so that the first definition of independence is satrisfied. This independence holds regardless of whether $A$ and $B$ are disjoint or not. (They might even be the same set.)

How do you define “independence” in combinatorics?

3 Answers

Add your own answers!

Ask a Question