Mixing Bound Lite

Problem

Compute the standard upper bound on the mixing time of a lazy random walk on a connected graph with n nodes.

Given the spectral gap gap and target accuracy epsilon, return ceil(ln(n / epsilon) / gap) as an integer. Use the natural logarithm.

Hint

A larger spectral gap means faster mixing and a smaller bound.

case 1

in: [100,0.1,0.01]

expected: 93

case 2

in: [4,0.5,0.25]

expected: 6

case 3

in: [16,0.25,0.001]

expected: 39

case 4

in: [10,1,0.1]

expected: 5

Starter codePython

import math
def mixing_bound(n, spectral_gap, epsilon):
    # Your code here
    pass

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