Results 1 to 2 of 2
Like Tree2Thanks
  • 2 Post By Maxim

Math Help - Is random data, mixed (xorred) with non-random data, still random?

  1. #1
    Newbie Maxim's Avatar
    Joined
    Sep 2007
    Posts
    18
    Thanks
    2

    Is random data, mixed (xorred) with non-random data, still random?

    For sake of argument, I want to propose this definition of good randomness:

    A piece of data can be considered "random" if it impossible to write a computer program* that is considerably smaller (let's say at least 1% less bits) which generates the same data.

    (* to be executed on any generic computer that is constructed or defined independently of the given data - to avoid nonsense workarounds like a theoretical computer that just so happens to generate the required data with a single instruction)

    Even though it may be hard to measure the randomness in this fashion (it can be quite difficult to prove no such program exists), at least it's easy to determine a piece of data to be non-random if you know how to reproduce it (for example with a pseudo random generator given specific parameters). Also structured or compressable data is typically non random.

    Now here's my question: suppose that considering the above criterium, I have a piece of random data A. I also have a piece of non-random data B of the same size. If I mix the two by XOR'ing both chunks of data bit by bit, this will produce another piece of data of again the same size. So C = A xor B. Is this new data C likely to be random as well?
    Thanks from topsquark and emakarov
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,612
    Thanks
    591

    Re: Is random data, mixed (xorred) with non-random data, still random?

    Hey maxim.

    As a formal measure, you should look at the entropy and distributions of the final set of data.

    Specifically you should look at theorems regarding mutual information and joint entropy for a specific way to prove (or dis-prove) your result.

    Intuitively, I think you are correct but proving it will require information theory.

    Note that the definition of random is that of maximum entropy given some alphabet and corresponding distribution under that specific probability distribution in relation to the alphabet being used to express the information.

    There is a good book on Information Theory by Cover if you need a good extensive resource.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: March 23rd 2012, 01:03 PM
  2. Probability and random random varible question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 15th 2010, 08:53 PM
  3. Proc mixed random: standard deviation equals 0
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 12th 2010, 01:45 PM
  4. Replies: 3
    Last Post: January 13th 2010, 10:44 AM
  5. Interpretting random data...
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 28th 2007, 01:10 AM

Search Tags


/mathhelpforum @mathhelpforum