redlizard comments on The Power of Noise - LessWrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (80)
Another way of swapping around the question is to ask under what circumstances Jacob Steinhardt would refuse to use a PRNG rather than an RNG because the PRNG wasn't random enough, and whether there's any instance of such that doesn't involve an intelligent adversary (or that ancient crude PRNG with bad distributional properties that everyone always cites when this topic comes up, i.e., has that happened more recently with an OK-appearing PRNG).
Obviously I don't intend to take a stance on the math-qua-math question of P vs. BPP. But to the extent that someone has to assert that an algorithm's good BPP-related properties only work for an RNG rather than a PRNG, and there's no intelligent adversary of any kind involved in the system, I have to question whether this could reasonably happen in real life. Having written that sentence it doesn't feel very clear to me. What I'm trying to point at generally is that unless I have an intelligent adversary I don't want my understanding of a piece of code to depend on whether a particular zero bit is "deterministic" or "random". I want my understanding to say that the code has just the same effect once the zero is generated, regardless of what factors generated the zero; I want to be able to screen off the "randomness" once I've looked at the output of that randomness, and just ask about the effectiveness of using a zero here or a one there. Furthermore I distrust any paradigm which doesn't look like that, and reject it as something I could really-truly believe, until the business about "randomness" has been screened off and eliminated from the analysis. Unless I'm trying to evade a cryptographic adversary who really can predict me if I choose the wrong PRNG or write down my random bits someplace that someone else can see them, so that writing down the output of an RNG and then feeding it into the computation as a deterministic constant is genuinely worse because my adversary might sneak a look at the RNG's output if I left it written down anywhere. Or I'm trying to randomize a study and prevent accidental correlations with other people's study, so I use an RNG just in case somebody else used a similar PRNG.
But otherwise I don't like my math treating the same bit differently depending on whether it's "random" or "deterministic" because its actual effect on the algorithm is the same and ought to be screened off from its origins once it becomes a 1 or 0.
(And there's also a deep Bayesian issue here regarding, e.g., our ability to actually look at the contents of an envelope in the two-envelope problem and update our prior about amounts of money in envelopes to arrive at the posterior, rather than finding it intuitive to think that we picked an envelope randomly and that the randomized version of this algorithm will initially pick the envelope containing the larger amount of money half the time, which I think is a very clear illustration of the Bad Confused Thoughts into which you're liable to be led down a garden-path, if you operate in a paradigm that doesn't find it intuitive to look at the actual value of the random bit and ask about what we think about that actual value apart from the "random" process that supposedly generated it. But this issue the margins are too small to contain.)
Is that helpful?
A more involved post about those Bad Confused Thoughts and the deep Bayesian issue underlying it would be really interesting, when and if you ever have time for it.