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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 24: 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
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. We may ask several questions regarding the distribution of balls in the bins, including:
* What is the probability that there is no bin with more than one balls. (the birthday problem)
* What is the expected number of balls in each bin? (occupancy problem)
* What is the maximum load of all bins, with high probability? (occupancy problem)
* What is the probability that there is no empty bin? (coupon collector problem)


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

Revision as of 09:20, 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. We may ask several questions regarding the distribution of balls in the bins, including:

  • What is the probability that there is no bin with more than one balls. (the birthday problem)
  • What is the expected number of balls in each bin? (occupancy problem)
  • What is the maximum load of all bins, with high probability? (occupancy problem)
  • What is 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