One thing I've heard is that "randomness" isn't something you can judge by the output of the sequence, but by the process of generating it. That is, knowing all previous outputs of the randomness generator, what is the probability that you can guess the next output? If it is impossible do better than 1/x (where x is the number of possible outputs), then the generator is random. That is of course assuming you want uniform randomness. The sum of two dice rolls can still be considered random, but not uniformly so (for 2D6, there are 6 ways to roll 7 but only 1 way to roll 2 or 12). So the expected amount of correct guesses would be harder to compute.
That’s the basis of Kolmogorov complexity. But if you don’t know the process, how do you figure it out? Consider that encrypted data, by design, looks indistinguishable from random noise. But if the plaintext data has low information content, then it would indeed be highly compressible, you just wouldn’t know it from the encrypted version.
There is a formalization of this called Kolomogorov-Loveland Stochastic. It turns out that there are non-random (in the sense of Kolmogorov complexity) sequences for which it is not possible to guess the next output by any fixed margin over guessing.
Subjective Bayesian statistician here. Bayes (& Price) (1973) asked how to predict the next 0/1 if the sequence was extended. That is, not how to encode n binary digits but the prediction of digit n+1 given digits 1 to n. Of course, the answer depends on your model for generating digits. Great videos. Keep up the good work.
i feel like another good way of describing this would be "psychological randomness", since it theoretically quantifies how random a sequence *looks*. statistically random sequences can appear less random, because statistical randomness kind of defies human intuition; it's nearly guaranteed you'll find some pattern, however convoluted or imperfect, in any given sequence, because finding patterns is the one thing human brains are really wired for.
These are such quality and entertaining videos, I am truly impressed! Thank you for the content. Cannot find any plausible explanation why these get so undeservingly low views and subscriptions...
Randomness is such a fascinating topic. Something that always boggles my mind is the relationship between randomness and information density. It seems intuitive that true randomness must hold no information. But at the same time something that holds maximum information will be maximally close to randomness. Consider a string of text. It will hold information, but because of the redundancy you can compress it. So long as it is not maximally complex you can continue to compress it. Once you no longer can, it will pass tests for randomness. But at the same time is maximally information dense. So seemingly minimal entropy (maximum information density) is indistinguishable from maximum entropy (pure randomness). Am i missing something?
I think that the problem is that we often confuse "patterns" with "information". We look for patterns to find meaning in things, but patterns are actually a way to _reduce_ information. There's just too much information in the world so we have to look for patterns to compress it into concepts that fit into our brain. If something is truly random, and contains no patterns, then we have trouble getting it into our heads. The best we can do is memorize the digits of Pi. It's sort of like somebody telling you that a lump of coal has more energy in it than a sandwich. Maybe, but I can actually EAT a sandwich! If there's too much information, it's overwhelming and chaotic and we can't use it, so we just dismiss it as "noise".
Glad you've enjoyed the videos! I use Affinity Designer and Procreate for graphics design, I use Blender for modeling and animation, and there's a fair amount of procedural generation for these animations that's done using Python scripts I've written myself.
It's quite interesting too, that if we asked humans to generate a "random" sequence of numbers, The answer with all ones wouldn't come up in their mind easily. It's not "random" enough for a human mind and that's really make it even more random in my opinion.
Dude I feel so much smarter after watching any of your videos. These are the questions I never ask myself, but when you give me the answer I'm like "Woah"
thanks for the information and guidance. She was very clear and all the information she share you could understand them as She explained the in a simple language.
You could associate randomness with entropy. A sequence is most random if it has maximum entropy. You can define, for a specific problem, the maximum available entropy and thus you could determine, relative to the available entropy, the level of randomness or complexity. In your example, lets say, the maximum entropy could be if the sequence has N/2 zeros and N/2 of ones and the maximum number of consecutive symbols should be less than 4.
My definition of randomness would be that given a "random" sequence of length n characters and an alphabet of size p, there is no way to predict the presence of a specific character at a specific location with a greater precision than 1 over p
An interesting alternate intuition on randomness might be 'predictability'. It doesn't really mean anything to say that a given piece of information is 'random'. The number "41" is no more or less inherently random than any other number would be, and its binary string "101001" may or may not be random. In the Kolmogorov interpretation above, it seems like it does indeed satisfy the condition for randomness. Does that make 41 a more 'random' number than 1023 ("1111111111")? The question itself seems like it is not the right one to be asking. On the other hand, we might more usefully talk about the *process* by which data is generated, with the understanding that it will continue to generate data past what we are able to see. A measure of the randomness of that *process* then, could perhaps be related to how many bits of data we need to be able to see to predict the next bit successfully. A sort of 'name that tune' for binary strings. We might call that measure the 'Bound of Predictability' of a process. A 'truly random' process, therefore, being defined as one which is never predictable, would have an infinite Bound of Predictability. Since computers are unable to access true randomness, but can only simulate it with sufficiently complex processes, any process a computer can implement would need to have some finite BoP - I would not be surprised if the BoP function (over the domain of sets of sequence-generating rules) is also incomputable, but that is ultimately conjecture. The question then of whether a given string of data is 'random' could be restated as "How much of this string of data do we need to know in order to predict the rest?" This does give us the intuitive result that a string like "1111111111111111111111111" is extremely predictable, so you would need very few bits in order to come up with the rule 'the next bit is always 1' To make the process more rigorous, we would have to define some way by which the process of predicting is 'updated' with each added bit, and there is the matter of false positives, where the 'wrong' rule 'successfully' predicts the next bit (but not the bit after that; or even the next several bits, before it becomes wrong). We would have to determine whether we are concerned with long-term/wholesale predictability, or partial predictability. For a sequence like "11110111011110111110", the "The next bit is 1" prediction is *usually* correct, but must be discarded after the fifth bit; what prediction might we expect to be made after only 5 bits? How does the predictability of a sequence relate to the predictability of subsequences of that sequence? This does also look to converge with Kolmogorov Complexity in the sense that, for a finite sequence that would have C(x) >= len(x), we also end up with a BoP such that you reach the end of the series without ever knowing what was going to come next, that BoP(the process that producing string X) >= len(X)
There is also a paradox related to this, I don't remember the details but it goes something like "the first number that can not be described by eleven words", which is by this sentence described by 11 words. Or something like this.
The shape of the output you describe is more an unorganized set than a random output, since any random generator is capable of deliver patterns as well as unorganized data sets (take dice for instance, if you throw 12 d6 there are chances for you to end up with a pattern sequence).
I like, "sufficiently difficult to predict". So if you don't see the pattern, it's random; but a property of patterns is that you can predict what comes next, so once you see it, it ceases to be random. Basically I think we should just accept that randomness is subjective.
this is a neat concept! off the top of my head, the downside is that this definition of randomness isn't very practical for evaluating the effectiveness of pseudo-RNG. by definition, pseudo-RNG can be described without listing the complete sequence, but there's diminishing returns as you walk along the axis from "hard to predict" to "hard to compute". I'd love to see a measure of randomness that accounts for this "bang for your buck" intuition, something like "how much output can you produce before an attacker can predict the next bit with 51% certainty? 90%? 99%?"
Typically, we say a good crypto-RNG is such that, given arbitrary amounts of output, producing the next bit with more than 50% certainty should be just as difficult as brute forcing the key/seed. So, bang for your buck is usually more a question of how difficult it is to beat 50% (by ANY amount), not how much you can exceed 50%. Ideally this is a binary question: It either requires brute force or it doesn't. In practice, algorithms often have flaws which reduce their effective key length, so one might say an algorithm's effective key length is reduced by N if one can break it 2^N times faster than brute force. Such a hole is normally considered a vulnerability; we don't want those in our algorithms at all! Even a tiny deviance from 50% is often enough for an oracle attack.
Proving randomness means proving the absence of information about what comes next. Which seems in general impossible to do. (Not the same thing as “you can’t prove a negative”, which is a nonsensical statement, by the way.)
Does this [address] Kolmogorov Complexity? The smallest description of a sequence of bits would be the location of the sequence in a preshared table of sequences. That raises the question, what is the optimal table to preshare?
Fun topic, thanks for bringing this up. I wonder how different would it be if we are looking for a random decimal number. 10101010 may not look random in binary but 170 could look pretty random.
Those are the details mentioned about Turing machines and the choice of language. In practice, it's an additive constant that dwarfs the use we could have for Kolmogorov complexity in our everyday lives. For example, AIXI is the theoretically supreme AI that learns everything that can be learned, as fast as possible (thanks to Solomonoff induction, which hinges on Kolmogorov complexity). But in practice, it is hard to make it yield results in our bounded world because of that pesky constant. The languages we use are typically optimized for the world that actually surrounds us (including programming languages, for the way they are designed to be used in). Simple Turing machines are not.
An interesting distinction is between a random *process* and a random *thing*. With equal probability of "0" and "1", a random process is equally likely to generate strings "011001100001" and "111111111111", even though *as a thing*, "011001100001" seems more random
I feel like now with the breakthroughs in AI technology, a GPT AI could be used to come up with the shortest representation of data to determine how random it is. That could be fit into a function that determines the Kolmogorov complexity of data.
I got chatgpt to find a pattern in a binary string and write the python code for it. This only on 2nd attempt when I asked it to assess the pattern and produce code for it.
Is it uncomputable or incomputable? Also, why is uncomputable? Is it uncomputable like the halting problem, or more like Cantors diagonlization argument ?
Yes, because of the quote marks, or something like that in whatever your description language is -- the mark that distinguishes "run this program" from "just print these digits".
There are actually rules and tests for the evaluation of random number generation algorithms. They are applied to pseudo-random number algorithms (which all "random" number algorithms in computers are), and only those that succeed can be used in critical systems, because otherwise they are a security vulnerability for important algorithms which rely on them, such as encryption key generators. There are several, but all of them describe aspects of one central requirement. Given any previously generated random result or sequence of random results, it is impossible to guess the next random result or sequence of random results with a greater probability then that sequence's chance to appear randomly. Basically, if you have 000 and the possible outcomes are 0 and 1, there should be a 50% chance the next is 0 and the next is 1. A flawed pseudorandom number generator, such as one which only produces infinite 0s, is flawed because you can predict with greater than 50% accuracy the next is 0.
So the Kolmogorov Randomness concept itself is random? Because you can’t compute it’s complexity anyhow, leaving the true complexity to be represented by the item itself (simply because of the fact a f(x) cannot be created), unless there’s approximation functions which then makes this concept more useful.
I define randomness as differing results coming from the same action assuming both happened at the same time. If I dropped a ball, and it bounced forward, and if I were to replay that same moment in time and it were to happen again, that wouldn’t be random. But, if I replayed the same moment in time with the exact same setup as before and got a different result, that would be random.
Are the digits of pi Kolmogorov random? Proving a sequence is Kolmogorov random means that there is no way to predict the next term of the sequence. The digits of pi never repeat, and so would "appear" to be random. But we have computer programs of finite size that can theoretically calculate the nth digit of pi for any n, given sufficient processing time.
So no, the digits of pi are *not* random. Neither is e, or the golden ratio, or any other computable irrational number. Don't use any widely-known irrational number as keys for cryptography, because then the key isn't the number, but the program to generate it. What pi, or e, or any other irrational number *might* be is "normal". The intuitive definition of "normal" is that every sequence of digits is equally likely to be in the number someplace. A little bit more rigor -- For any finite substring of digits, you can count and see that 0 is there 10% of the time, as are 1, 2, etc. 00 is there 1% of the time, as is 01, 02, 97, etc. If every possible substring occurs equally often, then the string of digits is normal. Obviously for a finite string of digits, say 10 digits 4731890562, you run into trouble when you try to find every 10 digit substring, because there are 10 billion of those and only one string. So, no finite string of digits can be normal. However, just because a number is normal, doesn't mean it's random. For instance, the first number ever proven to be normal is just the concatenation of each subsequence in order. It starts 0.123456789000102030405... first the one-digit substrings, then the two digit substrings 00,01,02, etc. Once you do this to infinity, every possible sequence will appear exactly as often as we expect. But, the program to generate this number is a Python one-liner.
I'm not a mathematician but instead of an arbitrary language, be it programming or human-words, why not use the most concise language we could use; math? Say I describe prime numbers, I'd say: For a whole number n, n should not have a smaller whole number d that is divisible without a remainder, except for 1. This expression would feel very Pythonic,, but can't we estimate some weights to operators (for, if X is ..., but/except for...)? For a somewhat complex notion like sum of values, or derivative of a function at different values, it's way less random, and succinct, than describing mod(X, Y+n) for n
how about i want a random number between 0 and 8192.. am i supose to refuse 256 or 1024 or 4096 (as binary ofcourse, as decimal i can say numbers like 5000 or 7000) because there is a pattern there too "first number is 7 and the rest is 0" or for binary 4096 is 1000000000000 and why would i refuse that number... i think its more related to repetition of the return value
But how is a pattern found in the sequence? The examples you gave rely on the brain's pattern recognition; is there no algorithmic way that always finds the pattern in a sequence if the pattern exists?
If we consider a bit value generator(1001110...) whose length is 8 bits, then isn't getting 11111111 equally random as getting 10010110? Let's say, today is my birthday and "coincidentally", today I also got a holiday from my school, so it is coincidental but also random... Randomness means a situation or a system which is unbiased and whatever will be the event, it will be still random, be it 11111111 or 10010101....
Exactly, if anyone looks at one number from generator, whatever it is it's always legit random number. He mentioned sequences but it wasn't clearning stated if it was sequence of bits, bytes or if this was whole 32bit number. If this was the case of 32bit number then if you look at it at as a decimal number then it would look like a legit random number from the range of 0 to 4294967296.
So true randomness can be gained using quantum mechanics. This stuff can used for non security applications like games. Now for human randomness or whatever this was called lmao, that seems random should used for security applications
I believe things can be random if you add a concept of mistake and uncertain probability. Taking a series of pie and choosing numbers based on time of day x weather x number of news link x... can create the perfect random function.
That’s how most video games do random number generation, and one look at a speed run of one of those games will tel you the system is not perfect at all. If you know the variables that determine something, affecting the outcome is as straightforward as altering those variables.
@@pretzelbomb6105 to be fair, speedruns that depend on RNG manipulation are usually tool-assisted - meaning the runner can see the current status of the RNG, and via usage of save states and slowing down the game, perform exactly the correct actions at exactly the correct time to get the state they need when they need it. true, the system still isn't perfect because it _can_ be manipulated, but it's very hard to do so without breaking the game open like that.
It took me like 5 minutes to come up with a "function" to compute Kolmogrov complexity... only works for binary numbers though. Thinking "length" is a misnomer here.
This is one of those things that tends to open up a can of worms very quickly, like using ZFC as your set theory and then using the Continuum _Theorem_ in proofs. There's not really a useful definition of randomness because when you finally get to the intuitive grain people consider as "random", they start describing things that start resembling independence and correlation. All you're left with is "random" is just anything that isn't deterministic, which itself does not have the most interesting definition either. What's infinitely more interesting is "does this thing exist in the first place?" and that's where the can of worms reveals its bottomless hole.
In the broadest possible sense, randomess is inability to predict. In other words, there may well be patterns to the data, but you can't predict which one it is.
That is not randomness its just unexpected like 10101010101 is still random but expected unlike 11001011001 it is still random just unexpected, randomness is just a chance for something to happen without a reason other than it happening
I think it is a mistake to even attempt to 'test' a sequence for randomness. Randomness is the property of a process, not a result. It would be like looking at a furniture item you got from a store to try and determine if the factory workers were being treated properly. Sure, it could potentially contain some hints, but it doesn't necessarily reveal anything at all. As long as the result is a possible output, no one can determine whether it was come to randomly or not, regardless of any observance of patterns. Sure, the odds of flipping a coin ten times in a row and getting all heads is 50% chance that at least one of them will get a result of all heads. If we just imagine 23,567 people have done this 10x flipping (99.99999999%) that at least one of them did get a result of all heads. It isn't because the person that got all heads was using a coin that wasn't fair, but because randomness simply can't be determined based on that result.
I don't understand. Why would it need to detect patterns, that would completely fake that random then generated Also to find patterns you would just need to do it like this: watch for any repetition of single numbers, then of two numbers, three, etc...
True randomness does not exist in reality, because to be "truly" random, a system has to be unpredictable yet at the same time be uniformly distributed, something which has an element of predictability and contradicts the previous requirement. If you remove the requirement for uniformity, then the only things that are random are things that are poorly understood, so then it's subjective whether or not something is "random". For example, if you have a trick coin where both sides are heads, the outcome of any flip is totally random to someone who doesn't know it's a trick coin or has no short term memory. To someone who does not know how to calculate pi, the digits of pi are random. To someone who does, they're not very random because they can calculate the digits themselves and anticipate future outputs. To an average super mario 64 player, the RNG is very random, but to pannenkoek2012 it's not random at all. You can make the argument that quantum fluctuations and cosmic noise are random, but really, for how long?
@@lawrencedoliveiro9104 _your interpretation_ of quantum physics says that. Quantum physics does not literally say anything is actually random though. Hard to predict and poorly understood? Yes. Impossible to measure without physically affecting it? Yes. Random? No. If you read about Schrodinger's cat and took that as evidence for randomness, then you didn't understand the thought experiment. Never mind the fact that is is highly criticized within the field and isn't meant to be taken literally because it's an analogy. It's also worth noting that Heisenberg uncertainty is one of the most misunderstood parts of quantum physics. People act like the particles magically know you're trying to measure their speed and position but actually the reason you can't know both the speed and position is because in order to measure one, you have to shoot photons at it, which is like trying to gauge the positions of the balls on a pool table by measuring the sound of the cueball hitting other balls. You will know their position from before you heard the strike, but knowing that after is nontrivial. The same is true of measuring a particle. They are so small that the act of measuring in itself physically affects the particle. That's why you can't know. It isn't random. There's just too much entropy at that scale.
@@lawrencedoliveiro9104 I'm not convinced that you understand Bell's theorem if you think it's about randomness and not about unresolved questions regarding locality
Actually in the long run everything will fall back to its ground state according to laws of nature and only those either became totally death or totally alive like matter or spirit is what things are trying to separate right now like gold or diamond had no spiritual but only halo while spirit became totally dark space time slowest ect the singularity is that where mind , body , spirit totally separate but it maybe futtile or it could be possible because taking total infinite probability then everything is possible
I guess the concept of randomness is a human invention in the first place. Intuitively, if the means by which a result is reached is too complex to be determined by all parties, then it might as well be random. A human being is not capable of manipulating or 100% predicting the result of a pair of fair dice. Of course the result is the result of forces and vectors and all that, but we cannot perceive it.
I made a password generator app that generates a random password depending on the micro seconds right now. It works very well, but it still not random, i learned that only human beings have the ability to randomly pick a number.
wait, dont humans cant pick random numbers? this is used to fight tax evasion for example , in false bills/pay (there's some programm that detect if 0-9 repartition is correct)
Human beings are notorious for picking “random” numbers that have patterns in them. There is a Numberphile video where a mathematician makes a bet that the guy making the video cannot pick truly random numbers, and cleans him out.
Underrated channel
Kanokarten [GD] Saying facts be like:
For now 😉
Fr
Underrated icon
Kolmogorov Complexity
One thing I've heard is that "randomness" isn't something you can judge by the output of the sequence, but by the process of generating it. That is, knowing all previous outputs of the randomness generator, what is the probability that you can guess the next output? If it is impossible do better than 1/x (where x is the number of possible outputs), then the generator is random.
That is of course assuming you want uniform randomness. The sum of two dice rolls can still be considered random, but not uniformly so (for 2D6, there are 6 ways to roll 7 but only 1 way to roll 2 or 12). So the expected amount of correct guesses would be harder to compute.
not being able to predict is needed for cryptographic randomness
but for most applications only statistical randomness is required
That’s the basis of Kolmogorov complexity. But if you don’t know the process, how do you figure it out?
Consider that encrypted data, by design, looks indistinguishable from random noise. But if the plaintext data has low information content, then it would indeed be highly compressible, you just wouldn’t know it from the encrypted version.
what if a fair dice with faces showing "1,1,2,3,4,5", is the outcome still random?
There is a formalization of this called Kolomogorov-Loveland Stochastic. It turns out that there are non-random (in the sense of Kolmogorov complexity) sequences for which it is not possible to guess the next output by any fixed margin over guessing.
Jesus loves you all! Please I literally beg you to REPENT AND TURN AWAY FROM YOUR SINS to escape eternal damnation. Tomorrow might be too late😢
Subjective Bayesian statistician here. Bayes (& Price) (1973) asked how to predict the next 0/1 if the sequence was extended. That is, not how to encode n binary digits but the prediction of digit n+1 given digits 1 to n. Of course, the answer depends on your model for generating digits. Great videos. Keep up the good work.
i feel like another good way of describing this would be "psychological randomness", since it theoretically quantifies how random a sequence *looks*. statistically random sequences can appear less random, because statistical randomness kind of defies human intuition; it's nearly guaranteed you'll find some pattern, however convoluted or imperfect, in any given sequence, because finding patterns is the one thing human brains are really wired for.
Jesus loves you all! Please I literally beg you to REPENT AND TURN AWAY FROM YOUR SINS to escape eternal damnation. Tomorrow might be too late😢
That is a fascinating idea, and so succinctly and beautifully explained. Thank you so much!
One of your most interesting videos.
I lost the count of how many times I watched it until this day.
These are such quality and entertaining videos, I am truly impressed! Thank you for the content. Cannot find any plausible explanation why these get so undeservingly low views and subscriptions...
01:37 is that the fibonacci series ??
1 zero
1 one
2 zeroes
3 ones
5 zeroes
Yes and I'm looking for such a comment!
Randomness is such a fascinating topic.
Something that always boggles my mind is the relationship between randomness and information density. It seems intuitive that true randomness must hold no information. But at the same time something that holds maximum information will be maximally close to randomness. Consider a string of text. It will hold information, but because of the redundancy you can compress it. So long as it is not maximally complex you can continue to compress it. Once you no longer can, it will pass tests for randomness. But at the same time is maximally information dense. So seemingly minimal entropy (maximum information density) is indistinguishable from maximum entropy (pure randomness). Am i missing something?
I think that the problem is that we often confuse "patterns" with "information". We look for patterns to find meaning in things, but patterns are actually a way to _reduce_ information. There's just too much information in the world so we have to look for patterns to compress it into concepts that fit into our brain.
If something is truly random, and contains no patterns, then we have trouble getting it into our heads. The best we can do is memorize the digits of Pi.
It's sort of like somebody telling you that a lump of coal has more energy in it than a sandwich. Maybe, but I can actually EAT a sandwich! If there's too much information, it's overwhelming and chaotic and we can't use it, so we just dismiss it as "noise".
Awesome content! Can't wait to see the next video!
I was thinking the whole time about compressibility, I'm glad you touched on that
Hello Brian, I am huge fan of your work. I find all these videos quite interesting,, what do you use to create these sort of videos?? Please
Glad you've enjoyed the videos! I use Affinity Designer and Procreate for graphics design, I use Blender for modeling and animation, and there's a fair amount of procedural generation for these animations that's done using Python scripts I've written myself.
My definition of randomness is the first one you gave. Wherein each one is equally random.
Underrated work. Thank you for your work, with love from Russia❤️
Such a great content, really impressed. Please continue.
It's quite interesting too, that if we asked humans to generate a "random" sequence of numbers, The answer with all ones wouldn't come up in their mind easily. It's not "random" enough for a human mind and that's really make it even more random in my opinion.
I am satisfied with randomness as "none of the possible outputs being more likely than any other".
Dude I feel so much smarter after watching any of your videos. These are the questions I never ask myself, but when you give me the answer I'm like "Woah"
Hey that was some very amazing content, thank you so much for the brilliant explanation
thanks for the information and guidance. She was very clear and all the information she share
you could understand them as She explained the in a simple language.
Thanks. Great explanation !
Great explaining
You could associate randomness with entropy. A sequence is most random if it has maximum entropy. You can define, for a specific problem, the maximum available entropy and thus you could determine, relative to the available entropy, the level of randomness or complexity. In your example, lets say, the maximum entropy could be if the sequence has N/2 zeros and N/2 of ones and the maximum number of consecutive symbols should be less than 4.
Fantastic video for a non-math wiz like me, thank you
2:56 *cracks fingers* css here we go
My definition of randomness would be that given a "random" sequence of length n characters and an alphabet of size p, there is no way to predict the presence of a specific character at a specific location with a greater precision than 1 over p
So for example, if the probability distribution of these characters wasnt uniform, you would stop considering this randomness?
Thank you for the video. It's truly very high quality. I hope to see more!!
An interesting alternate intuition on randomness might be 'predictability'.
It doesn't really mean anything to say that a given piece of information is 'random'. The number "41" is no more or less inherently random than any other number would be, and its binary string "101001" may or may not be random. In the Kolmogorov interpretation above, it seems like it does indeed satisfy the condition for randomness. Does that make 41 a more 'random' number than 1023 ("1111111111")? The question itself seems like it is not the right one to be asking.
On the other hand, we might more usefully talk about the *process* by which data is generated, with the understanding that it will continue to generate data past what we are able to see. A measure of the randomness of that *process* then, could perhaps be related to how many bits of data we need to be able to see to predict the next bit successfully. A sort of 'name that tune' for binary strings. We might call that measure the 'Bound of Predictability' of a process. A 'truly random' process, therefore, being defined as one which is never predictable, would have an infinite Bound of Predictability. Since computers are unable to access true randomness, but can only simulate it with sufficiently complex processes, any process a computer can implement would need to have some finite BoP - I would not be surprised if the BoP function (over the domain of sets of sequence-generating rules) is also incomputable, but that is ultimately conjecture.
The question then of whether a given string of data is 'random' could be restated as "How much of this string of data do we need to know in order to predict the rest?" This does give us the intuitive result that a string like "1111111111111111111111111" is extremely predictable, so you would need very few bits in order to come up with the rule 'the next bit is always 1'
To make the process more rigorous, we would have to define some way by which the process of predicting is 'updated' with each added bit, and there is the matter of false positives, where the 'wrong' rule 'successfully' predicts the next bit (but not the bit after that; or even the next several bits, before it becomes wrong). We would have to determine whether we are concerned with long-term/wholesale predictability, or partial predictability. For a sequence like "11110111011110111110", the "The next bit is 1" prediction is *usually* correct, but must be discarded after the fifth bit; what prediction might we expect to be made after only 5 bits? How does the predictability of a sequence relate to the predictability of subsequences of that sequence?
This does also look to converge with Kolmogorov Complexity in the sense that, for a finite sequence that would have C(x) >= len(x), we also end up with a BoP such that you reach the end of the series without ever knowing what was going to come next, that BoP(the process that producing string X) >= len(X)
There is also a paradox related to this, I don't remember the details but it goes something like "the first number that can not be described by eleven words", which is by this sentence described by 11 words. Or something like this.
yes it is called "Berry's paradox" for anyone interested
Heard the voice and instantly recognised you from CS50. Best of luck to you in life.
Great explanation. Thank You!
The shape of the output you describe is more an unorganized set than a random output, since any random generator is capable of deliver patterns as well as unorganized data sets (take dice for instance, if you throw 12 d6 there are chances for you to end up with a pattern sequence).
Fibbonacci making his way into science videos again ❤️
A comment to support the channel
I like, "sufficiently difficult to predict". So if you don't see the pattern, it's random; but a property of patterns is that you can predict what comes next, so once you see it, it ceases to be random.
Basically I think we should just accept that randomness is subjective.
this is a neat concept! off the top of my head, the downside is that this definition of randomness isn't very practical for evaluating the effectiveness of pseudo-RNG. by definition, pseudo-RNG can be described without listing the complete sequence, but there's diminishing returns as you walk along the axis from "hard to predict" to "hard to compute". I'd love to see a measure of randomness that accounts for this "bang for your buck" intuition, something like "how much output can you produce before an attacker can predict the next bit with 51% certainty? 90%? 99%?"
Typically, we say a good crypto-RNG is such that, given arbitrary amounts of output, producing the next bit with more than 50% certainty should be just as difficult as brute forcing the key/seed. So, bang for your buck is usually more a question of how difficult it is to beat 50% (by ANY amount), not how much you can exceed 50%. Ideally this is a binary question: It either requires brute force or it doesn't. In practice, algorithms often have flaws which reduce their effective key length, so one might say an algorithm's effective key length is reduced by N if one can break it 2^N times faster than brute force. Such a hole is normally considered a vulnerability; we don't want those in our algorithms at all!
Even a tiny deviance from 50% is often enough for an oracle attack.
Proving randomness means proving the absence of information about what comes next. Which seems in general impossible to do.
(Not the same thing as “you can’t prove a negative”, which is a nonsensical statement, by the way.)
Aren't you the guy from CS50? I am also a huge fan of your work.
Does this [address] Kolmogorov Complexity?
The smallest description of a sequence of bits would be the location of the sequence in a preshared table of sequences. That raises the question, what is the optimal table to preshare?
NIST publications on randomness are quite good aswell for further reading!
(edit: typo)
Great videos
Fun topic, thanks for bringing this up.
I wonder how different would it be if we are looking for a random decimal number. 10101010 may not look random in binary but 170 could look pretty random.
Those are the details mentioned about Turing machines and the choice of language. In practice, it's an additive constant that dwarfs the use we could have for Kolmogorov complexity in our everyday lives.
For example, AIXI is the theoretically supreme AI that learns everything that can be learned, as fast as possible (thanks to Solomonoff induction, which hinges on Kolmogorov complexity). But in practice, it is hard to make it yield results in our bounded world because of that pesky constant.
The languages we use are typically optimized for the world that actually surrounds us (including programming languages, for the way they are designed to be used in). Simple Turing machines are not.
This video is Awesome and edx python javascript course is ultimate 👌
An interesting distinction is between a random *process* and a random *thing*. With equal probability of "0" and "1", a random process is equally likely to generate strings "011001100001" and "111111111111", even though *as a thing*, "011001100001" seems more random
I feel like now with the breakthroughs in AI technology, a GPT AI could be used to come up with the shortest representation of data to determine how random it is. That could be fit into a function that determines the Kolmogorov complexity of data.
I got chatgpt to find a pattern in a binary string and write the python code for it. This only on 2nd attempt when I asked it to assess the pattern and produce code for it.
You are awesome!!
Very nice thanks
Why you stopped making videos?
Is it uncomputable or incomputable?
Also, why is uncomputable? Is it uncomputable like the halting problem, or more like Cantors diagonlization argument ?
What about "The digits of pi"?
Can C(x) ever be greater than x? Context: 4:24
that's a good point, maybe there are other nuances that Spanning Tree hadn't talked about
Yes if the representation language is different from the input language (for example: x = 101 represented in english C(x) = "one zero one")
Yes, because of the quote marks, or something like that in whatever your description language is -- the mark that distinguishes "run this program" from "just print these digits".
There are actually rules and tests for the evaluation of random number generation algorithms. They are applied to pseudo-random number algorithms (which all "random" number algorithms in computers are), and only those that succeed can be used in critical systems, because otherwise they are a security vulnerability for important algorithms which rely on them, such as encryption key generators. There are several, but all of them describe aspects of one central requirement. Given any previously generated random result or sequence of random results, it is impossible to guess the next random result or sequence of random results with a greater probability then that sequence's chance to appear randomly. Basically, if you have 000 and the possible outcomes are 0 and 1, there should be a 50% chance the next is 0 and the next is 1. A flawed pseudorandom number generator, such as one which only produces infinite 0s, is flawed because you can predict with greater than 50% accuracy the next is 0.
So the Kolmogorov Randomness concept itself is random? Because you can’t compute it’s complexity anyhow, leaving the true complexity to be represented by the item itself (simply because of the fact a f(x) cannot be created), unless there’s approximation functions which then makes this concept more useful.
I define randomness as differing results coming from the same action assuming both happened at the same time. If I dropped a ball, and it bounced forward, and if I were to replay that same moment in time and it were to happen again, that wouldn’t be random. But, if I replayed the same moment in time with the exact same setup as before and got a different result, that would be random.
Are the digits of pi Kolmogorov random? Proving a sequence is Kolmogorov random means that there is no way to predict the next term of the sequence. The digits of pi never repeat, and so would "appear" to be random. But we have computer programs of finite size that can theoretically calculate the nth digit of pi for any n, given sufficient processing time.
So no, the digits of pi are *not* random. Neither is e, or the golden ratio, or any other computable irrational number. Don't use any widely-known irrational number as keys for cryptography, because then the key isn't the number, but the program to generate it.
What pi, or e, or any other irrational number *might* be is "normal". The intuitive definition of "normal" is that every sequence of digits is equally likely to be in the number someplace. A little bit more rigor -- For any finite substring of digits, you can count and see that 0 is there 10% of the time, as are 1, 2, etc. 00 is there 1% of the time, as is 01, 02, 97, etc. If every possible substring occurs equally often, then the string of digits is normal. Obviously for a finite string of digits, say 10 digits 4731890562, you run into trouble when you try to find every 10 digit substring, because there are 10 billion of those and only one string. So, no finite string of digits can be normal.
However, just because a number is normal, doesn't mean it's random. For instance, the first number ever proven to be normal is just the concatenation of each subsequence in order. It starts 0.123456789000102030405... first the one-digit substrings, then the two digit substrings 00,01,02, etc. Once you do this to infinity, every possible sequence will appear exactly as often as we expect. But, the program to generate this number is a Python one-liner.
very nice video, I hope you'll make more :) I'm not a fan of the background music though
I'm not a mathematician but instead of an arbitrary language, be it programming or human-words, why not use the most concise language we could use; math?
Say I describe prime numbers, I'd say:
For a whole number n, n should not have a smaller whole number d that is divisible without a remainder, except for 1.
This expression would feel very Pythonic,, but can't we estimate some weights to operators (for, if X is ..., but/except for...)? For a somewhat complex notion like sum of values, or derivative of a function at different values, it's way less random, and succinct, than describing mod(X, Y+n) for n
What is the less obvious pattern? Fibonacci?
I believe so. 1 1 2 3 5
how about i want a random number between 0 and 8192.. am i supose to refuse 256 or 1024 or 4096 (as binary ofcourse, as decimal i can say numbers like 5000 or 7000)
because there is a pattern there too "first number is 7 and the rest is 0" or for binary 4096 is 1000000000000 and why would i refuse that number... i think its more related to repetition of the return value
i love ur accent 🤩
But how is a pattern found in the sequence? The examples you gave rely on the brain's pattern recognition; is there no algorithmic way that always finds the pattern in a sequence if the pattern exists?
if I can't see any pattern in a sequence of things, I define it as a random sequence
If we consider a bit value generator(1001110...) whose length is 8 bits, then isn't getting 11111111 equally random as getting 10010110? Let's say, today is my birthday and "coincidentally", today I also got a holiday from my school, so it is coincidental but also random...
Randomness means a situation or a system which is unbiased and whatever will be the event, it will be still random, be it 11111111 or 10010101....
Exactly, if anyone looks at one number from generator, whatever it is it's always legit random number. He mentioned sequences but it wasn't clearning stated if it was sequence of bits, bytes or if this was whole 32bit number. If this was the case of 32bit number then if you look at it at as a decimal number then it would look like a legit random number from the range of 0 to 4294967296.
So true randomness can be gained using quantum mechanics. This stuff can used for non security applications like games. Now for human randomness or whatever this was called lmao, that seems random should used for security applications
Here there and everywhere
I believe things can be random if you add a concept of mistake and uncertain probability. Taking a series of pie and choosing numbers based on time of day x weather x number of news link x... can create the perfect random function.
That’s how most video games do random number generation, and one look at a speed run of one of those games will tel you the system is not perfect at all.
If you know the variables that determine something, affecting the outcome is as straightforward as altering those variables.
@@pretzelbomb6105 to be fair, speedruns that depend on RNG manipulation are usually tool-assisted - meaning the runner can see the current status of the RNG, and via usage of save states and slowing down the game, perform exactly the correct actions at exactly the correct time to get the state they need when they need it.
true, the system still isn't perfect because it _can_ be manipulated, but it's very hard to do so without breaking the game open like that.
It took me like 5 minutes to come up with a "function" to compute Kolmogrov complexity... only works for binary numbers though. Thinking "length" is a misnomer here.
This is one of those things that tends to open up a can of worms very quickly, like using ZFC as your set theory and then using the Continuum _Theorem_ in proofs.
There's not really a useful definition of randomness because when you finally get to the intuitive grain people consider as "random", they start describing things that start resembling independence and correlation. All you're left with is "random" is just anything that isn't deterministic, which itself does not have the most interesting definition either.
What's infinitely more interesting is "does this thing exist in the first place?" and that's where the can of worms reveals its bottomless hole.
i think we just consider things to be random when the pattern that they hold is just above human computing capacity to decypher
fibonacci
Me: sin(timestamp) 😅
Wouldn't "1" be random because it is so short?
Computer generated random numbers (1,2,...,100):50, 50, 50, 50, 50
The shortest description is converting the binary into a higher base like decimal or hexadecimal and just describing it as the number it is lol
Why not compile a library of all available model families and try to fit it to the data? If none are applicable, then the dataset is random
In the broadest possible sense, randomess is inability to predict. In other words, there may well be patterns to the data, but you can't predict which one it is.
the amount of info required is the number of bits
i think another way to show how random something is is how long untill it repeats
That is not randomness its just unexpected like 10101010101 is still random but expected unlike 11001011001 it is still random just unexpected, randomness is just a chance for something to happen without a reason other than it happening
exactly! as long as something was randomly generated it is random. Even if it has patterns in it
@@ΓεώργιοςΠαπαδόπουλος-μ9μ ty! that was the word i was thinking of, its patterned.
I think it is a mistake to even attempt to 'test' a sequence for randomness. Randomness is the property of a process, not a result. It would be like looking at a furniture item you got from a store to try and determine if the factory workers were being treated properly. Sure, it could potentially contain some hints, but it doesn't necessarily reveal anything at all. As long as the result is a possible output, no one can determine whether it was come to randomly or not, regardless of any observance of patterns.
Sure, the odds of flipping a coin ten times in a row and getting all heads is 50% chance that at least one of them will get a result of all heads. If we just imagine 23,567 people have done this 10x flipping (99.99999999%) that at least one of them did get a result of all heads. It isn't because the person that got all heads was using a coin that wasn't fair, but because randomness simply can't be determined based on that result.
I don't understand. Why would it need to detect patterns, that would completely fake that random then generated
Also to find patterns you would just need to do it like this: watch for any repetition of single numbers, then of two numbers, three, etc...
Shortest expression of this in programming #ff
A random sequence is a random sequence, you can't just say it's only a half
"Inability to predict the rest of the sequence"
True randomness does not exist in reality, because to be "truly" random, a system has to be unpredictable yet at the same time be uniformly distributed, something which has an element of predictability and contradicts the previous requirement. If you remove the requirement for uniformity, then the only things that are random are things that are poorly understood, so then it's subjective whether or not something is "random". For example, if you have a trick coin where both sides are heads, the outcome of any flip is totally random to someone who doesn't know it's a trick coin or has no short term memory. To someone who does not know how to calculate pi, the digits of pi are random. To someone who does, they're not very random because they can calculate the digits themselves and anticipate future outputs. To an average super mario 64 player, the RNG is very random, but to pannenkoek2012 it's not random at all. You can make the argument that quantum fluctuations and cosmic noise are random, but really, for how long?
Quantum theory says that reality is indeed founded on true randomness.
@@lawrencedoliveiro9104 _your interpretation_ of quantum physics says that. Quantum physics does not literally say anything is actually random though. Hard to predict and poorly understood? Yes. Impossible to measure without physically affecting it? Yes. Random? No. If you read about Schrodinger's cat and took that as evidence for randomness, then you didn't understand the thought experiment. Never mind the fact that is is highly criticized within the field and isn't meant to be taken literally because it's an analogy.
It's also worth noting that Heisenberg uncertainty is one of the most misunderstood parts of quantum physics. People act like the particles magically know you're trying to measure their speed and position but actually the reason you can't know both the speed and position is because in order to measure one, you have to shoot photons at it, which is like trying to gauge the positions of the balls on a pool table by measuring the sound of the cueball hitting other balls. You will know their position from before you heard the strike, but knowing that after is nontrivial. The same is true of measuring a particle. They are so small that the act of measuring in itself physically affects the particle. That's why you can't know. It isn't random. There's just too much entropy at that scale.
@@BradenBest Bell’s inequality quantifies the random probabilities involved.
@@lawrencedoliveiro9104 I'm not convinced that you understand Bell's theorem if you think it's about randomness and not about unresolved questions regarding locality
@@BradenBest I’ll just let that speak for itself.
Actually in the long run everything will fall back to its ground state according to laws of nature and only those either became totally death or totally alive like matter or spirit is what things are trying to separate right now like gold or diamond had no spiritual but only halo while spirit became totally dark space time slowest ect the singularity is that where mind , body , spirit totally separate but it maybe futtile or it could be possible because taking total infinite probability then everything is possible
i know cryptographic key generation software that asks the user to move the mouse around in a zone for generating randomness
I guess the concept of randomness is a human invention in the first place.
Intuitively, if the means by which a result is reached is too complex to be determined by all parties, then it might as well be random.
A human being is not capable of manipulating or 100% predicting the result of a pair of fair dice.
Of course the result is the result of forces and vectors and all that, but we cannot perceive it.
Free-will believers don't believe this. They want their illusion to be true
practical definition. a humanly random sequence cannot. be predicted by humans . rand9m depends on the observer.
So randomness is something that isn't yet made. If made then it's not random.
These comments are pretty random
background music isn't loud and annoying enough
cancel ruzzia fk em LOOOOOOOOOOOOO
:/
I made a password generator app that generates a random password depending on the micro seconds right now. It works very well, but it still not random, i learned that only human beings have the ability to randomly pick a number.
wait, dont humans cant pick random numbers? this is used to fight tax evasion for example , in false bills/pay (there's some programm that detect if 0-9 repartition is correct)
Humans can't, but Uranium can.
Human beings are notorious for picking “random” numbers that have patterns in them.
There is a Numberphile video where a mathematician makes a bet that the guy making the video cannot pick truly random numbers, and cleans him out.
There is no such thing as 'random', only sequences that we can't predict.
Why would you use the word randomness, and then redefine it to be "we cannot easily describe a pattern". That is not related to randomness at all
Girls are random 😉