What makes it possible to learn probability distributions in the natural world?

Organisms and algorithms learn probability distributions from previous observations, either over evolutionary time or on the fly. In the absence of regularities, estimating the underlying distribution from data would require observing each possible outcome many times. Here we show that two conditions allow us to escape this infeasible requirement. First, the mutual information between two halves of the system should be consistently sub-extensive. Second, this shared information should be compressible, so that it can be represented by a number of bits proportional to the information rather than to the entropy. Under these conditions, a distribution can be described with a number of parameters that grows linearly with system size. These conditions are borne out in natural images and in models from statistical physics, respectively.