def GenerateTransitionMatrix(counts):
    """
    Convert a countr matrix into a probability transition matrix.
    @param counts: for each key, how many times is the future node seen
    """
    transitions = {}

    for key in counts:
        destination_actions = counts[key]

        # initialize the empty list
        transitions[key] = []

        # how many times was this key seen
        noccurrences = 0

        for action in destination_actions:
            noccurrences += destination_actions[action]

        # keep track of cumulative probabilities
        cumulative_probability = 0.0
        for action in destination_actions:
            cumulative_probability += destination_actions[action] / noccurrences
            transitions[key].append((cumulative_probability, action))

    return transitions