If the output is random,then it will have no mathametical structure,so I shouldn't be able to compress it at all.
You could very well end up with all tails. That's a sequence that has the same probability of happening that any other sequence. A compressor will look for redundancy in the input you give it, not in the algorithm you used to generate that input (conceptually, a compressor could deduce the (determinist) algorithm from the output, but if you bring it true randomness, chances are it will not). Thus, a compressor will compress very well a sequence made of all tails, but badly another which exhibits no detectable redundancy. Once you have the sequence, you lost a lot of info about whatever algorithm was used to generate it. A sequence of all tails could have been generated by a simple algorithm which generates all tails. That's an emergement description of this one particular sequence, but one that would not apply to *all* sequences your algorithm can ever produce. That's lost information, and that's why it can be compressed. -- Vincent Penquerc'h