22
Nov 23

Simple tools for combinatorial problems

Solution to problem 1(b) from exam ST2133 ZA, 2019

Simple tools for combinatorial problems

Before solving the problem, it is useful to compare the case of independent events with that of dependent events.

Suppose the events A_{1},A_{2},...,A_{n} are independent (in the context of the problem, it will be drawings with replacement). Then by definition the joint probability is the product of individual probabilities:

(1) P\left( A_{1}\cap ... \cap A_{n}\right) =P\left( A_{1}\right) ... P\left(A_{n}\right) .

Now assume that the event A_{1} occurs first, A_{2} occurs second, ...., A_{n} occurs last and each subsequent event depends on the previous one (as in the case of drawings without replacement). Then

P\left( A_{1}\cap A_{2}\right) =\frac{P\left( A_{1}\cap A_{2}\right) }{P\left( A_{1}\right) }P\left( A_{1}\right) =P\left( A_{2}|A_{1}\right)P\left( A_{1}\right) .

Similarly, by multiplying and dividing many times, we get

(2) P\left( A_{1}\cap ... \cap A_{n}\right) =P\left(A_{n}|A_{1},...,A_{n-1}\right) P\left( A_{n-1}|A_{1},...,A_{n-2}\right)... P\left( A_{1}\right) .

Equation (2) is called a chain rule for probability. Several of my students have been able to solve the problem without explicitly using (2). It is advisable to use (2) or other relevant theoretical properties to achieve clarity and avoid errors.

Problem statement and solution

Suppose there are n\geq 2 red balls and 3 green balls in a bag. All balls with the same color are indistinguishable.

Part i.

Suppose one ball is drawn at a time at random with replacement from the bag. Let X be the number of balls drawn until a red ball is obtained (including the red ball). Write down the probability mass function of X.

Solution. Most students answer that this is a hypergeometric distribution with probabilities given by q^{x-1}p, x=1,2,... where p is the probability of success. Without specifying p (the probability of drawing a red ball) the answer is incomplete. Since p=\frac{n}{n+3}, we have

q^{x-1}p=\left( \frac{3}{n+3}\right) ^{x-1}\frac{n}{n+3}=\frac{n3^{x-1}}{\left( n+3\right) ^{x}}.

Part ii.

Now suppose one ball is drawn at random at a time without replacement from the bag. Let Y be the number of balls drawn until a red ball is obtained (including the red ball). Write down the probability mass function of Y.

Solution. Let us denote R_{i} the event that the ith ball is red and G_{i} the event that the ith ball is green, respectively. Note that the only way R_{3} appears is by obtaining G_{1},G_{2} before it. Hence, R_{3} equals \left( G_{1},G_{2},R_{3}\right) . Besides, R_{1},...,R_{4} are the only (mutually exclusive) possibilities and it remains to find their probabilities.

Obviously, P\left( R_{1}\right) =\frac{n}{n+3}.

Next, using (2)

P\left( R_{2}\right) =P\left( G_{1},R_{2}\right) =P\left( G_{1}\right)P\left( R_{2}|G_{1}\right) =\frac{3}{n+3}\frac{n}{n+2}.

Further,

P\left( R_{3}\right) =P\left( G_{1},G_{2},R_{3}\right) =P\left(G_{1}\right) P\left( G_{2}|G_{1}\right) P\left( R_{3}|G_{1},G_{2}\right) =\frac{3}{n+3}\frac{2}{n+2}\frac{n}{n+1}.

Finally,

P\left( R_{4}\right) =P\left( G_{1},G_{2},G_{3},R_{4}\right)

=P\left( G_{1}\right) P\left( G_{2}|G_{1}\right) P\left(G_{3}|G_{1},G_{2}\right) P\left( R_{4}|G_{1},G_{2},G_{3}\right) =\frac{3}{n+3}\frac{2}{n+2}\frac{1}{n+1}\frac{n}{n}.

The results can be summarized in a table:

\begin{array}{cc}  \textrm{Values} & \textrm{Prob}\\R_{1} & \frac{n}{n+3} \\R_{2} & \frac{3}{n+3}\frac{n}{n+2} \\R_{3} & \frac{3}{n+3}\frac{2}{n+2}\frac{n}{n+1} \\R_{4} & \frac{3}{n+3}\frac{2}{n+2}\frac{1}{n+1}\frac{n}{n}\end{array}

This distribution is not of one of standard types.

Part iii.

Suppose two balls are drawn at the same time at random with replacement from the bag. Let Z denote the number of these double draws performed until two green balls are obtained. Show that the probability of drawing two green balls is

\frac{6}{\left( n+2\right) \left( n+3\right) }.

Hence, show that the probability mass function for Z is

P\left( Z=z\right) =\frac{6\left( n^{2}+5n\right) ^{z-1}}{\left( n+3\right)^{z}\left( n+2\right) ^{z}}, z=1,2,...

Solution. Using the same notation as before,

P\left( G_{1},G_{2}\right) =P\left( G_{2}|G_{1}\right) P\left( G_{1}\right)=\frac{2}{n+2}\frac{3}{n+3}.

All other events (two red balls or one green and one red) are considered a failure. Thus we have a hypergeometric distribution with

p=\frac{6}{\left( n+2\right) \left( n+3\right) },

q=1-\frac{6}{\left( n+2\right) \left( n+3\right) }=\frac{n^{2}+5n+6-6}{\left( n+2\right) \left( n+3\right) }=\frac{n^{2}+5n}{\left( n+2\right)  \left( n+3\right) }

and

q^{z-1}p=\left[ \frac{n^{2}+5n}{\left( n+2\right) \left( n+3\right) }\right]^{z-1}\frac{6}{\left( n+2\right) \left( n+3\right) }=\frac{6\left(  n^{2}+5n\right) ^{z-1}}{\left( n+2\right) ^{z}\left( n+3\right) ^{2}}, z=1,2,...