4 ms·

I've looked around abit and pseudorandomness is not an accessible subject, if you have any links for something then please share. I can not judge this, at leas

I've looked around abit and pseudorandomness is not an accessible subject, if you have any links for something then please share. I can not judge this, at least it seems thorough, but too much math but it feels like it at least is a good starting point.

martythemaniak 6y ago
Wolfram has a lot of talks, etc but this interview seems like a decent intro: https://www.youtube.com/watch?v=VguG_y05Xe8 https://www.youtube.com/watch?v=VguG_y05Xe8 Let's implement Rule30, which is quite beautiful and he talks about it a lot: https://mathworld.wolfram.com/Rule30.html https://mathworld.wolfram.com/Rule30.html https://jsfiddle.net/zL6pgyo4/1/ https://jsfiddle.net/zL6pgyo4/1/ We start with a simple seed and apply a set of simple rules over and over again. If you scroll past the first few lines of the output, you start to get very complicated patters. If you try other rules, you usually don't see any patterns or anything interesting, rule30 is kind of rare. Wolfram's done some analysis and he says if you go down the central line (assuming the width keep on growing, which is not the case in my fiddle), and take each "bit" (which I represent as "-" and "X") and plot it, you'll find they're fairly uniformly distributed. Once we have these stream of uniformly distributed bits, you can convert it a string of integers or whatever you need. For the math behind whether something is random or not, you can look up the "chi squared test", but I think the intuition is way simpler - random things are uniformly distributed. Random things look like white noise on old TVs. If you plot the frequency of their occurrence, each one should be just as likely as every other thing. In our example, if you take the output, flatten it into a string, segment it into chunks of 8 (representing a byte), then count the occurrence of each byte ("--------", "-------X", "------X-") they should have the same number of occurrences.
price 6y ago
Here's an alternative exposition (by Goldreich) recommended in this one's introduction: http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html It ends up getting pretty mathematical too, but it seems like Goldreich takes more time up front to really get into the concepts at a philosophical level before proceeding to the math - so you might enjoy reading the introduction, if nothing else.

martythemaniak 6y ago

Wolfram has a lot of talks, etc but this interview seems like a decent intro: https://www.youtube.com/watch?v=VguG_y05Xe8 https://www.youtube.com/watch?v=VguG_y05Xe8 Let's implement Rule30, which is quite beautiful and he talks about it a lot: https://mathworld.wolfram.com/Rule30.html https://mathworld.wolfram.com/Rule30.html https://jsfiddle.net/zL6pgyo4/1/ https://jsfiddle.net/zL6pgyo4/1/ We start with a simple seed and apply a set of simple rules over and over again. If you scroll past the first few lines of the output, you start to get very complicated patters. If you try other rules, you usually don't see any patterns or anything interesting, rule30 is kind of rare. Wolfram's done some analysis and he says if you go down the central line (assuming the width keep on growing, which is not the case in my fiddle), and take each "bit" (which I represent as "-" and "X") and plot it, you'll find they're fairly uniformly distributed. Once we have these stream of uniformly distributed bits, you can convert it a string of integers or whatever you need. For the math behind whether something is random or not, you can look up the "chi squared test", but I think the intuition is way simpler - random things are uniformly distributed. Random things look like white noise on old TVs. If you plot the frequency of their occurrence, each one should be just as likely as every other thing. In our example, if you take the output, flatten it into a string, segment it into chunks of 8 (representing a byte), then count the occurrence of each byte ("--------", "-------X", "------X-") they should have the same number of occurrences.

price 6y ago

Here's an alternative exposition (by Goldreich) recommended in this one's introduction: http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html It ends up getting pretty mathematical too, but it seems like Goldreich takes more time up front to really get into the concepts at a philosophical level before proceeding to the math - so you might enjoy reading the introduction, if nothing else.