如何確定此概率的上界？

12-30

已知 $x_{1}，...,x_{n}$ 是weakly dependent的隨機變數， $c_{1},...,c_{n}$ 是實數，記 $S_{n}=c_{1}x_{1}+...+c_{n}x_{n}$ 。如何確定 $Pleft{ |S_{n}-ES_{n}|>lambda<br /> ight}$ 的上界，其中 $lambda$ 是某個正實數？非概率專業，在研究一個計量模型的時候遇到這個問題，看了很多論文，但是仍一頭霧水，請大家指教。

這個問題屬於一系列的 concentration inequality。上界的取決於幾個因素：（為了討論方便，我們暫時把係數c_n一起算到x_n里。即 x"_n = c_n x_n）

1、x_i 的bound和tail： x_i 是否一致有界，比如都在[a,b]之間。如果不是一致有界，那麼tail是什麼樣子的。比如sub-Gaussian， sub-exponential （i.e. 比正態decay快，比指數分布decay快）。一般來說上界的大小：有界 ~ sub-Gaussian &< sub-exponential &< power-law.

這個主要影響到是如下的問題：假如S_n 很大，那麼究竟是因為某一個x_i特別大，還是因為很多x_i都大一點點。

一般來說，越heavy tail比如powerlaw 和 sub-exponential，越偏向於第一個原因。此時對比較大的lambda，最後的上界基本上就是union bound 即一個X_i比較大的概率乘以n。

i.e. P(S_n &> lambda) ~ nP(X_1&>lambda)。

有界和sub-Gaussian的情況更偏向於第二個原因，這個時候的上界一般會有一些non-trivial的bound。所以一般性的結論也多數是對有界和sub-Gaussian variable討論的，或者sub-exponential比較小的lambda。

2、x_i的variance：這個和第一點的區別是：比如x_i是取值範圍{0,1}的隨機變數（a.k.a indicator)，取1的概率是p_n。那麼p_n = p (與n無關） p_n = O(n^{-c}),0 &< c &< 1 和 p_n = O(1/n)的時候，最好的bound 都不一樣。

好久之前研究過的一時有點記不清，不過假設 p_n= O(n^{-c})，那麼：

c &<= 1/2的時候： Azuma-Hoeffding最好（Chernoff是Azuma-Hoeffding的簡化版）

1/2 &< c &< 1的時候：對比較小的lambda，Bernstein 給的bound 要好於 Azuma-Hoeffding

（Azuma 是 Bernstein的一個特例，但Bernstein的形式有點繞，第一次用容易頭暈。）

c &>= 1 的時候：直接用 Binomial收斂到 Poisson就好了。

此外還有Bennett inequality，但我一直沒有用過。可以參見wiki的討論：Bennett"s inequality

以及這裡我說的最好都是類似於O(exp{-clambda^epsilon})的形式下最好的epsilon。對於c的optimization也有，但就更細緻了。

3、x_i間的dependency：其實以上的不等式最基本的形式都是要求x_i i.i.d. 或者一致有界。但其實這些不等式基本上都可以放寬到weakly dependent，一般有兩種表示方式：

bounded martingale difference：比如Doob martingale - Wikipedia 裡面的McDiarmid inequality。
第二種也和martingale相關。大概是說conditioned on x_1,...,x_{i-1}，x_i的conditional distribution依舊是bounded/sub-Gaussian等等。比如這篇很新的文章里的情形https://arxiv.org/pdf/1109.4359.pdf

總之如果dependency很weak那麼基本上就不會影響到bound。但證明起來還要看具體的dependency structure 然後從證明裡面hack。

至於證明的方法主要是將各種函數帶入Markov inequality裡面。非獨立情形會用到Doob』s martingale的技巧。

這個問題按照目前的描述還比較大。這個答案主要是提了幾個進一步細分問題的要點。題主可以按照自己的問題再具體描述一下。

Empirical process for dependent data，dependent一般用mixing condition來刻畫。

對於獨立且加權的隨機變數，Rio(2013)基於McDiarmid inequality給出了加權獨立隨機合的一個上界：

$Pleft{ S_{n}geqlambda ight}leq exp(-frac{||c||_{2}^{1}}{||c||_{2}^{2}}l^{*}(frac{lambda}{||c||_{1}})$ ,

其中 $l^{*}$ 是 $l$ 的Legendre-Fenchel dual（ $l$ 是一個使得 $logE(exp(tc_{i}x_{i}))leq l(t)$ 對於任意的 $tgeq 0$ 恆成立的單增函數）， $||c||_{p}=(c_{1}^p +c_{2}^p+...+c_{n}^p)^{1/p}$ 。