"No more than 1/5 of the population can have more than 5 times the average income."
Proof by Picture! :-)
Proof by Algebra:
Idea: Apply Markov's Inequality to RV , since .
Example:
Consider the following coin flipping games
Let's compute expected value of winnings :
Proof:
Proof:
Proof:
General Properties:
General Properties:
Main Idea:
Input: Unsorted array of integers;
Output: median of
Find and such that:
Proof:
Time Complexity:
Correctness:
Proof:
Proof:
Proof:
Can we make this a Las Vegas algorithm?