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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 5: Line 5:
|'''Definition (Independence):'''  
|'''Definition (Independence):'''  
:Two random variables <math>X</math> and <math>Y</math> are independent if and only if  
:Two random variables <math>X</math> and <math>Y</math> are independent if and only if  
:<math>\begin{align}
::<math>\begin{align}
\Pr[X=x\wedge Y=y]
\Pr[X=x\wedge Y=y]
&=
&=

Revision as of 11:18, 15 January 2010

Random Variables and Expectations

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

Definition (Independence):
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 (Expectation):
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. We may ask several questions regarding the distribution of balls in the bins, including:

  • the probability that there is no bin with more than one balls (the birthday problem)
  • the expected number of balls in each bin (occupancy problem)
  • the maximum load of all bins with high probability (occupancy problem)
  • the probability that there is no empty bin (coupon collector problem)

The coupon collector problem

Deviation bounds

Markov's inequality

Chebyshev's inequality

The coupon collector revisited

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