We propose a novel approach to concentration for non-independent random variables. The main idea is to ``pretend'' that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper bounded leveraging tensorisation properties. Our bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid's inequality) when the random variables are independent. Furthermore, in a ``large deviations'' regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies. To show this, we consider a number of applications of interest. First, we provide a bound for Markov chains with finite state space. Then, we consider the Simple Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting in which the stochastic process depends on its entire past. To conclude, we propose an application to Markov Chain Monte Carlo methods, where our approach leads to an improved lower bound on the minimum burn-in period required to reach a certain accuracy. In all of these settings, we provide a regime of parameters in which our bound fares better than what the state of the art can provide.
翻译:我们提出一种新的方法来集中非独立随机变量。 主要的想法是“ 假设 ” 随机变量是独立的, 并支付一个倍增价格, 以衡量它们实际上离独立有多远。 这一价格被封在边际联合和产品之间的希腊格灵格整体中, 后者是高度捆绑的拉拉度特性。 我们的界限代表了依赖性情况下集中不平等的自然概括化: 当随机变量是独立的时, 我们完全恢复了经典界限( 麦克迪亚米德的不平等 ) 。 此外, 在“ 大偏差” 的制度中, 我们获得与独立案例相同的衰败概率, 即使随机变量显示非三角依赖性。 为了显示这一点, 我们考虑了一系列利益应用。 首先, 我们为Markov 链提供了一条带有有限状态的束缚。 然后, 我们考虑简单度随机行走法, 这是一种不承包的马科夫的参数, 以及一个非马尔科米亚的设置, 它取决于整个“ 大规模偏差” 。 在“ 偏差” 制度下, 我们提出一个最起码的连锁, 我们提出一个更精确到一个最起码的路径。</s>