3 ms·
I'm programmer - for me random string is a string, that is shorter than any programm that generates it (random string has Kolmogorov complexity greater or equal
by ajuc 16y ago
I'm programmer - for me random string is a string, that is shorter than any programm that generates it (random string has Kolmogorov complexity greater or equal its length).
I think this is the definition for mathematicians as well.
It's just that "random" is a common shortcut for - string comming out of probability experiment - it is very likely that it is random according to Kolmogorov complexity, because most strings are random, and space is very very big.
- omaranto 16y agoWhile I think that while most mathematicians are aware of Kolmogorov/Chaitin complexity theory, the first thing that comes to mind when they hear "random" is the theory of probability. In probability a random variable is, roughly speaking, an experiment that has a set of possible outcomes each occuring with a certain probability. The probabilities are not necessarily the same. I think most mathematicians would agree that Probability is a much larger and important branch of mathematics than Kolmogorov-Chaitin complexity, and usually use "random" in its probabilistic meaning.
- ajuc 16y agoI was always confused by lack of definition of randomness in statistic/probabilistic meaning, so I've somewhat mixed these 2 branches of math. Thanks for clearing this up.