Probabilistic Method – 1

Q.1. Let A_1, \ldots, A_n and B_1, \ldots, B_n be distinct subsets of \mathbb{N}, such that:

  • \forall i, A_i \cap B_i = \phi.
  • \forall distinct i,j (A_i \cap B_j) \cup (A_j \cap B_i) \neq \phi.

Prove that, for every real 0 \leq p \leq 1, \sum_i {p^{|A_i|} (1-p)^{|B_i|}} \leq 1.

Solution. Let us create a random subset R by sampling each element of \mathbb{N} with probability p.

Let E_i denote the event that R contains all elements of A_i and none of B_i. Pr [E_i] = p^{|A_i|} (1-p)^{|B_i|}.

Now, the events E_i are pairwise disjoint.

Therefore, \sum_i {p^{|A_i|} (1-p)^{|B_i|}} = Pr[ some E_i occurs] \leq 1.

--

Q.2. Let A_1, \ldots, A_n and B_1, \ldots, B_n be distinct subsets of \mathbb{N} such that:-

  • \forall i, A_i \cap B_i = \phi.
  • \forall distinct i, j, A_i \cap B_j \neq \phi.
  • \forall i, |A_i| =r, |B_i| = s.

Prove that n \leq {r+s} \choose {r}.

Solution.

Consider a random permutation of the universe X consisting of all elements in the sets A_i, B_i.

Let E_i denote the event that all elements of A_i occur before every element of B_i in the permutation.

Pr [ E_i] = { {r+s} \choose {r}}^{-1}.

Now, the events E_i are pairwise disjoint.

Therefore, n. {{r+s} \choose {r}}^{-1} \leq 1.

--

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: