You are not logged in. Please login at to post your questions!


CARDS777 - Editorial




Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan




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.



This question is marked "community wiki".

asked 19 Mar, 20:23

lg5293's gravatar image

accept rate: 10%

edited 20 Mar, 00:23

admin's gravatar image

0★admin ♦♦

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's gravatar image

accept rate: 4%

Well, we already showed that every strategy is an optimal strategy, so that's why this greedy solution works :) In fact, it doesn't matter what card you play, you can choose anything you have left available.

(20 Mar, 00:53) lg52937★

I used this approach.

(20 Mar, 00:59) mathecodician5★

@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

ps_1234's gravatar image

accept rate: 0%


This strategy is the best because all strategies are equally good. The proof is in the statement above (by induction). For more intuition, you can see that your moves are all fixed but cards are randomized, meaning there isn't a way for you to "beat" the randomness in this case.

(20 Mar, 03:29) lg52937★

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

yakumo_yukari's gravatar image

accept rate: 0%

Hello Yakumo. I am not sure I your explanation works (or maybe I don't understand it properly). It is said that you can adjust your next token choice based on previous cards. So a strategy is more than a list of tokens. The same strategy can lead to tokens being played in different order, for 2 different card permutations.

(31 Mar, 03:30) beroul6★

This link would be helpful in understanding the Linearity of Expectation :


answered 20 Mar, 19:33

pankajkhan's gravatar image

accept rate: 14%

@rajat1603 i had attempted the question by keeping the values of r and b and not their expected value ,can you explain why should we keep the expected value of the variables?


answered 25 May, 17:55

ocher's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 19 Mar, 20:23

question was seen: 1,454 times

last updated: 25 May, 17:55