def weighted_random(sample, embedding):
    """Determines the sample values by weighed random choice.

    Args:
        sample (dict): A sample of the form {v: val, ...} where v is
            a variable in the target graph and val is the associated value as
            determined by a binary quadratic model sampler.
        embedding (dict): The mapping from the source graph to the target graph.
            Should be of the form {v: {s, ...}, ...} where v is a node in the
            source graph and s is a node in the target graph.

    Yields:
        dict: The unembedded sample. When there is a chain break, the value
        is chosen randomly, weighted by the frequency of the values
        within the chain.

    """
    unembeded = {}

    for v, chain in iteritems(embedding):
        vals = [sample[u] for u in chain]

        # pick a random element uniformly from all vals, this weights them by
        # the proportion of each
        unembeded[v] = random.choice(vals)

    yield unembeded