I should probably stress that I agree with you on pretty much everything except that last sentence.
As for the Miller-Rabin test, it's basically a case where you can get a correct answer with an arbitrarily low probability of error. So I guess the tie in is that just because our decisions are predictable (or at least mostly so), doesn't mean there isn't randomness involved.
I'm starting to suspect that I'm responding to an interpretation you didn't intend, though.