Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking at a past homework solution and there is a part of it I don't understand. Specifically I'm talking about number 2 in this problem set:

Let $m=\lfloor(8/7)^{n/3}\rfloor$. Show that there exist distinct sets $A_1,A_2,\dots,A_m\subseteq[n]$ such that for all distinct $i,j,k\in[m]$ we have $A_i\cap A_j\nsubseteq A_k$.

Given $A_1, A_2, A_3,..., A_m$ which are subsets of $ [n] $. Can someone explain in detail why the probability of $A_i \cap A_j \subseteq A_k$ is equal to $(\frac7 8)^{n}$.

share|improve this question
    
For each $x \in [n]$, the three membership values can assume any of the eight (equally likely) possibilities except for one: $x \in A_i \wedge x \in A_j \wedge x \not\in A_k$. So each $x \in [n]$ is okay with independent probability $7/8$; hence all $n$ are okay with probability $(7/8)^{n}$. –  mjqxxxx Oct 16 '12 at 23:29

2 Answers 2

up vote 0 down vote accepted

Suppose that $A_i\cap A_j\subseteq A_k$. Then for each $r\in[n]$ one of the following must be true:

  1. $r\in A_i$ and $r\in A_j$ and $r\in A_k$.
  2. $r\in A_i$ and $r\notin A_j$, in which case it doesn’t matter whether $r\in A_k$.
  3. $r\notin A_i$ and $r\in A_j$, in which case it doesn’t matter whether $r\in A_k$.
  4. $r\notin A_i$ and $\notin A_j$, in which case it doesn’t matter whether $r\in A_k$.

Since each $r\in[m]$ is in any given $A_s$ with probability $\frac12$, the probability of (1) is $\frac12\cdot\frac12\cdot\frac12=\frac18$. The probability of (2) is $\frac12\cdot\frac12\cdot1=\frac14$, and exactly the same calculation gives the probability of (3) and the probability of (4). These four possibilities are mutually exclusive, so the probability that one of them is true is $\frac18+\frac14+\frac14+\frac14=\frac78$.

In other words, for each $r\in[n]$ the probability that $r$ behaves in one of the ways consistent with $A_i\cap A_j\subseteq A_k$ is $\frac78$. This is the case independently for each $r\in[n]$, so the probability that all of them behave properly is $\left(\frac78\right)^n$.

share|improve this answer

The sets $A_i$ were constructed by taking each element of $[n]$ with probability $\frac 12$. An element $p$ can render $A_i \cap A_j \subseteq A_k$ false if it is in $A_i$ and $A_j$ but not in $A_k$. This requires three choices to be right, so happens in $\frac 18$ of the cases. To have $A_i \cap A_j \subseteq A_k$ true, none of the elements can render it false, so the chance is $(\frac 78)^n$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.