With exploring, the starting state should only affect which local-maximum you end up in. Therefore you need to make an argument that a random starting state is likely to end up in a higher local-maximum than a non-random starting state.
There is always a starting state; using a random one only means you don't know what it is.
There is always a starting state; using a random one only means you don't know what it is.