Suppose you observe people entering a store and you see this sequence:

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0

where 0 is a man and 1 is a woman. Is the pattern random or not? It doesn’t look very random. You can examine this using the Wald-Wolfowitz runs test.

The data has r = 5 runs of consecutive items: (0, 0), (1, 1, 1, 1, 1, 1, 1, 1), (0), (1, 1, 1, 1, 1), (0, 0, 0). Let n1 = number of men, zeros = 6. Let n2 = number of women, ones = 13. The total number of items is N = n1 + n2 = 19.

Statistically, if the sequence was random, you would expect the mean number of runs (u) to be 9.21, calculated as:

u = ((2 * n1 * n2) / N) + 1
  = ((2 * 6 * 13) / 19) + 1
  = (156 / 19) + 1
  = 8.21 + 1
  = 9.21

And the expected variance (v) is:

a = (2 * n1 * n2) * ((2 * n1 * n2) - N) 
  = (2 * 6 * 13) * ((2 * 6 * 13 - 19)
  = 156 * (156 - 19)
  = 156 * 137
  = 21,372

b = N^2 * (N - 1)
  = 19^2 * (19 - 1)
  = 361 * 18
  = 6,498

v = a / b
  = 21,372 / 6,498
  = 3.2890

The standard normal score is

z = (r - u) / sqrt(v)
  = (5 - 9.21) / sqrt(3.2890)
  = -4.21 / 1.8136
  = -2.3217

If you look up or compute p1 for z = +2.3217 (it’s common practice to use the positive value of z — because of symmetry it doesn’t matter) in the Standard Normal table, you get a one-tail probability of p1 = 0.0101. For the Runs test, you are wondering if there are too many or too few runs so you use a two-tail test and get p2 = 2 * p1 = 0.0202.

The p2 value is, loosely speaking, the probability that you’d see as few as 5 runs if the sequence was random. Because p2 is so low, only 2%, you’d conclude that it’s unlikely that the sequence is random.

In my college probability and statistics classes, for binary sequences it was standard to call the two possible outcomes S and F, for “success” and “failure”. Here are three early personal computers that by any measure were { S, S, S }. Left: The Apple II (1977) gave rise to the Apple empire. I did my first assembly language programming on a IIe model 6502 processor. Center: The Commodore 64 (1982) dominated the personal computer market. I wrote my first version of my NFL football prediction system on a C64 using the BASIC language. Right: The Tandy TRS-80 (1977) was beautiful in my eyes. I remember writing a cellular automata program on one, based on an article in Scientific American magazine.

Demo code. Replace “lt” with less-than Boolean operator symbol.

using System;
namespace RunsTest
{
  internal class RunsTestProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin Wald-Wolfowitz Runs example ");

      int[] seq = new int[] { 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
        1, 1, 1, 1, 1, 0, 0, 0 };
      Console.WriteLine("\nObserved sequence: ");
      ShowSeq(seq, 40);

      int n1 = 6;
      int n2 = 13;
      int r = 5;

      Console.WriteLine("\nNumber items in sequence: " +
        seq.Length);
      Console.WriteLine("Number of item 1: " + n1);
      Console.WriteLine("Number of item 2: " + n2);
      Console.WriteLine("Observed number runs: " + r);

      double m = Mean(n1, n2);      // 9.21
      double v = Variance(n1, n2);  // 3.2890
      double z = (r - m)/ Math.Sqrt(v);  // -2.3217

      Console.WriteLine("\nExpected number runs if random: " + 
        m.ToString("F2"));
      Console.WriteLine("Variance if random: " + 
        v.ToString("F4"));
      Console.WriteLine("Computed z statistic: " + 
        z.ToString("F4"));

      double p = TwoTail(z);  // 0.0202
      Console.WriteLine("\nprob if random: " +
        p.ToString("F4"));

      Console.WriteLine("\nEnd example ");
      Console.ReadLine();
    } // Main

    static void ShowSeq(int[] seq, int n)
    {
      for (int i = 0; i "lt" seq.Length; i++)
      {
        Console.Write(seq[i] + " ");
        if ((i+1) % n == 0)
          Console.WriteLine("");
      }
      Console.WriteLine("");
    }

    static double Mean(int n1, int n2)
    {
      double numer = 2.0 * n1 * n2;
      double denom = n1 + n2;
      return (numer / denom) + 1.0;
    }

    static double Variance(int n1, int n2)
    {
      int N = n1 + n2;
      double numer = (2.0 * n1 * n2) * 
        ((2.0 * n1 * n2) - N);
      double denom = (N * N) * (N - 1);
      return numer / denom;
    }

    static double TwoTail(double z)
    {
      // likehood of z
      if (z "lt" 0.0)
        z = -z;  // make z positive is standard
      double p = 1.0 - Phi(z);  // z to +infinity
      return 2.0 * p;
    }

    static double Phi(double z)
    {
      // cumulative density of Standard Normal
      // erf is Abramowitz and Stegun 7.1.26
      double a0 = 0.3275911;
      double a1 = 0.254829592;
      double a2 = -0.284496736;
      double a3 = 1.421413741;
      double a4 = -1.453152027;
      double a5 = 1.061405429;

      int sign = 0;
      if (z "lt" 0.0)
        sign = -1;
      else
        sign = 1;

      double x = Math.Abs(z) / Math.Sqrt(2.0); 
      double t = 1.0 / (1.0 + a0 * x);
      double erf = 1.0 - (((((a5 * t + a4) * t) + a3) * 
        t + a2) * t + a1) * t * Math.Exp(-x * x);
      return 0.5 * (1.0 + (sign * erf));
    }

  } // Program

} // ns