You make in interesting point. Much of algorithmic information theory seems to be focused on the worst case, when the average behavior may be more relevant -- a

You make in interesting point. Much of algorithmic information theory seems to be focused on the worst case, when the average behavior may be more relevant -- and significantly more pleasant. It brings to mind Zipf's law and optimal coding. There's a 'no-free-lunch' theorem waiting to be discovered, I suspect -- or maybe it already exists and I just haven't heard of it. Something along the lines that optimal encoding maximizes the channel capacity, but makes the worst case error exponentially disastrous.