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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 1: Line 1:
== Random Variables and Expectations ==
== Random Variables and Expectations ==
Let <math>X</math> be a discrete '''random variable'''. The expectation of <math>X</math> is defined as follows.
Let <math>X</math> be a discrete '''random variable'''.  


{|border="1"
{|border="1"
|'''Definition 1: '''The '''expectation''' of a discrete random variable <math>X</math>, denoted by <math>\mathbb{E}[X]</math>, is given by
|'''Definition 1: Two random variables <math>X</math> and <math>Y</math> are independent if and only if
:<math>\begin{align}
\Pr[X=x\wedge Y=y]
&=
\Pr[X=x]\cdot\Pr[Y=y]
\end{align}</math>
:for all values <math>x</math> and <math>y</math>.
|}
 
The expectation of <math>X</math> is defined as follows.
{|border="1"
|'''Definition 2: '''The '''expectation''' of a discrete random variable <math>X</math>, denoted by <math>\mathbb{E}[X]</math>, is given by
::<math>\begin{align}
::<math>\begin{align}
\mathbb{E}[X] &= \sum_{x}x\Pr[X=x],
\mathbb{E}[X] &= \sum_{x}x\Pr[X=x],
Line 13: Line 24:


=== Balls-into-bins model ===
=== Balls-into-bins model ===
Imagine that <math>m</math> balls are thrown into <math>n</math> bins, in such a way that each ball is thrown into a bin which is uniformly and independently chosen from all <math>n</math> bins. This


=== The coupon collector problem ===
=== The coupon collector problem ===

Revision as of 07:16, 15 January 2010

Random Variables and Expectations

Let [math]\displaystyle{ X }[/math] be a discrete random variable.

Definition 1: Two random variables [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are independent if and only if
[math]\displaystyle{ \begin{align} \Pr[X=x\wedge Y=y] &= \Pr[X=x]\cdot\Pr[Y=y] \end{align} }[/math]
for all values [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math].

The expectation of [math]\displaystyle{ X }[/math] is defined as follows.

Definition 2: The expectation of a discrete random variable [math]\displaystyle{ X }[/math], denoted by [math]\displaystyle{ \mathbb{E}[X] }[/math], is given by
[math]\displaystyle{ \begin{align} \mathbb{E}[X] &= \sum_{x}x\Pr[X=x], \end{align} }[/math]
where the summation is over all values [math]\displaystyle{ x }[/math] in the range of [math]\displaystyle{ X }[/math].

Linearity of Expectation

Balls-into-bins model

Imagine that [math]\displaystyle{ m }[/math] balls are thrown into [math]\displaystyle{ n }[/math] bins, in such a way that each ball is thrown into a bin which is uniformly and independently chosen from all [math]\displaystyle{ n }[/math] bins. This

The coupon collector problem

Deviation bounds

Markov's inequality

Chebyshev's inequality

The coupon collector revisited

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