2.15 Analysis of Algorithms MPRI
Lecturer: Lucas Gerin

2.15 Analysis of Algorithms

4th Part: Probabilistic approach (Lectures 14 to 17)

Online review

Table of contents

References

[Bre17] P.Brémaud. Discrete Probability Models and Methods. Springer (2017).

[FS09] P.Flajolet, R.Sedgewick. Analytic Combinatorics. Cambridge University Press (2009).

[MU95] M.Mitzenmacher, E.Upfal. Probability and computing: randomized algorithms and probabilistic analysis . Cambridge University Press (1995).

Lecture 14: Probabilistic Toolbox

14.1. Events and random variables

Application. Randomized algorithm for checking a polynomial identity. Ref: [MU95] p.1.

14.2. Conditioning

Application. Analysis of QuickSelect. Ref: Adapted from the blog 11011110.

14.3. Inequalities and deviations

Application. An (optimal) Randomized algorithm for the mean. Ref: [MU95] p.59.

Lecture 15: The Probabilistic Method

Ref: Chap.6 in [MU95].

15.1. The 1st moment method

Proposition. Let $N$ be a random variable in $\mathbb{Z}_{\geq 0}$. Then $$ \mathbb{P}(N=1)\leq \mathbb{E}[N]. $$


Proposition. Let $N$ be a random variable in $\mathbb{Z}_{\geq 0}$, and let $\mu=\mathbb{E}[N]$. Then $$ \mathbb{P}(N\geq \mu)>0,\qquad \mathbb{P}(N\leq \mu)>0. $$


Application. No large monochromatic subcliques in the complete graph. A glimpse of Ramsey Theory. Ref: [MU95] p.135.


Application. A Las Vegas algorithm for finding a large cut. Ref: [MU95] p.138.
Application. : An algorithm for finding large independent sets in a graph. Ref: [MU95] p.142.

15.2. The 2d moment

Proposition. Let $N$ be a random variable in $\mathbb{Z}_{\geq 0}$. Then $$ \mathbb{P}(N\geq 1)\geq \frac{\mathbb{E}[N]^2}{\mathbb{E}[N^2]}. $$


Application. Triangles in Erdös-Rényi random graphs. Ref: Ex.10.2.8 in [Bre17]

Lecture 16: Balls in bins

The general model: we put $n$ balls uniformly at random into $r$ bins.
Reference for this lecture: [FS09] p.111-118.

16.1. Collisions and the birthday paradox

Proposition. Let $T_b$ be the first time of a $b$-collision (i.e. $b$ balls land in the same bin). Then $$ \mathbb{E}[T_b]\sim c_br^{1-1/b} $$ for some explicit $c_b$ (see [FS09] p.114-118).


Application. Hashing ([MU95 Sec.5.5])

16.2. The coupon collector

Proposition. Let $C$ be the first time at which there is no more empty bins. $$ \mathbb{E}[C]\sim r\log(r). $$


Application. Lower bound for the 1+1 EA Algorithm. Source: Sec.5.5 in: B.Doerr. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics (2018).

16.3. Maximal load

Ref: Sec.5.4.[MU95]

Proposition. (Informal statement) Assume $n=\alpha r$ for some $\alpha >0$. Then with high probability the fullest bins contains $\mathcal{O}\left(\frac{\log(r)}{\log(\log(r)}\right)$ balls.
(See [MU95] Sec.5.4. or [FS09] Proposition VIII.10. for precise results.)

Lecture 17: Data streams algorithms

A short introduction do streaming algorithms: Chap.6 (Filtering and Streaming) in Jeff Erickson. Algorithms (2019).

17.1. Prehistory: Morris' counting algorithm

17.2. Cardinality estimation: MinCount

17.3. CVM's algorithm