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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
imported>WikiSysop
Line 8: Line 8:




== Deviation ==
== Deviation bounds ==


=== Markov's inequality ===
=== Markov's inequality ===

Revision as of 07:23, 10 January 2010

Expectation

Linearity of Expectation

Balls-into-bins model

The coupon collector problem

Deviation bounds

Markov's inequality

Chebyshev's inequality

The coupon collector revisited

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Randomized_Algorithms_(Spring_2010)/Balls_and_bins&oldid=952"