There are R red and G green balls in a box. Alice and Bob pick one ball from the box in turns without replacement. First one to draw a red ball wins. What is the probability that Alice wins if she draws first?
Here is my attempt – Could someone please advise where I went wrong?
For any draw, the probability of picking a red ball is equal to picking $k$ green balls before that and a red ball on $k+1$ draw.
$\displaystyle P(i=k)=\frac{1}{(k+1)}\frac{\dbinom{G}{k}\dbinom{R}{1}}{\dbinom{N}{k+1}}=\displaystyle \frac{R}{(k+1)} \frac{G!}{k!(G-k)!}\frac{(N-k-1)!(k+1)!}{N!}$
$\displaystyle=\frac{G!}{N!} \frac{(R+G-k-1)!}{(G-k)!}.R\frac{(R-1)!}{(R-1)!}=\displaystyle\frac{1}{\binom{R+G}{G}}\dbinom{R+G-k-1}{G-k}$
Let $P(A)$=Alice wins, $P(B)$=Bob wins. Let $P(x)=P(A) – P(B)$. Therefore $P(A) =\displaystyle\frac{1}{2}(1+P(x)) $
$\displaystyle P(x)=\frac{1}{\dbinom{R+G}{G}} \sum_{k=0}^{G} (-1)^{k} \dbinom{R+G-k-1}{G-k}$
If $G$ is even, $-1^k=-1^{G-k}$; using binomial identity
$\dbinom{n}{k} = -1^k \dbinom{k-n-1}{k}$, we get,
$\displaystyle P(x)=\frac{1}{\dbinom{R+G}{G}} \sum_{k=0}^{G} \dbinom{-R}{G-k}$
$\displaystyle P(x)=\frac{1}{2^N\dbinom{R+G}{G}} \sum_{k=0}^N \dbinom{N}{k} \sum_{k=0}^G \dbinom{-R}{G-k}$
$\displaystyle P(x)=\frac{1}{2^N\dbinom{R+G}{G}} \sum_{k=0}^N \sum_{k=0}^G \dbinom{G+R}{k} \dbinom{-R}{G-k}$
Using Chu-Vandermonde identity, we get,
$\displaystyle P(x)=\frac{1}{2^N\dbinom{R+G}{G}} \sum_{k=0}^N \dbinom{G}{G}$
$\displaystyle P(x)=\frac{N+1}{2^{N}\dbinom{R+G}{G}}$ – which seems wrong e.g. set $G=0$
Best Answer
Let random variable $R_1$ be the number of draws to get the first red ball. For $k\in\{1,\dots,G+1\}$, we have \begin{align} P(R_1=k) &= \left(\prod_{d=0}^{k-2} \frac{G-d}{R+G-d}\right)\frac{R}{R+G-(k-1)} \\ &= \frac{\binom{G}{k-1}}{\binom{R+G}{k-1}}\frac{R}{R+G-(k-1)}\\ &= \frac{\binom{R+G-(k-1)}{G-(k-1)}}{\binom{R+G}{G}}\frac{R}{R+G-(k-1)}\\ &= \frac{\binom{R+G-(k-1)}{R}}{\binom{R+G}{G}}\frac{R}{R+G-(k-1)}\\ &= \frac{\binom{R+G-k}{R-1}}{\binom{R+G}{G}}. \end{align} So the probability that Alice wins is \begin{align} \sum_{k=0}^{\lfloor G/2 \rfloor} P(R_1=2k+1) &=\sum_{k=0}^{\lfloor G/2 \rfloor} \frac{\binom{R+G-(2k+1)}{R-1}}{\binom{R+G}{G}} \\ &=\frac{1}{\binom{R+G}{G}}\sum_{k=0}^{\lfloor G/2 \rfloor}\binom{R-1+G-2k}{R-1} \\ &=\frac{1}{\binom{R+G}{G}} \sum_{k=0}^G\frac{1+(-1)^k}{2}\binom{R-1+G-k}{R-1} \\ &=\frac{1}{2\binom{R+G}{G}}\left( \sum_{k=0}^G\binom{R-1+G-k}{R-1} +\sum_{k=0}^G(-1)^k\binom{R-1+G-k}{R-1} \right)\\ &=\frac{1}{2\binom{R+G}{G}}\left( \binom{R+G}{R} +(-1)^G \sum_{k=0}^G\binom{-(G-k)-1}{R-1} \right)\\ &=\frac{1}{2}+\frac{(-1)^G}{2\binom{R+G}{R}} \sum_{k=0}^G\binom{-(G-k)-1}{R-1} \\ \end{align}