Question

The number of red balls in an urn that contains \(n\) balls is a random variable that is equally likely to be any of the values \(0,1, \ldots, n\). That is, $$ P\\{i \text { red, } n-i \text { non-red }\\}=\frac{1}{n+1}, \quad i=0, \ldots, n $$ The \(n\) balls are then randomly removed one at a time. Let \(Y_{k}\) denote the number of red balls in the first \(k\) selections, \(k=1, \ldots, n\) (a) Find \(P\left\\{Y_{n}=j\right\\}, j=0, \ldots, n\). (b) Find \(P\left\\{Y_{n-1}=j\right\\}, j=0, \ldots, n\) (c) What do you think is the value of \(P\left\\{Y_{k}=j\right\\}, j=0, \ldots, n ?\) (d) Verify your answer to part (c) by a backwards induction argument. That is, check that your answer is correct when \(k=n\), and then show that whenever it is true for \(k\) it is also true for \(k-1, k=1, \ldots, n\).

Short answer

The probability of having j red balls in the first k selections can be represented as \(P\left\{Y_{k}=j\right\}\) and is given by the following formula: \[P\left\{Y_{k}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-k+j} \binom{i}{j}\binom{n-i}{k-j}\]

Step-by-step solution

(a) Find \(P\left\{Y_{n}=j\right\}\), \(j=0, \ldots, n\).

First, let's find the probability of having j red balls in the first n selections. This can be represented as \(P\left\{Y_{n}=j\right\}\): 1. For each value of i (i.e., the number of red balls initially present), we calculate the probability of selecting j red balls in the first n selections. 2. Sum all the probabilities obtained in step 1 to get the final answer. To calculate the probability of selecting j red balls in the first n selections given i red balls in the urn initially, we use conditional probability: \(P\left\{Y_{n}=j|i \text{ red, } n-i \text{ non-red }\right\} = \frac{\binom{i}{j}\binom{n-i}{n-j}}{\binom{n}{n}}\) To find the final probability, we multiply this conditional probability by the probability of having i red balls initially and sum for i = 0, 1, ..., n: \(P\left\{Y_{n}=j\right\} = \sum_{i=0}^{n} P\left\{i \text{ red, } n-i \text{ non-red }\right\} \times P\left\{Y_{n}=j|i \text{ red, } n-i \text{ non-red }\right\}\) \(= \sum_{i=0}^{n} \frac{1}{n+1}\times \frac{\binom{i}{j}\binom{n-i}{n-j}}{\binom{n}{n}}\) The denominator is just 1, and we only need to sum over the values of i that yield non-negative integer values for both the binomial coefficients, so the final answer is: \[P\left\{Y_{n}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-j} \binom{i}{j}\binom{n-i}{n-j}\]

(b) Find \(P\left\{Y_{n-1}=j\right\}\), \(j=0, \ldots, n\).

Now, let's find the probability of having j red balls in the first n-1 selections. This can be represented as \(P\left\{Y_{n-1}=j\right\}\): For this, we will follow a similar process as in part (a) but for the first n-1 selections: \(P\left\{Y_{n-1}=j|i \text{ red, } n-i \text{ non-red }\right\} = \frac{\binom{i}{j}\binom{n-i}{n-1-j}}{\binom{n}{n-1}}\) So, the final probability will be: \[P\left\{Y_{n-1}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-j+1} \binom{i}{j}\binom{n-i}{n-1-j}\]

(c) Find the value of \(P\left\{Y_{k}=j\right\}\), \(j=0, \ldots, n\).

We can generalize the solution for any k, representing the probability as \(P\left\{Y_{k}=j\right\}\): \(P\left\{Y_{k}=j|i \text{ red, } n-i \text{ non-red }\right\} = \frac{\binom{i}{j}\binom{n-i}{k-j}}{\binom{n}{k}}\) So, the final formula for any k is: \[P\left\{Y_{k}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-k+j} \binom{i}{j}\binom{n-i}{k-j}\]

(d) Verify the answer to part (c) by a backwards induction argument.

We'll first check our answer for k=n: \(P\left\{Y_{n}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n} \binom{i}{j}\binom{n-i}{n-j}\) This is the same formula as we derived in part (a), so our generalized formula holds for k=n. Now, let's assume our generalized formula holds for any specific k: \(P\left\{Y_{k}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-k+j} \binom{i}{j}\binom{n-i}{k-j}\) We need to show that it also holds for k-1. If it does, then by induction, our formula is valid for all values of k. We can express \(P\left\{Y_{k-1}=j\right\}\) using the conditional probability formula, just as we did in parts (a) and (b): \(P\left\{Y_{k-1}=j|i \text{ red, } n-i \text{ non-red }\right\} = \frac{\binom{i}{j}\binom{n-i}{(k-1)-j}}{\binom{n}{k-1}}\) Thus, \[P\left\{Y_{k-1}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-(k-1)+j} \binom{i}{j}\binom{n-i}{(k-1)-j}\] Comparing this to our formula for \(P\left\{Y_{k}=j\right\}\), we can see that it matches when we replace k with \(k-1\): \[P\left\{Y_{k-1}=j\right\} = \frac{1}{n+1} \sum_{i=j}^{n-(k-1)+j} \binom{i}{j}\binom{n-i}{(k-1)-j}\] Our generalized formula is valid for k=n and for all values of k if it holds for k-1. We've shown this through induction, so our formula for \(P\left\{Y_{k}=j\right\}\) is correct.