[carlmr]

>>When Are Randomized Algorithms Better Than LRU?

>When the access pattern is random: recently used items are not more likely to be accessed than other items.

Wouldn't they perform equally well in this case? There's no advantage in LRU, but also no disadvantage if they're really unpredictably random.

[adrianN]

A random strategy has less overhead than LRU because there is no bookkeeping.

[dan-robertson]

This argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”

[carlmr]

Yes, and bookkeeping and randomness both cost something.