A sample space \(\Omega\) is the set of all possible outcomes of an experiment.
- Toss a coin: \(\Omega=\{H,T\}\).
- Roll a die: \(\Omega=\{1,2,3,4,5,6\}\).
- Toss two coins: \(\Omega=\{(H,H),(H,T),(T,H),(T,T)\}\).
- Room allocation Problem: Suppose 10 students need to be allocated in 10 rooms. \[ \Omega=\{(w_{1},\dots,w_{10}) \mid w_{i} \in \{1,\dots,10\}, w_i \neq w_j \text{ for } i \neq j\} \] \[ |\Omega| = \text{total possibilities} = 10 \times 9 \times \dots \times 1 = 10! \]
- Coupon collecting problem without replacement: There are coupons in a bag, and coupons are collected one by one without replacement.
Random placement of \(r\) balls (distinguishable/Labelled) in \(n\) Urns/Cells (distinguishable/Labelled).
Example: \(r=2\), \(n=2\)
\[ |\Omega| = n^r \]
\[ \Omega=\{(w_{1},w_{2}) \mid w_{1},w_{2} \in \{1,2\}\} = \{(1,2),(2,1),(1,1),(2,2)\} \]
In general: \[ \Omega=\{(w_{1},\dots,w_{r}) \mid w_{1},\dots,w_{r} \in \{1,2,\dots,n\}\} \]
Note:
- \(w_{1}=4\) means 1st ball is placed in 4th cell.
- \(w_{2}=1\) means 2nd ball is placed in 1st cell.
- Thus, \(w_{i}\) denotes the position of the \(i\)-th ball.
- Toss a coin: \(r=1\), \(n=2\).
- Roll two dice: \(r=2\), \(n=6\).
- Birthdays: Possible configuration of the birthdays of 100 students. In this case, \(r=100\), \(n=365\).
- Random digits: The possible number of PIN (4-digit) numbers. \(n=10\), \(r=4\).
- Coupon Collecting: There are 10 coupons in a bag and choose three coupons with replacement. In this case: \(r=3\), \(n=10\).
Placement of \(r\) indistinguishable/unlabelled balls in \(n\) Labelled Cells/bins. Find the number of distinguishable configurations.
Example: \(r=2\), \(n=2\)
\[ \Omega=\{(w_{1},w_{2}) \mid w_{1}+w_{2}=2, \; w_{1},w_{2} \geq 0\} = \{(1,1),(2,0),(0,2)\} \]
In general: \[ \Omega=\{(w_{1},\dots,w_{n}) \mid w_{1}+\dots+w_{n}=r, \; w_{1},\dots,w_{n} \geq 0\} \]
Note: \(w_{i}\) denotes the number of balls in \(i\)-th cell.
A subset of a sample space is known as an event.
Examples:
- Toss a coin: \(\Omega=\{H,T\}\), \(E=\{H\}\).
- Roll a die: \(\Omega=\{1,2,\dots,6\}\), \(E=\{2,4,6\}\).
- Urn-ball Problem (r balls in n cells): \(E = \text{1st cell is empty}\).
- \(r\)-labelled balls, \(n\)-labelled cells: \[ E=\{(w_{1},\dots,w_{r}) \mid w_{1},\dots,w_{r} \in \{2,\dots,n\}\} \]
- \(r\)-indistinguishable balls, \(n\)-labelled cells: \[ E=\{(w_{1},\dots,w_{n}) \mid w_{1}=0, \; w_{1}+\dots+w_{n}=r, \; w_{i} \geq 0\} \]
Sample space \(\Omega\) = the collection of all events.
Example: If \(|\Omega| < \infty\) then \(F=P(\Omega)\) (Power set of \(\Omega\)).
A map \(P: F \rightarrow [0,1]\) is said to be a probability measure on \(\Omega\) if the following hold:
- \(P(\Omega)=1\), \(P(\emptyset)=0\).
- If \(E_{1}, E_{2}, \dots\) is a sequence of mutually disjoint events (i.e. \(E_{i} \cap E_{j}=\emptyset\) for \(i \neq j\)), then \[ P\left(\bigcup_{i=1}^{\infty}E_{i}\right)=\sum_{i=1}^{\infty}P(E_{i}) \]
Then \(P(E)\) is said to be the probability of event \(E\).
- If \(E_{1},\dots,E_{n}\) are mutually disjoint, then \[ P\left(\bigcup_{i=1}^{n}E_{i}\right)=\sum_{i=1}^{n}P(E_{i}) \] In particular, for \(n=2\): \(P(E_{1}\cup E_{2})=P(E_{1})+P(E_{2})\).
- \(P(E^c)=1-P(E)\).
- If \(E \subseteq F\), then \(P(F \setminus E)=P(F)-P(E)\) and \(P(E) \le P(F)\).
- For any two events \(E\) and \(F\): \[ P(E \cup F) = P(E)+P(F) - P(E \cap F) \]
- \(\Omega=\{H,T\}\), \(P(\{H\})=\frac{2}{3}\) and \(P(\{T\})=\frac{1}{3}\) \(\implies\) \(P\) is a probability measure.
- \(\Omega=\{H,T\}\), \(P(\{H\})=p\) and \(P(\{T\})=1-p\), \(0 \le p \le 1\) \(\implies\) \(P\) is a probability measure.
- \(\Omega=\{H,T\}\). If \(P(\{H\})=\frac{1}{2}\) and \(P(\{T\})=\frac{1}{2}\), then all outcomes are equally likely.
- Roll a die: \(\Omega=\{1,2,3,4,5,6\}\). If \(P(\{1\})=\frac{2}{9}=P(\{3\})=P(\{5\})\) and \(P(\{2\})=P(\{4\})=P(\{6\})=\frac{1}{9}\), then \(P\) is a probability measure.
Let \(E = \text{outcome is even}\). Then \(E=\{2,4,6\}\). \[ P(E)=P(\{2\})+P(\{4\})+P(\{6\})=\frac{1}{9}+\frac{1}{9}+\frac{1}{9}=\frac{1}{3} \] - If all outcomes are equally likely then \[ P(E)=P(\{2\})+P(\{4\})+P(\{6\}) = \frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{3}{6}=\frac{1}{2} \]
Throughout, unless specified, we assume that all outcomes are equally likely.
If \(|\Omega| < \infty\) and all outcomes are equally likely, then \(P(\{x\})=\frac{1}{|\Omega|}\) for all \(x\).
Let \(E \subseteq \Omega\). Then \(P(E)=\frac{|\{x \mid x \in E\}|}{|\Omega|}=\frac{|E|}{|\Omega|}\).
Suppose \(n\) rooms need to be allotted to \(n\) students. Find the probability that the \(k\)-th student gets the room no. 1.
Solution:
\(\Omega=\{(w_{1},\dots,w_{n}) \mid w_{i} \in \{1,\dots,n\}, w_i \neq w_j \text{ for } i \neq j\}\).
\(|\Omega|=n \times (n-1) \times \dots \times 3 \times 2 \times 1=n!\)
\(E=\{(w_{1},\dots,w_{n})\in\Omega \mid w_{k}=1\}\). As \(w_{k}=1\), we have \((n-1)\) choices for the remaining.
\(|E|=(n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1=(n-1)!\)
\[ P(E)=\frac{|E|}{|\Omega|}=\frac{(n-1)!}{n!}=\frac{1}{n} \]
A drunkard man is given \(n\) keys of which only one fits his door. He tries them successively (sampling without replacement). Find the probability that he opens the door in the \(k\)-th trial.
Solution: Same as problem 1. Probability is \(\frac{1}{n}\).
Suppose that each of \(n\) men at a party throws his hat into the center of the room. The hats are mixed up, and then each man randomly selects a hat. Find the probabilities of the following events.
- \(E_{1}\): 1st person selects his own hat.
- \(E_{2}\): at least one man selects his own hat.
- \(E_{3}\): none of the men selects his own hat.
Solution:
\(\Omega=\{(w_{1},\dots,w_{n}) \mid w_{i} \in \{1,\dots,n\}, w_i \neq w_j \text{ for } i \neq j\}\).
\(|\Omega|=n!\)
- (i) \(E_{1}=\\{(w_{1},\dots,w_{n})\in\Omega \mid w_{1}=1\}\).
\(|E_{1}|= 1 \times (n-1) \times \dots \times 2 \times 1=(n-1)!\)
\[ P(E_{1})=\frac{|E_{1}|}{|\Omega|}=\frac{(n-1)!}{n!}=\frac{1}{n} \] - (ii) Observe that \(P(E_{3})=1-P(E_{2})\).
We calculate \(P(E_{2})\) using the inclusion-exclusion formula.
Let \(A_{1},A_{2},\dots,A_{n}\) be \(n\) events. Then
\[ P\left(\bigcup_{i=1}^{n}A_{i}\right) = \sum_{i=1}^{n}P(A_{i}) - \sum_{i_1 < i_2}P(A_{i_1} \cap A_{i_2}) + \sum_{i_1 < i_2 < i_3}P(A_{i_1} \cap A_{i_2} \cap A_{i_3}) - \dots + (-1)^{n+1}P(A_{1} \cap A_{2} \cap \dots \cap A_{n}). \]Using this formula, we proceed to calculate \(P(E_{2})\) for Problem 3.
Note that \(E_{2}=\bigcup_{i=1}^{n}A_{i}\), where \(A_{i}=\{(w_{1},\dots,w_{n})\in\Omega \mid w_{i}=i\}\), \(1 \le i \le n\).
Again, \(A_{1}=\{(w_{1},\dots,w_{n}) \mid w_{1}=1\} \implies |A_{1}|=(n-1)!\).
\(A_{1} \cap A_{2}=\\{(w_{1},\dots,w_{n})\in\Omega \mid w_{1}=1, w_{2}=2\} \implies |A_{1} \cap A_{2}|=(n-2)!\).
\(\dots\)
\(A_{1} \cap \dots \cap A_{n}=\\{(w_{1},\dots,w_{n})\in\Omega \mid w_{i}=i, \forall 1 \le i \le n\} \implies |A_{1} \cap \dots \cap A_{n}|=1\).
Hence,
\[ P(E_{2}) = n \cdot \frac{(n-1)!}{n!} - \binom{n}{2}\frac{(n-2)!}{n!} + \binom{n}{3}\frac{(n-3)!}{n!} - \dots + (-1)^{n+1}\frac{1}{n!} \] \[ = 1 - \frac{1}{2!} + \frac{1}{3!} - \dots + (-1)^{n+1}\frac{1}{n!} \]For \(n=3\):
\[ P(E_{1} \cup E_{2} \cup E_{3}) = P(E_{1})+P(E_{2})+P(E_{3}) - P(E_{1} \cap E_{2}) - P(E_{2} \cap E_{3}) - P(E_{3} \cap E_{1}) + P(E_{1} \cap E_{2} \cap E_{3}). \]For \(n=2\):
\[ P(E_{1} \cup E_{2}) = P(E_{1})+P(E_{2}) - P(E_{1} \cap E_{2}). \]Proof for \(n=2\):
By property of \(P\), we have:
\(P(E_{1} \cup E_{2}) = P(E_{1} \cap E_{2}^c) + P(E_{2} \cap E_{1}^c) + P(E_{1} \cap E_{2})\).
Again, \(P(E_{1}) = P(E_{1} \cap E_{2}^c) + P(E_{1} \cap E_{2}) \implies P(E_{1} \cap E_{2}^c) = P(E_{1}) - P(E_{1} \cap E_{2})\).
Similarly, \(P(E_{2} \cap E_{1}^c) = P(E_{2}) - P(E_{1} \cap E_{2})\).
Thus,
\(P(E_{1} \cup E_{2}) = [P(E_{1}) - P(E_{1} \cap E_{2})] + [P(E_{2}) - P(E_{1} \cap E_{2})] + P(E_{1} \cap E_{2}) = P(E_{1}) + P(E_{2}) - P(E_{1} \cap E_{2})\).
Suppose \(r\) balls are placed in \(n\) boxes. Find the probability that at least one box is empty in the following cases:
- (i) balls and boxes are labelled.
- (ii) balls are unlabelled but boxes are labelled.
Solution:
Let \(A_i\) denote the event that the \(i\)-th box is empty.
\(E = \text{at least one box is empty} = \bigcup_{i=1}^{n} A_{i}\).
Apply inclusion-exclusion:
Case (i):
In this case, \(\Omega = \{(w_{1},\dots,w_{r}) \mid w_{1},\dots,w_{r} \in [n]\}\).
\(|\Omega| = n \times n \times \dots \times n = n^{r}\).
\(A_{i} = \{(w_{1},\dots,w_{r}) \in \Omega \mid w_{1},\dots,w_{r} \in [n] \setminus \{i\}\}\).
\(|A_{i}| = (n-1)^{r} \implies P(A_{i}) = \left(\frac{n-1}{n}\right)^r = \left(1-\frac{1}{n}\right)^{r}\).
\(\implies P(A_{1} \cap A_{2}) = \left(1-\frac{2}{n}\right)^{r}\).
Putting these values in (*) we get the result.
Case (ii):
Let \(E_{1} = \text{each box is non-empty}\).
\(E = E_{1}^{c} \implies P(E) = 1 - P(E_{1})\). \quad (**)
\(\Omega = \{(w_{1},\dots,w_{n}) \mid w_{1}+\dots+w_{n}=r, \quad w_{i} \ge 0\}\).
\(|\Omega| = \binom{n+r-1}{n-1}\).
\(E_{1} = \{(w_{1},\dots,w_{n}) \mid w_{1}+\dots+w_{n}=r, \quad w_{i} \ge 1\}\).
Note, \(|E_{1}| = 0\) if \(r < n\).
Assume, \(r \ge n\). Then \(|E_{1}| = \binom{r-1}{n-1}\).
We have the result from (**).
A 5-card poker hand is said to be a Full house if it consists of 3 cards of the same denomination and 2 other cards of the same denomination (of course, different from the first denomination). Thus, a full house is three of a kind plus a pair. What is the probability that one is dealt a full house?
Solution:
The set of all cards can be written as: \(S = \{(x,y) \mid 1 \le x \le 4, \ 1 \le y \le 13\}\).
\(\Omega = \{\{w_{1},\dots,w_{5}\} \mid w_{1},\dots,w_{5} \in S\}\).
\(|\Omega| = \binom{52}{5}\).
\(E = \text{Full house}\).
\(E = \{\{w_{1},\dots,w_{5}\} \in \Omega \mid w_{1}(2)=w_{2}(2)=w_{3}(2), \ w_{4}(2)=w_{5}(2), \ w_{1}(2) \neq w_{4}(2)\}\).
(Here \(w_i(2)\) denotes the 2nd coordinate, i.e., the denomination).
Number of choices:
Suppose 60% of the students in a school passed in both maths and english. 20% of them failed in maths and 30% failed in english. Find the probability that a student:
- (1) failed in maths or english.
- (2) failed in both maths and english.
Solution:
In this case, no need to write sample space & event space.
Let \(E_{1} = \text{students failed in mathematics}\).
Let \(E_{2} = \text{students failed in english}\).
Given, \(P(E_{1}) = 20\% = \frac{2}{10}\).
\(P(E_{2}) = 30\% = \frac{3}{10}\).
\(P(E_{1}^{c} \cap E_{2}^{c}) = 60\% = \frac{6}{10}\). \quad (Passed in both)
(1) \(E = \text{failed in maths or english}\).
\(E = E_{1} \cup E_{2}\).
(2) \(F = \text{failed in both maths and english}\).
\(F = E_{1} \cap E_{2}\).
As \(P(E_{1} \cup E_{2}) = P(E_{1}) + P(E_{2}) - P(E_{1} \cap E_{2})\), we have: