irreducible randomness

[miriam_e]

Any natural stream of random numbers will have occasional patterns appear randomly within it. These patters can be encoded for with compression software rules -- they are then, to some degree reducible. However at some point you might have an unpatterned stream. Is that irreducible?

Imagine some way of producing completely patternless random numbers was found. Such numbers use as many combinations of the digit "1" followed by one of the other nine digits as possible, so can't be compressed by finding runs of duplicated digits. However there are other kinds of patterns, beyond simple runs of digits and these other patterns lend themselves to compression schemes too. Half of any random numbers will be divisible by 2 and the factor might open itself to further compression because of patterns in the digit stream. Even looking only at prime numbers there may still be patters, for instance 1231 is prime, so is 2131 and the patterns in those numbers are obvious... and that is just in base 10. Using other number bases could turn up further patterns.

Only a small proportion of all thousand-digit numbers would be incompressibly random. Might there be some simple way to characterise them? If we simply listed all such numbers then we would necessarily use less than a thousand digits to indicate any of the numbers on the list, thus reducing the irreducibly random still further.

Is there any limit to this? Surely there would be. Perhaps when the information required to describe the rules for compression equalled the numbers being examined.

In fact, is the lack of pattern a pattern itself? Gah!!!

Interesting stuff.

Comments

[idealistagain.livejournal.com]

Any string of random data can be reduced to a simple instruction of "Insert string of random data of x type and y length here" or something to that effect. So it can be argued that randomness is not incredibly complex. Of course, there are also other ways of conceptualizing complexity other than "inability to be reduced to simpler terms."

For non-random complexity, I always think of examples such as data that, while it may or may not have patterns, is inherently unpredictable. A spreadsheet full of daily weather observations, for instance.

[miriam-e.livejournal.com]

That is a terrific idea I hadn't thought of: that strings of random data could be encoded as runs of shorter, classified, random strings.

Yes. Non-random complexity can be unpredictable while being completely deterministic -- chaos. As you mention, the weather is a wonderful example of that.

All this sounds quite esoteric, but it relates to some ideas my mind has been dancing around lately without actually coming to any real conclusions yet, on associative systems for indexing data.

In the old days we had a flat system, where all files were simply listed in order of creation or alphabetically. It soon grew far too unwieldy Later, the directory system with its series of folders inside folders was developed and imposed upon the flat filing system. This helped a lot. But now managing utterly vast amounts of data has brought the directory system to its limits. Something better is needed. Some kind of associative filing system seems the logical next step.

My thoughts on encoding randomness may be of some use there or may not. I'm not sure yet. But it is fun. :)

[idealistagain.livejournal.com]

I've had a lot of ideas wandering around in the out-of-the-way corners of my brain about information theory lately and you're right, it's certainly fun.

One thing I find interesting is how the ways in which we organize information tend to parallel other things in the larger society. For instance, for the longest time, as you said, we organized information in heirachies. This was paralled by the growth of bureaucracy and other essentially heirarchial systems for running businesses and other organizations. Now we find society moving away from heirachies, toward more "flattened" organizational forms and toward systems more open and democratic in nature. This is paralled by the rising popularity of tagging for organizing information, as tagging is non-heirarchial and open to anyone participating. Not that tagging is perfect and we have all sorts of challenges with "tag spamming" and differences in how different individuals organize information and other such complications. Tagging seems to me like an associative system, but I'm not sure if this is precisely what you have in mind?

If any of this theory could be turned into anything practical, I've no doubt there's money to be made with it, considering the increasing challenges for individuals and organizations in keeping information organized and accessible. Of course, I want to help improve the world too, but I don't believe the two are mutually exclusive--one must make a living, after all.

[miriam-e.livejournal.com]

I hadn't thought about the wider social context, but yes, the shift to a more diverse system instead of a centralised one is an interesting parallel.

Tagging feels like the beginning of an associative system, but needs to be automated more. Humans don't have the time to tag everything, and each person has their own preferred system of tags. Even more inconveniently, any person's tagset definitions will shift over time. No two sets of tags will overlap completely. These sound like a major faults, but I think they may nevertheless be useful, especially if an automated associative index can be used to help. The human associative system added to the automated one could make for something far more useful than either alone.

I'm certain this is very practical stuff (and great fun). Lately (prior to NaNoWriMo this year) I'd been coming close to working out something usable I think... though it will probably have to wait till after I finish my story now. :)

[idealistagain.livejournal.com]

I hadn't thought about automating the tagging process before and I'm not quite sure how this might work. Something to think about, I suppose.

Perhaps if you come up with a sytem, we could work out something to use our marketing tools to advertise and promote it and share in the revenues.

[miriam-e.livejournal.com]

The automated side is related to my thoughts about discerning and classifying patterns even from apparently patternless streams. I'm not sure how useful that aspect is or how far it can be taken. I have some other ideas not directly related to that, and more to do with simple AI pattern matching, which may eventually prove more practical. Whatever gets used needs to be fast. The numeric approaches might end up being too slow to be useful. On the other hand sometimes I get the feeling that the AI and numeric aspects are two sides of the same coin. All this needs a lot more thought. After NaNoWriMo I expect I'll jump back into it. :)

[idealistagain.livejournal.com]

Good luck with NaNo. I wanted to do it, but I have far more projects than I can handle as it is without adding one more.

[miriam-e.livejournal.com]

Thanks.

Yes, I know what you mean. I have far too many projects too, but I learn so much each time I do NaNo that it is worth giving up a month (or in this case probably a month and a half).

Good luck with your projects too.