A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
复制标题
独立多路选择函数的大偏差不等式
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
David A. Grable
中科院分区：
文献类型：
--
作者：
David A. Grable
通常，当分析随机算法，尤其是并行或分布式算法时，有人要求表明许多独立选择的某些功能紧密集中于其预期值。例如，该算法可能会为给定图的顶点带有两种颜色，并希望表明，以高概率，几乎所有边缘的一半都是单色的。当函数是独立指标随机变量之和时，Chernoff [3]的经典结果给出了如此大的偏差结果。 Hoeffding [5]和Azuma [2]的结果给出了类似的结果，该功能可以表示为具有界差属性的Martingales。粗略地说，这意味着每个选择对函数的价值都有界限。 McDiarmid [9]很好地总结了这些结果，并提供了许多应用程序。表达有所不同，他的主要结果如下。
Often when analysing randomized algorithms, especially parallel or distributed algorithms, one is called upon to show that some function of many independent choices is tightly concentrated about its expected value. For example, the algorithm might colour the vertices of a given graph with two colours and one would wish to show that, with high probability, very nearly half of all edges are monochromatic. The classic result of Chernoff [3] gives such a large deviation result when the function is a sum of independent indicator random variables. The results of Hoeffding [5] and Azuma [2] give similar results for functions which can be expressed as martingales with a bounded difference property. Roughly speaking, this means that each individual choice has a bounded effect on the value of the function. McDiarmid [9] nicely summarized these results and gave a host of applications. Expressed a little differently, his main result is as follows.