import random


def sampling(probs):
    """
    Dictionary key samplin -- the sampling probability of a key is proportional to the value.
    :param probs: Probability distribution over keys in a dictionary.
    :return key: Sampled key.
    """
    prob = random.random()
    score = 0
    for key, value in probs.items():
        score = score + value
        if prob <= score:
            return key
    assert False, 'unreachable'