标题： 从短轨迹估计可逆马尔可夫链的谱隙 显示英文标题

标题： Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory

摘要： 遍历且可逆的马尔可夫链的谱隙 $\gamma$ 是衡量渐近收敛速率的一个重要参数。 在应用中，转移矩阵 $P$ 可能未知，但可以观察到链的一次采样直至固定时间 $t$。 Hsu、Kontorovich 和 Szepesvári（2015）考虑了从此数据估计 $\gamma$ 的问题。 设 $\pi$ 为 $P$ 的平稳分布，以及 $\pi_\star = \min_x \pi(x)$。 他们证明了，如果$t = \tilde{O}\bigl(\frac{1}{\gamma^3 \pi_\star}\bigr)$，则$\gamma$可以以高概率被估计到乘法常数的精度。他们还证明了需要$\tilde{\Omega}\bigl(\frac{n}{\gamma}\bigr)$步才能精确估计$\gamma$。我们表明，链的$\tilde{O}\bigl(\frac{1}{\gamma \pi_\star}\bigr)$步就足以以高概率将$\gamma$估计到乘法常数的精度。当$\pi$是均匀分布时，这与 Hsu、Kontorovich 和 Szepesvári 的下界匹配（对数修正项除外）。 显示英文摘要

摘要： The spectral gap $\gamma$ of an ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $t$ may be observed. Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating $\gamma$ from this data. Let $\pi$ be the stationary distribution of $P$, and $\pi_\star = \min_x \pi(x)$. They showed that, if $t = \tilde{O}\bigl(\frac{1}{\gamma^3 \pi_\star}\bigr)$, then $\gamma$ can be estimated to within multiplicative constants with high probability. They also proved that $\tilde{\Omega}\bigl(\frac{n}{\gamma}\bigr)$ steps are required for precise estimation of $\gamma$. We show that $\tilde{O}\bigl(\frac{1}{\gamma \pi_\star}\bigr)$ steps of the chain suffice to estimate $\gamma$ up to multiplicative constants with high probability. When $\pi$ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.