My confusion is with your claim that the Rigol could theoretically anti-alias without doing the random decimation before storing samples into the waveform. If it can sample fast enough to store that sine wave into sample memory, it already doesn't alias. (If that sine wave is in sample memory, the aliased low frequency sine wave will never be what's on the screen.)
It's about speed!
At 5ms/div, with a 56M sample length, the Rigol is sampling at 500MSa/s. With those settings,
the interface is slow!. Do you know why? Not because of the sampling time - its capturing ~6 wfrm/s (compared to ~14 wfrm/s with a 14k sample length). It's because the Rigol has to reduce (decimate) those 56 million sample bytes to the 1400 bytes of display memory - and that takes a hell of a long time.
OTOH, let's say the Rigol only has to decimate a 4000th of that amount of memory (14k) to the 1400 bytes - do you think it might be faster? You can test this quite easily: just see how responsive the scope is at 5ms/div with a 14k sample length - and then with a 56M sample length.
So, if the DSO just grabs every 4000th byte of sample memory for decimation, things will certainly speed up, but the sample rate will then become equivalent to 125kSa/s, and all of a sudden aliasing will be a problem.
But not if it does RANDOM decimation with those 14k samples, varying the number of sample it grabs between the Nth and 4000th.
So all of a sudden, you have a DSO working faster at a lower sample rate, but without aliasing.
How much faster? Test the responsiveness of the DSO with a 56M sample length at 5ms/div (it is decimating ALL 56M of 56M), and then again at 500ns/div (it is decimating only 14k of 56M).