Randomized Algorithms (Spring 2010)/Balls and bins

From TCS Wiki
Revision as of 06:18, 15 January 2010 by imported>WikiSysop (→‎Expectation)
Jump to navigation Jump to search

Random Variables and Expectations

What do we mean by the sentence "[math]\displaystyle{ X }[/math] is a random variable"? I guess most os us just imagine that [math]\displaystyle{ X }[/math] is like a random dice whose value is ranging over a set [math]\displaystyle{ R }[/math] of values, such that for each [math]\displaystyle{ x\in R }[/math], [math]\displaystyle{ X=x }[/math] with some specific probability [math]\displaystyle{ p(x) }[/math], so we say that "[math]\displaystyle{ X }[/math] is distributed over [math]\displaystyle{ R }[/math] with probability distribution [math]\displaystyle{ p }[/math]".


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