[chmike]

It depends on the distribution of probabilities of being used. If least recently used data has the same probability to be requested than the others, then random picking will do as well as LRU.

When the least recently used data does have a lower probability to be requested, than LRU will outperform random picking.

There is no silver bullet algorithm.