Linearity of expectation
Find the expected value of an optimal strategy for a game involving cards and tokens.
The main observation is that all strategies are optimal strategies; all strategies will lead to the same expected value.
Using the observation above, we get a really simple solution. Let's play all red tokens, then all blue tokens. By linearity of expectation, we can get the total expectation to be $$p * (r / (r+b)) + (r+b-p) * (b / (r+b))$$.
Intuitively, you can guess this by noticing that the cards are played randomly. We can prove this more formally with induction.
Consider a O(rbp) dp solution as follows. Let $f(r,b,p)$ denote the expected value given we have r red cards, b blue cards, p red tokens, and r+b-p red tokens.
We claim that $$f(r,b,p) = p * (r / (r+b)) + (r+b-p) * (b / (r+b)) = (p*r + (r+b-p)*b) / (r+b)$$. We prove this by inducting on r+b.
We can check that the base cases f(1,0,1), f(0,1,1), f(1,0,0) and f(1,0,1) all make sense (i.e. f(1,0,1) = 1, since we have a red token and red card, so we get 1 point).
Now, for the inductive case, consider two cases: we either play a red token or blue token.
Play a red token: $$f(r,b,p) = (f(r-1,b,p-1) + 1) * (r / (r + b)) + (f(r,b-1,p-1)) * (b / (r + b))$$ $$ = (((((p-1)(r-1) + (r+b-p)*b) / (r+b-1) + 1) * r + ((p-1)*r + (r+b-p)*(b-1)) / (r+b-1)) * b) / (r+b)$$
This is a bit hard to simplify, but we can use wolfram alpha here.
Thus, we get $$ = (p*r + (r+b-p)*b) / (r + b)$$
Play a blue token: $$f(r,b,p) = (f(r-1,b,p)) * (r / (r + b)) + (f(r,b-1,p) + 1) * (b / (r + b))$$ $$ = ((((p(r-1) + (r+b-p-1)*b) / (r+b-1)) * r + (((p*r + (r+b-p-1)*(b-1)) / (r+b-1)) + 1) * b) / (r+b)$$
This can be simplified with wolfram alpha again here.
Thus, we get $$ = (p*r + (r+b-p)*b) / (r + b)$$.
Thus, in both cases, we get the same expected value, so this completes the induction step. Thus, we've proven this formula works.
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Mar, 20:23
alternately this can be solved in O(R + B) by keeping the expected number of Red and Blue Cards and at each step choosing the one which is higher in value and subtracting the probability of a card being chosen from the expected value. code
answered 20 Mar, 00:52
@rajat1603 I had the same thought,but couldn’t prove it mathematicaly why this strategy would be the best.Can you elaborate?
answered 20 Mar, 01:07
I have a more natural explanation for this problem. It is exactly dependent on the randomness of the card. Basically, we can number the cards and tokens from 1,2,..,n. So there are n! order of drawing card (the number of permutation) and their probability is equal (1/n!). Considering any two strategies of choosing tokens. There are always two permutations that make the same number of point corresponding to each strategies. For example r+b=3. 2 strategies choosing tokens 1,2,3 and 3,2,1. The permutation (of drawing card) 1,2,3 and 3,2,1 make the same number of points in both cases. Therefore, we proved that all strategy is equally good. What is left is calculate the E[X]. Denote X_i = 1 if the ith tokens matched the ith drawing cards. We can see X=X_1+X_2+...+X_n. By the linearity of expectation, X=E[X_1]+...+E[X_n]. if X_i is red, E[X_i]=r/(r+b) else E[X-i]=b/(r+b). Then it concluded my proof
answered 20 Mar, 09:13
This link would be helpful in understanding the Linearity of Expectation : https://brilliant.org/wiki/linearity-of-expectation/
answered 20 Mar, 19:33