Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Absolute compression = true randomness?

  1. Nov 29, 2015 #1
    So i've read from various places that maximal compression produces a truly random output. But suppose you were going to apply compression to a truly random series of numbers with something like LZW. Well wouldn't it be the case that since randomness often produces sequences which do not appear to be random, that therefore compression would work at some point in a random sequence of numbers? In the case of finite sequences it means that the efficiency of LZW here would be random since a true random number generator could produce a compressible sequence of numbers.

    Thus true randomness does not mean absolute compression. In an infinite sequence of random numbers you would expect it to contain many sequences which don't actually seem random like how randomness could produce the sequence 111111111111 purely by chance. Its similar to how in PI you can find sequences of numbers which don't appear to be random, but in the context of a larger set of numbers the distribution between all different numbers is the same.

    So clearly this is compressible. This implies that an infinite sequence of numbers is infinitely compressible in theory right? So really absolute compression != true randomness because it only works in some cases where a finite sequence of numbers was random and has no sequence or pattern of numbers. From my understanding of randomness, it would be impossible, in an infinite sequence of numbers, to find no compressible patterns at any point. I don't have a proof for this but if anyone knows of one or can show me how i'm wrong i'd love to hear it. Thanks.
  2. jcsd
  3. Nov 29, 2015 #2
    Infinitely compressible would mean that every set of data could be reduced to single number.
    So every number should uncompress to give a unique set of data.
    That doesn't makes sense (to me),.
    What unique set of data is represented by for example the number 3?
  4. Nov 29, 2015 #3
    An infinite number is one that goes on forever and so there are an infinite number of compressible sequences inside a completely random number. 3 obviously doesn't represent infinity so that point is moot. So compression could run an infinite number of times especially considering compression produces a new number each time it runs so it spawns off an infinite number of new numbers.

    Infinity simply doesn't work that way. Consider the infinite hotel with infinite buses bringing people. Just because the hotel is infinite and takes on an infinite number of people doesn't mean that there are no buses left--there are still an infinite number of buses and an infinite number of rooms.
  5. Nov 30, 2015 #4


    Staff: Mentor

    No. An infinite number is one that is larger than any finite number. By your definition, 1/3 = 0.3333... would be an infinite number -- it is not. The decimal representation of 1/3 takes an infinite number of digits, that's true, but it is not an infinite number.
    This makes no sense to me.
    Last edited: Nov 30, 2015
  6. Nov 30, 2015 #5
    You won't get 111111111111 very often. So how are you going to compress it? What you gain for an occasional 111111111111, you will loose elsewhere.
    When it comes to computer generated random codes, you need to be pragmatic. For example, if the purpose is cryptography, you are looking for something with even distribution (all codes equally possible) that cannot be reproduced. You might do some sanity checks on it - just to make sure your random bit generator hasn't broken but that's it. For a Monte Carlo analysis, you may want a reproducible series that doesn't have patterns that match with your problem set. For a white noise generator, you would be looking for good frequency distribution and no repetition.
  7. Nov 30, 2015 #6
    Its infinite because it has an infinite number of decimal places. I didn't say infinite in magnitude i just said infinite.That second part refers to an infinite number like pi for instance which has random decimal numbers. The idea is that contained in something like pi is all possible patterns and sequences and so there are an infinite number of compressions that could take place.
  8. Nov 30, 2015 #7


    Staff: Mentor

    Your use of "infinite number" is nonstandard, and one that most mathematicians would disagree with you on.
    I don't see this going anywhere, and it seems more like philosophy than mathematics, so I am closing this thread.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Absolute compression = true randomness?
  1. An absolute beginner (Replies: 13)

  2. Random Matrix (Replies: 7)

  3. Compression conundrum (Replies: 7)

  4. Randomization Question (Replies: 4)

  5. Random # Generator (Replies: 2)