Name
Abstract | ||
|---|---|---|
It is well known that any objective function Y = Y-n = Y-n(X-1,...,X-n) that depends on an underlying sequence (X-n) of random variables may be represented as a martingale in the canonical fashion introduced by J. L. Doob. Inequalities such as the Azuma-Hoeffding inequality may then be used to bound the probabilities P(\Y - EY\ > lambda) in a meaningful way provided, e.g., that the corresponding martingale differences are uniformly bounded by appropriately small quantities. In many applications, however, this last condition is not satisfied; the purpose of this note is to survey and compare results that enable one to give a useful bound on the corresponding tail probability in such cases. Applications to random proximity graphs will be presented. |
Year | Venue | DocType |
|---|---|---|
1997 | DIMACS SERIES IN DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCES | Conference |
Volume | Citations | PageRank |
41 | 3 | 0.56 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anant P. Godbole | 1 | 95 | 16.08 |
| Pawel Hitczenko | 2 | 52 | 15.48 |