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
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
. 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:
This is a bit hard to simplify, but we can use wolfram alpha here.
Thus, we get
Play a blue token:
This can be simplified with wolfram alpha again [here].
Thus, we get
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: