Lazy Walk Mixing Steps Estimate

Problem

Estimate the number of steps a lazy random walk needs to mix within epsilon.

Form the lazy normalized walk M = (I + D^-1/2 A D^-1/2) / 2, deflate the stationary direction D^1/2 1, and run 2000 iterations of power iteration on a deterministic start vector to estimate the second eigenvalue mu. Return ceil(ln(n / epsilon) / (1 - mu)), or -1 when some node is isolated or the gap is non-positive. edges is a list of [u, v] pairs.

Hint

Deflating the stationary vector makes power iteration converge to the second eigenvalue.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3],[3,0]],0.01]

expected: 12

case 2

in: [4,[[0,1],[0,2],[0,3]],0.01]

expected: 12

case 3

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]],0.01]

expected: 9

case 4

in: [5,[[0,1],[1,2],[2,3],[3,4]],0.05]

expected: 32

case 5

in: [3,[[0,1]],0.01]

expected: -1

Starter codePython

import math
def mixing_steps_estimate(n, edges, epsilon):
    # Your code here
    pass

5 test cases · run your code against them in the editor