  For a broad class of input-output maps, arguments based on the coding theorem
from algorithmic information theory (AIT) predict that simple (low Kolmogorov
complexity) outputs are exponentially more likely to occur upon uniform random
sampling of inputs than complex outputs are. Here, we derive probability bounds
that are based on the complexities of the inputs as well as the outputs, rather
than just on the complexities of the outputs. The more that outputs deviate
from the coding theorem bound, the lower the complexity of their inputs. Our
new bounds are tested for an RNA sequence to structure map, a finite state
transducer and a perceptron. These results open avenues for AIT to be more
widely used in physics.
