An example of a bad case for random exploration would be a narrow ridge where you die if you fall off and you only receive reward if you get to the end.

So it's a worst case result with respect to the MDP, but expected time/high probability with wrt random chance.