𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the concentration of multivariate polynomials with small expectation

✍ Scribed by Van H. Vu

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
172 KB
Volume
16
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Let t 1 t n be independent, but not necessarily identical, 0 1 random variables. We prove a general large deviation bound for multivariate polynomials (in t 1 t n ) with small expectation [order O polylog n ]. Few applications in random graphs and combinatorial number theory will be discussed. Our result is closely related to a classical result of Janson [Random Struct Algorithms 1 (1990), 221-230]. Both of them can be applied in similar situations. On the other hand, our result is symmetric, while Janson's inequality only deals with the lower tail probability.

πŸ“œ SIMILAR VOLUMES

On the vibrations of a plate with a conc
On the vibrations of a plate with a concentrated mass and very small thickness
✍ D. GΓ³mez; M. Lobo; E. PΓ©rez πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 339 KB

## Abstract We consider the vibrations of an elastic plate that contains a small region whose size depends on a small parameter __Ξ΅__. The density is of order __O__(__Ξ΅^–m^__) in the small region, the __concentrated mass__, and it is of order __O__(1) outside; __m__ is a positive parameter. The __t

Exponentially small bounds on the expect
Exponentially small bounds on the expected optimum of the partition and subset sum problems
✍ George S. Lueker πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 172 KB

In the partition problem we seek to partition a list of numbers into two sublists to minimize the difference between the sums of the two sublists. For this and the related subset sum problem, under suitable assumptions on the probability distributions of the input, it is known that the median of the

On Some Classes of Polynomials Orthogona
On Some Classes of Polynomials Orthogonal on Arcs of the Unit Circle Connected with Symmetric Orthogonal Polynomials on an Interval
✍ Alexei Zhedanov πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 404 KB

Starting from the Delsarte Genin (DG) mapping of the symmetric orthogonal polynomials on an interval (OPI) we construct a one-parameter family of polynomials orthogonal on the unit circle (OPC). The value of the parameter defines the arc on the circle where the weight function vanishes. Some explici