A standard deck of 52 card. Draw cards one by one without replacement and place it with the face up (i.e. You know what card is drawn) At any point, you may stop me and say a color. If the next two cards I draw both have that color, you win. Otherwise, you lose. What is the optimal strategy?
So I have tried a few approaches but none of them succeed. Would appreciate if anyone can go through them and spot my mistakes / tips on continuing.
Approach 1:
Let $r$,$b$ be the number of red and black card drawn at that time.
P(win) = $\frac{(26-r)(25-r)+(26-b)(25-b)}{[52-(r+b)][51-(r+b)]}$ and we would like to find $r$,$b$ which yields $max$ P(win).
However, the numerator reaches its maximum when $r = b = 0$. While the denominator reaches its minimum (so that it maximize the whole term) when $r + b = 51.5$ which is a different direction of the numeration. Therefore, I am not sure how to continue on this approach in solving for $r$, $b$.
Approach 2:
Here I would like to compare the probability of the edge cases (i.e. Stop before any card is drawn and Stop after one colour is exhausted (all 26 cards were drawn)).
P(win | no card is drawn) = $\frac{1}{2}\frac{25}{51}$, as you have 50% chance of calling the right colour and $\frac{25}{51}$ for the second card to match.
As for P(win|one colour is exhaused), it may be a little bit confusing.
P(win|one colour is exhausted) = P(one colour is exhausted while another have at least 2 cards left)
Therefore, it is equal to $1 - $P(last two cards are of different colours).
P(last two card are of different colours) = $\frac{50!*13^2*2}{52!} = \frac{13}{102}$
So P(win|one colour is exhausted) should be $ 1 - \frac{13}{102} = \frac{89}{102}$, but it sounds way too large for me....
Thats all of my approaches, thanks everyone in advance!
EDIT: I actually went and do some python. The probability of the last 2 card is the same colour is $~0.88$ which agrees with the $\frac{89}{102}$ answer.
Assume that all ($52!$) sequences of cards have equal probability. We claim that an optimal strategy is to draw cards till there remain two cards and then say the dominating color of the deck.
Indeed, for each non-negative integers $r$ and $b$ with $r+b\ge 2$ let $p(r,b)$ be a probability to win using an optimal strategy when in the deck remains $r$ red cards and $b$ black cards. Clearly, $p(r,0)=p(0,b)=1$ and it this case the proposed strategy is optimal. So further we assume that $r,b\ge 1$. Since, by symmetry (following from the recursive analysis below), $p(b,r)=p(r,b)$ we consider only a case when $r\ge b$.
When in the deck remains $r$ red cards and $b$ black cards, we have two possible choices.
1)) Stop to draw the cards and say the dominating color (which is red, because $r\ge b$ ) of the deck. It is easy to calculate that in this case we win with a probability $p_1(r,b)=\tfrac {r(r-1)}{(r+b)(r+b-1)}$.
2)) Draw the next card. It is easy to see that in this case the winning probability $p_2(r,b)$ equals $\tfrac 1{r+b}(rp(r-1,b)+bp(r,b-1))$, if $r>b$, and $p(r,r-1)$, if $r=b$. For technical reasons we also put $p_2(1,1)=0$ and $p_2(r,0)=p_2(0,b)=1$ for each $r$ and $b$.
To prove the optimality of the proposed strategy it suffices to prove an inequality $p_1(r,b)\le p_2(r,b)$ for each $r\ge b\ge 1$. We do this by induction with the respect to the sum $s=r+b\ge 3$. When $s=3$ we have $r=2$ and $b=1$, so $p_1(r,b)=\tfrac {1}{3}=p_2(r,b)$, and the inequality is true. Suppose that the inequality holds for $s\ge 3$ and $r+b=s+1$. The following cases are possible.
1)) $r=b$. Then, by the induction hypothesis, $$p_2(r,r)=p(r,r-1)=p_2(r,r-1)\ge p_1(r,r-1)=\frac{r(r-1)}{(2r-1)(2r-2)}\ge \frac{r(r-1)}{2r(2r-1)}=p_1(r,r).$$
2)) $r>b$. Then, by the induction hypothesis, $$p_2(r,b)=\frac 1{r+b}(rp(r-1,b)+bp(r,b-1))=\frac 1{r+b}(rp_2(r-1,b)+bp_2(r,b-1))\ge$$ $$\frac 1{r+b}(rp_1(r-1,b)+bp_1(r,b-1))=\frac 1{r+b}\left(r\tfrac {(r-1)(r-2)}{(r+b-1)(r+b-2)}+ b\tfrac {r(r-1)}{(r+b-1)(r+b-2)}\right)=\tfrac {r(r-1)}{(r+b)(r+b-1)}.$$