论文标题
改善了非可逆马尔可夫链中松弛时间的估计
Improved Estimation of Relaxation Time in Non-reversible Markov Chains
论文作者
论文摘要
我们表明，在持续的乘法错误中，以$ \tildeθ\ left（\ frac {1} {1} {γ_{γ_ {γ{γ{ps persssf}}的顺序，用于估算估算伪贡克马尔可夫链的伪谱间隔$γ_ { \ right），$$，其中$π_\ star $是最低固定概率，在可逆环境中恢复了已知的界限，以估计绝对光谱差距[Hsu等，2019]，并解决了Wolfer和Kontorovich的开放问题[2019]。此外，我们通过使其完全适应数据，减少置信区间并降低计算复杂性来增强已知的经验程序。一路上，我们得出了伪谱间隙的新特性，并引入了随机基质的可逆扩张的概念。
We show that the minimax sample complexity for estimating the pseudo-spectral gap $γ_{\mathsf{ps}}$ of an ergodic Markov chain in constant multiplicative error is of the order of $$\tildeΘ\left( \frac{1}{γ_{\mathsf{ps}} π_{\star}} \right),$$ where $π_\star$ is the minimum stationary probability, recovering the known bound in the reversible setting for estimating the absolute spectral gap [Hsu et al., 2019], and resolving an open problem of Wolfer and Kontorovich [2019]. Furthermore, we strengthen the known empirical procedure by making it fully-adaptive to the data, thinning the confidence intervals and reducing the computational complexity. Along the way, we derive new properties of the pseudo-spectral gap and introduce the notion of a reversible dilation of a stochastic matrix.
