Asymmetric Polya

Relevant wiki: Induction - Problem Solving

Let $p_{n,k}$ be the probability that there are $k+3$ black marbles in the urn after $n$ minutes. Conditional probability considerations tell us that $p_{n,0} \; = \; \frac{n}{n+3} p_{n-1,0} \qquad \qquad p_{n,n} \; = \; \frac{n+2}{n+3} p_{n-1,n-1}$ for any $n \ge 1$ , with $p_{0,0} = 1$ , and hence $p_{n,0} \; = \; \frac{6}{(n+1)(n+2)(n+3)} \qquad \qquad p_{n,n} \; = \; \frac{3}{n+3}$ More generally, if $1 \le k \le n-1$ then $p_{n,k} \; = \; \frac{n-k}{n+3} \times p_{n-1,k} + \frac{k+2}{n+3} \times p_{n-1,k-1}$ and these equations can be solved inductively to yield $p_{n,k} \; = \; \frac{3(k+1)(k+2)}{(n+1)(n+2)(n+3)} \qquad \qquad 0 \le k \le n$ In particular $p_{60,45} = \frac{1081}{39711}$ , making the answer $\boxed{40792}$ .

This was one of my favorite problems on the site. Original, and fun to solve... Thanks for posting it @Mark Hennings ! (+1 like!)

My solution:

Let $T_i$ be the $i$ 'th triangular number. i.e. $T_i = 1+2+...+i$

Let $P(m,n) =$ The probability that you will have $m$ black balls and $n$ white balls once the corresponding number of moves have taken place after starting with $3$ black balls and $1$ white ball.

Then, $P(m,n) = \frac{T_{m-2}}{\sum_{i=1}^{m+n-3}T_i}$

So, $P(48,16) = \frac{T_{46}}{\sum_{i=1}^{61}T_i} = \frac{1081}{37711}$

$1081$ (factors $23$ and $47$ ) and $37711$ (factors $3$ , $7$ , $31$ and $61$ ) are coprime, so the answer is $1081 + 37711 = \boxed{40792}$

$LaTeX$ I'll show two ways of doing it, the second way is cooler. The first way is: By observing the terms that go in when applying Bayes rule, one notices it doesn't matter what order you pick the balls in, the probability of a specific order of choosing 15 white balls and 45 black balls is the same. The number of orderings is ${60\choose 15}$ and so the answer is \begin{equation*} {60\choose 15}\frac{3\times 4\times 5\times\ldots \times 47\times 1 \times 2\times\ldots \times 15}{4\times 5\times\ldots\times 63} = \frac{47\times 23}{21\times 31\times 61} \end{equation*}

Here is the second way, a combinatorial solution. Consider the setup \begin{equation*} BB| \end{equation*} The | represents a divider, the B's are "black weights" and since there is only one white ball we don't need a W or a "white weight." Let me explain. There are 3 insertion positions to the left of the divider and 1 insertion position to the right of the divider so the probability of inserting a ball on the left vs. on the right is the same as choosing a black ball vs. a white ball. And one can see that even after you add a ball to either side, the probabilities of inserting on either side keeps on matching the probability of choosing a black/white ball. Since we are adding balls randomly to this configuration it turns out that all final configurations are equally likely. There are ${63 \choose 3}$ final positions (fix the BB|) and there are ${47\choose 2}$ valid configurations (45 added on the left of the divider, 15 on the right, fix two of the 47 positions on the left) so another way to get the answer is \begin{equation*} \frac{{47\choose 2}}{{63 \choose 3}} = \frac{47\times 23}{21\times 31\times 61}\end{equation*}

My solution. Consider the ways one can choose the marbles. First of all, we will have to pick a white marble 15 times and a black marble 45 times. This means that at some point the probability will be a number ranging from 1 to 15 divided by some number and from 3 to 47 over some number because these are the number of choices. Now the denominator is the product of the total number of choices, which ranges from 4 to 63. To account for permutations, we add all work together multiplying 47!/2! for the numbers 3 to 47, 15! for the number 1 to 15, and the permutation 60!/15!/45! which will count the permutations, and finally dividing by 62!/3!. Multiplying this out yields 1081/39711 and our answer is 40792.

The probability of a single combinations is given by:

$\prod_{n=3}^{47}\frac{n}{n + 1} * \prod_{n=1}^{16}\frac{n}{n + 48}$

There are $\binom{60}{45}$ ways new marbles can be picked.

There are $\binom{4}{3}$ ways to arrange the marbles that are already in the urn.

Hence the probability for all the combinations is:

$\prod_{n=3}^{47}\frac{n}{n + 1} * \prod_{n=1}^{16}\frac{n}{n + 48}* \binom{60}{45} * \binom{4}{3}=\frac{1081}{39711}$

The answer is $1081+39711=\boxed{40792}$

Another form of recurrence:

Let $P(a,b)$ be the probability of the urn having $a$ white and $b$ black marbles.

Then $\begin{aligned} P(a,b) &= \frac{a-1}{a+b-1} \cdot P(a-1,b)+\frac{b-1}{a+b-1} \cdot P(a,b-1)\\ P(1,3) &= 1 \end{aligned}$ and $0$ if $a<1$ or $b<3$

We need to find $P(16,48)$