15
$\begingroup$

From Wikipedia's statistical randoness:

Global randomness and local randomness are different. Most philosophical conceptions of randomness are global—because they are based on the idea that "in the long run" a sequence looks truly random, even if certain sub-sequences would not look random. In a "truly" random sequence of numbers of sufficient length, for example, it is probable there would be long sequences of nothing but zeros, though on the whole the sequence might be random. Local randomness refers to the idea that there can be minimum sequence lengths in which random distributions are approximated. Long stretches of the same digits, even those generated by "truly" random processes, would diminish the "local randomness" of a sample (it might only be locally random for sequences of 10,000 digits; taking sequences of less than 1,000 might not appear random at all, for example).

A sequence exhibiting a pattern is not thereby proved not statistically random. According to principles of Ramsey theory, sufficiently large objects must necessarily contain a given substructure ("complete disorder is impossible").

I don't quite understand the meanings of the two sentences in bold.

  1. Does the first sentence mean that something makes a sequence local random at a longer length, and not local random at a shorter length?

    How does the example inside the parenthesis work?

  2. Does the second sentence mean that a sequence exhibiting a pattern cannot be proved to be not statistically random? Why?

Thanks

$\endgroup$
  • 1
    $\begingroup$ good question. I find this text a bit baffling myself. I would have thought that whether a sequence is random or not is to do with how it is generated; not what the result is. I suspect there is a linguistic problem here - for me random means how it is generated; for common sense (and possibly less clear-thinking philosophers?) it is about something that appears disordered? $\endgroup$ – Peter Ellis Sep 26 '12 at 21:32
  • 3
    $\begingroup$ @Peter, you might have a difficult time even defining randomness if you could refer only to the generation mechanism. Ultimately, because all the utility of random sequences lies in the numbers they contain--and not in how those numbers were produced--there must be a way to define and test randomness purely in terms of the sequences, don't you think? $\endgroup$ – whuber Sep 26 '12 at 22:10
  • 1
    $\begingroup$ Certainly I agree you can test randomness from its results - for plausibility of randomness, without aspiring to proof of it. I probably need to do some more reading and thinking on the philosophical challenges of a definition based on generation. $\endgroup$ – Peter Ellis Sep 26 '12 at 22:29
  • $\begingroup$ I think randomness is merely a synonym for unknown. I too find this sentence bizzare $\endgroup$ – probabilityislogic Sep 26 '12 at 23:26
  • 2
    $\begingroup$ Dilbert $\endgroup$ – Henry Sep 27 '12 at 15:39
15
$\begingroup$

The concept can be neatly illustrated by some executable code. We begin (in R) by using a good pseudo random number generator to create a sequence of 10,000 zeros and ones:

set.seed(17)
x <- floor(runif(10000, min=0, max=2))

This passes some basic random number tests. For instance, a t-test to compare the mean to $1/2$ has a p-value of $40.09$%, which allows us to accept the hypothesis that zeros and ones are equally likely.

From these numbers we proceed to extract a subsequence of $1000$ successive values starting at the 5081st value:

x0 <- x[1:1000 + 5080]

If these are to look random, they should also pass the same random number tests. For instance, let's test whether their mean is 1/2:

> t.test(x0-1/2)

    One Sample t-test

data:  x0 - 1/2 
t = 2.6005, df = 999, p-value = 0.009445
alternative hypothesis: true mean is not equal to 0 
95 percent confidence interval:
 0.01006167 0.07193833 
sample estimates:
mean of x 
    0.041 

The low p-value (less than 1%) strongly suggests the mean is significantly greater than $1/2$. Indeed, the cumulative sum of this subsequence has a strong upward trend:

> plot(cumsum(x0-1/2))

Random walk?

That's not random behavior!

Comparing the original sequence (plotted as a cumulative sum) to this subsequence reveals what's going on:

Random walk

The long sequence indeed behaves like a random walk--as it should--but the particular subsequence I extracted contains the longest upward rise among all subsequences of the same length. It looks like I could have extracted some other subsequences exhibiting "nonrandom" behavior, too, such as the one centered around $9000$ where approximately 20 ones in a row appear!


As these simple analyses have shown, no test can "prove" that a sequence appears random. All we can do is test whether sequences deviate enough from the behaviors expected of random sequences to offer evidence that they are not random. This is how batteries of random-number tests work: they look for patterns highly unlikely to arise in random number sequences. Every once in a long while they will cause us to conclude that a truly random sequence of numbers does not appear random: we will reject it an try something else.

In the long run, though--just as we are all dead--any truly random number generator will generate every possible sequence of 1000 digits, and it will do so infinitely many times. What rescues us from a logical quandary is that we would have to wait an awfully long time for such an apparent aberration to occur.

$\endgroup$
  • $\begingroup$ Thanks! A related question: when testing randomness of the pseudo random numbers generated by some methods, does randomness mean uniform distribution? In other words, does randomness testing only for testing uniform distributions? I asked this because those more biased distributions seem less random to me intuitively. $\endgroup$ – Tim Sep 26 '12 at 22:39
  • $\begingroup$ @Tim: no, there are many common tests for Gaussian randomness, and it should be possible to construct tests for any distribution. $\endgroup$ – naught101 Sep 26 '12 at 23:37
  • 1
    $\begingroup$ Tim, every distribution bears a definite mathematical relationship to a uniform distribution via the probability integral transform (and its generalization to discrete and non-absolutely continuous distributions). Thus, to understand randomness generally, it suffices to understand uniform distributions. Indeed, those in turn can be related to infinite strings of binary digits: they represent real numbers in the interval $[0,1)$. $\endgroup$ – whuber Sep 27 '12 at 0:41
  • 2
    $\begingroup$ I can almost "look" at the top of the answer and say "Whuber" :) Very Nice! $\endgroup$ – PhD Sep 27 '12 at 3:14
2
$\begingroup$

This excerpt uses terms "local randomness" and "global randomness" to distinguish between what can occur with a finite number of samples of a random variable, and the probability distribution or expectation of a random variable.

For example, repeated trials $x_i$ of a Bernoulli random variable (taking values in $\{0,1\}$) with expectation $\theta$ will, as the number of samples of goes to infinity, produce sample mean $\theta$. That is, $\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i = \theta$. This comes from the law of large numbers.

However, when evaluating the sample mean for finite samples we will get all kinds of values in $[0,1]$. In fact there is a finite probability of getting the sample mean to fall in the range $[a,b]$ for any $0 \leq a < b \leq 1$ for any value of $\theta$.

Nothing new here.

However, this excerpt seems to be making the rather obvious point that the larger $n$ is, the more likely we are to see behavior looks "locally random" with "locally random" defined (incorrectly) as exhibiting patterns that are close to the mean (in this example.)

Thus, I wouldn't burn too many brain cells thinking about this excerpt. It's not mathematically so precise and is actually misleading about the nature of randomness.

Edit based on comment: @kjetilbhalvorsen +1 to your comment for the historical knowledge. However, I still think the value of these terms is limited and misleading. The tables you're describing seem to make the misleading implication that small samples which have, for example, sample mean far from the actual expected value or perhaps an improbable but certainly possible long sequence of repeated 0's (in my Bernoulli example), somehow exhibit less randomness (by saying they do not exhibit this phony "local randomness"). I can't think of anything more misleading for the budding statistician!

$\endgroup$
  • $\begingroup$ Although "global randomness" appears idiosyncratic, "local randomness" has at least a 20 year history. See isiweb.ee.ethz.ch/papers/arch/umaure-mass-inspec-1991-1.pdf, for instance. $\endgroup$ – whuber Sep 27 '12 at 1:19
  • $\begingroup$ Fine, I agree, but the distinction and the way they are using it is misleading and imprecise. Really they are talking about low $n$ versus large $n$ no? $\endgroup$ – Chris A. Sep 27 '12 at 1:20
  • 2
    $\begingroup$ I remember I read sometimes this: In the time when people published books with tables of "random numbers" to be used for simulation, experimentation etc, some of this had marked parts of the tables as suitable for use in small simulations (exhibiting "local randomness") and other parts which should only be used for larger simulations (exhibiting "global randomness") So the concepts seem to point to something valuable! $\endgroup$ – kjetil b halvorsen Sep 27 '12 at 10:15
  • 1
    $\begingroup$ Sorry, I can't remember where I have read this. But it is almost obvious: quite apart from the philosophical problems in defining randomness, If you have a very small simulations where you need 1000 random numbers, and your high-quality random generator gives you 1000 zeros, ¿What do you do? In spite of the fact that such ocurrences are possible and indeed necessary in a "truly random" sequence, your simulation is ruined! $\endgroup$ – kjetil b halvorsen Sep 27 '12 at 12:13
  • 1
    $\begingroup$ Thanks guys, I was perhaps too harsh in my condemnation. I'll change the language of this a bit. $\endgroup$ – Chris A. Sep 27 '12 at 14:14
-1
$\begingroup$

I think the authors of the Wikipedia post are misconstruing randomness. Yes, there might be stretches that appear not to be random, but if the process that created the sequence is truly random, so must be the output. If certain sequences appear to be non random, that is an erroneous perception of the reader (i.e. humans are designed to find patterns). Our ability to see the Big Dipper, and Orion, etc in the night sky is no evidence that the patterns of stars is nonrandom. I agree that randomness often appears nonrandom. If a process generates truly nonrandom patterns for short sequences, it isn't a random process.

I don't think that the process changes at different sample sizes. You increase the sample size, you increase the probability that we see a random sequence that appears to us to be nonrandom. If there is a 10% chance that we would see a pattern in 20 random observations, increasing the total number of observations to 10000 would increase the likelihood that we would see nonrandomness, somewhere.

$\endgroup$
  • 2
    $\begingroup$ "If a process generates truly nonrandom patterns for short sequences, it isn't a random process" is, I am afraid, wholly incorrect. For instance, in any 100 flips of a fair coin, we would expect to observe six heads or six tails in a row--and that is a "truly nonrandom pattern for [a] short sequence" by almost anybody's meaning of "random." I suspect you meant to write something that needs to be more carefully qualified, such as applying "all" before "short sequences." $\endgroup$ – whuber Sep 26 '12 at 21:54
  • $\begingroup$ Really? I would have thought that, since one expects to see strings of heads of tails from a random number generator, that when we do see it, we should not be surprised. Why consider it to be nonrandom? If one had a number generator that did 100 flips, and it purposefully avoided 4 or more heads or tails in a row, it would look more random than a truly random process, but it would actually be nonrandom. A naive view of randomness is the lack of all patterns - but that would be nonrandom. $\endgroup$ – P auritus Sep 26 '12 at 22:05
  • $\begingroup$ Your comment is correct, but the exposition in your answer is unclear and even contradictory on this point. Consider explaining more precisely what you mean by generating "truly nonrandom patterns for short sequences," for instance, or what it means to "see nonrandomness." $\endgroup$ – whuber Sep 26 '12 at 22:06
  • $\begingroup$ I see no contradiction. You seem to think that random generators create nonrandom patterns. That is the contradiction. You are arguing that truly random processes will generate non random observations. What you are describing is sometomes called the "clustering illusion", which is the tendency to incorrectly perceive clusters from random distributions. All I am saying is that if a process creates nonrandom observations, then it isn't random. You argue that you expect a random process to create strings of nonrandom observations, yet you call that nonrandom. Classic example of Apophenia. $\endgroup$ – P auritus Sep 26 '12 at 23:56
  • 1
    $\begingroup$ It's hard to carry on a conversation with an interlocutor who misstates one's position, so I will bow out of this one. Sorry. $\endgroup$ – whuber Sep 27 '12 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.