Vandermone's SRSWR | MStat 2017 PSB Problem 3

This is a beautiful problem form ISI MStat 2017 PSB Problem 3, where we use the basics of Bijection principle and Vandermone's identity to solve this problem.

Problem

Consider an urn containing 5 red, 5 black, and 10 white balls. If balls are drawn without replacement from the urn, calculate the probability that in the first 7 draws, at least one ball of each color is drawn.

Prerequisites

Algebrify the problem
Vandermone's Identity $${{n_{1}+\cdots+n_{p}} \choose m} = \sum_{k_{1}+\cdots+k_{p}=m} {n_{1} \choose k_{1}} \times {n_{2} \choose k_{2}} \times \cdots \times {n_{p} \choose k_{p}}$$

Bijection Principle

Solution

It may give you the intuition, there is atleast in the problem, so let's do complementing counting. Okay! I suggest you to travel that path to help you realize the complexity of that approach.

Nevertheless, let's algebrify the problem.

You want to select $x_1$ red balls, $x_2$ blue balls, and $x_3$ white balls so that $x_1 + x_2 + x_3 = 7$.

Now, $ 1 \leq x_1 \leq 5$, $1 \leq x_2 \leq 5$ and $1 \leq x_3 \leq 10$ represents our desired scenario.

$ 0 \leq x_1 \leq 5$, $0 \leq x_2 \leq 5$ and $ 0 \leq x_3 \leq 10$ denotes total number of cases.

Now, for each such triplet ($x_1, x_2, x_3$) of the number of balls of each colour we have selected, we can select them in $ { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} $.

Let $ P = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 0 \leq x_1 \leq 5, 0 \leq x_2 \leq 5, 0 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls =

$$ \sum_{(x_1, x_2, x_3) \in P} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} = { {5 + 5 + 10} \choose { x_1 + x_2+ x_3} } = { {5 + 5 + 10} \choose {7} }$$

$ Q = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 1 \leq x_1 \leq 5, 1 \leq x_2 \leq 5, 1 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in Q} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3}$$

Let, $ R = \{ (z_1, z_2, z_3) | z_1 + z_2 + z_3 = 4, 0 \leq z_1 \leq 4, 0 \leq z_2 \leq 4, 0 \leq z_3 \leq 9 \} $.

Observe that $Q$ has a bijection with $R$. $ x_i = z_i +1$.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in R} { 4 \choose z_1} \times {4 \choose z_2 } \times {9 \choose z_3} = { {4 + 4 + 9} \choose { z_1 + z_2+ z_3} } = { {4 + 4 + 9} \choose {4} }$$

Exercises

Prove the Vandermone's Identity.
Find the Probability.
Generalize the problem to general numbers and prove it.
Generalize the problem where the lower bounds of $x_i$ are $m_i$.
What if there are upper bounds on $(x_1, x_2, x_3)$? [ Hint: Generating Functions ].

Stay Tuned! Stay Blessed!

Problem

Consider an urn containing 5 red, 5 black, and 10 white balls. If balls are drawn without replacement from the urn, calculate the probability that in the first 7 draws, at least one ball of each color is drawn.

Prerequisites

Algebrify the problem
Vandermone's Identity $${{n_{1}+\cdots+n_{p}} \choose m} = \sum_{k_{1}+\cdots+k_{p}=m} {n_{1} \choose k_{1}} \times {n_{2} \choose k_{2}} \times \cdots \times {n_{p} \choose k_{p}}$$

Bijection Principle

Solution

It may give you the intuition, there is atleast in the problem, so let's do complementing counting. Okay! I suggest you to travel that path to help you realize the complexity of that approach.

Nevertheless, let's algebrify the problem.

You want to select $x_1$ red balls, $x_2$ blue balls, and $x_3$ white balls so that $x_1 + x_2 + x_3 = 7$.

Now, $ 1 \leq x_1 \leq 5$, $1 \leq x_2 \leq 5$ and $1 \leq x_3 \leq 10$ represents our desired scenario.

$ 0 \leq x_1 \leq 5$, $0 \leq x_2 \leq 5$ and $ 0 \leq x_3 \leq 10$ denotes total number of cases.

Now, for each such triplet ($x_1, x_2, x_3$) of the number of balls of each colour we have selected, we can select them in $ { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} $.

Let $ P = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 0 \leq x_1 \leq 5, 0 \leq x_2 \leq 5, 0 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls =

$$ \sum_{(x_1, x_2, x_3) \in P} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} = { {5 + 5 + 10} \choose { x_1 + x_2+ x_3} } = { {5 + 5 + 10} \choose {7} }$$

$ Q = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 1 \leq x_1 \leq 5, 1 \leq x_2 \leq 5, 1 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in Q} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3}$$

Let, $ R = \{ (z_1, z_2, z_3) | z_1 + z_2 + z_3 = 4, 0 \leq z_1 \leq 4, 0 \leq z_2 \leq 4, 0 \leq z_3 \leq 9 \} $.

Observe that $Q$ has a bijection with $R$. $ x_i = z_i +1$.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in R} { 4 \choose z_1} \times {4 \choose z_2 } \times {9 \choose z_3} = { {4 + 4 + 9} \choose { z_1 + z_2+ z_3} } = { {4 + 4 + 9} \choose {4} }$$

Exercises

Prove the Vandermone's Identity.
Find the Probability.
Generalize the problem to general numbers and prove it.
Generalize the problem where the lower bounds of $x_i$ are $m_i$.
What if there are upper bounds on $(x_1, x_2, x_3)$? [ Hint: Generating Functions ].

Stay Tuned! Stay Blessed!