Any page replacement policy/algo. suffers from Belady's Anomaly's iff its does not follow "STACK ALGORITHM" . LRU and Optimal always follow the stack algorithm property. So they never suffers from Belady's Anamoly.
You have to understand Stack Algorithm first.
As far as you question is concerned ,Answer is "YES,Random page replacement algorithm may suffers from Belady's Anomaly".