The more randomness, the more information bits you need to encode the observed outcome. But I can see where your dissonance comes from: you probably parsed "information" as "information I already have about the system", not "information I need to describe the system state".