On Mon, Dec 12, 2016 at 02:45:11PM -0700, Nick Thompson wrote:
>
>
> Let’s take out all the colorful stuff and try again. Imagine a thousand
> computers, each generating a list of random numbers. Now imagine that for
> some small quantity of these computers, the numbers generated are in n a
> normal (Poisson?) distribution with mean mu and standard deviation s. Now,
> the problem is how to detect these non-random computers and estimate the
> values of mu and s.
>
Your question comes down to: given a set of statistical distributions
(ie models), which model best fits a given data source. In your case,
presumably you have two models - a uniform distribution and a normal
(or Poisson - they're two different distibutions resulting from
additive versus multiplicative processes respectively) distribution.
The paper to read on this topic is
@Article{Clauset-etal07,
author = {Aaron Clauset and Cosma R. Shalizi and Mark E. J. Newman},
title = {Power-law Distributions in Empirical Data},
journal = {SIAM Review},
volume = 51,
pages = {661-703},
year = 2009,
note = {arXiv:0706.1062}
}
Almost everyone doing work in Complex Systems theory with power laws
has been doing it wrong! The way it should be done is to compare a
metric called "likelihood" calculated over the data and a model, for
the different models in question.
I was scheduled to give a talk "Perils of Power Laws" at a local
Complex Systems conference in 2007. Originally, when I proposed the
topic, I planned to synthesise and collect some of my war stories
relating to power law problems - but a couple of months before the
conference, someone showed me Clauset's paper. I was so impressed by
it, not only superseding anything I could do on the timescale, but
also I felt was so important for my colleagues to know about that I
took the unprecedented step of presenting someone else's paper at the
conference. With full attribution, of course. I still feel it was the
most important paper in my field of 2007, and one of the most
important papers of this century. Even though it didn't officially get
published until 2009 :).
Nick's question is unrelated to the question of how to detect whether
a source is random or not. A non-uniform random source is one that can
be transformed into a uniform random source by a computable
transformation, so uniformity is not really a test of randomness.
Detecting whether a source is random or not is not a computational
feasible task. All one can do is prove that a given source is
non-random (by providing an effective generator of the data), but you
can never prove a source is truly random, except by exhaustive testing
of all Turing machines less than the data's complexity, which suffers
from combinatoric computational complexity.
Cheers
--
----------------------------------------------------------------------------
Dr Russell Standish Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellow hpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au
----------------------------------------------------------------------------
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
