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.