7dec2002 Origin of power laws Abstract: - What are power laws? - Where do power laws come from? - A hypothesis - Testing - Results - Conclusion * WHAT ARE POWER LAWS? I've been wondering where power laws come from. They're found in all kinds of places: - earthquake size - size of cities - community size on LiveJournal - fluctuation magnitude of a share price Power laws are characterised by a property: - the distribution looks the same, regardless of the scale you consider This is called scale invariance. So for example: with earthquakes, if you double the energy, earthquakes become four times as rare ...and this happens at whatever energy you start with. City growth in the USA: For any city size, there are four times that many cities at half the size. So, if there's one city of four million people, there will be four at two million, and sixteen with one million inhabitants. That adjustment factor (four times as rare; four times the number of cities) isn't the important bit -- that can be any number as long as it stays the same regardless of the scale. * WHERE DO POWER LAWS COME FROM? But where do these power laws come from? "Ubiquity" by Mark Buchanan (from where I've also lifted many of these examples) suggests a number of different types of game that produce these power laws: - earthquake system models - randomly chosen adaptive evolution but doesn't actually say why these laws emerge (or at least, not before the last three chapters...) Other commonly found distributions are: - Normal distribution (values distributed around a point, for example the heights of people are all distributed around 5 foot 10 inches, with many close to that and very few further away) - Poisson distribution (as Normal distribution, but skewed because 0 acts as a lower bound) but Buchanan points out that although people *thought* one of these distributions would explain earthquakes or share price fluctuation, they don't: power laws do. * A HYPOTHESIS What's missing in these other statistical distributions is a concept that the values are all interlinked. For example, if a person goes and lives in a city, they can't live in another city. If an earthquake happens, that energy can't be used for another earthquake. There's a dependency on a scarce resource. So my hypothesis is that numbers picked randomly from a scarce resource will organise themselves into a power law distribution. * TESTING The directory http://interconnected.org/notes/2002/12/power_laws/ contains the script and notes. resource_allocation.pl - starts off with an initial resource - takes a random amount of that resource, and remembers it - continues until there's no resource left The script sorts the random chunks taken off the resource in different ways. - into percentile buckets (that is, how many chunks are between 42% and 43% of the initial resource) - into scales. Scales go down as a factor of a half. (That is, how many chunks are between a half and a quarter the size of the initial resource.) (to even things out a bit, this resource allocation is done many, many times, and the results added together.) If a random allocation from a scarce resource does produce a power law, then: - the percentile bucket sorting should show that there are X times more chunks in the 50th percentile bucket as the 100th percentile, and X times more again in the 25th percentile. X has to stay the same - the scale bucket sorting should show the number of chunks at each scale staying roughly the same if it's a power law where X is about 2 * RESULTS In that same directory, - chunks_per_percentile.gif does indeed show that the number of chunks doubles as you halve the size of the chunk you're looking at. So the X factor is about 2 here - chunks_per_halving.gif shows that the number of chunks visible at each scale (halving the chunk size for each scale) remains pretty much the same. These are characteristic of a power law. * CONCLUSION Power laws are characteristic of randomly distributed values that come from a scarce resource.