Spectral Gap
The difference between the largest eigenvalue (1) and the absolute value of the second-largest eigenvalue of a Markov chain transition operator. It measures the mixing speed of the chain: a larger spectral gap implies faster convergence to the stationary distribution.
Timeline (last 90 days)
The paper establishes non-asymptotic, high-probability upper bounds for the convergence of empirical occupation measures to the invariant measure, under the contraction assumption in kernel-induced geometry and the standard spectral gap assumption.
In the convergence bounds of this paper, the spectral gap determines the effective sample size in the dominant term.
For a reversible Markov chain, the largest eigenvalue of the transition operator is 1, the absolute value of the second largest eigenvalue is denoted λ₂, and the spectral gap is defined as 1−|λ₂|.
For a Markov chain with spectral gap γ, the effective sample size is approximately nγ and the mixing time is approximately 1/γ.
All Facts (4)
The paper establishes non-asymptotic, high-probability upper bounds for the convergence of empirical occupation measures to the invariant measure, under the contraction assumption in kernel-induced geometry and the standard spectral gap assumption.
50%UnverifiedIn the convergence bounds of this paper, the spectral gap determines the effective sample size in the dominant term.
50%UnverifiedFor a reversible Markov chain, the largest eigenvalue of the transition operator is 1, the absolute value of the second largest eigenvalue is denoted λ₂, and the spectral gap is defined as 1−|λ₂|.
50%UnverifiedFor a Markov chain with spectral gap γ, the effective sample size is approximately nγ and the mixing time is approximately 1/γ.
50%