Empirical Probability Mass Function (PMF)

Problem

Given a dataset of discrete outcomes, compute the Empirical Probability Mass Function (PMF). For each unique value in the data, calculate the fraction of times it appears. Return a dictionary mapping each unique value to its probability.

Solution

def empirical_pmf(data: list) -> dict:
    counts = {}
    n = len(data)
    for x in data:
        counts[x] = counts.get(x, 0) + 1
    pmf = {}
    for k in sorted(counts.keys()):
        pmf[k] = round(counts[k] / n, 4)
    return pmf

Explanation

1. Count how many times each unique value appears in the dataset using a dictionary.
2. Divide each count by the total number of observations n to get the probability.
3. Return the result sorted by key for consistency.

Complexity

• Time: O(n + k log k) where n is the number of data points and k is the number of unique values (sorting the keys)
• Space: O(k) for storing counts and the PMF dictionary