3
$\begingroup$

Source: Example 1.11, p 26, *Introduction to Probability (1 Ed, 2002) by Bertsekas, Tsitsiklis.

Hereafter abbreviate graduate students to GS and undergraduate students to UG.

Example 1.11. A class consisting of 4 graduate and 12 undergraduate students is randomly divided into 4 groups of 4. What is the probability that each group includes a GS? We interpret “randomly” to mean that given the assignment of some students to certain slots, any of the remaining students is equally likely to be assigned to any of the remaining slots.

Solution: We then calculate the desired probability using the multiplication rule, based on the sequential description shown in Fig. 1.12. Let us denote the four GS by 1, 2, 3, 4, and consider the 4 events
$A_1$ = {GS 1 and 2 are in different groups},
$A_2$ = {GS 1, 2, and 3 are in different groups},
$A_3$ = {GS 1, 2, 3, and 4 are in different groups}.

We will calculate $\Pr(A_3)$ using the multiplication rule:

$\Pr(A_3) = \Pr(A_1 ∩ A_2 ∩ A_3) = \Pr(A_1)\Pr(A_2 |A_1) \Pr(A_3 \mid A_1 \cap A_2)$. $\qquad [...]$

  1. How is $\Pr(A_3) = \Pr(A_1 ∩ A_2 ∩ A_3)$?

  2. I understand that the question asks for $\Pr(A_1 ∩ A_2 ∩ A_3)$; but how would you know (or divine) to reinterpret and then rewrite $\Pr(A_1 ∩ A_2 ∩ A_3)$ as $\Pr(A_3)$? 1 appears the key but tricky but step in formulating this problem.

$\endgroup$
4
$\begingroup$
  1. How is $\Pr(A_3) = \Pr(A_1 ∩ A_2 ∩ A_3)$?

If GS 1, 2, 3, and 4 are in different groups, then

  • GS 1, 2, and 3 are in different groups; and
  • GS 1 and 2 are in different groups.

Therefore, if $A_3$, then $A_2$ and $A_1$.

In set-theoretic terms, $A_3 \subseteq A_2 \subseteq A_1$. The intersection of a set with any one of its subsets is the subset. Therefore, $A_1 \cap A_2 \cap A_3 = (A_1 \cap A_2) \cap A_3 = A_2 \cap A_3 = A_3$.

  1. I understand that the question asks for $\Pr(A_1 ∩ A_2 ∩ A_3)$; but how would you know (or divine) to reinterpret and then rewrite $\Pr(A_1 ∩ A_2 ∩ A_3)$ as $\Pr(A_3)$? 1 appears the key but tricky but step in formulating this problem.

The motivation behind recasting $\Pr(A_3)$ as $\Pr(A_1 \cap A_2 \cap A_3)$ is a desire to work with conditional probabilities, such as the ones in $\Pr(A_1) \Pr(A_2 \mid A_1) \Pr(A_3 \mid A_1 \cap A_2)$. In this light, $\Pr(A_1 \cap A_2 \cap A_3)$ acts a bridge to conditional probabilities.

When you ask how I would know to recast the problem in terms of conditional probabilities, I assume you mean how should you have known. In short, you shouldn't have known! You encountered the problem as an example in a textbook. The purpose of the example is to teach you how to solve problems of this sort. You were expected not to know the method of solution beforehand. (If, to the contrary, you often do know the method of solution beforehand, then you are reading below your level.)

Take this example as a lesson: The relationship between probabilities of intersections and conditional probabilities can be a useful one to exploit when encountering either. Now, when you encounter a similar problem in the exercises, you should know to consider recasting the problem in terms of conditional probabilities.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. About 2 though, I was referring to the solver of this problem, and not to the authors? Your writing that a desire to work with conditional probabilities pertains to the authors, and not students (who may not think of Conditional Pr). $\endgroup$ – NNOX Apps Feb 3 '16 at 3:28
  • 2
    $\begingroup$ I have responded in my answer per your request. To quote Brualdi, "The implication is that with combinatorics, as with mathematics in general, the more problems one solves, the more likely one is able to solve the next problem." You, as a student, are not expected to have a full toolbox of tools for tackling combinatorial problems. After studying this problem, however, you should have added a new tool to your toolbox. I hope that helps! $\endgroup$ – Andrew Feb 6 '16 at 15:24
1
$\begingroup$

An alternative solution:


The number of ways to arrange the $16$ students in a line and then split it into $4$ equal segments:

$$16!=20922789888000$$


The number of ways to do it such that each segment contains a graduate student:

$$\binom{4}{1}\cdot\binom{12}{3}\cdot4!\cdot\binom{3}{1}\cdot\binom{9}{3}\cdot4!\cdot\binom{2}{1}\cdot\binom{6}{3}\cdot4!\cdot\binom{1}{1}\cdot\binom{3}{3}\cdot4!=2942985830400$$


Hence the probability of each segment containing a graduate student:

$$\frac{2942985830400}{20922789888000}=\frac{64}{455}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1. I hope that others will upvote your answer (as I did), which I find as equally as beneficient and helpful as the others. So please accept my assurance that I accepted another answer not because of inequity between answers, but because SE presently allows only one acceptance and so I have used my acceptance to aid those with fewer reputation points. $\endgroup$ – NNOX Apps Feb 7 '16 at 7:03
  • $\begingroup$ @LePressentiment: No problem :) $\endgroup$ – barak manos Feb 7 '16 at 9:26
1
$\begingroup$

The specifics of your actual questions (about how $A_3=A_3\cap A_2\cap A_1$ and such) seem to be adequately answered above.

Here instead, I provide an alternative solution to the stated problem which may be more intuitive than the book's approach. Let us approach this via direct counting.

Temporarily assume that the four groups are considered distinct (this will help us with our counting attempts but is not necessary to do. It does not have any adverse affect on the results however).

Let $U=\{\text{all ways in which the sixteen people can break into four distinct groups of four}\}$. How many ways can the sixteen people break into four distinct groups of four? This will be our sample space.

We have then $|U|=\binom{16}{4,4,4,4}=\frac{16!}{4!4!4!4!}$

1. If you wanted to consider the problem where groups are considered identical, our sample space changes and we would have $|U|=\frac{1}{4!}\binom{16}{4,4,4,4}$ instead. Again, it is easier for me to think using the other sample space since there is the frustration of having to deal with the symmetries involved with this alternate sample space.

In how many ways can the students be arranged such that there is exactly one graduate student (and three undergrads) in each group?

  • Pick the grad student for group one
  • Pick the undergrads for group one
  • Pick the grad student for group two
  • Pick the undergrads for group two
  • $\vdots$

Applying the multiplication principle of counting, there are a total of $\binom{4}{1}\binom{12}{3}\binom{3}{1}\binom{9}{3}\binom{2}{1}\binom{6}{3}\binom{1}{1}\binom{3}{3} = \binom{4}{1,1,1,1}\binom{12}{3,3,3,3} = \frac{4!12!}{3!3!3!3!}$ different ways in which this can happen.

2. Now you can understand why I averted the method in 1 above (and concealed the text): in 1, the number calculated overcounted by a factor of $4!$, but dividing by $4!$ fixes the issue.

Noting that all outcomes in our sample space are equiprobable, the probability of this occurring is then:

$$\dfrac{4!\binom{12}{3,3,3,3}}{\binom{16}{4,4,4,4}} = \dfrac{4!12!4!4!4!4!}{3!3!3!3!16!}=\frac{64}{455}$$

3. With the alternative sample space in 1, we have an additional $\frac{1}{4!}$ appearing on both the top and bottom of the fraction and these cancel out, yielding the same probability.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks; I need to review my Multinomial Coefficients, but please excuse me if my edit offends; I did so to allow you to see whether I understood your thinking. Do please correct them, if I erred. $\endgroup$ – NNOX Apps Feb 4 '16 at 15:36
  • $\begingroup$ +1. I hope that others will upvote your answer (as I did), which I find as equally as beneficient and helpful as the others. So please accept my assurance that I accepted another answer not because of inequity between answers, but because SE presently allows only one acceptance and so I have used my acceptance to aid those with fewer reputation points. $\endgroup$ – NNOX Apps Feb 7 '16 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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