Randomized Algorithms (Spring 2010)/Balls and bins: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Expectation == === Linearity of Expectation === === Balls-into-bins model === === The coupon collector problem === == Deviation == === Markov's inequality === === Varia…'
 
imported>WikiSysop
Line 12: Line 12:
=== Markov's inequality ===
=== Markov's inequality ===


=== Variance ===
=== Variance and Chebyshev's inequality ===
 
=== Chebyshev's inequality ===


=== The coupon collector revisited ===
=== The coupon collector revisited ===


== The <math>k</math>-Median Problem ==
== The <math>k</math>-Median Problem ==

Revision as of 06:38, 10 January 2010

Expectation

Linearity of Expectation

Balls-into-bins model

The coupon collector problem

Deviation

Markov's inequality

Variance and Chebyshev's inequality

The coupon collector revisited

The [math]\displaystyle{ k }[/math]-Median Problem