𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Simple proofs of occupancy tail bounds

✍ Scribed by Devdatt Dubhashi

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
130 KB
Volume
11
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We give a simple proof of an occupancy tail bound in the balls and bins experiment using the method of bounded differences in expected form. We also indicate how a short, calculation-free proof of another occupancy tail bound follows from an extension of the standard Chernoff᎐Hoeffding bounds to variables that satisfy some general notions of negative dependence.

πŸ“œ SIMILAR VOLUMES

Simple proof of the pairing theorem
Simple proof of the pairing theorem
✍ I. Mayer πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 112 KB πŸ‘ 2 views

A very simple constructive proof of Lowdin's pairing theorem is presented.

A simple proof of Moser's theorem
A simple proof of Moser's theorem
✍ Zhu, Xuding πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 2 views

This article gives a simple proof of a result of Moser, which says that, for any rational number r between 2 and 3, there exists a planar graph G whose circular chromatic number is equal to r.

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 318 KB πŸ‘ 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti