Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?

Question

I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1.

You take a test sequence and compress it with a standard compression algorithm. You then shuffle that sequence randomly using a PRNG, and re-compress. We expect that the randomly shuffled sequence to be harder to compress as any and all redundancy and correlations will have been destroyed. It's entropy will have increased.

So if there is any auto correlation, $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} > 1$ .

This works using NIST's recommended bz2 algorithm, and on my data samples, the ratio is ~1.03. This indicates a slight correlation within the data. When I switch to LZMA, the ratio is ~0.99 which is < 1. And this holds over hundreds of runs so it's not just a stochastic fluke.

What would cause the LZMA algorithm to repetitively compress a randomly shuffled sequence (slightly) better than a non shuffled one?

Answer 1

I now think that it's because of this:-

ZPAQ has 5 compression levels from fast to best. At all but the best level, it uses the statistics of the order-1 prediction table used for deduplication to test whether the input appears random. If so, it is stored without compression as a speed optimization.

... from https://en.wikipedia.org/wiki/ZPAQ#Compression

I'm referring to LZMA in my question, but I'm not familiar with how it's implemented in code. If it followed the same speed optimisation strategy as ZPAQ, the hypothesis would be consistent with my observations. You can imagine in edge cases where $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} = 1 - \epsilon $, that an $n$ order predictor decides that there is insufficient advantage to be had due to the necessary compression encoding overhead. My $\alpha \approx 0.01$, but recently I've seen it as high as 0.04.