You are playing a game with a deck of r red cards and b blue cards. You are also given p red tokens and r+b-p blue tokens. (0 ≤ p ≤ r+b).
You will now play a game with r+b turns. On the i-th turn, you choose one of your tokens, then choose a random card from the deck uniformly at random. You earn a point if the color of the token matches the color of the card. Otherwise, your score doesn’t change. Afterwards, both the token and the card will get discarded.
Compute the expected value of your score, assuming you play optimally
I found that optimal score will be (p*r + (r+b-p)*b)/(r+b)
Can anyone explain the logic behind this >
Let's recap here :
R red cards
B blue cards
P red tokens
Q = R+B-P blue tokens
Turn 1 :
Playing optimally leads you to choose the tokens of the same color as the largest set of cards.
For example, if $R\ge B$ meaning there's more red cards, then you would choose the red token and you chances of winning would be :
$$ P(\text{Win turn 1})= {\text{number of red cards}\over \text{total number of cards}} = {R\over R+B} $$
If we generalize, at the n-th turn you chances to win are :
$$ P(\text{Win turn n})= {\text{biggest stack of colored cards}\over \text{total number of cards}} = {\max(R_n,B_n)\over R_n+B_n} $$
Where $R_n$ and $B_n$ are respectively the number of remaining red and blue cards in the deck at the n-th turn.
At some point you'll run out of options for the tokens, let's say you end up with only blue tokens then your chances would be :
$$P(\text{Win turn n})={B_n\over R_n+B_n}$$
Now you have to compute the expectation but I can't help you with that, since I'm still at learning bernoulli's. Good luck !