You can have 100% accuracy with non-determinism. The time is just variable.

https://en.wikipedia.org/wiki/Las_Vegas_algorithm

This is not to say you can ALWAYS have 100% accuracy from something non-deterministic. Just that non-determinism doesnt necessarily make something inaccurate.