Probability Of Winning A Game

Let $P(a,N)$ denote the probability of $A$ winning $a$ games out of first $N$ games. Then we can write down the following recursion on $P(\cdot,\cdot)$ . $P(a,N)=P(a-1,N-1)\frac{a-1}{N-1} + P(a,N-1)\big(1-\frac{a}{N-1}\big)\hspace{10pt}(1)$ We have the following initial condition $P(0,3)=P(3,3)=0, P(1,3)=P(2,3)=\frac{1}{2}$ Now we show that the above recursion (1) has the solution $P(a,N)=\frac{1}{N-1}, a=1,2,\ldots, N-1\\ =0,\hspace{10pt} a=0, N$ Proof : Clear via induction on $N$ . $\hspace{5pt}\blacksquare$

Hence $P(\frac{2014}{2}, 2014)=\frac{1}{2013}$ .

P.S. This problem is a special case of a very interesting discrete time stochastic process, known as Polya's Urn Process .

We can represent the situation as a string in which the first two states are given ( $A$ wins and $B$ wins subsequently)

$\displaystyle AB|ABBABBBAA...$

For clarity, let's consider the case in which only $8$ games are played, so that $A$ and $B$ win $\frac{8}{2}=4$ games. A possbile outcome is

$\displaystyle AB|BABAAB$

whose probability is $\displaystyle \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{2}{4} \cdot \frac{2}{5} \cdot \frac{3}{6} \cdot \frac{3}{7}$ . But an other possible outcome is

$\displaystyle AB|AAABBB$

whose probability is $\displaystyle \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdot \frac{1}{5} \cdot \frac{2}{6} \cdot \frac{3}{7}$ . Notice that the two probabilities are equal and can be written as $\displaystyle \frac{(1 \cdot 2 \cdot 3)^2}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7}$ . Multiplying it by the number of possible combination (in the case $\binom{6}{3}$ ) we obtain our final probability. This pattern holds for $n=2k$ , $k \in \mathbb{N}$ number of games (I'll try to submit a proof), leading to a formula for a general case

$\displaystyle \mathbb{P}(n=2k)=\frac{1}{(n-1)!}\prod_{i=1}^{k-1} i^2 \binom{n-2}{k-1}$ .

For our case $n=2014$ , so

$\displaystyle \mathbb{P}(n=2 \cdot 1007 )=\frac{1}{(2013)!}\prod_{i=1}^{1006} i^2 \binom{2012}{1006}=\frac{1}{2013}=\frac{a}{b}$

Eventually,

$\displaystyle a+b+1=1+2013+1=\boxed{2015}$