 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Truly random?
  Page 2 of 3   |
|||||
| Author | Message | ||||
twofingers Guru  Joined: 02/06/2014 Location: GermanyPosts: 1576 |
always? There are truly random bit streams which can be compressed and others which can not. For example: My random bit stream is 2 bit long and contains 2 zeros. ... Regards Michael causality ≠ correlation ≠ coincidence |
||||
| robert.rozee Guru Joined: 31/12/2012 Location: New ZealandPosts: 2437 |
it is probably not worth arguing about. but my initial comment still stands, that: if you are wanting to test the output from an RNG that outputs a bit stream, one rough-and-ready method is to capture a (very) long data stream into a file and then feed it through a good file compressor. if it compresses, your RNG is not performing so well. if it does not compress, then it is worthy of doing further testing. while a 'true' random sequence may contain regularities, these will not be predictable and no compression will be possible over an extended sequence. if you select a segment from such a sequence, then your mileage may vary, but on average no compression will be possible without arriving at an embarrassing paradox. cheers, rob :-) |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
That's wrong. Over a long enough sequence it will always be possible to get some compression - see my simple example. Indeed, if no compression at all were possible then I'm fairly sure it could not be a truly random sequence since such a sequence must eventually match my example. I love mathematical paradoxes and the like :) John |
||||
| robert.rozee Guru Joined: 31/12/2012 Location: New ZealandPosts: 2437 |
lets assume you are right, that "over a long enough sequence it will always be possible to get some compression". 1. start with a random number generator, we shall call it RNG0. and we shall call your compression algorithm CAL0. your assertion is that RNG0 -> CAL0 will produce an output stream that is shorter than that produced by RNG0 - that is if n bits are fed into CAL0, then m bits will come out, where m<n. is this (1.) correct? 2. let us now define RNG1 as being RNG0 -> CAL0. RNG1 is in itself a random number generator in the same way that RNG0 was. are you ok with this (2.) step? 3. we can then apply to RNG1 the same process as we did to RNG0. that is, your assertion would seem to be that there should exist some compression algorithm, CAL1, such that RNG1 -> CAL1 will produce an even shorter output stream. would you disagree with step 3.? there is no reason to not carry on indefinitely, until such time as we have an output stream of trivial length, without loss on informational content - our paradox. the only way to 'break' out of the paradox is to accept that there will be some output stream from an RNGn that can not be further compressed. by any means. rob :-) |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
#2 is false John |
||||
| robert.rozee Guru Joined: 31/12/2012 Location: New ZealandPosts: 2437 |
you believe that defining RNG1 as being RNG0 -> CAL0 is in some way wrong? in what way is this wrong? is RNG1 not also a random number generator? we are just taking an output stream from one process (RNG0) and feeding it through a reversible algorithm. will this result in something non-random? rob :-) |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
@rob If a random generator can not generate - randomly! - a compressible bit stream then the RNG is not a true RNG. A RNG can (and may!) not know if his product is compressible! Regards Michael causality ≠ correlation ≠ coincidence |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
#2 is false - because RNG1 is not a random number generator. It's going to be close but it's not one. The act of compressing has imposed some order. John |
||||
| Dylan Regular Member  Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem It isn't a mathematical Paradox. Rob is explaining some basic computer science, perhaps not perfectly, but not badly either. A truly random bit stream has maximum entropy, BY DEFINITION. Arguing that a million zeros could show up and then be compressed is all very well and good. A little knowledge is a dangerous thing. Because there isn't anything special about zeros. You might as well say that if the random number generator gives Hamlet in ASCII, that sequence is equally easily compressed. Compression does not "impose order", it "increases entropy" which is almost the exact opposite. A random bit stream has an entropy of 1 bit per bit. Compression algorithms do not exist which can increase information density to more than 1 bit per bit - for the simple reason that a bit can't HOLD more than a bit. Any encoding which says "we will use fewer bits for certain inputs" MUST also use more bits than the original input for other inputs. In a ZIP/RAR etc, it is not uncommon for jpg/mp3 etc already-compressed files to simply be stored. |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
Shannon's not disagreeing with me. His theorem is about what happens in the limit and as it is approached. Before that, what I posted must be true. Let us say that in 10^x (where x is 20 or 1000 or whatever) random bytes there are 10^6 zeros in a row. Then the stream can be stored in fewer than 10^x bytes. Let's try this another way. What was stated was that a random bit stream cannot be compressed. That statement is false. Now, some will grow when put into particular compression algorithms, but some will shrink. See - the statement was false. John |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
Nobody disputes that a non-random bit stream can be compressed. A random bit stream has the property of NOT being non-random. There is no value in compressing a specific series of bits when those bits are random, because that will come at the COST of making the (infinite) stream (infinitely) longer. What you posted is in part what mathematicians call "trivially true". The other part is extrapolating something which is sometimes called "bullsh*t" (pardon my French). The sequence of 10^6 zeros can be compressed by sending a single 0. This leaves 999999 other sequences to be transmitted as 1 followed by the sequence. If the source is truly random, then the output will be longer, and hence not compressed at all. Let's try this another way. Bit streams are INFINITELY long. PNRGs are effectively encoded by perhaps three (32 bit) integers, on of which is likely the word size on a machine (a*seed+b mod 2^w). These are good enough for random, often. But they are deterministic. |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
You're not reading the statement that was made. You're acting as if it was not made or was a different statement. Have another go at it please. To prove it untrue I only need ONE example of a random stream that does compress. There exist many that do, never mind one. I did not refer to an infinite stream in that context, just as the statement did not and indeed one cannot have such a stream in practice thus cannot apply any compression either. You will notice the context was in terms of testing an actual RNG by trying to compress some output from it. You appear to have forgotten the context. I continue to argue in that context that testing whether a stream of bytes compresses or not is not an adequate test since it could be a truly RNG and yet its output can compress. John |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
@Dylan Question (to make things more clear): What is the maximum number of identical bits (or bit pattern) in a sequence of a truly bit stream? Is there a limit (below of the length of the stream)? Michael ps: PNRG = PRNG? causality ≠ correlation ≠ coincidence |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
Typo on Pseudo-RNG indeed, twofingers. John, I am not disputing your "reasons", because you are correct to a degree. What I am telling you - trying to at least - is that although a random sequence might be compressed by some compression algorithm, it is impossible to design such an algorithm which will "always work". Infinity is a funny thing. We would agree that it is not unlikely that there would be a run of two zeros in a stream of 10 random bits. We could work out the odds. The odds of four, five, even six zeros in a stream of 100 bits are not negligible. As you go to an infinite number of random bits, so does the length of the number of identical bits go to infinity. Fun! |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
It is good enough if there is any algorithm that works. I think, we have almost consensus. Sleep well! Michael causality ≠ correlation ≠ coincidence |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
My point is that I disagreed with the blanket statement that a test for randomness is to (try to) compress a chunk and it won't. Well, it may. As I expect you know, in maths a single counter example is enough (to disprove the claim). I don't need any algorithm that will always work. The person making the statement would need to prove that every random stream of any length cannot be compressed - quite tough when clearly there exist ones that can be (and I've given examples). To me it was and is blindingly obvious that a test for true randomness that is simply to try compression and if it compresses then it wasn't random - is garbage. It might be an OK way to get a feel for whether a (P)RNG works but pretty hopeless if you really want to know. I wouldn't want to try compression on an infinite stream. If Shannon says that in the limit it wouldn't be compressible so be it but it's irrelevant to the statement under discussion. John |
||||
G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Daniel enters the Lion's den ! There is no such thing as randomness. To be able to prove that there is randomness, is also to prove that randomness does not exist. Over the long run, ie infinity, every combination/sequence of digits/events must by definition occur, thereby proving that nothing is actually random - everything that can occur will occur. For practical purposes, humans are interested in local randomness, randomness in our time-scale - 100-1000 years at most, ie what we humans think of as unconnected/unrelated events, that's what we think of as being "random". If a Random Number Generator produces a sequence of numbers which we (as humans) are unable to predict/discern any pattern to their generation, then we (humans) will think that the sequence is random. A sentient being who is immortal and observes every digit sequence being produced by this RNG might observe repeatable patterns/sequences which we (humans) because of our short life-time span would not have observed/noticed, so we would have no doubt that we saw randomness, but the immortal might think otherwise, and in the process discover some law of physics regarding the noise generation by diodes is entirely predictable !!!! I'm no mathematician, computer scientist, physicist or other kind of expert, but I try to look at things logically and dispassionately, so please take it easy when you prove me wrong ! Peter The only Konstant is Change |
||||
Grogster Admin Group  Joined: 31/12/2012 Location: New ZealandPosts: 9593 |
 Smoke makes things work. When the smoke gets out, it stops! |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
@G Brilliant ! LOL, LOL, LOL I can't stop laughing. The Radio version with Peter Jones was the best IMHO Peter The only Konstant is Change |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Look here https://www.youtube.com/watch?v=tTNuldPhP20 Episode one when Arthur finds out they're going to build a bypas through Earth ! Peter Jones voice-over is brilliant Peter The only Konstant is Change |
||||
| Page 2 of 3 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
