You NEED tests to behave consistently. If you run the tests twice against the same code, it needs to return the same result. Otherwise, how will you know you have fixed the issue the tests caught?
Speaking from experience, soon after you introduce randomness to tests, you will start to get intermittent test failures. When that happens, people will start to ignore failing tests because, 'hey, this is probably just a random failure'