Monday, August 30, 2010

2 Apples, a Peach and a Pear. Measuring the disorder of a sequence.

(p197 of the text.)

M, possibilities within the pool that you are drawing from = 3 (there are three different things I can draw: apple, peach or pear)
N, length of the sequence = 4
Ω, total possible sequences = N! / (N1!N2!N3!)
Where N1, number of apples in pool = 2
N2, number of peaches in pool = 1
N3, number of pears in pool = 1

Therefore Ω = 4! / 2!1!1! = 12
List of possibilities (AABC , AACB, ABAC, ACAB, ABCA, ACBA, CABA, BACA, BCAA, CBAA,CAAB, BAAC) = 12
I, number of bits = K[lnN! - ∑lnNj!] = K[lnΩ] = ln(12)/ln(2) = 3.59 bits

It can be seen that a sequence of 2 apples, a peach and a pear is not perfectly disordered as 3.59 < 4.

5 comments:

  1. This example brings up a good point. If we can only communicate with apples, oragnes and peaches, but we must use twice as many apples as either other fruit, we can consider an alphabet that consists of the 12 'letters' Heather named above (AABC , AACB, ABAC, ACAB, ABCA, ACBA, CABA, BACA, BCAA, CBAA, CAAB, BAAC). If each of these letters are equally likely, then we can create a language with maximal disorder, given the restriction that we use twice as many apples as each other fruit.

    ReplyDelete
  2. Just as an interesting point, a sequence of any 4 things is unable to achieve perfect disorder. If we reverse the perfect disorder equation, we have 4 * ln (2) approximately equals 2.773, which if we then do e^2.773, we get 16
    now, if we look at the omega term, it will always be equal to 24 divided by a multiplication of factorials, and since factorials take whole numbers, a denominator of 2/3 can not be achieved, thereby making a sequence of length 4 impossible to achieve

    ReplyDelete
  3. I don't think it is possible to have fractions of bits. In binary the value can either be 1 or 0, there are no intermediate states, the same would apply here, you are either in a state or not - information is discrete. In this case wouldn't you have to round down to 3 bits?

    ReplyDelete
  4. It is possible for an overall distribution to have fractions of bits. Entropy does not have to be discrete. I'll try think of an example for the meeting tomorrow.

    Matt, if we have a sequence of 4 object that allows repetition, then we can have maximum disorder. By imposing the restriction on that we are only allowed one of each item then we cannot reach perfect disorder. Every restriction we impose we increase the order, and thus reduce the entropy.

    If we are allowed repeats: \Omega = 4^4=256
    Information = ln(256)/ln(2)=8.

    So the maximum entropy of a message of lenght 4 with an alphabet of 4 is 8.

    ReplyDelete
  5. Sorry, I made an error in the post above, I assumed the alphabet had 4 letters rather than 3. So the maximum entropy is 4.

    ReplyDelete