A Hoeffding inequality for Markov chains
A Hoeffding inequality for Markov chains
复制标题
马尔可夫链的 Hoeffding 不等式
DOI：
--
复制
发表时间：
2018
影响因子：
0.5
通讯作者：
Shravas Rao
中科院分区：
文献类型：
--
作者：
Shravas Rao
我们证明随机变量 $sum_{i=1}^{n} f_i(Y_i)$ 的偏差界限，其中 ${Y_i}_{i=1}^{infty}$ 是具有平稳分布和状态空间 $[N]$ 的可逆马尔可夫链，并且 $f_i: [N]
ightarrow [-a_i, a_i]$。我们的界限改进了先前已知的界限，因为依赖于 $sqrt{a_1^2+cdots+a_n^2}$ 而不是 $max_{i}{a_i}sqrt{n}。$ 我们还以类似的方式证明了从马尔可夫链获得的某些类型的向量值随机变量之和的偏差界限。一种应用包括限制随机矩阵的 Schatten $infty$ 范数的期望值，该随机矩阵的条目是从马尔可夫链获得的。
We prove deviation bounds for the random variable $sum_{i=1}^{n} f_i(Y_i)$ in which ${Y_i}_{i=1}^{infty}$ is a reversible Markov chain with stationary distribution and state space $[N]$, and $f_i: [N]
ightarrow [-a_i, a_i]$. Our bound improves upon previously known bounds in that the dependence is on $sqrt{a_1^2+cdots+a_n^2}$ rather than $max_{i}{a_i}sqrt{n}.$ We also prove deviation bounds for certain types of sums of vector--valued random variables obtained from a Markov chain in a similar manner. One application includes bounding the expected value of the Schatten $infty$-norm of a random matrix whose entries are obtained from a Markov chain.