Total Variation Distance

Total variation distance is a way of quantifying how different two probability distributions are by looking at the biggest possible gap in the chances they assign to the same event. Imagine you have two ways of describing the outcomes of a random process; the total variation distance asks, for any set of outcomes you could pick, what is the largest difference between the probabilities that each description gives to that set. In other words it measures the maximum discrepancy one could observe if you tried to decide which distribution generated an observed outcome.

This notion matters because it provides a clear and interpretable bound on how distinguishable two random models are. A small total variation distance guarantees that any statistical test will have little power to tell the distributions apart, while a large distance means there is at least one event that occurs with very different likelihoods under the two models. The concept shows up whenever people need to compare randomness: in theoretical work on how quickly Markov chains converge to their steady state, in privacy research where it describes how much information an adversary can gain from a perturbed dataset, and in machine learning when evaluating how closely a learned model matches the true data-generating distribution.