def METHOD_NAME(states):
    cumulative = []
    p = 0
    for state, prob in states.items():
        cumulative.append((state, p + prob))
        p += prob
    assert round(p, 3) == 1
    r = random.random()
    for state, prob in cumulative:
        if r <= prob:
            return state
    assert False