Monday, April 16, 2007

Factoidals

Brian Hayes has a very interesting article in American Scientist on the 'factoidal', a stochastic version of the factorial that he coined. It's defined as follows: for input n, pick numbers at random between 1 and n, multiplying them together until you pick a 1.

He expands at some length on the stochastic properties of this function: unsurprisingly, the arithmetic mean of samples of this function doesn't converge with more samples, but the geometric mean does. What's a little more surprising is that the distribution isn't log-normal. One might expect that since upon taking logs, we're averaging a collection of random numbers between 1 and log n, we might expect the average of the logs to display normality, but that doesn't happen.

The explanation is a nice take-way nugget from this article. In short, work by William Reed and Barry Hughes from 2002 shows (this example taken from their abstract) that if you take an exponentially growing process (for example $X(t) = e^{\mu t}$), and truncate it at a random time given by an exponential process (for example, with parameter $\nu$), then the resulting random variable exhibits the power law distribution

$(\nu/\mu)x^{-\nu/\mu -1}, x > 1$