Randomized Algorithms (Spring 2010)/Balls and bins: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop m Protected "Randomized Algorithms (Spring 2010)/Expectations, moments, deviations" ([edit=sysop] (indefinite) [move=sysop] (indefinite)) |
imported>WikiSysop |
||
| Line 1: | Line 1: | ||
== | == Random Variables and Expectations == | ||
What do we mean by the sentence "<math>X</math> is a '''random variable'''"? I guess most os us just imagine that <math>X</math> is like a random dice whose value is ranging over a set <math>R</math> of values, such that for each <math>x\in R</math>, <math>X=x</math> with some specific probability <math>p(x)</math>, so we say that "<math>X</math> is distributed over <math>R</math> with probability distribution <math>p</math>". | |||
=== Linearity of Expectation === | === Linearity of Expectation === | ||
| Line 6: | Line 8: | ||
=== The coupon collector problem === | === The coupon collector problem === | ||
== Deviation bounds == | == Deviation bounds == | ||
Revision as of 06:18, 15 January 2010
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]".