Mixing time of a random walk from the absolute spectral gap

The walk matrix P = D^-1 A is similar to D^-1/2 A D^-1/2, so its spectrum is real and comes from a symmetric eigenproblem. The bound uses the ABSOLUTE spectral gap gamma* = 1 - max_{i>=2} |lambda_i|: a bipartite graph has lambda_n = -1 and never mixes, which the signed gap misses.

Usage

Sgtmix(A, epsilon = 0.01)

Arguments

A

Symmetric non-negative adjacency; positive row sums.

epsilon

Total-variation target in (0, 1).

Value

List with tau_mix, estimate, gap, slem, n.

Details

Formula: tau_mix(eps) <= log(1 / eps) / gamma*.

References

Levin, D. A., Peres, Y. & Wilmer, E. L. (2017). Markov Chains and Mixing Times, 2nd edition, American Mathematical Society; Theorem 12.4.

Examples

A <- matrix(c(4, 1, 0.5, 1, 3, 0.8, 0.5, 0.8, 2), nrow = 3)
res <- Sgtmix(A = A)
res
#> $tau_mix
#> [1] 10.36941
#> 
#> $estimate
#> [1] 10.36941
#> 
#> $gap
#> [1] 0.4441113
#> 
#> $slem
#> [1] 0.5558887
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "Relaxation-time mixing bound, log(1/eps)/gamma*"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"