The Rich Get Richer

Relevant wiki: Expected Value - Problem Solving

The answer is $\frac{3046176}{2015}$ , giving $p+q = 3048191$ .

We will prove the following surprising claim:

Claim : If the bag has $n$ balls, then the probability that it has $r$ red balls (and thus $n-r$ blue balls) is exactly $\frac{1}{n-1}$ , for all $n \ge 2, 1 \le r \le n-1$ .

We will prove this claim by induction on $n$ . For $n = 2$ , this is trivial (the bag starts with 1 red ball and 1 blue ball, so the probability that it has 1 red ball is $1 = \frac{1}{2-1}$ ).

Now, suppose we have proven the claim for $n = n_0$ , and we'd like to prove the claim for $n = n_0 + 1$ .

Fix $r$ with $1 \le r \le n_0$ . We want to compute the probability that when we have $n_0 + 1$ balls, we have $r$ red balls. Consider the last ball added into the bag. There are two cases:

Case 1 : This ball was red, so the previous bag has $r-1$ red balls out of $n_0$ balls. If $r \ge 2$ , the probability of this happening is $\frac{1}{n_0 - 1} \cdot \frac{r-1}{n_0}$ : the probability that we do have $r-1$ red balls when we have $n_0$ balls (inductive hypothesis), multiplied by the actual probability of taking a red ball in this case. If $r = 1$ , the probability is zero since we cannot have no red balls in the bag (the original red ball must always remain in), but this can also be represented as $\frac{1}{n_0-1} \cdot \frac{r-1}{n_0}$ because the second term is zero. So the probability that a red ball is taken to make our bag to have $r$ red balls out of $n_0 + 1$ balls is $\frac{1}{n_0 - 1} \cdot \frac{r - 1}{n_0}$ .

Case 2 : This ball was blue, so the previous bag has $r$ red balls (and thus $n_0 - r$ blue balls) out of $n_0$ balls. This case is completely analogous with the above; the probability of this case happening is $\frac{1}{n_0 - 1} \cdot \frac{n_0 - r}{n_0}$ .

In total, the probability that we have $r$ red balls out of $n_0 + 1$ balls is simply the sum of the probabilities contributed by the two cases above; that is, $\frac{1}{n_0 - 1} \cdot \frac{r - 1}{n_0} + \frac{1}{n_0 - 1} \cdot \frac{n_0 - r}{n_0} = \frac{1}{n_0}$ . This completes the proof.

Now that we have proven this, we can compute the expected value easily:

$\displaystyle\begin{aligned} E(\text{number of majority balls}) &= \sum_{r=1}^{2015} P(\text{\$r\$ red balls}) \cdot \text{number of majority balls} \\ &= \sum_{r=1}^{2015} \frac{1}{2015} \cdot \max \{r, 2016-r\} \\ &= \frac{1}{2015} \cdot \left( \sum_{r=1}^{2015} \max \{r, 2016-r\} \right) \\ &= \frac{1}{2015} \cdot \left( \sum_{r=1}^{1007} (2016-r) + \sum_{r=1008}^{2015} r \right) \\ &= \frac{1}{2015} \cdot \left( \sum_{r=1}^{1007} (2016-r) + \sum_{r=1}^{1008} (2016-r) \right) \\ &= \frac{1}{2015} \cdot ( 2016 \cdot 2015 - (1+2+\ldots+1007+1008+1007+\ldots+1) ) \\ &= \frac{1}{2015} \cdot (2016 \cdot 2015 - 1008^2) \\ &= \boxed{ \dfrac{3046176}{2015} } \end{aligned}$

The second equality uses our result, together with the fact that the number of majority balls is simply the larger of $r$ (number of red balls) and $2016-r$ (number of blue balls). The fourth equality uses the result that when $r < 1008$ , the bigger one is $2016-r$ , and when $r \ge 1008$ , the bigger one is $r$ . (Okay, they are equal when $r = 1008$ , but we can choose either one.) The fifth equality performs the replacement $r \to 2016-r$ (this also reverses the order of summation). The sixth equality takes everything apart, setting the 2016's to the side. The seventh equality uses the (easily proven) fact $1+2+\ldots+n+(n-1)+\ldots+1 = n^2$ .

It's easy to notice that the probability of any particular sequence of draws resulting in $r$ red balls and $b$ blue balls in the bag is $\displaystyle\frac{(r-1)!(b-1)!}{(n-1)!}$ (where $n$ is the total number of balls) regardless of the order of the draws.

The number of paths leading to $r$ red balls and $b$ blue balls, which is the same as the total number of possible sequences of $r-1$ red ball draws and $b-1$ blue ball draws, is simply $\displaystyle\frac{(n-2)!}{(r-1)!(b-1)!}$ .

It follows that the total probability of every sequence of draws leading to $r$ red balls and $b$ blue balls is the product of these:

$\frac{(r-1)!(b-1)!}{(n-1)!}\times\frac{(n-2)!}{(r-1)!(b-1)!}=\frac{(r-1)!(b-1)!(n-2)!}{(r-1)!(b-1)!(n-1)!}=\frac{1}{n-1}$

Knowing that the probability of each of the the 2015 outcomes resulting in 2016 total balls is uniformly distributed, calculating the expected value of the majority color is now very easy.

To account for the cases where the red ball is the majority: $\displaystyle\sum_{k=1009}^{2016}\frac{k}{2015}$

Similarly, to account for the blue ball majority cases: $\displaystyle\sum_{k=1009}^{2016}\frac{k}{2015}$

In the event of a tie: $\displaystyle\frac{1008}{2015}$

Summing these:

$\frac{1008}{2015}+2\sum_{k=1009}^{2016}\frac{k}{2015}=\frac{1008+2\sum_{k=1009}^{2016}{k}}{2015}=\frac{3046176}{2015}$

$3046176+2015=\boxed{3048191}$

This is another case of Polya's urn; the probability that there are $b+1$ blue balls after $2n$ ball choices is $\tfrac{1}{2n+1}$ for $0 \le b \le 2n$ . If there are $b+1$ blue balls after $2n$ choices, there are $\mathrm{max}(b+1,2n-b+1)$ balls of whichever is the greater colour. Thus the expected number of the number of balls of the larger number after $2n$ ball choices is $\begin{array}{rcl} M_n & = & \displaystyle \tfrac{1}{2n+1} \sum_{b=0}^{2n} \mathrm{max}(b+1,2n-b+1)\\ & = &\displaystyle \tfrac{1}{2n+1}\left(\sum_{b=0}^{n-1} (2n- b+1) + (n+1) + \sum_{b=n+1}^{2n} (b+1)\right) \\ & = & \displaystyle \tfrac{1}{2n+1}\left(n+1 + 2\sum_{b=n+1}^{2n} (b+1)\right) \; = \; \tfrac{1}{2n+1}\left(n+1 + 2n(n+1) + 2\sum_{b=1}^n b\right) \\ & = & \tfrac{1}{2n+1} \left( n+1 + 3n(n+1)\right) \; = \; \tfrac{(n+1)(3n+1)}{2n+1} \end{array}$ With $n = 1007$ we have $M_n \,=\, \tfrac{3046176}{2015}$ , and so the answer is $\boxed{3048191}$ .