Suppose you observe 24 people entering a store. You see this pattern:

0 0 3 3 2 1 1 2 0 0 3 3 2 0 0 1 1 2 2 2 2 0 1 1

where 0 = White person, 1 = Asian, 2 = Hispanic, 3 = Black. Is the pattern random or not? The pattern doesn’t look random. One way to examine the sequence/pattern is to count the number of runs. A run is a set of consecutive items that are the same. The data has 13 runs:

(0 0)(3 3)(2)(1 1)(2)(0 0)(3 3)(2)(0 0)(1 1)(2 2 2 2)(0)(1 1)
  1    2   3   4   5   6    7   8   9    10     11    12  13

Because same people-types are clumped together a lot, there aren’t as many runs as you’d expect if the pattern was random.

I did a simulation like this:

set up the observed pattern
loop many times
  scramble the pattern randomly
  count number of runs
end-loop
compute mean number of runs seen
compute variance of runs seen

The mean is 18.75 and is the expected number of runs you’d see if the 24 people arrived randomly. This is more than the observed number of runs (13). Put another way, you observed fewer runs (13) than you’d expect if the pattern is random (18.75).

The variance of the number of runs in the simulation is 3.94.

Using the mean and variance, I computed a z-score: (13 – 18.75) / sqrt(3.94) = -2.89. Then I fed that z-score to the cumulative density function for the Standard Normal distribution and got a two-tailed probability of 0.0038. The probability is the approximate likelihood that you’d see the observed number of runs if the pattern is random.

Because the p value is so small, you’d conclude that it’s very unlikely the pattern is random — therefore, people are likely arriving at the store in a non-random way.

This analysis assumes that the mean and variance are Normal distributed which is only true if the sequence has lots (say 10 or more) of each type of person. But even with fewer than 10 people the approximation is OK.

As with any statistical analysis, the conclusion is soft: “it’s unlikely the pattern is random” rather than “the pattern is not random”.

This problem was all motivated by me thinking about the Wald-Wolfowitz Runs Test. It relies on calculations instead of a simulation, but isn’t feasible with more than two types of items in pattern being investigated.

Demo C# code. Replace “lt” with Boolean operator symbol.

using System;
namespace RunsTestSim
{
  internal class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin test runs using simulation ");

      Random rnd = new Random(0);

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

      int runs = NumRuns(seq);
      Console.WriteLine("\nObserved number runs: " + runs);

      int[] counts = new int[25];  // note the 25. 
      int[] scratch = new int[24];
      Array.Copy(seq, scratch, seq.Length);

      int nTrials = 1000000;
      Console.WriteLine("\nStart simulation with nTrials = " +
        nTrials);
      for (int i = 0; i "lt" nTrials; ++i)
      {
        Shuffle(scratch, rnd);
        int r = NumRuns(scratch);
        ++counts[r];
      }
      Console.WriteLine("Done ");

      Console.WriteLine("\nCounts of runs from simulation: ");
      ShowCounts(counts, 40);

      double m = Mean(counts);
      Console.WriteLine("\nMean runs for simulation: " +
        m.ToString("F2"));

      double v = Variance(counts, m);
      Console.WriteLine("\nVariance for simulation: " +
         v.ToString("F2"));

      double z = (runs - m) / Math.Sqrt(v);
      Console.WriteLine("\nComputed z statistic: " + 
        z.ToString("F4"));

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

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

    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));
    }

    static int NumRuns(int[] seq)
    {
      int runs = 0;
      int last = -1;
      for (int i = 0; i "lt" seq.Length; i++)
      {
        if (seq[i] != last)
        {
          ++runs;
          last = seq[i];
        }
      }
      return runs;
    }

    static double Mean(int[] counts)
    {
      int sum = 0;
      int n = 0;  // number of values
      for (int i = 0; i "lt" counts.Length; ++i)
      {
        sum += i * counts[i];  // i is number runs
        n += counts[i];
      }
      //Console.WriteLine(sum);
      //Console.WriteLine(n);
      double mean = (sum * 1.0) / n;
      return mean;
    }

    static double Variance(int[] counts, double mean)
    {
      double sumSquares = 0.0;
      int n = 0;
      for (int i = 0; i "lt" counts.Length; ++i)
      {
        sumSquares += counts[i] * ((i - mean) * (i - mean));
        n += counts[i];
      }
      return sumSquares / n;
    }

    static void Shuffle(int[] seq, Random rnd)
    {
      int n = seq.Length;
      for (int i = 0; i "lt" n; ++i)
      {
        int ri = rnd.Next(i, n);
        int tmp = seq[ri];
        seq[ri] = seq[i];
        seq[i] = tmp;
      }
    }

    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 void ShowCounts(int[] counts, int n)
    {
      for (int i = 0; i "lt" counts.Length; i++)
      {
        Console.Write(counts[i] + " ");
        if ((i + 1) % n == 0)
          Console.WriteLine("");
      }
      Console.WriteLine("");
    }
  } // Program
} // ns