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'

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.