disorderliness

Dear intelligent LG players,

  Question: how do we define "disorderliness (or disorder)"? or in other words, what is a good definition of disorder?

  If we put 100 black stones and 100 white stones into a bag, the more we shake the bag, the better mixed these stones will become (i. e. the entropy of the bag will increase as time elapses). Is there a well-defined way (either qualitative or quantitative) to describe the state of "better-mixedness"?

  Thank you all in advance. Have a wonderful summer.

Tim Shih

Winter for some of us

I would say "size of the smallest computer program" who can describe the state of your bag.

If by chance after shaking, you get 50 white stones underneath and 50 black stones above, then a really small computer program can output this, so not much information...

Well for a bag of 100, not much difference for disorderliness, as for a bag a say a billion stones, you can start to see differences, but you must be *very lucky* to be far away of a nice mixing, as when you put milk in your tea, and see the milk on one side and the tea on the other...

Carroll, I like your definition of disorderliness. Though the metric needs some clarification: How do you actually measure the size of a computer program that encodes the state? It can't just be the size of the source code because one may invent a programming language that requires zero bytes to represent an arbitrary state.

Hi, Terrance806, All troubling events are happening on the northern hemisphere. That is why I failed to remember that there existed a paradise named Australia.

z, nice to hear from you. I see that your Slither rating has improved by leaps and bounds, which may be a good definition of disorderliness.

Carroll, give us an example, please.   (a) BBBBWWWW (b) BWBWBWBW. Please write a small computer program to instruct us which case is associated with higher disorderliness. Sorry, computer programming languages that I know are only: FORTRAN, MATLAB, and possibly C. It is amazing that I am still able to live with good health.

Carroll's approach sounds a lot like the Kolmogorov Complexity, which seems to me to be a pretty good answer to Tim's question.

The Binary lambda calculus is a suitable language for defining descriptional complexity.

See  https://en.wikipedia.org/wiki/Binary_lambda_calculus for details.

Richard, Carroll, and fhourplay,

I am immensely indebted to you all for your being generous to share your knowledge with the community. Kolmogorov Complexity, Turing machine, and Binary Lambda Calculas are all important topics that will constitute very meaningful homework for me to do.

Is it safe for us to claim that the most disorderly state is also the most probable state?

 Is it safe for us to claim that the most disorderly state is also the most probable state?

I think this is true if you meant "states" in both cases. Any one particular state is going to have the same probability as any other state, regardless of its Kolmogorov Complexity, namely 1 / (total number of states). However, the disorderly states are going to outnumber the orderly states (there are more big TM's than little ones) so the probability of seeing a disorderly state will be greater.

I agree with the good doctor. All states are equally probably unless there's a good reason for them not to be. The disorderly states all look the same to us - "random", and so we don't distinguish between the enormous number of those states. Not so the highly ordered ones, even a slight change will be noticeable in the most ordered ones. I recommend Cover and Thomas' book on Information Theory, if a nearby university library carries it. (It's perhaps a bit heavy for an local library).

I would try finding orderliness at various levels and then invert it some how

gap          1    2    3   total of frequency/gap

BBWW    2    0    0                    2

BWBW    0    2    0                    1

BWWB    1    0    1                    1.333

and same if all inverted

or maybe divide by gap squared

Richard and FatPhil: Yes, thank you. I meant to say macrostates (plural) that share similar characteristics [for exameple, consider throwing 3 dices. To see a total score of 16 is less probable than to see a total score of 10. So we may claim that former states (4/6/6 or 5/5/6) are less disorderly than latter states (1/3/6, 1/4/5, 2/2/6, 2/3/5, 2/4/4, 3/3/4)].

TheBurglar: I tried very hard to figure out what you said. But I failed. Could you kindly slightly elaborate your table?

Back to the stone problem and the dice problem. Perhaps these two problems can be viewed as being similar if a combination of 3 stones is equivalent to a dice.  (red=0; green=1; blue=2) So, let us see....

6/6/6 = bbb/bbb/bbb --> least probable, least disorderly (most orderly), least entropy

1/3/6 = rrg/ggg/bbb or 1/4/5 =  rrg/rbb/gbb or .... --> very disorderly, high entropy.

Under these rule, you cast, say, 5 dices. You first line them up. The outcome of your cast is 5/4/6/1/3. You then sum up the scores to be 19. You then look up the pre-determined probability chart (for 5 dices, the probability of obtaining 19 is, say, 0.134). I then grab 2 blue stones and 1 green stones from a bag to match your 5.........

Are there flaws in my definition of disorderliness? (namely, disorderliness = probability)

I don't see any definition, Tim.

For simplicity, let's forget about dice, and consider coinflips with outcomes 0 & 1.

And let's use the more standard term "complexity" instead of "disorderliness".

So, what is your definition of complexity of a binary string?

What is its value for the string 0110100110010110100101100110100110010110011010010110100110010110 ?

My impression is that you're focussing on only one form of regularity, namely sum of values, saying that a high

sum is unlikely. But you have to realize that regularity can take many forms, which is why you want to use programs

to capture regularities. Then you arrive at complexity = program size.

I think what Tim's looking for is the (Shannon) entropy. If say 50 black stones are put into the bag followed by 50 white stones, and drawing w/o replacement proceeds before any shaking, the entropy will be low, because the probabilities of sequences that have a lot of white stones at the beginning and a lot of black stones at the end are much higher than other sequences. If the drawing is done after one shake, the entropy should be higher because the shake reduces the bunching up of the white stones toward the beginning and the black stones toward the end.

To measure the entropy empirically, you'd put 50 black stones followed by 50 white stones into the bag a whole lot of times. You'd repeatedly draw 100 stones without shaking to establish bounds on the probability of each sequence. You'd repeatedly draw 100 stones after shaking once to establish limits on the sequences' probabilities after one shake. You'd repeatedly draw 100 stones after s shakes to establish bounds on the sequences' probabilities after s shakes. With those bounds on probabilities, you'd be able to calculate a mean entropy and error limits on that entropy after 0 shakes, 1 shake, ... s shakes.

Background: The entropy of an event that can have n different outcomes denoted by 1..n is sum_i=1..n(-p[i]*log(p[i])), where p[i] is the probability of the outcome denoted by i, and sum_i=1..n(p[i])=1. Use log base 2 to get the entropy in bits. The entropy is maximized when all the p[i] are equal, in which case it's log(n). Any bunching up that makes some outcomes more likely than others reduces the entropy. For the stones-in-bag, the event is the sequence of 100 stones drawn. Note: Regard p[i]*log(p[i]) as zero if p[i] is zero.

Say you have a chain of 2n bits. Does a perfect shuffle increase the Shannon entropy of your chain?

A perfect shuffle of say 50 zero bits followed by 50 one bits will yield 50 zero one sequences.

  Is it safe for us to claim that the most disorderly state is also the most probable state?

In the real world there are hackers that will exploit bugs in your bag shaking device.

Also, in the real world your stones are NSA-"optimized" such that some (hard to detect) structure will remain.

To fhourplay: Let me take the challenge.

You assigned me a binary string of 64 digits. The total number of possible microstates N = 2^64. You also interspersed the string with 32 "1"s. Therefore, the number of microstates in the macrostate whose total value is equal to 32 (let us identify "head" with 1 and "tail" with 0) should be n=64!/(32! x 32!). In addition, this macrostate should be most probable among all other macrostates whose total value are less than 32. Hence, finally, the complexity value (or if it is equal to the probability of forming this macrostate) is n/N.

Here I assume that the sequence does matter (meaning, 10000 is different from 00001, or 10100 is different from 00101). In other words, I assume that the symmetry of the string does not apply.

For the purpose of enhancing the clarity of our communications, let us use a shorter string, say, 5 digits. And we desire to find the complexity value of 10100. Then,

There are 32 ways of forming the string (32 microstates). There are 5!/(3! x 2!) = 10 ways (10 microstates) to form the macrostate whose total value is equal to 2. Namely,

1 1 0 0 0; 1 0 1 0 0; 1 0 0 1 0; 1 0 0 0 1; 0 1 1 0 0; 0 1 0 1 0; 0 1 0 0 1; 0 0 1 1 0; 0 0 1 0 1; 0 0 0 1 1.

Hence, the complexity value = 10/32. btw, clearly, there are 5 macrostates (if we base on the total value of a microstate to form a macrostate).

Personally, I think that this definition of disorderliness happens to coincide with that of macroscopic entropy. Let us consider, for example, a bottle of beer (m=2 kg, cv=4180 J/kg-K, A=0.0768 m^2) taken out from a refrigerator at 5 C (or 278 K; when considering entropy, we'd better use K), and placed in the living room at 298 K. Assume that the beer warming process is governed by the Newton's cooling law, i. e., J(t) = h A (298 - T(t)), where J(t) is the energy (in watts) transferred from the room to the beer bottle as a function of time (in second); h the heat transfer coefficient (assumed to be 10 W/m^2-K); A is the area of the bottle exposed to the air. We may be able to find the entropy of the universe (beer bottle + room), S_u (t), to coincide with its microscopic counterpart (complexity value, Shannon entropy, or disorderliness).

I have not had time to digest MarleysGhost's and Carroll's comments yet. But thank you all from the bottom of my heart, again.

Dear Mirko, NSA will be interested in big discussions on the largest prime number ever on earth, but will not take a 2nd look at our small discussions on entropy stuff. :)

@Carroll: I don't have any suggestions for measuring the disorderliness of any specific sequence of bits. Shannon entropy applies to the process that generates various bit sequences with known probabilities.

Having said that; if process X generates bit sequences with some known probabilities, and process Y consists of generating a bit sequence using X and then applying a deterministic reversible permutation to that bit sequence, then X and Y have the same entropy. The permutation may be your perfect shuffle (which I have seen called the Faro shuffle ( http://en.wikipedia.org/wiki/Faro_shuffle) in other contexts).

The proof involves noting that the terms summed in finding Y's entropy are the same terms summed in finding X's entropy, albeit in a different order, but changing the order does not change the value of the sum.

Yes I agree, I found a nice article looking for more explanations on Shannon entropy and the like:

http://www.science4all.org/le-nguyen-hoang/entropy/