.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that functions of random variables are typically near their means. Of particular importance is the case wheref(X) is a function of independent random variablesX= (X1, . . .,Xn). Here the well-knownbounded differences inequality(also called McDiarmid's inequality or the Hoeffding–Azuma inequality) establishes sharp concentration if the functionfdoes not depend too much on any of the variables. One attractive feature is that it relies on a very simple Lipschitz condition (L): it suffices to show that |f(X) −f(X′)| ⩽ckwheneverX, X′differ only inXk. While this is easy to check, the main disadvantage is that it considersworst-casechangesck, which often makes the resulting bounds too weak to be useful.In this paper we prove a variant of the bounded differences inequality which can be used to establish concentration of functionsf(X) where (i) thetypicalchanges are small, although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple condition that (a) is easy to check and (b) coincides with heuristic considerations as to why concentration should hold. Indeed, given an event Γ that holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where Γ occurs. The point is that the resultingtypicalchangesckare often much smaller than the worst case ones.To illustrate its application we consider the reverseH-free process, whereHis 2-balanced. We prove that the final number of edges in this process is concentrated, and also determine its likely value up to constant factors. This answers a question of Bollobás and Erdős.
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息